Independent sets for small pictures of the reals and measure/category dichotomies for graphs on the reals: the surviving open questions of Erdős–Hajnal, Some remarks on set theory. VIII (1960)

The 1960 paper of P. Erdős and A. Hajnal (Michigan Mathematical Journal 7, 187-191) associates to each real $x$ a picture $S(x)\subseteq\mathbb{R}$ with $x\notin S(x)$ and asks how measure-theoretic, topological, and order-theoretic smallness of the pictures forces the existence and size of independent (free) sets, and, in the parallel graph formulation, which dichotomy theorems hold for graphs on the real line that guarantee either a large complete subgraph or an independent set large in the sense of measure or Baire category. The paper proves that null, non-everywhere-dense pictures always admit an independent pair, that bounded pictures of outer measure at most 1 admit $k$ independent points for every finite $k$ , that under the well-ordering hypothesis $H_0$ the bounded-measure conjecture of the series fails by an explicit construction, and several dichotomy theorems in the graph formulation (Theorems 3, $3'$ , and $3''$ under CH and a cofinality property P of the relevant sigma-ideals, Theorem 4 unconditionally); but it leaves open a precise list of questions: the strength of $H_0$ ; whether the negation of $H_0$ rescues the original bounded-measure conjecture or yields independent triplets; whether Theorem 2's hypotheses force an infinite independent set; uncountable independent sets under order-type restrictions on the pictures; the countable-bipartite strengthening of the main graph dichotomy; the extensions of the multi-ideal Theorem 5; and three further questions of the paper (both parts of power $\mathfrak{c}$ in the strengthened Theorem 1, closed pictures with outer measure at most 1, and the $\aleph_1$ -subfamily intersection question for positive-measure families). The authors' own 1966 result that every uncountably chromatic graph contains a 4-cycle rules out the proposed quadrilateral-free counterexample, but leaves the remaining questions open.

Background

In a series of papers under the title 'Some remarks on set theory', P. Erdős, A. Hajnal, and a few coauthors developed, among other things, a free-set theory for the real line. The eighth paper of the series (1960) works with the following notion. A set mapping, called a picture there, assigns to each real number $x$ a set $S(x)\subseteq\mathbb{R}$ of reals with $x\notin S(x)$ ; one should think of $S(x)$ as a forbidden neighborhood of $x$ . A set $M'\subseteq\mathbb{R}$ is independent (or free) if $x\notin S(y)$ and $y\notin S(x)$ for every pair $x,y\in M'$ . The guiding question of the series is: if every picture is small in some sense (by measure, by topology, or by order type), how large an independent set must exist? An earlier paper of the series (Erdős's remarks III, quoted as [2, I, p. 52] in the 1960 paper) had conjectured that if the Lebesgue measure of each $S(x)$ is bounded and no $S(x)$ is everywhere dense (i.e., the closure of no picture is all of $\mathbb{R}$ ), then an independent pair always exists.

The relevant smallness vocabulary is the following. A null set is a set of Lebesgue measure 0. The outer measure of a set $A$ is the infimum of the total lengths of countable families of open intervals covering $A$ ; it is defined for every set of reals, agrees with Lebesgue measure on measurable sets, and a bounded picture means a picture that is bounded as a set of reals. A set is nowhere dense if its closure has empty interior, and of first category (meagre) if it is a countable union of nowhere dense sets; a set of second category is one not of first category. A sigma-ideal is a collection of subsets of $\mathbb{R}$ , not containing $\mathbb{R}$ itself, closed under taking subsets and countable unions; the null sets and the meagre sets are the two standard examples. Writing $\mathfrak{c}=2^{\aleph_{0}}$ for the cardinality of the continuum, $\Omega_{\mathfrak{c}}$ for the least ordinal of that cardinality, and CH for the continuum hypothesis $\mathfrak{c}=\aleph_{1}$ , a sigma-ideal $I$ is said in the 1960 paper to have property P if there is a transfinite sequence $\{B_{\beta}:0<\beta<\Omega_{\mathfrak{c}}\}$ of sets in $I$ such that every member of $I$ is contained in one of the $B_{\beta}$ ; that is, $I$ admits a cofinal covering family indexed by the continuum.

The paper introduces the hypothesis $H_0$ : the reals can be well-ordered as $\{x_{\alpha}:\alpha<\Omega_{\mathfrak{c}}\}$ so that every set of reals that is not cofinal in this well-ordering (i.e., contained in $\{x_{\beta}:\beta<\alpha\}$ for some $\alpha<\Omega_{\mathfrak{c}}$ ) has measure 0. Since a countable union of null sets is null, $H_0$ follows from the hypothesis that every set of power less than $\mathfrak{c}$ has measure 0, which itself follows from CH; whether $H_0$ is strictly weaker is one of the paper's questions. Under $H_0$ the original conjecture of the series fails: the paper constructs, from any well-ordering witnessing $H_0$ , pictures of measure exactly 1, none everywhere dense, with no two points independent. On the positive side the paper proves: (Theorem 1) if every $S(x)$ is null and not everywhere dense, an independent pair always exists, though under $H_0$ an independent triplet can fail; (strengthened Theorem 1) if every $S(x)$ is null and nowhere dense, there are sets $A$ of power $\aleph_{0}$ and $B$ of power $\mathfrak{c}$ such that every pair $x\in A$ , $y\in B$ is independent; and (Theorem 2) if every $S(x)$ is bounded and has outer measure at most 1, then for every positive integer $k$ there exist $k$ independent points. The paper also records, quoting an earlier theorem, that if every $S(x)$ is closed, an independent set of cardinality $\mathfrak{c}$ exists; but if every $S(x)$ has outer measure at most 1 and the set $\{x\}\cup S(x)$ is closed, even an independent pair was out of reach. Uncountable independent sets can fail in general: for $S(x)=(x-\tfrac{1}{2},x)\cup(x,x+\tfrac{1}{2})$ every independent set is at most countable. The paper also recalls, again from remarks III, that if every picture is nowhere dense then an infinite (denumerable) independent set exists, and asks whether this can be improved to an uncountable one; two order-type restrictions appear in these questions: no picture containing a subset of type $\eta$ (a subset order-isomorphic to the rational numbers with their usual order), and every picture being a sequence of type $\omega$ whose only limit point is $x$ (a countable set whose sole accumulation point is $x$ ).

The second half of the paper translates the same phenomenon into graph theory. Here $M$ denotes the set of real numbers, and $G_{M}$ denotes an arbitrary graph whose vertices are the elements of $M$ ; a set of vertices is independent (in the graph sense) if no two of its elements are joined by an edge, and a subgraph is complete if every pair of its vertices is joined. A classical dichotomy quoted in the paper states that every graph of uncountable power $\lambda$ contains either an infinite complete subgraph or an independent set of power $\lambda$ . The paper asks for analogues in which 'large' is measured by the sigma-ideals of null and meagre sets. Using the classical facts, quoted there, that under CH there is a set of power $\mathfrak{c}$ meeting every null set in a countable set, and the analogous fact for meagre sets, it proves under CH that every graph $G_{M}$ contains an infinite complete subgraph or an independent set of positive outer measure (Theorem 3), respectively of second category (Theorem 3 $'$ ), and more generally an independent set outside any sigma-ideal with property P (Theorem 3 $''$ ). An explicit partition $\mathbb{R}=A\cup B$ with $A$ null, $B$ of first category, and all cross pairs joined shows that 'second category and positive outer measure' cannot be forced simultaneously by these hypotheses alone. Theorem 4 overcomes this: if for some finite $n$ the graph contains no complete bipartite subgraph with parts of sizes $n$ and $\aleph_{0}$ (no family of $n$ vertices jointly adjacent, each to every vertex of a common countably infinite family), then it has an independent set of vertices which is both of second category and of positive outer measure. If $\mathfrak{c}$ is regular (has cofinality $\mathfrak{c}$ ), the first alternative improves to a complete bipartite subgraph with parts of sizes $n$ and $\mathfrak{c}$ , for each $n$ . Theorem 5 extends Theorem 4 from the two ideals of null and meagre sets to any family of $\mathfrak{m}<\mathfrak{c}$ sigma-ideals with property P: the graph either contains, for every $n<\omega$ , a complete bipartite subgraph with parts of sizes $n$ and $\mathfrak{m}$ , or an independent set contained in none of the ideals.

The authors' own 1966 paper began the systematic theory of graphs of uncountable chromatic number, the chromatic number $\chi(G)$ being the least number of colors needed to color the vertices so that adjacent vertices receive different colors (so 'uncountable chromatic number' means $\chi(G)>\omega$ ). Its Corollary 5.6, as stated in that paper's introduction, implies that a graph containing no quadrilateral (no 4-cycle, $C_{4}$ ) has colouring number at most $\omega$ ; the colouring number is the least cardinal $\kappa$ such that the vertices admit a well-ordering in which each vertex has fewer than $\kappa$ earlier neighbours, and it is always at least the chromatic number. In particular, every graph of uncountable chromatic number contains a 4-cycle. Soukup (2018) records this directly (if $\chi(G)>\omega$ then $G$ contains a 4-cycle, originally proved in the 1966 paper) and surveys the modern obligatory-subgraph program, which classifies the subgraphs that must embed in every uncountably chromatic graph; Joó (2020) records the same fact in his study of directed analogues. On the set-mapping side, Garti (2016) studies dense free sets for set mappings $f:\mathbb{R}\to\mathcal{P}(\mathbb{R})$ under combinatorial intersection properties $C(\omega,\kappa)$ and $C(\kappa,\omega)$ (bounds on how many images $f(x)$ the arguments of a small set can meet), proving that if the reaping number $\mathfrak{r}$ , a cardinal characteristic of the continuum (a cardinal invariant with $\aleph_{1}\leq\mathfrak{r}\leq\mathfrak{c}$ measuring unsplittable families of infinite binary sequences), is below the cofinality of $\kappa$ , then every $\kappa$ -reasonable set mapping on the reals has an infinite dense free set. These hypotheses are combinatorial rather than measure- or category-theoretic.

Problem Statement

Determine the status (ZFC theorem, refutation by explicit construction, or calibration against the named hypotheses) of the following questions, which are the open questions left by Erdős and Hajnal's 1960 paper. Throughout, $S(x)\subseteq\mathbb{R}$ denotes a picture with $x\notin S(x)$ , $\mathfrak{c}=2^{\aleph_{0}}$ , and $H_0$ is the hypothesis that $\mathbb{R}$ can be well-ordered in type $\Omega_{\mathfrak{c}}$ so that every non-cofinal set has measure 0.

P1. Is $H_0$ equivalent to the hypothesis that every set of reals of power less than $\mathfrak{c}$ has measure 0?

P2. If every $S(x)$ has bounded measure and is not everywhere dense, does the negation of $H_0$ imply the existence of an independent pair? (Under $H_0$ the answer is negative by the paper's counterexample.)

P3. If every $S(x)$ is null and not everywhere dense, so that an independent pair always exists, does the negation of $H_0$ imply the existence of an independent triplet? (Under $H_0$ a triplet can fail.)

P4. If every $S(x)$ is null and nowhere dense, can the sets $A$ and $B$ , with every cross pair independent, be chosen so that both have power $\mathfrak{c}$ ?

P5. If every $S(x)$ is bounded and has outer measure at most 1, so that $k$ independent points exist for every finite $k$ by Theorem 2, must an infinite independent set exist? (An uncountable independent set need not exist even for simple open pictures.)

P6a. If every $S(x)$ is nowhere dense, so that an infinite independent set always exists, must there exist an uncountable independent set? P6b. If every $S(x)$ is nowhere dense and none of the pictures $S(x)$ contains a subset of type $\eta$ (order-isomorphic to the rationals), must there exist an uncountable independent set? P6c. If every $S(x)$ is nowhere dense and each $S(x)$ is a sequence of type $\omega$ whose only limit point is $x$ , must there exist an uncountable independent set?

P7. If every $S(x)$ has outer measure at most 1 and the set $\{x\}\cup S(x)$ is closed, must an independent pair exist? (For closed pictures alone, an independent set of cardinality $\mathfrak{c}$ exists.)

P8. Does every graph $G_{M}$ on the real line contain either a complete bipartite subgraph with both parts countably infinite (vertices $\{x_{i}\}_{i<\omega}$ and $\{y_{j}\}_{j<\omega}$ with every pair $(x_{i},y_{j})$ joined, i.e., a $K_{\omega,\omega}$ ), or else an independent set of vertices which is both of second category and of positive outer measure?

P9a. Does Theorem 5 remain true for $\mathfrak{m}=\mathfrak{c}$ : must every graph $G_{M}$ contain, for every $n<\omega$ , a complete bipartite subgraph with parts of sizes $n$ and $\mathfrak{c}$ , or else have an independent set contained in none of the given $\mathfrak{c}$ sigma-ideals (the ideals being assumed to have property P, as in Theorem 5)? P9b. Does the conclusion of Theorem 5 hold without property P, even for $n=\mathfrak{m}=2$ ? (The 1960 paper's suggested counterexample to this, a quadrilateral-free graph of uncountable chromatic number, cannot exist, since every uncountably chromatic graph contains a 4-cycle by the 1966 Corollary 5.6; the question itself is untouched.)

P10. Can there exist a family $\{E_{\alpha}:\alpha<\mathfrak{c}\}$ of sets of reals of positive measure such that every subfamily of power $\aleph_{1}$ has empty intersection? (The paper notes the problem becomes obvious when $\mathfrak{c}=\aleph_{1}$ ; the question concerns $\mathfrak{c}>\aleph_{1}$ .)

References

P. Erdős and A. Hajnal, "Some remarks on set theory. VIII.", Michigan Mathematical Journal 7 (1960), no. 2, 187-191. DOI: 10.1307/mmj/1028998389, https://doi.org/10.1307/mmj/1028998389 (official scan at the Rényi Institute Erdős archive, https://www.renyi.hu/~p_erdos/1960-19.pdf).
P. Erdős, "Some remarks on set theory. III.", Michigan Mathematical Journal 2 (1953-1954), 51-57. DOI: 10.1307/mmj/1028989869, https://doi.org/10.1307/mmj/1028989869 (official scan at https://www.renyi.hu/~p_erdos/1954-08.pdf).
P. Erdős and A. Hajnal, "On chromatic number of graphs and set-systems", Acta Mathematica Academiae Scientiarum Hungaricae 17 (1966), no. 1-2, 61-99. DOI: 10.1007/bf02020444, https://doi.org/10.1007/bf02020444 (official scan at https://www.renyi.hu/~p_erdos/1966-07.pdf).
P. Erdős and A. Hajnal, "Some remarks on set theory. IX. Combinatorial problems in measure theory and set theory", Michigan Mathematical Journal 11 (1964), no. 2, 107-127. DOI: 10.1307/mmj/1028999083, https://doi.org/10.1307/mmj/1028999083 (official scan at https://www.renyi.hu/~p_erdos/1964-28.pdf).
P. Erdős and M. Makkai, "Some remarks on set theory. X", Studia Scientiarum Mathematicarum Hungarica 1 (1966), 157-159. No DOI assigned; official scan at https://www.renyi.hu/~p_erdos/1966-19.pdf (zbMATH, https://zbmath.org/?q=an%3A0199.02303).
Dániel T. Soukup, "Orientations of graphs with uncountable chromatic number", Journal of Graph Theory 88 (2018), no. 4, 606-630. DOI: 10.1002/jgt.22233, https://doi.org/10.1002/jgt.22233 (preprint arXiv:1608.06981, https://arxiv.org/abs/1608.06981).
Attila Joó, "Uncountable dichromatic number without short directed cycles", Journal of Graph Theory 94 (2020), no. 1, 113-116. DOI: 10.1002/jgt.22509, https://doi.org/10.1002/jgt.22509 (preprint arXiv:1905.00782, https://arxiv.org/abs/1905.00782).
Shimon Garti, "Dense free sets", Order 33 (2016), no. 3, 411-417. DOI: 10.1007/s11083-015-9375-7, https://doi.org/10.1007/s11083-015-9375-7 (preprint arXiv:1509.05132, https://arxiv.org/abs/1509.05132).