The minimum-size conjecture for minimal uncolorable uniform bi-hypergraphs

From papers

Let m(r)m(r) be the smallest positive integer for which there exists a minimal uncolorable rr-uniform bi-hypergraph with m(r)m(r) edges. Complete rr-uniform bi-hypergraphs on (r1)2+1(r-1)^2+1 vertices have ((r1)2+1r)\binom{(r-1)^2+1}{r} edges.

Minimum-size conjecture. For any rNr\in \mathbb{N} with r4r\ge 4,

m(r)=((r1)2+1r).m(r)=\binom{(r-1)^2+1}{r}.

The conjecture predicts that the complete construction gives the smallest possible minimal uncolorable rr-uniform bi-hypergraph for every r4r\ge 4. For r=4r=4, the source reduces this to proving colorability of every 44-uniform bi-hypergraph of order at most 4949 and size at most 209209; the general conjecture remains unresolved in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Meiqiao Zhang, Fengming Dong and Ruixue Zhang, “On the colorability of bi-hypergraphs”, arXiv:2310.06464 (2023).

Solutions 0

No solutions have been posted yet.