[FOM] 467: Comment on Minimal Dominators
Harvey Friedman
friedman at math.ohio-state.edu
Tue Jun 14 05:20:31 EDT 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS BRIEF POSTING IS A COMMENT ON http://www.cs.nyu.edu/pipermail/fom/2011-June/015567.html
*****************************************
Recall that I said in http://www.cs.nyu.edu/pipermail/fom/2011-June/015567.html
that
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.
I also wrote
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.
Although the maximal independent sets are the same as the independent
dominators, they are NOT the same as the minimal dominators. The
maximal independent sets and the independent dominators ARE minimal
dominators, but generally, SOME minimal dominators are NOT independent.
I correctly stated (assuming large cardinals)
MAXIMAL CLIQUE SPLIT THEOREM. In every order invariant graph on
Q[-1,1]^k, some maximal clique contains its strict upper split.
INDEPENDENT DOMINATOR SPLIT THEOREM. In every order invariant graph on
Q[-1,1]^k, some independent dominator contains its strict upper split.
Therefore,
MINIMAL DOMINATOR SPLIT THEOREM. In every order invariant graph on
Q[-1,1]^k, some minimal dominator contains its strict upper split.
is also correct (assuming large cardinals). HOWEVER, I have NOT had a
chance to see if the Minimal Domination Split Theorem is provable in
ZFC.
PLEASE NOTE: I changed the ENGLISH in the above three statements. This
avoids any possible ambiguity in the statements in http://www.cs.nyu.edu/pipermail/fom/2011-June/015567.html
- i.e., the scope of "maximal".
I have started to write a detailed sketch of a proof that the Maximal
Clique and Independent Dominator Split Theorems are provably
equivalent to Con(SMAH) over WKL_0.
Thus the moment of ###TRUTH### is approaching, and assuming all goes
well, I will see if I can modify the proof to handle the Minimal
Dominator Split Theorem.
Independent Dominators (the same as maximal independent sets) are also
discussed extensively in [1] - see Chapter 3, and also section 6.2.
Also in [1], there are a large variety of conditions that are imposed
on dominators - in addition to minimality and independence - and thus
we see that there is an enormous amount of material in [1] to examine
carefully in order to create perhaps lots of additional necessary uses
of large cardinals. This also promises to create a greater variety of
finite forms taking more issues into account than in http://www.cs.nyu.edu/pipermail/fom/2011-June/015567.html
.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 467th 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
466: RETURN TO 463/Dominators 6/13/11 12:15AM
Harvey Friedman
More information about the FOM
mailing list