---

Claim. $n^{1/3}\ll g(n)\ll(n\log n)^{1/2}$. Theorem 12 of Erdős and Hajnal [ErHa58] (pp. 129–131) concerns set-mappings of type $k$ and order $l+1$ on an $m$-set: each $k$-subset $X$ is sent to a set of fewer than $l+1$ points outside $X$, and a set $P$ is free when $f(X)$ misses $P$ for every $k$-subset $X$ of $P$. Writing $p(m,l,k)$ for the largest $p$ such that every such mapping has a free set of $p$ elements, the theorem states that

$$c_1\,m^{1/(k+1)}<p(m,l,k)<c_2\,(m\log m)^{1/k},$$

with $c_1,c_2>0$ depending only on $k$ and $l$. The lower bound comes from a counting argument and the upper bound from a uniformly random mapping. With $k=2$ and $l=1$ the mapping sends each pair to one point outside it and a free set is an independent set as [[problems/set_systems/E1025/_index|Problem 1025]] defines it, so $g(n)=p(n,1,2)$ and the theorem gives $n^{1/3}\ll g(n)\ll(n\log n)^{1/2}$. The paper asks for the exact order of $p(m,l,k)$ as its Problem 4, which is the question the site poses for $g(n)$. The paper is carded at On the structure of set-mappings.

Covers. The two bounds $g(n)\gg n^{1/3}$ and $g(n)\ll(n\log n)^{1/2}$, both superseded: the lower bound by Spencer's $g(n)\gg n^{1/2}$, and the upper bound by Füredi's and by Conlon, Fox and Sudakov's $g(n)\ll n^{1/2}$. The theorem does not determine the order of $g(n)$.

Depends on. No page of this wiki.

Acceptance. Refereed: P. Erdős and A. Hajnal, On the structure of set-mappings, Acta Math. Acad. Sci. Hungar. 9 (1958), no. 1–2, 111–131; the record dates the issue to March 1958 and gives no day, so the page is dated to the first day of that month. The site's label SOLVED (LEAN) rests on Spencer and on Conlon, Fox and Sudakov, so no reviewed is listed for these bounds. Nothing here rests on this project's own review.