Problem 1025

Let $f$ be a function from all pairs of elements in $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ such that $f(x,y)\neq x$ and $\neq y$ for all $x,y$ . We call $X\subseteq \{1,\ldots,n\}$ independent if whenever $x,y\in X$ we have $f(x,y)\not\in X$ .

Let $g(n)$ be such that, in every function $f$ , there is an independent set of size at least $g(n)$ . Estimate $g(n)$ .

Source: erdosproblems.com/1025

Combinatorics

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

The site labels the problem SOLVED (LEAN), the Lean qualification recorded in the community database since 2026-09-15, crediting Spencer [Sp72] with $g(n)\gg n^{1/2}$ and Conlon, Fox and Sudakov [CFS16] with $g(n)\ll n^{1/2}$ , so $g(n)\asymp n^{1/2}$ .

CFS16: Conlon, David and Fox, Jacob and Sudakov, Benny, Short proofs of some extremal results II. J. Combin. Theory Ser. B (2016), 173-196.
ErHa58: Erdős, P. and Hajnal, A., On the structure of set mappings. Acta Math. Acad. Sci. Hungar. 9 (1958), 111-131.
Fu91: Füredi, Z., Maximal independent subsets in Steiner systems and in planar sets. SIAM J. Discrete Math. 4 (1991), 196-199.
Sp72: Spencer, Joel, Turán's theorem for $k$ -graphs. Discrete Math. (1972), 183-186.

Problem 1025

Status

Proof claims

Discussion