[FOM] 466: RETURN TO 463/Dominators
Harvey Friedman
friedman at math.ohio-state.edu
Sun Jun 12 23:09:42 EDT 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
The last comprehensive statement of the Pi01 independent statements is
#463, http://www.cs.nyu.edu/pipermail/fom/2011-May/015464.html This
features MAXIMAL CLIQUES, and the MAXIMAL CLIQUE SPLIT THEOREM is
implicitly Pi01. That posting is STILL OPERATIVE - but with caution to
the reader in the preliminary remarks there.
Postings #464, #465 made a huge jump into local facts about order
invariant graphs - with no cliques.
I am now confident that, UNFORTUNATELY, these statements are NOT
independent of ZFC.
This overly ambitious approach was generated by my seeking a really
good finite form of the MAXIMAL CLIQUE SPLIT THEOREM. I now want to
get back on track with this.
My working assumption is that I will come up with a manuscript for the
claims in #463 concerning the Maximal Clique Split Theorem.
We now present new explicitly Pi01 independent statements. We begin by
presenting a DUAL form of the Maximal Clique Split Theorem, called the
Independent Dominator Split Theorem. Here Cliques correspond to
Independent sets, and Maximality corresponds to Domination. However,
the main feature of Maximal Cliques is Cliques (and not maximality),
whereas the main feature of Independent Dominators is Dominators (and
not independence). This is a subtle kind of change of intuitive
perspective - even though formally we have a trivial kind of duality.
In fact, this change of intuitive perspective has driven us to the
INDEPENDENT DOMINATOR SPLIT THEOREM, but what is the advantage??
The advantage lies in the motivation and purpose of DOMINATION. For
the FINITE DOMINATOR SPLITE THEOREMS we need a quantitative form of
(relative) domination. This seems reasonably well motivated in light
of the motivation and purpose of DOMINATION.
Domination in Graphs is now a huge theoretical and applied topic. See
[1] Haynes, Hedetniemi, Slater, Fundamentals of Domination in Graphs,
1998.
where it is stated that there are over 1200 research papers on the
topic. That was in 1998, and presumably there are considerably more
papers now.
NOTE: Many many postings ago, we were using kernels/dominators in
DIRECTED GRAPHS, which is quite a different topic. They don't always
exist. [1] states that there are about 10% as many papers on the
directed graph situation.
In [1], there is a considerable discussion of motivation and
applications, in contexts including Facilities Location, Scheduling,
School Bus Routing, Computer Communication Networks, Radio Stations
(placement), Social Network Theory, Game Theory, and Chess.
E.g., we quote from Haynes et al:
"Suppose that each vertex in a graph represents a site where customers
are located, and we can choose one or more sites at which to locate
facilities to serve these customers optimally."
Such motivations for Domination discussed there provide sound general
motivation for the notion of Relative Domination and Relative c-
Domination that we use below for the Independent Dominator Split
Theorems.
NOTE: For c-Domination, we need a norm on the vertices of a graph. We
use a very natural norm on rational [-1,1]^k. That particular norm may
not be tailor made to any particular purpose of DOMINATION. (There is
the idea of this norm being related to accuracy of measurement, which
MIGHT mesh well with certain purposes of DOMINATION). So it is
compelling to determine the status of the FINITE DOMINATOR SPLIT
THEOREMS as we vary the norm. Fortunately, it appears that we can use
a very general class of norms, and also the mere existence of a
(reasonable) norm is enough to make the statement unprovable in ZFC.
This lack of sensitivity to a particular norm or even kind of norm is
very encouraging.
NOTE: We have not even begun to think about norms on the edges of a
graph. Also, we have not even begun to think about the myriad
fundamental pure and applied purposes of DOMINATION, and how they
might drive the search for necessary uses of large cardinals in the
finite.
EPILOGUE: This posting purports to show that explicitly finite forms,
even explicitly Pi01 forms, are under reasonably well motivated
control, through DOMINATION. It now becomes CRITICAL to see that the
so far very stable infinite forms: MAXIMAL CLIQUE SPLIT THEOREM,
INDEPENDENT DOMINATOR SPLIT THEOREM, do in fact have the properties
claimed. E.g., are independent of ZFC. So barring any new excitement,
I will be writing up a complete proof for these two infinite statements.
INDEPENDENT DOMINATOR SPLIT THEOREMS
by
Harvey M. Friedman
June 12, 2011
1. Graphs, Cliques, Independence, Domination, Order Invariance, Splits.
2. Maximal Clique and Independent Dominator Split Theorems.
3. Normed Graphs, Relative Domination.
4. Finite Dominator Split Theorems.
1. GRAPHS, CLIQUES, INDEPENDENCE, DOMINATION, ORDER INVARIANCE, SPLITS.
A (simple) graph is a pair G = (V,E), where V is a set and E is an
irreflexive, symmetric relation on V.
We say that x,y are adjacent if and only if x E y.
A clique is a set of vertices, where any two distinct elements are
adjacent.
An independent set is a set of vertices, where no two elements are
adjacent.
A dominator is a set S of vertices, where every vertex is equal to or
adjacent to an element of S.
[1] focuses on minimal dominators.
THEOREM 1.1. Every graph has a maximal clique. Every graph has a
maximal independent set. The maximal independent sets are the same as
the independent dominators, and the minimal dominators.
We say that x,y in R^k are order equivalent if and only if for all 1
<= i,j <= k, x_i < x_j iff y_i < y_j.
Let V be a subset of R^k. We say that S containedin V is order
invariant if and only if for all order equivalent x,y in V, x in S iff
y in S.
We say that G is an order invariant graph on V if and only if G =
(V,E), where E is an order invariant subset of V^2.
The strict upper split of S contained in R^k is the subset of R^k
resulting from dividing all coordinates of elements of S by 2, and
then removing all vectors in which 0 is a coordinate.
We use Q[-1,1] for the interval [-1,1] in the rationals.
2. MAXIMAL CLIQUE AND INDEPENDENT DOMINATOR SPLIT THEOREMS.
MAXIMAL CLIQUE SPLIT THEOREM. Every order invariant graph on Q[-1,1]^k
has a maximal clique containing its strict upper split.
INDEPENDENT DOMINATOR SPLIT THEOREM. Every order invariant graph on
Q[-1,1]^k has an independent dominator containing its strict upper
split.
THEOREM 2.1. The Maximal Clique and Independent Dominator Split
Theorems are provable in SMAH+ but not in any consistent fragment of
SMAH that proves RCA_0. The Maximal Clique and Independent Dominator
Split Theorems are provably equivalent to Con(SMAH) over RCA_0.
3. NORMED GRAPHS, RELATIVE c-DOMINATION.
We now introduce relative domination. Let A,B be sets of vertices in a
graph. We say that A dominates B, or A is a dominator of B, if and
only if every element of B is in A or adjacent to an element of A.
Given the motivation for domination cited from [1], it seems
reasonable to place a "bound" on the element of A in terms of the
given element of B. For this purpose, we introduce vertex normed graphs.
A vertex normed graph is a triple G = (V,E,h), where (V,E) is a graph,
and h:V into N.
Let c be a positive real constant. We say that A is a c-dominator of B
if and only if every x in B is in A or adjacent to some y in A with
h(y) <= ch(x).
4. FINITE DOMINATOR SPLIT THEOREMS.
We use the following natural norm on Q[-1,1]^k. h(x) is the least
positive integer n such that every coordinate of x can be written with
denominator of magnitude at most n.
This makes every graph on Q[-1,1]^k into a vertex normed graph.
FINITE DOMINATOR SPLIT THEOREM. In every order invariant graph on
Q[-1,1]^k, every finite set of vertices has an independent 8k-
dominator containing the strict upper split of their intersection.
It is clear that the Finite Dominator Split Theorem is Pi02, using the
decision procedure for (Q,<,doubling). The existential quantifier
corresponds to the size of the dominator.
But clearly the Finite Dominator Split Theorem is equivalent to the
following.
FINITE DOMINATOR SPLIT THEOREM (1). In every order invariant graph on
Q[-1,1]^k, every finite set of vertices has an independent 8k-
dominator with at most twice as many elements, containing the strict
upper split of their intersection.
It is clear that the Finite Dominator Split Theorem (1) is Pi01, using
the decision procedure for (Q,<,doubling).
Here is an explicitly Pi01 form, involving only finite graphs. Write
Q[-1,1]^k|<=r for the set of elements of Q[-1,1]^k of norm at most r.
FINITE DOMINATOR SPLIT THEOREM (2). In every order invariant graph on
Q[-1,1]^k|<=n, Q[-1,1]^k|<=n/(8k)! has an independent 8k-dominator
containing the strict upper split of their intersection.
The quantities here are crude but safe. Assuming this is the form that
is written up, we will see just what is needed.
THEOREM 4.1. All three forms of the Finite Dominator Split Theorem are
provable in SMAH+ but not in any consistent fragment of SMAH that
proves EFA. All three forms of the Finite Dominator Split Theorem are
provably equivalent to Con(SMAH) over EFA. For the first two of the
three forms of the Finite Dominator Split Theorem, we obtain the same
results even if we fix k to be a sufficiently large integer. In fact,
k = 16 suffices, and likely much smaller k like k = 8 (or even lower)
will suffice.
We intend to modify the strict upper split using any given rational
partial piecewise linear function from Q into Q, for all of the
Theorems presented, and determine the truth or falsity using small
large cardinals. This is my Templating methodology.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 466th 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
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
Harvey Friedman
More information about the FOM
mailing list