[FOM] 460: Greedy Clique Constructions Simplified
Harvey Friedman
friedman at math.ohio-state.edu
Sun May 8 19:39:11 EDT 2011
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
More information about the FOM
mailing list