Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 624

Statement. Let $X$ be a finite set of size $n$ and $H(n)$ be such that there is a function $f:\{A : A\subseteq X\}\to X$ so that for every $Y\subseteq X$ with $\lvert Y\rvert \geq H(n)$ we have

\{ f(A) : A\subseteq Y\}=X.

Prove that

H(n)-\log_2 n \to \infty.

Status. Open.

Source. erdosproblems.com/624, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #624, https://www.erdosproblems.com/624.

References.

[ErHa68] Erdős, P. and Hajnal, A., On a combinatorial problem. Mat. Lapok (1968), 345-348.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (10)

Set Systems, Designs and Hypergraphs Set Systems, Designs and Hypergraphs set_systems/erdos_1968_egy_kombinatorikus_problemarol Conjecture (p. 346; English summary p. 348): H(n) - log n/log 2 tends to infinity Theorem (Tétel, p. 345): log n/log 2 < H(n) < log n/log 2 + (3+ε) log log n/log 2 for n > n_0(ε)set_systems/kunen_2013_impact_paul_erdos_set_theory Free Set Lemma (Hajnal, p. 359): a set mapping into [λ]^{<κ} with κ < λ has a free set of size λ Theorem 6 of Erdős 1954 (p. 359): nowhere dense images give a free set of size ℵ_0, and size ℵ_1 is independent Theorem 3.8 of Erdős-Hajnal-Máté 1973 (p. 360): free sets for regular λ under Condition B on ran(g)set_theory/komjath_2025_erdos_hajnal_problem_list

Graph