[FOM] 459: Greedy Clique Constructions in the Integers

Harvey Friedman friedman at math.ohio-state.edu
Sun May 8 13:18:15 EDT 2011




First, let me correct a typo:

In http://www.cs.nyu.edu/pipermail/fom/2011-May/015381.html I wrote

"the upper split of {(1,4),(-1,3)} is {(0,2),(-1,3/2)}."

This should read

"the upper split of {(1,4),(-1,3)} is {(1/2,2),(-1,3/2)}."

I now throw everything into the integers, and deal with finite order  
invariant graphs. This results in remarkably clear finite statements.


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 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,y in Z^k. The birthdate of y over x_1,...,x_n is the  
least i such that every coordinate of y is a coordinate of some x_j, 1  
<= j <= i.

The candidates over x_1,...,x_n are the y in Z^k not among  
x_1,...,x_n, with the earliest possible birthdates.

2. Finite Greedy Clique Construction Theorem.

Let G be a graph on {-kn,...,kn}^k. A G construction has the form  
x_1,...,x_r in {-kn,...,kn}^k, together with P contained in {1,...,r}.  
The requirements are

i. x_1 = (0,n,...,(k-1)n).
ii. If i < r is in P, then x_i+1 is a candidate over x_1,...,x_i if  
such exists; x_i otherwise.
iii. If i < r is not in P, then i+1 is in P, max(x_i) > max(x_i+1),  
and x_i,x_i+1 are not connected in G.

We say that the G construction is successful if and only if the x_i, i  
in P, forms a clique in G.

We say that the G construction is upper n-shift successful if and only  
if the x_i, i in P, together with their upper n-shifts, forms a clique  
in G.

order invariant graph G on {-kn,...,kn}^k has an upper n-shift  
successful G sequence of length r.

Note that the Finite Greedy Clique Construction Theorem is explicitly  

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  


I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 457th 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

Harvey Friedman 

More information about the FOM mailing list