
Topics
 Combinatorics
 Set Theory
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 (Dorais 2013). 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, will denote a graph with vertex set . If , then will denote the induced subgraph of with vertex set . The four cardinal characteristics of a graph that we need are:
 The clique number is
 The stability number is
 The chromatic number is the smallest size of a cover of by anticliques.
 The cliquecover number is the smallest size of a cover of by cliques.
We have the following obvious inequalities between these cardinals
When does equality hold?
It’s not hard to see that in the case of an odd cycle with , we have
and
By duality, we also have strict inequalities for the complement of an odd cycle for . In the 1960’s, Claude Berge conjectured that odd cycles and their complements were the minimal finite graphs for which the equalities and fails. This conjecture became known as the Strong Perfect Graph Conjecture, which remained open for a long time until Chudnovsky, Robertson, Seymour and Thomas (2006) finally proved the conjecture in 2002. Since then, Berge’s conjecture has become:
Strong Perfect Graph Theorem (Lovász 1972; Lovász 1972; Chudnovsky–Robertson–Seymour–Thomas 2006). The following are equivalent for every graph :
 contains no induced copies of the odd cycle nor its complement for .
 for every finite .
 for every finite .
 for every finite .
A graph 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 and continue to hold in the uncountable case.
Both equalities are trivial for infinite bipartite graphs. The fact that for line graphs of bipartite graphs are perfect is known as König’s Duality Theorem; it is a deep result of Aharoni (1984) that this result continues to hold in the uncountable case. Unfortunately, the equalities and can fail very badly for uncountable perfect graphs. For example, Perles (1963) observed that if is an infinite cardinal then the comparability graph of the product ordering has no infinite anticliques but cannot be covered by fewer than cliques.
There is an alternative way to think of the equalities and which is much more promising in the uncountable case.
Theorem. Suppose is a perfect graph and is a positive integer.
 if and only if for every .
 if and only if for every .
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 for every means that has no clique of size . Therefore, and hence for every finite . By compactness, it follows that . QED
It is natural to ask whether this result continues to hold when is replaced by an infinite cardinal , and is replaced by its cardinal successor . 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 2011) is an excellent survey of the type of compactness issues involved here.
The first case , is already interesting to look at. This leads us to a pair of conjectures:
 In 1968, Fred Galvin conjectured that if is a comparability graph then if and only if for every .
 In 1981, Richard Rado conjectured that if is an interval graph then if and only if for every .
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 Todorcevic (1983). Recently, I extended Todorcevic’s result to the class of all chordal graphs.
Theorem (Dorais 2013). It is consistent relative to the existence of a supercompact cardinal that
holds for every chordal graph .
The dual statement for chordal graphs had already been proved by Stan Wagon.
Theorem (Wagon 1978). If is a chordal graph, then
In fact, Wagon showed that if is an uncountable chordal graph with and , then must contain the comparability graph of a Suslin tree. Since Suslin trees have size , the result follows immediately. However, note that if Suslin’s Hypothesis is true then the equality continues to hold up to .
Towards Galvin’s conjecture, the best unconditional result is due to Uri Abraham.
Theorem (Abraham 1987). If is a comparability graph without infinite anticliques, then
To prove this, Abraham looked at Perles’s example . He then generalized this example and showed that all graphs without infinite anticliques such that must contain an induced subgraph of Perles type. Since graphs of Perles type have size , 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 finitedimensional comparability graphs.
Theorem (Todorcevic 2011). It is consistent relative to the existence of a supercompact cardinal that
holds for every finitedimensional comparability graph .
This follows from a remark without proof in (Todorcevic 2011). However, I had obtained an independent proof of this fact sometime ago, you can find my proof in (Dorais 2013).
It appears that not much is known about the dual of Galvin’s Conjecture.
Theorem (Dorais 2013). It is consistent relative to the existence of a supercompact cardinal that
holds for every twodimensional comparability graph .
In fact, I show that the dual of Galvin’s Conjecture restricted to twodimensional comparability graphs is equivalent to Rado’s Conjecture. Since trees are twodimensional, this includes an earlier result of Todorcevic (1983). The consistency of the dual of Galvin’s Conjecture restricted to threedimensional comparability graphs appears to be open.
It follows from results of (Todorcevic 1983) that Rado’s Conjecture is the equivalent to the statement that a comparability graph can be covered by countably many sets such that each has no infinite clique if and only if this is true for every with . Therefore, the dual of Abraham’s Theorem would suffice to establish the consistency of the dual of Galvin’s Conjecture.
References

U. Abraham, 1987: A note on Dilworth’s theorem in the infinite case, Order 4, no. 2, 107–125.

mr: 0916489

zbl: 0629.06002

doi: 10.1007/BF00337691


R. Aharoni, 1984: König’s duality theorem for infinite bipartite graphs, J. London Math. Soc. (2) 29, no. 1, 1–12.

mr: 0734985

zbl: 0505.05049


M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, 2006: The strong perfect graph theorem, Ann. of Math. (2) 164, no. 1, 51–229.

mr: 2233847

zbl: 1112.05042


F. G. Dorais, 2013: A note on conjectures of F. Galvin and R. Rado, Canad. Math. Bull. 56, 317–325.

mr: 3043059

zbl: 1315.03077

arxiv: 1110.6563


L. Lovász, 1972: A characterization of perfect graphs, J. Combinatorial Theory Ser. B 13, 95–98.

mr: 0309780

zbl: 0241.05107


L. Lovász, 1972: Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2, no. 3, 253–267.

mr: 0302480

zbl: 0239.05111


M. A. Perles, 1963: On Dilworth’s theorem in the infinite case, Israel J. Math. 1, 108–109.

mr: 0168497

zbl: 0115.01703

doi: 10.1007/BF02759806


S. Todorcevic, 2011: Combinatorial dichotomies in set theory, Bull. Symbolic Logic 17, no. 1, 1–72.

mr: 2760116

zbl: 1230.03075


S. Todorcevic, 1983: On a conjecture of R. Rado, J. London Math. Soc. (2) 27, no. 1, 1–8.

mr: 0620672

zbl: 0463.06001


S. Wagon, 1978: Infinite triangulated graphs, Discrete Math. 22, no. 2, 183–189.

mr: 0523302

zbl: 0382.05047

Originally posted on by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.
Comments

François G. Dorais wrote
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…