← All problems

Erdős Problem #1022 — Sparse set systems with property B

55 years old · traced to

For each positive integer tt, is there a real constant ctc_t, with ct→∞c_t\to\infty as t→∞t\to\infty, such that the following implication holds? Let F\mathcal F be a finite family of finite sets, each of size at least tt, and let V=⋃A∈FAV=\bigcup_{A\in\mathcal F}A. Suppose that for every nonempty subset X⊆VX\subseteq V,

∣{A∈F:A⊆X}∣<ct∣X∣.\bigl|\{A\in\mathcal F:A\subseteq X\}\bigr|<c_t|X|.

Must the elements of VV be assigned two colors so that every member A∈FA\in\mathcal F contains vertices of both colors—that is, must F\mathcal F have property B (equivalently, chromatic number 2)? The nonempty restriction on XX avoids the impossible inequality 0<00<0 at X=∅X=\varnothing; restricting to subsets of VV 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 c2=1c_2=1 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

Progress summary

Never refreshed

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.