← All problems

Erdős Problem #901 — Minimum edges in hypergraphs without Property B

65 years old · traced to

For an integer n≥2n\ge 2, let H=(V,E)H=(V,E) be a finite nn-uniform hypergraph: VV is a finite set and E⊆{A⊆V:∣A∣=n}E\subseteq\{A\subseteq V:|A|=n\}. A coloring of VV is proper if no edge is monochromatic, and the chromatic number is the least number of colors in a proper coloring. Define

m(n)=min⁡{∣E∣:H=(V,E) is finite and has chromatic number 3}.m(n)=\min\bigl\{|E|: H=(V,E)\text{ is finite and has chromatic number }3\bigr\}.

Thus the minimizing hypergraph must admit a proper 3-coloring but no proper 2-coloring. The question is to estimate m(n)m(n) as n→∞n\to\infty. 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 nn-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 m(n)m(n) might have order n2nn2^n. 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 2n2^n; 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

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.