Erdős Problem #1022 — Sparse set systems with property B
For each positive integer , is there a real constant , with as , such that the following implication holds? Let be a finite family of finite sets, each of size at least , and let . Suppose that for every nonempty subset ,
Must the elements of be assigned two colors so that every member contains vertices of both colors—that is, must have property B (equivalently, chromatic number 2)? The nonempty restriction on avoids the impossible inequality at ; restricting to subsets of does not change the condition. Erdős Problem #1022
Background
Erdős posed the problem in his 1971 collection of unsolved problems. The problem account reports that he initially conjectured the special case and said Lovász had proved it. The account also notes that the cited 1968 Lovász paper does not contain that result, so the attribution is best understood as a report by Erdős rather than as a result verified by that citation. Erdős Problem #1022 Erdős (1971) Lovász (1968)
The hypothesis is an edge-count condition: it bounds the number of members of the family lying wholly inside each vertex set. It is related to degeneracy, which requires every subhypergraph to have a vertex contained in at most a prescribed number of edges. Repeatedly removing such a vertex gives an ordering in which each edge can be counted at its first removed vertex, yielding a linear bound on the number of edges inside any vertex set. Erdős Problem #1022 Hypergraph Colouring and Degeneracy
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.