[FOM] 460: Greedy Clique Constructions Simplified

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

*****************************************

THIS POSTING IS SELF CONTAINED AND SUPERSEDES http://www.cs.nyu.edu/pipermail/fom/2011-May/015387.html 
.

An overall nicer way of stating the nondeterministic greedy clique  
construction.

GREEDY CLIQUE CONSTRUCTIONS IN THE INTEGERS 5/8/11.

1. Graphs, Cliques, Order invariance, n-shift, Upper n-shift,  
Birthdates, Candidates.

A graph is a pair (V,E), where E is an irreflexive symmetric relation  
on the set V of vertices. A G clique is a set S of vertices where any  
two distinct elements of S are connected by E.

We will work only with graphs on V = {-t,...,t}^k, t >= 0. Thus we  
will work only with finite graphs.

We say that x,y in Z^k are order equivalent if and only if for all 1  
<= i,j <= k, x_i < x_j iff y_i < y_j.

We say that E contained in {-t,...,t}^k is order invariant if and only  
if for all order equivalent x,y in {-t,...,t}^k, x in E iff y in E.

We say that G is an order invariant graph on {-t,...,t}^k if and only  
if the edge relation E is an order invariant subset of {-t,...,t}^2k.

Note that there are only finitely many order invariant graphs on {- 
t,...,t}^k. Furthermore, the number of such depends only on k and not  
on t.

Let S be contained in Z^k. For n in Z, the n-shift of S is obtained by  
adding n to all coordinates of vectors in S.

For n in Z, the upper n-shift of S is obtained by adding n to all  
nonnegative coordinates of vectors in S.

Let x_1,...,x_n in Z^k. The birthdate of y over x_1,...,x_n is the  
least i such that y is in Z^k and every coordinate of y is a  
coordinate of some x_j, 1 <= j <= i. If there is no such i, then the  
birthdate of y is infinity.

The clique candidates over x_1,...,x_n are the y in Z^k not among  
x_1,...,x_n such that {x_1,...,x_n,y} is a G clique. In special cases,  
x_1,...,x_n may not have a clique candidate.

2. Finite Greedy Clique Construction Theorem.

Let G be a graph on {-kn,...,kn}^k. We describe the greedy G clique  
construction.

i. Set x_1 = (0,n,...,(k-1)n).
ii. Suppose x_1,...,x_i in {-kn,...,kn}^k have been constructed.  
Choose a clique candidate y over x_1,...,x_i with least possible  
birthdate over x_1,...,x_i. Set x_i+1 = y or set x_i+1 in {- 
kn,...,kn}^k, where max(x_i) > max(x_i+1) and x_i,x_i+1 are not  
connected in G.

The construction terminates if there is no clique candidate y in  
clause ii). This will eventually happen because the vertex set is  
finite.

We say that the greedy G clique construction is r-successful if and  
only if x_1,...,x_r forms a G clique.

We say that the greedy G clique construction is r,n-successful if and  
only if x_1,...,x_r together with their upper n-shifts, forms a G  
clique.

FINITE GREEDY CLIQUE CONSTRUCTION THEOREM. Let n >= (8kr)!!. Every  
order invariant graph on {-kn,...,kn}^k has an r,n-successful greedy  
clique construction.

The use of (8kr)!! is safe overkill. When things settle down, I will  
replace this with something reasonable.

Note that the Finite Greedy Clique Construction Theorem is explicitly  
Pi01.

THEOREM. FGCCT is provable in SRP+ but not in any fragment of SRP that  
logically implies EFA. FGCCT is provably equivalent to Con(SRP) over  
EFA.

*****************************************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 460th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html

450: Maximal Sets and Large Cardinals II  12/6/10  12:48PM
451: Rational Graphs and Large Cardinals I  12/18/10  10:56PM
452: Rational Graphs and Large Cardinals II  1/9/11  1:36AM
453: Rational Graphs and Large Cardinals III  1/20/11  2:33AM
454: Three Milestones in Incompleteness  2/7/11  12:05AM
455: The Quantifier "most"  2/22/11  4:47PM
456: The Quantifiers "majority/minority"  2/23/11  9:51AM
457: Maximal Cliques and Large Cardinals  5/3/11  3:40AM
458: Sequential Constructions for Large Cardinals  5/5/11  10:37AM
459: Greedy CLique Constructions in the Integers  5/8/11  1:18PM

Harvey Friedman