[FOM] 459: Greedy Clique Constructions in the Integers

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS SELF CONTAINED.

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.

GREEDY CLIQUE CONSTRUCTIONS IN THE INTEGERS.

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.

FINITE GREEDY CLIQUE CONSTRUCTION THEOREM. Let n >= (8kr)!!. Every  
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  
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 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