[FOM] 467: Comment on Minimal Dominators

[Harvey Friedman]

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