Free sets for set mappings: the open boundary cases of the Erdős–Hajnal free-set problems of 1958

A set mapping is a function $f$ that assigns to certain subsets $X$ of a ground set $S$ a value $f(X)$ disjoint from $X$, and a subset of $S$ is free for $f$ if it avoids the values assigned to its own applicable subsets. In their 1958 paper 'On the structure of set-mappings', Erdős and Hajnal asked how large a free set every set mapping of a given type (arity of the domain) and order (bound on the size of the values) must admit on an $m$-element ground set — the partition-style relation $(m,n,t)\rightarrow p$ — and proved sharp results in ZFC for finite orders, under the generalized continuum hypothesis at regular-cardinal thresholds, and under a measurable-cardinal hypothesis at inaccessibles, leaving explicit problems at the boundaries. Hajnal settled type 1 in ZFC in 1961. Hajnal–Máté (1975), Komjáth (1991, 1994) and Komjáth–Shelah (1994, 2000) showed by forcing that for mappings of types 2–4 the guaranteed free-set sizes need not be absolute — their counterexamples have infinite order or kill all uncountable free sets — though all of them live strictly below the cardinal thresholds that Erdős and Hajnal left open. Gillibert (2008) and Gillibert–Wehrung (2011) proved that type-4 mappings at $\mu^{+4}$ always have a free set of size 6, with size 7 open. On the finite side, Spencer (1972), Füredi (1991) and Conlon–Fox–Sudakov (2016) determined the extremal parameter $p_{k,\ell}(N)$ up to a logarithmic factor that remains open for small $\ell$; Caro–Patkós–Tuza–Vizer (2024) and Gishboliner–Jin–Sudakov (2026) generalized the finite problem to graphs. The original boundary questions — most prominently whether $(\aleph_\omega,2,\omega)\rightarrow\aleph_0$ (does every order-2 set mapping defined on all finite subsets of $\aleph_\omega$ have an infinite free set?), the largest $p$ with $(\aleph_{\alpha+k},\aleph_\alpha,k)\rightarrow p$ for $k\ge 3$, the small-value finite asymptotics, and the auxiliary selector question — remain open.

Background

Fix an infinite ground set $S$ and a cardinal $t$. A set mapping of type $t$ is a function $f:[S]^t\rightarrow\mathcal{P}(S)$, where $[S]^t$ is the family of $t$-element subsets of $S$ and $\mathcal{P}(S)$ is the power set, such that $f(X)\cap X=\emptyset$ for every $X\in[S]^t$ (a value never meets its own argument). The mapping has order $n$ if $|f(X)|<n$ for all $X$; 'type $\omega$' abbreviates type $<\aleph_0$, meaning the domain is the family $[S]^{<\omega}$ of all finite subsets. A set $S'\subseteq S$ is free (for $f$) if $f(X)\cap S'=\emptyset$ for every applicable $X\subseteq S'$ with $X\in[S]^t$. Following Erdős and Hajnal, the arrow $(m,n,t)\rightarrow p$ expresses that every order-$n$ set mapping of type $t$ on a set of size $m$ has a free set of size at least $p$; the free-set problem is to determine, for each triple $(m,n,t)$, the largest such $p$. (The later notation of Gillibert and Wehrung, $(\lambda,k,\mu)\rightarrow\rho$, places the arity in the middle and the value bound last — the middle and last entries are reversed relative to the 1958 convention used throughout this record.)

The starting point is the theorem of Kuratowski and Sierpiński: for finite $k$, a set mapping $f:[S]^k\rightarrow\mathcal{P}(S)$ with $|f(X)|<\mu$ on a ground set of size at least $\mu^{+k}$ (the $k$-th successor cardinal of $\mu$, obtained by iterating $k$ times the operation of passing to the least cardinal strictly above) has a free set of size $k+1$, and below $\mu^{+k}$ it need not; the question is therefore how much larger than $k+1$ a free set can be forced above the threshold.

The source of this problem is the 1958 paper of Erdős and Hajnal, which created this field. Writing $\aleph_\alpha$ for the $\alpha$-th infinite cardinal and $\aleph_\omega=\sup_n\aleph_n$ (the first singular cardinal — unlike a regular cardinal, which is not the union of fewer smaller sets, it is the supremum of the countable sequence $\aleph_0,\aleph_1,\aleph_2,\dots$, so its cofinality, the least size of an unbounded subset, is $\omega$), and using GCH — the generalized continuum hypothesis, $2^{\aleph_\alpha}=\aleph_{\alpha+1}$ for every $\alpha$ — the paper proved: (a) in ZFC — the standard Zermelo–Fraenkel axioms of set theory with the axiom of choice — every set mapping of finite type $k$ and finite order $\ell+1$ on any infinite set has an infinite free set, that is, $(m,\ell+1,k)\rightarrow\aleph_0$; (b) in ZFC, $(m,2,\omega)\nrightarrow\aleph_0$ for every infinite $m<\aleph_\omega$, that is, below $\aleph_\omega$ there is a set mapping defined on all finite subsets, with values of size at most 1, having no infinite free set; (c) under GCH, $(\aleph_{\alpha+k},\aleph_\alpha,k)\rightarrow\aleph_{\alpha+1}$, and this is sharp at the top in that $(\aleph_{\alpha+k},\aleph_\alpha,k)\nrightarrow\aleph_{\alpha+k}$ for $k\ge 2$; (d) under hypothesis (**) — the existence, on a strongly inaccessible cardinal $\aleph_\alpha$ (an uncountable regular cardinal strictly larger than $2^m$ for every smaller cardinal $m$), of a two-valued $\aleph_\alpha$-additive measure (a function on the subsets of the ground set taking only the values 0 and 1, additive under unions of fewer than $\aleph_\alpha$ summands) that vanishes on singletons (equivalently, measurability of $\aleph_\alpha$) — even type-$\omega$ mappings of order $\aleph_\beta$ ($\beta<\alpha$) have free sets of size $\aleph_\alpha$; and (e) for a finite ground set of size $m$, order-of-magnitude bounds $c_1m^{1/(k+1)}<p(m,\ell,k)<c_2(m\log m)^{1/k}$ for the largest integer $p$ such that every type-$k$ mapping with $|f(X)|\le\ell$ on an $m$-element set has a free set of size $p$.

The paper closes with five numbered problems at the boundaries of these results, together with an unnumbered remark questioning whether the theorems proved from (**) are equivalent to that hypothesis. The later literature built an extensive landscape around them: Hajnal settled the type-1 case in ZFC (1961); Hajnal and Máté (1975) proved that above the Kuratowski–Sierpiński threshold, mappings of types 2 and 3 have arbitrarily large finite free sets in ZFC, and posed further questions; Komjáth (1991, 1994) and Komjáth–Shelah (1994, 2000) then showed by forcing — Cohen's technique for building a model of set theory in which a chosen statement fails — that several of the expected positive statements are independent of ZFC (neither provable nor refutable there), and that for type 4 only finite free sets can be guaranteed in suitable models; Gillibert (2008) and Gillibert–Wehrung (2011) pushed the type-4 guaranteed size from 5 to 6; and the finite combinatorial problem was developed by Spencer, Füredi, Conlon–Fox–Sudakov and, most recently, by Caro–Patkós–Tuza–Vizer and Gishboliner–Jin–Sudakov for general graphs. None of these works touches the boundary cells stated below.

Problem Statement

Determine the free-set relations for set mappings left open by Erdős and Hajnal (1958), in the arrow notation $(m,n,t)\rightarrow p$ (ground-set size $m$, order $n$ = bound on $|f(X)|$, type $t$ = arity of the domain, $p$ = guaranteed free-set size) defined in the background:

(1) The singular-cardinal boundary for type-$\omega$ mappings of order 2. Is $(\aleph_\omega,2,\omega)\rightarrow\aleph_0$? Equivalently: does every function $f:[\aleph_\omega]^{<\omega}\rightarrow\mathcal{P}(\aleph_\omega)$ with $f(X)\cap X=\emptyset$ and $|f(X)|\le 1$ for every finite $X$ admit an infinite free set, that is, an infinite $Y\subseteq\aleph_\omega$ with $f(X)\cap Y=\emptyset$ for every finite $X\subseteq Y$? The source paper constructs such mappings with no infinite free set on every ground set of cardinality $m<\aleph_\omega$, and the case $m=\aleph_\omega$ is open (in ZFC; also open is whether the answer is model-dependent).

(2) The largest guaranteed free set above the Kuratowski–Sierpiński threshold for types $k\ge 3$. For fixed finite $k\ge 3$ and ordinals $\alpha$, determine the largest cardinal $p$ such that $(\aleph_{\alpha+k},\aleph_\alpha,k)\rightarrow p$, that is, the largest free set forced for type-$k$ set mappings of order $\aleph_\alpha$ on $\aleph_{\alpha+k}$. Under GCH the truth lies between $\aleph_{\alpha+1}$ (true, source paper) and $\aleph_{\alpha+k}$ (false, source paper); the prototype instance is the paper's Problem 2: is $(\aleph_3,\aleph_0,3)\rightarrow\aleph_2$? (the paper notes that $(\aleph_3,\aleph_0,3)\rightarrow\aleph_1$ is true and $(\aleph_3,\aleph_0,3)\rightarrow\aleph_3$ is false). The companion finite-order question is the paper's Problem 3: is $(\aleph_2,2,3)\rightarrow\aleph_1$? (the paper notes that $(\aleph_2,2,3)\rightarrow\aleph_0$ is true in ZFC by its finite-order theorem and that $(\aleph_2,2,3)\rightarrow\aleph_2$ is false; its explicitly GCH-marked negatives are $(\aleph_{\alpha+k},\aleph_\alpha,k)\nrightarrow\aleph_{\alpha+k}$ for $k\ge 2$ and the type-2 analogue $(\aleph_{\alpha+1},2,2)\nrightarrow\aleph_{\alpha+1}$.) The paper's Problems 2 and 3 bear on this cell: Problem 2 is the case $k=3$, $\alpha=0$ of the general determination, while Problem 3 is an independent finite-order case.

(3) The exact order of magnitude of the finite parameter $p(m,\ell,k)$ — the largest $p$ such that every type-$k$ mapping with $|f(X)|\le\ell$ on an $m$-element set has a free set of size $p$, written $p_{k,\ell}(N)$ with $N=m$ in the modern literature — in the range not settled by later work: for $1\le\ell<(k-1)!$ with $k\ge 3$, close the gap between the known bounds $\Omega(N^{1/k})$ and $O((N\log N)^{1/k})$ — in particular, decide whether $p_{k,\ell}(N)=\Theta(N^{1/k})$ there, as it is now known to be for $\ell\ge(k-1)!$.

(4) The auxiliary selector question stated in the source paper (its Problem 5). The paper's negative examples are built from a selector $g$ defined on $[S]^t$ satisfying the numbered conditions of its Lemma 1 and the following remark: (1) $g(X)\subsetneq X$; (2) $|g(X)|=t$ for every $X\in[S]^t$; (3) $g(X)\neq g(Y)$ if $X\neq Y$; and (4) for every $Y\in[S]^t$ there is an $X\in[S]^t$ with $Y=g(X)$. The question is: for $|S|>t\ge\aleph_0$, does there exist a function $g_2$ defined on $[S]^t$ satisfying conditions (2), (3), (4) together with the strengthened condition (1'): $g_2(X)\subseteq X$ and $|X\setminus g_2(X)|=t$ for all $X$ — a selector that discards a full $t$-sized piece of each $X$ rather than fewer than $t$ elements?

(5) The logical strength of the results proved from hypothesis () (a two-valued $m$-additive measure on a strongly inaccessible cardinal, i.e. measurability): are those free-set theorems equivalent to ()? The paper poses this as an unnumbered remark in its definitions section — 'In the present paper we do not investigate the problem, if these theorems are equivalent to the above hypothesis' — not as one of its five numbered problems; asking whether the theorems follow from strictly weaker assumptions only spells out what a negative answer to the equivalence question would mean.

The objective is to complete the free-set calculus for set mappings at the cells the 1958 paper left open.

References

1. P. Erdős and A. Hajnal, On the structure of set-mappings, Acta Mathematica Academiae Scientiarum Hungaricae 9 (1958) 111–131, doi:10.1007/bf02023868, https://doi.org/10.1007/bf02023868
2. P. Erdős and A. Hajnal, Some remarks concerning our paper 'On the structure of set-mappings' — Non-existence of a two-valued σ-measure for the first uncountable inaccessible cardinal, Acta Mathematica Academiae Scientiarum Hungaricae 13 (1962) 223–226, doi:10.1007/BF02033641, https://doi.org/10.1007/BF02033641
3. A. Hajnal, Proof of a conjecture of B. Ruziewicz, Fundamenta Mathematicae 50 (1961) 123–128, doi:10.4064/fm-50-2-123-128, https://doi.org/10.4064/fm-50-2-123-128
4. A. Hajnal and A. Máté, Set mappings, partitions, and chromatic numbers, in: Logic Colloquium '73 (Bristol, 1973), H. E. Rose and J. C. Shepherdson (eds.), Studies in Logic and the Foundations of Mathematics 80, North-Holland, Amsterdam, 1975, pp. 347–379
5. P. Erdős, A. Hajnal, A. Máté and R. Rado, Combinatorial set theory: Partition relations for cardinals, Studies in Logic and the Foundations of Mathematics 106, North-Holland/Elsevier, Amsterdam, 1984, doi:10.1016/S0049-237X(08)x7083-1, https://doi.org/10.1016/S0049-237X(08)x7083-1
6. J. Spencer, Turán's theorem for k-graphs, Discrete Mathematics 2 (1972) 183–186, doi:10.1016/0012-365x(72)90084-2, https://doi.org/10.1016/0012-365x(72)90084-2
7. Z. Füredi, Maximal independent subsets in Steiner systems and in planar sets, SIAM Journal on Discrete Mathematics 4 (1991) 196–199, doi:10.1137/0404019, https://doi.org/10.1137/0404019
8. D. Conlon, J. Fox and B. Sudakov, Short proofs of some extremal results II, Journal of Combinatorial Theory, Series B 121 (2016) 173–196, doi:10.1016/j.jctb.2016.03.005, https://doi.org/10.1016/j.jctb.2016.03.005
9. P. Komjáth, A set mapping with no infinite free subsets, Journal of Symbolic Logic 56 (1991) 1400–1402, doi:10.2307/2275484, https://doi.org/10.2307/2275484
10. P. Komjáth, A consistency result concerning set mappings, Acta Mathematica Hungarica 64 (1994) 93–99, doi:10.1007/BF01873973, https://doi.org/10.1007/BF01873973
11. P. Komjáth and S. Shelah, A note on a set-mapping problem of Hajnal and Máté, Periodica Mathematica Hungarica 28 (1994) 39–42, doi:10.1007/bf01876368, https://doi.org/10.1007/bf01876368
12. P. Komjáth and S. Shelah, Two consistency results on set mappings, Journal of Symbolic Logic 65 (2000) 333–338, doi:10.2307/2586540, https://doi.org/10.2307/2586540; preprint at https://arxiv.org/abs/math/9807182, filed under the variant title 'Consistency of the existence of a 4-place function on aleph_2 with no independent subset of size k_n' with unaccented author names 'Peter Komjath, Saharon Shelah'
13. S. Mohsenipour and S. Shelah, Set mappings on 4-tuples, Notre Dame Journal of Formal Logic 59 (2018), no. 3, 405–416, doi:10.1215/00294527-2018-0002, https://doi.org/10.1215/00294527-2018-0002; preprint at https://arxiv.org/abs/1510.02216
14. P. Gillibert and F. Wehrung, An infinite combinatorial statement with a poset parameter, Combinatorica 31 (2011) 183–200, doi:10.1007/s00493-011-2602-y, https://doi.org/10.1007/s00493-011-2602-y
15. A. Avilés and C. Piña, Free sets for set-mappings relative to a family of sets, Mathematical Logic Quarterly 63 (2017) 605–613, doi:10.1002/malq.201600100, https://doi.org/10.1002/malq.201600100; preprint at https://arxiv.org/abs/1607.03291, filed under the variant title 'Free sets for a set-mapping relative to a family of sets'
16. P. Komjáth, Set mappings with free sets which are arithmetic progressions, Mathematika 64 (2018) 71–76, doi:10.1112/S0025579317000353, https://doi.org/10.1112/S0025579317000353
17. P. Komjáth, A note on set mappings: an extension of results of Hajnal and Máté under GCH, Fundamenta Mathematicae 246 (2019) 1–7, doi:10.4064/fm638-9-2018, https://doi.org/10.4064/fm638-9-2018
18. Y. Caro, B. Patkós, Z. Tuza and M. Vizer, Edge mappings of graphs: Turán type parameters, arXiv:2402.01006, https://arxiv.org/abs/2402.01006; published as European Journal of Combinatorics 127 (2025) 104140, doi:10.1016/j.ejc.2025.104140, https://doi.org/10.1016/j.ejc.2025.104140
19. L. Gishboliner, Z. Jin and B. Sudakov, Set mappings for general graphs, arXiv:2601.00766, https://arxiv.org/abs/2601.00766