Open threads from Erdős–Hajnal–Milner's almost-disjoint transversal theory: the $\mathscr S \Rightarrow \mathscr H$ converse, necessity at inaccessible cardinals, and removal of cardinal-arithmetic hypotheses

Erdős–Hajnal–Milner's 1968 Acta Mathematica Hungarica paper 'On sets of almost disjoint subsets of a set' (DOI 10.1007/BF01894696) founded the theory of pairwise almost-disjoint transversals of disjoint set systems. The paper leaves three threads open: (1) the paper derives, from the transversal hypothesis $\mathscr H$ (existence of $\aleph_2$ pairwise almost-disjoint transversals of $\aleph_1$ disjoint countable sets, equivalently $\aleph_2$ functions $\omega_1\to\omega$ pairwise agreeing on fewer than $\aleph_1$ coordinates — the functional form of the weak Kurepa hypothesis at $\omega_1$), a partition statement $\mathscr S$ (a partition of the pairs of an $\aleph_2$-sized set into $\aleph_1$ parts such that every $\aleph_1$-sized subfamily meets $\aleph_1$ parts, i.e. the negative square-bracket relation $\aleph_2\not\to[\aleph_1]^2_{\aleph_1}$); whether $\mathscr S$ conversely implies $\mathscr H$ is not known. (2) The paper's stationary-set criterion for the size of almost-disjoint-transversal families has its sufficiency direction — non-stationarity of the relevant index set yields $\mathfrak m^+$ pairwise almost-disjoint transversals — proved in ZFC for every limit cardinal $\mathfrak m$ not cofinal with $\aleph_0$, hence including inaccessible cardinals, while the necessity direction (stationarity forces every such family to have size at most $\mathfrak m$) is proved only for singular $\mathfrak m$ of uncountable cofinality under a cardinal-arithmetic hypothesis; the paper explicitly asks whether a similar necessity result holds for inaccessible cardinals, and this remains open. (3) Several of its non-maximality and Cater-generalization theorems are proved only under cardinal-arithmetic hypotheses such as $2^{\mathfrak n}<\mathfrak m$, $\mathfrak n^{\mathfrak m'}<\mathfrak m^+$, $2^{\mathfrak m}=\mathfrak m^+$, and $\mathfrak n^{\mathfrak m'}<\mathfrak m$, and their ZFC status is unknown.

Background

Two sets are almost disjoint if the cardinality of their intersection is strictly smaller than that of either set. Given a family of pairwise disjoint nonempty sets $(A_v)$, a transversal is a set $B$ contained in the union that meets each $A_v$ in exactly one element, and two transversals of the same system are almost disjoint when their intersection has cardinality below the common size of the transversals themselves (every transversal of a system of $\mathfrak m$ disjoint sets has size $\mathfrak m$, so there this means $|B\cap B'|<\mathfrak m$). Sierpiński had shown, as recounted at the outset of this theory, that $\mathfrak m$ disjoint sets each of size $\mathfrak m$ possess more than $\mathfrak m$ pairwise almost-disjoint transversals; Milner's contemporary paper 'Transversals of disjoint sets' (1968) poses the general question of how many pairwise almost-disjoint transversals a system of disjoint sets admits; and Erdős, Hajnal, and Milner (1968) launched the systematic theory: they proved, for example, that $\aleph_{\alpha+1}$ disjoint sets of power $\aleph_\alpha$ possess a maximal family of $\aleph_{\alpha+1}$ pairwise almost-disjoint transversals, and studied when such a family is not maximal. The hypothesis they call $\mathscr H$ is the existence of $\aleph_2$ pairwise almost-disjoint transversals of $\aleph_1$ pairwise disjoint countably infinite sets; identifying the $v$-th countable block $A_v=\{v\}\times\omega$, each transversal is the graph of a function $\omega_1\to\omega$, and pairwise almost disjointness says that any two of the $\aleph_2$ functions agree on fewer than $\aleph_1$ coordinates. This is exactly the weak Kurepa hypothesis for $\kappa=\omega_1$ in the functional form studied by Kanamori (1986) and Walker (1988): there is a family $\{f_\alpha: \alpha<\kappa^+\}\subseteq\,^{\kappa}(\kappa^-)$ (functions from $\kappa$ to the smaller cardinal $\kappa^-$) with $|\{\xi<\kappa: f_\alpha(\xi)=f_\beta(\xi)\}|<\kappa$ for $\alpha<\beta<\kappa^+$; it is a weak relative of the Kurepa hypothesis, which asserts, at a cardinal $\lambda$, a family of more than $\lambda$ subsets of $\lambda$ whose traces on every smaller infinite subset have size at most that subset. From $\mathscr H$, Erdős–Hajnal–Milner derive a partition statement $\mathscr S$: there exists a partition of the pairs of an $\aleph_2$-sized set into $\aleph_1$ parts such that every $\aleph_1$-sized subfamily has its pairs in $\aleph_1$ distinct parts — a statement that had been asked separately in the partition calculus. In the standard notation this is the negative two-cardinal square-bracket relation $\aleph_2\not\to[\aleph_1]^2_{\aleph_1}$: a coloring of the two-element subsets of $\aleph_2$ with $\aleph_1$ colors such that every $\aleph_1$-sized subfamily realizes all $\aleph_1$ colors. The one-cardinal-level analogue $\aleph_1\not\to[\aleph_1]^2_{\aleph_1}$ was proved outright in ZFC by Todorcevic (1987) using the method of walks on ordinals (a recursive descent from one ordinal to another through a fixed sequence of closed unbounded subsets); his extensions to larger cardinals require additional principles such as non-reflecting stationary sets (stationary sets whose restriction below any smaller ordinal of uncountable cofinality is non-stationary there) or square sequences (coherent systems of closed unbounded subsets), so that literature does not settle the ZFC status of the two-cardinal statement $\mathscr S$ itself. The paper also develops a criterion via stationary sets of indices (a set of ordinals is stationary in $\lambda$ if it meets every closed unbounded subset of $\lambda$): in ZFC, for every limit cardinal $\mathfrak m$ not cofinal with $\aleph_0$ — a class that includes the inaccessible cardinals — non-stationarity of the relevant index set yields a family of $\mathfrak m^+$ pairwise almost-disjoint transversals, while, at singular $\mathfrak m>\mathrm{cf}(\mathfrak m)>\aleph_0$ and under the cardinal-arithmetic hypothesis $\mathfrak n^{\mathfrak m'}<\mathfrak m^+$ for all $\mathfrak n<\mathfrak m$, stationarity of that index set conversely forces every such family to have size at most $\mathfrak m$; the paper explicitly notes that it does not know whether a similar necessity result holds for inaccessible cardinals. Komjáth–Milner (1987) apply this criterion at cardinals $\lambda>\mathrm{cf}(\lambda)>\omega$, and Golshani (2019) quotes it verbatim in the equivalent language of the generalized Kurepa hypothesis $KH_\lambda$ at singular $\lambda$ of uncountable cofinality. Finally, several of the paper's non-maximality theorems, and its generalization of a transversal problem posed by F. S. Cater (Problem 5370, with E. C. Milner, 1967), are proved under cardinal-arithmetic hypotheses — assumptions on exponentiation such as $2^{\mathfrak n}<\mathfrak m$ for all $\mathfrak n<\mathfrak m$ (that is, $\mathfrak m$ is a strong limit), $\mathfrak n^{\mathfrak m'}<\mathfrak m^+$, $2^{\mathfrak m}=\mathfrak m^+$, or $\mathfrak n^{\mathfrak m'}<\mathfrak m$, where $\mathfrak m'$ denotes the cofinality of $\mathfrak m$ and $\mathfrak n$ ranges over cardinals below $\mathfrak m$ — which behave differently in different models of set theory, and the paper's criteria do not unify into a single statement covering all cardinals.

Problem Statement

The Erdős–Hajnal–Milner theory of pairwise almost-disjoint transversals leaves three threads open.

Thread 1 (converse). Let $\mathscr H$ be the statement that there exist $\aleph_2$ pairwise almost-disjoint transversals of a system of $\aleph_1$ pairwise disjoint countably infinite sets; equivalently, that there exist $\aleph_2$ functions $\omega_1\to\omega$, any two of which agree on fewer than $\aleph_1$ coordinates (the functional weak Kurepa hypothesis at $\omega_1$). Let $\mathscr S$ be the statement that there exists a partition of the pairs of an $\aleph_2$-sized set into $\aleph_1$ parts such that every $\aleph_1$-sized subfamily has its pairs in $\aleph_1$ distinct parts (the negative square-bracket relation $\aleph_2\not\to[\aleph_1]^2_{\aleph_1}$), a statement that had been asked separately in the partition calculus. Erdős–Hajnal–Milner proved that $\mathscr H$ implies $\mathscr S$. It is not known whether $\mathscr S$ conversely implies $\mathscr H$ — that is, whether this derivation of a two-cardinal negative square-bracket partition relation from a weak-Kurepa-type function family loses strength. Determine whether $\mathscr S$ conversely implies $\mathscr H$. The one-cardinal analogue $\aleph_1\not\to[\aleph_1]^2_{\aleph_1}$ is a theorem of ZFC (Todorcevic 1987), but the ZFC status of $\mathscr S$ itself is open: neither a ZFC proof of $\mathscr S$ nor a separation of $\mathscr S$ from $\mathscr H$ is known.

Thread 2 (necessity at inaccessible cardinals). In the paper's setting, let $\mathfrak m$ be a limit cardinal with cofinality $\mathfrak m'$, let $\lambda=\omega(\mathfrak m')$ be the smallest ordinal of cardinality $\mathfrak m'$, and let $(A_\nu)_{\nu<\lambda}$ be $\mathfrak m'$ pairwise disjoint sets with $0<|A_0|\le|A_1|\le\cdots$ and $\lim_{\nu<\lambda}|A_\nu|=\mathfrak m$; fix a closed increasing enumeration $(\mathfrak m_\nu)_{\nu<\lambda}$ of cardinals cofinal in $\mathfrak m$ and write $C=\{\nu<\lambda:|A_\nu|\le\mathfrak m_\nu\}$ for the associated index set. The paper proves in ZFC (Theorem 5) that if $\mathfrak m$ is not cofinal with $\aleph_0$ — a class that includes the inaccessible cardinals (uncountable regular limit cardinals) — and $C$ is non-stationary in $\lambda$, then there are $\mathfrak m^+$ pairwise almost-disjoint transversals of the $A_\nu$; and it proves (Theorem 6) that if $\mathfrak m>\mathfrak m'>\aleph_0$ is singular, $\mathfrak n^{\mathfrak m'}<\mathfrak m^+$ for all $\mathfrak n<\mathfrak m$, and $C$ is stationary, then every family of pairwise almost-disjoint transversals of the $A_\nu$ has size at most $\mathfrak m$. Immediately after Theorem 6 the paper asks: 'We do not know if a similar result holds for inaccessible cardinals.' Determine whether this necessity result holds when $\mathfrak m$ is inaccessible: does stationarity of $C$ — alone, or under an appropriate cardinal-arithmetic hypothesis — force every family of pairwise almost-disjoint transversals to have size at most $\mathfrak m$, or can this be refuted?

Thread 3 (removal of cardinal-arithmetic hypotheses). Four of the paper's theorems are proved under cardinal-arithmetic hypotheses, and the paper explicitly notes that its proofs need them:

• Theorem 4: suppose $\mathrm{cf}(\mathfrak m)=\mathfrak m'=\aleph_0$ and $2^{\mathfrak n}<\mathfrak m$ for all $\mathfrak n<\mathfrak m$ (hypothesis (4)). Then any family of $\mathfrak m$ pairwise almost-disjoint transversals of $\omega$ disjoint sets $A_\nu$ ($\nu<\omega$) with $0<|A_0|\le|A_1|\le\cdots$ and $\lim_{\nu<\omega}|A_\nu|=\mathfrak m$ is non-maximal, i.e. some further transversal is almost disjoint from every member of the family. The paper states: 'We cannot prove Theorem 4 without the hypothesis (4).'
• Theorem 6: under the hypotheses of Thread 2 with $\mathfrak m$ singular and $\mathfrak n^{\mathfrak m'}<\mathfrak m^+$ for all $\mathfrak n<\mathfrak m$ (hypothesis (6)), stationarity of $C$ forces every family of pairwise almost-disjoint transversals to have size at most $\mathfrak m$.
• Theorem 7: suppose $\mathfrak m$ is infinite and $\mathfrak n^{\mathfrak m'}<\mathfrak m$ for all $\mathfrak n$ with $\mathfrak m'<\mathfrak n<\mathfrak m$ (hypothesis (11), vacuous when $\mathfrak m$ is regular). Then any family of $\mathfrak m$ pairwise almost-disjoint weak transversals of $\mathfrak m'$ disjoint sets is non-maximal, where a weak transversal meets each set in at most one element and has size $\mathfrak m$.
• Theorem 8 (the Cater generalization): assuming $2^{\mathfrak m}=\mathfrak m^+$ and $\mathfrak n^{\mathfrak m'}<\mathfrak m^+$ for $\mathfrak m'<\mathfrak n<\mathfrak m$, Cater's statement holds for arbitrary $\mathfrak m\ge\aleph_0$, with its condition (9) replaced by the stronger condition (10): if $|S|=\mathfrak m$, there is a family of more than $\mathfrak m$ pairwise almost-disjoint subsets of $S$ of power $\mathfrak m$ such that every subfamily of size $\mathfrak m$ has some member of the family, outside the subfamily, contained in the union of the subfamily. The paper states: 'We cannot prove this result without the g.c.h. even in the case of regular $\mathfrak m$.'

Determine which of these four theorems hold in ZFC without the stated cardinal-arithmetic hypotheses. The remark that no unified criterion covering all cardinals is given is a program-level remark; the open content is the three threads above. The three threads are independent: none of them implies another.

References

1. F. S. Cater, E. C. Milner (1967), 'Problem 5370', The American Mathematical Monthly 74(4), 447. DOI: 10.2307/2314598. URL: https://doi.org/10.2307/2314598
2. E. C. Milner (1968), 'Transversals of Disjoint Sets', Journal of the London Mathematical Society s1-43, 495–500. DOI: 10.1112/jlms/s1-43.1.495. URL: https://doi.org/10.1112/jlms/s1-43.1.495
3. P. Erdős, A. Hajnal, E. C. Milner (1968), 'On sets of almost disjoint subsets of a set', Acta Mathematica Academiae Scientiarum Hungaricae 19, 209–218. DOI: 10.1007/BF01894696. URL: https://doi.org/10.1007/BF01894696
4. P. Erdős, A. Hajnal (1971), 'Unsolved problems in set theory', in Axiomatic Set Theory, Proc. Sympos. Pure Math. XIII, Part I, American Mathematical Society, 17–48. zbMATH: Zbl 0228.04001. URL: https://zbmath.org/3361883
5. A. Kanamori (1986), 'Partition relations for successor cardinals', Advances in Mathematics 59, 152–169. DOI: 10.1016/0001-8708(86)90049-6. URL: https://doi.org/10.1016/0001-8708(86)90049-6
6. P. Komjáth, E. C. Milner (1987), 'On representing sets of an almost disjoint family of sets', Mathematical Proceedings of the Cambridge Philosophical Society 101, 385–393. DOI: 10.1017/S0305004100066779. URL: https://doi.org/10.1017/S0305004100066779
7. S. Todorcevic (1987), 'Partitioning pairs of countable ordinals', Acta Mathematica 159, 261–294. DOI: 10.1007/BF02392561. URL: https://doi.org/10.1007/BF02392561
8. D. J. Walker (1988), 'On the transversal hypothesis and the weak Kurepa hypothesis', Journal of Symbolic Logic 53(3), 854–877. DOI: 10.2307/2274577. URL: https://doi.org/10.2307/2274577
9. P. Szeptycki (2007), 'Transversals for strongly almost disjoint families', Proceedings of the American Mathematical Society 135(7), 2273–2282. DOI: 10.1090/S0002-9939-07-08714-X. URL: https://doi.org/10.1090/S0002-9939-07-08714-X
10. M. Kojman (2016), 'On the arithmetic of density', Topology and its Applications 213, 145–153. DOI: 10.1016/j.topol.2016.08.016. URL: https://doi.org/10.1016/j.topol.2016.08.016
11. M. Golshani (2019), 'The generalized Kurepa hypothesis at singular cardinals', Periodica Mathematica Hungarica 78(2), 200–202 (published online 2018). DOI: 10.1007/s10998-018-0267-7. URL: https://doi.org/10.1007/s10998-018-0267-7
12. R. Mohammadpour (2024), 'Martin's Axiom and Weak Kurepa Hypothesis', arXiv:2411.04835. URL: https://arxiv.org/abs/2411.04835
13. J. Krueger, S. Stejskalová (2025), 'A Strongly Non-Saturated Aronszajn Tree Without Weak Kurepa Trees', arXiv:2506.06878. URL: https://arxiv.org/abs/2506.06878