Uncountable perfect graphs

I have been fascinated with perfect graphs for many years. These graphs are very intensely studied in finite combinatorics and new wonderful properties of finite perfect graphs are discovered on a regular basis. However, it is still unclear whether or how these wonderful properties might extend to the countable and uncountable cases. There are several deep questions about this. One of the most interesting question is the consistency of Galvin’s Conjecture. I recently wrote a paper on this question [4]. Since I believe this and related questions deserve more attention, here is a brief survey of known results around Galvin’s Conjecture.

Perfection has to do with some cardinal characteristics of graphs. Throughout the following, $G$ will denote a graph with vertex set $V$. If $X \subseteq V$, then $G_X$ will denote the induced subgraph of $G$ with vertex set $X$. The four cardinal characteristics of a graph $G$ that we need are:

  • The clique number is $$\omega(G) = \sup \set{|X|:\text{$X$ is a clique of $G$}}.$$
  • The stability number is $$\alpha(G) = \sup\set{|X|:\text{$X$ is an anticlique of $G$}}.$$
  • The chromatic number $\chi(G)$ is the smallest size of a cover of $V$ by anticliques.
  • The clique-cover number $\theta(G)$ is the smallest size of a cover of $V$ by cliques.

We have the following obvious inequalities between these cardinals $$\omega(G) \leq \chi(G) \qquad \alpha(G) \leq \theta(G).$$ When does equality hold?

It’s not hard to see that in the case of an odd cycle $C_{2n+1}$ with $n \geq 2$, we have $$2 = \omega(C_{2n+1}) \lt \chi(C_{2n+1}) = 3$$ and $$n = \alpha(C_{2n+1}) \lt \theta(C_{2n+1}) = n+1.$$ By duality, we also have strict inequalities for the complement $\overline{C}_{2n+1}$ of an odd cycle for $n \geq 2$. In the 1960’s, Claude Berge conjectured that odd cycles and their complements were the minimal finite graphs for which the equalities $\omega = \chi$ and $\alpha = \theta$ fails. This conjecture became known as the Strong Perfect Graph Conjecture, which remained open for a long time until Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas finally proved the conjecture in 2002. Since then, Berge’s conjecture has become the Strong Perfect Graph Theorem:

Theorem (Lovász [6, 5]; Chudnovsky–Robertson–Seymour–Thomas [3]). The following are equivalent for every graph $G$:

  1. $G$ contains no induced copies of the odd cycle $C_{2n+1}$ nor its complement $\overline{C}_{2n+1}$ for $n \geq 2$.
  2. $\omega(G_X) = \chi(G_X)$ for every finite $X \subseteq V$.
  3. $\alpha(G_X) = \theta(G_X)$ for every finite $X \subseteq V$.
  4. $\alpha(G_X)\omega(G_X) \geq |X|$ for every finite $X \subseteq V$.

A graph $G$ with these properties is called a perfect graph. Several classes of graphs are known to be perfect:

  • Bipartite graphs are perfect.
  • Line graphs of bipartite graphs are perfect.
  • Comparability graphs are perfect.
  • Interval graphs are perfect.
  • Chordal graphs are perfect.

All of these families make sense for infinite graphs. It is natural to ask whether the equalities $\omega = \chi$ and $\alpha = \theta$ continue to hold in the uncountable case.

Both equalities are trivial for infinite bipartite graphs. The fact that $\alpha = \theta$ for line graphs of bipartite graphs are perfect is known as König’s Duality Theorem; it is a deep result of Ron Aharoni [2] that this result continues to hold in the uncountable case. Unfortunately, the equalities $\omega = \chi$ and $\alpha = \theta$ can fail very badly for uncountable perfect graphs. For example, Misha Perles [7] observed that if $\kappa$ is an infinite cardinal then the comparability graph of the product ordering $\kappa\times\kappa$ has no infinite anticliques but cannot be covered by fewer than $\kappa$ cliques.

There is an alternative way to think of the equalities $\omega = \chi$ and $\alpha = \theta$ which is much more promising in the uncountable case.

Theorem. Suppose $G$ is a perfect graph and $k$ is a positive integer.

  1. $\chi(G) \leq k$ if and only if $\chi(G_X) \leq k$ for every $X \in [V]^{k+1}$.
  2. $\theta(G) \leq k$ if and only if $\theta(G_X) \leq k$ for every $X \in [V]^{k+1}$.

Proof. The two statements are dual, so I will only prove the first. The forward implication is trivial. For the backward implication, note that the fact that $\chi(G_X) \leq k$ for every $X \in [V]^{k+1}$ means that $G$ has no clique of size $k+1$. Therefore, $\omega(G) \leq k$ and hence $\chi(G_X) \leq k$ for every finite $X \subseteq V$. By compactness, it follows that $\chi(G) \leq k$. QED

It is natural to ask whether this result continues to hold when $k$ is replaced by an infinite cardinal $\kappa$, and $k+1$ is replaced by its cardinal successor $\kappa^+$. Since compactness plays a key role in the above proof, this type of generalization is intimately tied with infinitary generalizations of compactness. It is therefore expected that large cardinals will play a role in determining whether such generalizations are plausible or not. Todorcevic [9] is an excellent survey of the type of compactness issues involved here.

The first case $\kappa = \aleph_0$, $\kappa^+ = \aleph_1$ is already interesting to look at. This leads us to a pair of conjectures:

  • In 1968, Fred Galvin conjectured that if $G$ is a comparability graph then $\theta(G) \leq \aleph_0$ if and only if $\theta(G_X) \leq \aleph_0$ for every $X \in [V]^{\aleph_1}$.
  • In 1981, Richard Rado conjectured that if $G$ is an interval graph then $\chi(G) \leq \aleph_0$ if and only if $\chi(G_X) \leq \aleph_0$ for every $X \in [V]^{\aleph_1}$.

Note that Galvin’s Conjecture implies Rado’s Conjecture since the complement of an interval graph is a comparability graph.

It turns out that both conjectures are consistently false. However, Rado’s Conjecture was shown to be consistent relative to a supercompact cardinal by Stevo Todorcevic [8]. Recently, I extended Todorcevic’s result to the class of all chordal graphs.

Theorem (Dorais [4]). It is consistent relative to the existence of a supercompact cardinal that $$\chi(G) \leq \aleph_0 \IFF (\forall X \in [V]^{\aleph_1})(\chi(G_X) \leq \aleph_0)$$ holds for every chordal graph $G$.

The dual statement for chordal graphs had already been proved by Stan Wagon.

Theorem (Wagon [10]). If $G$ is a chordal graph, then $$\theta(G) \leq \aleph_0 \IFF (\forall X \in [V]^{\aleph_1})(\theta(G_X) \leq \aleph_0).$$

In fact, Wagon showed that if $G$ is an uncountable chordal graph with $\alpha(G) \leq \aleph_0$ and $\theta(G) \geq \aleph_1$, then $G$ must contain the comparability graph of a Suslin tree. Since Suslin trees have size $\aleph_1$, the result follows immediately. However, note that if Suslin’s Hypothesis is true then the equality $\alpha = \theta$ continues to hold up to $\aleph_1$.

Towards Galvin’s conjecture, the best unconditional result is due to Uri Abraham.

Theorem (Abraham [1]). If $G$ is a comparability graph without infinite anticliques, then $$\theta(G) \leq \aleph_0 \IFF (\forall X \in [V]^{\aleph_1})(\theta(G_X) \leq \aleph_0).$$

To prove this, Abraham looked at Perles’s example $\omega_1 \times \omega_1$. He then generalized this example and showed that all graphs $G$ without infinite anticliques such that $\theta(G) \geq \aleph_1$ must contain an induced subgraph of Perles type. Since graphs of Perles type have size $\aleph_1$, the result follows immediately.

Another step towards Galvin’s conjecture is due to Stevo Todorcevic, who showed that Rado’s conjecture is equivalent to the restriction of Galvin’s conjecture to finite-dimensional comparability graphs.

Theorem (Todorcevic [9]). It is consistent relative to the existence of a supercompact cardinal that $$\theta(G) \leq \aleph_0 \IFF (\forall X \in [V]^{\aleph_1})(\theta(G_X) \leq \aleph_0)$$ holds for every finite-dimensional comparability graph $G$.

This follows from a remark without proof in [9]. However, I had obtained an independent proof of this fact sometime ago, you can find my proof in [4].

It appears that not much is known about the dual of Galvin’s Conjecture.

Theorem (Dorais [4]). It is consistent relative to the existence of a supercompact cardinal that $$\chi(G) \leq \aleph_0 \IFF (\forall X \in [V]^{\aleph_1})(\chi(G_X) \leq \aleph_0)$$ holds for every two-dimensional comparability graph $G$.

In fact, I show that the dual of Galvin’s Conjecture restricted to two-dimensional comparability graphs is equivalent to Rado’s Conjecture. Since trees are two-dimensional, this includes an earlier result of Todorcevic [8]. The consistency of the dual of Galvin’s Conjecture restricted to three-dimensional comparability graphs appears to be open.

It follows from results of Todorcevic [8] that Rado’s Conjecture is the equivalent to the statement that a comparability graph $G$ can be covered by countably many sets $V_0,V_1,\dots$ such that each $G_{V_i}$ has no infinite clique if and only if this is true for every $G_X$ with $X \in [V]^{\aleph_1}$. Therefore, the dual of Abraham’s Theorem would suffice to establish the consistency of the dual of Galvin’s Conjecture.

References

[1] [doi] U. Abraham, “A note on Dilworth’s theorem in the infinite case,” Order, vol. 4, iss. 2, pp. 107-125, 1987.
[Bibtex]
@article {Abraham,
AUTHOR = {Abraham, Uri},
TITLE = {A note on {D}ilworth's theorem in the infinite case},
JOURNAL = {Order},
FJOURNAL = {Order},
VOLUME = {4},
YEAR = {1987},
NUMBER = {2},
PAGES = {107--125},
ISSN = {0167-8094},
CODEN = {ORDRE5},
MRCLASS = {06A10 (03E05 03E10)},
MRNUMBER = {916489 (89g:06001)},
MRREVIEWER = {E. C. Milner},
DOI = {10.1007/BF00337691},
URL = {http://dx.doi.org/10.1007/BF00337691},
}
[2] [doi] R. Aharoni, “König’s duality theorem for infinite bipartite graphs,” J. london math. soc. (2), vol. 29, iss. 1, pp. 1-12, 1984.
[Bibtex]
@article {Aharoni,
AUTHOR = {Aharoni, Ron},
TITLE = {K\"onig's duality theorem for infinite bipartite graphs},
JOURNAL = {J. London Math. Soc. (2)},
FJOURNAL = {Journal of the London Mathematical Society. Second Series},
VOLUME = {29},
YEAR = {1984},
NUMBER = {1},
PAGES = {1--12},
DOI = {10.1112/jlms/s2-29.1.1},
URL = {http://dx.doi.org/10.1112/jlms/s2-29.1.1},
}
[3] [doi] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, “The strong perfect graph theorem,” Ann. of math. (2), vol. 164, iss. 1, pp. 51-229, 2006.
[Bibtex]
@article {ChudnovskyRobertsonSeymourThomas,
AUTHOR = {Chudnovsky, Maria and Robertson, Neil and Seymour, Paul and Thomas, Robin},
TITLE = {The strong perfect graph theorem},
JOURNAL = {Ann. of Math. (2)},
FJOURNAL = {Annals of Mathematics. Second Series},
VOLUME = {164},
YEAR = {2006},
NUMBER = {1},
PAGES = {51--229},
ISSN = {0003-486X},
CODEN = {ANMAAH},
MRCLASS = {05C17},
MRNUMBER = {2233847 (2007c:05091)},
MRREVIEWER = {Carsten Thomassen},
DOI = {10.4007/annals.2006.164.51},
URL = {http://dx.doi.org/10.4007/annals.2006.164.51},
}
[4] [doi] F. G. Dorais, “A note on conjectures of F. Galvin and R. Rado,” Canad. math. bull., 2011.
[Bibtex]
@article {Dorais,
AUTHOR = {Dorais, Fran{\c{c}}ois G.},
TITLE = {A note on conjectures of {F}. {G}alvin and {R}. {R}ado},
JOURNAL = {Canad. Math. Bull.},
FJOURNAL = {Canadian Mathematical Bulletin. Bulletin Canadien de Math\'ematiques},
YEAR = {2011},
DOI = {10.4153/CMB-2011-192-8},
URL = {http://dx.doi.org/10.4153/CMB-2011-192-8},
NOTE = {to appear},
EPRINT = {1110.6563},
}
[5] [doi] L. Lovász, “A characterization of perfect graphs,” J. combinatorial theory ser. b, vol. 13, pp. 95-98, 1972.
[Bibtex]
@article {LovaszB,
AUTHOR = {Lov{\'a}sz, L{\'a}sl{\'o}},
TITLE = {A characterization of perfect graphs},
JOURNAL = {J. Combinatorial Theory Ser. B},
FJOURNAL = {Journal of Combinatorial Theory. Series B},
VOLUME = {13},
YEAR = {1972},
PAGES = {95--98},
DOI = {10.1016/0095-8956(72)90045-7},
URL = {http://dx.doi.org/10.1016/0095-8956(72)90045-7},
}
[6] [doi] L. Lovász, “Normal hypergraphs and the perfect graph conjecture,” Discrete math., vol. 2, iss. 3, pp. 253-267, 1972.
[Bibtex]
@article {LovaszA,
AUTHOR = {Lov{\'a}sz, L{\'a}sl{\'o}},
TITLE = {Normal hypergraphs and the perfect graph conjecture},
JOURNAL = {Discrete Math.},
FJOURNAL = {Discrete Mathematics},
VOLUME = {2},
YEAR = {1972},
NUMBER = {3},
PAGES = {253--267},
DOI = {10.1016/0012-365X(72)90006-4},
URL = {http://dx.doi.org/10.1016/0012-365X(72)90006-4},
}
[7] [doi] M. A. Perles, “On Dilworth’s theorem in the infinite case,” Israel j. math., vol. 1, pp. 108-109, 1963.
[Bibtex]
@article {Perles,
AUTHOR = {Perles, Micha Asher},
TITLE = {On {D}ilworth's theorem in the infinite case},
JOURNAL = {Israel J. Math.},
FJOURNAL = {Israel Journal of Mathematics},
VOLUME = {1},
YEAR = {1963},
PAGES = {108--109},
ISSN = {0021-2172},
MRCLASS = {06.20},
MRNUMBER = {0168497 (29 \#5759)},
MRREVIEWER = {J. McLaughlin},
DOI = {10.1007/BF02759806},
URL = {http://dx.doi.org/10.1007/BF02759806},
}
[8] [doi] S. Todorcevic, “On a conjecture of R. Rado,” J. london math. soc. (2), vol. 27, iss. 1, pp. 1-8, 1983.
[Bibtex]
@article {TodorcevicA,
AUTHOR = {Todorcevic, Stevo},
TITLE = {On a conjecture of {R}. {R}ado},
JOURNAL = {J. London Math. Soc. (2)},
FJOURNAL = {Journal of the London Mathematical Society. Second Series},
VOLUME = {27},
YEAR = {1983},
NUMBER = {1},
PAGES = {1--8},
ISSN = {0024-6107},
CODEN = {JLMSAK},
MRCLASS = {03E35 (03E05 03E55 05C15 06A05)},
MRNUMBER = {686495 (85e:03117)},
DOI = {10.1112/jlms/s2-27.1.1},
URL = {http://dx.doi.org/10.1112/jlms/s2-27.1.1},
}
[9] [doi] S. Todorcevic, “Combinatorial dichotomies in set theory,” Bull. symbolic logic, vol. 17, iss. 1, pp. 1-72, 2011.
[Bibtex]
@article {TodorcevicB,
AUTHOR = {Todorcevic, Stevo},
TITLE = {Combinatorial dichotomies in set theory},
JOURNAL = {Bull. Symbolic Logic},
FJOURNAL = {The Bulletin of Symbolic Logic},
VOLUME = {17},
YEAR = {2011},
NUMBER = {1},
PAGES = {1--72},
ISSN = {1079-8986},
MRCLASS = {03E05},
MRNUMBER = {2760116},
DOI = {10.2178/bsl/1294186662},
URL = {http://dx.doi.org/10.2178/bsl/1294186662},
}
[10] [doi] S. Wagon, “Infinite triangulated graphs,” Discrete math., vol. 22, iss. 2, pp. 183-189, 1978.
[Bibtex]
@article {Wagon,
AUTHOR = {Wagon, Stanley},
TITLE = {Infinite triangulated graphs},
JOURNAL = {Discrete Math.},
FJOURNAL = {Discrete Mathematics},
VOLUME = {22},
YEAR = {1978},
NUMBER = {2},
PAGES = {183--189},
ISSN = {0012-365X},
CODEN = {DSMHA4},
MRCLASS = {05C99},
MRNUMBER = {523302 (80i:05078)},
MRREVIEWER = {H. Sachs},
DOI = {10.1016/0012-365X(78)90123-1},
URL = {http://dx.doi.org/10.1016/0012-365X(78)90123-1},
}
 

One thought on “Uncountable perfect graphs

  1. David Eppstein just wrote a post where he generalizes chordal graphs to the infinite case in a manner much different than I do. It is interesting to compare the two…

Leave a Reply

Your email address will not be published. Required fields are marked *