[FOM] 459: Greedy Clique Constructions in the Integers

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

```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)}."

"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.

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

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

```