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

At least 2 years old · documented by

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 (r−1)2+1(r-1)^2+1 vertices have ((r−1)2+1r)\binom{(r-1)^2+1}{r} edges.

Minimum-size conjecture. For any r∈Nr\in \mathbb{N} with r≥4r\ge 4,

m(r)=((r−1)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 r≥4r\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.

References

Primary source

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

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.