Erdős Problem #901 — Minimum edges in hypergraphs without Property B
For an integer , let be a finite -uniform hypergraph: is a finite set and . A coloring of is proper if no edge is monochromatic, and the chromatic number is the least number of colors in a proper coloring. Define
Thus the minimizing hypergraph must admit a proper 3-coloring but no proper 2-coloring. The question is to estimate as . A hypergraph has Property B precisely when its vertices can be 2-colored properly: equivalently, there is a set meeting every edge whose complement also meets every edge. The problem is commonly phrased as finding the minimum number of edges in an -uniform hypergraph without Property B. Erdős Problem #901 Improved Lower Bounds for Property B
Background
Property B asks whether the vertices of a uniform hypergraph can be divided into two classes so that every edge meets both classes. Its failure is a basic obstruction to two-colorability, and the minimum number of edges needed to force that obstruction is the quantity under study. Erdős and Lovász highlighted the scale of the problem in 1975, speculating that might have order . Erdős and Lovász (1975)
Erdős established exponential-scale bounds in the 1960s. Beck’s work then showed that the minimum grows faster than ; successive lower-bound improvements culminated in the Radhakrishnan–Srinivasan bound. A useful idea in this line of work is to start with a random coloring and alter it to avoid monochromatic edges. Pluhár introduced a random-greedy coloring approach, later used by Cherkashin and Kozik in a simplified proof of the Radhakrishnan–Srinivasan result. Erdős (1963, 1964); Beck (1977, 1978); Pluhár (2009) Improved Lower Bounds for Property B
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.