Asymptotic formula for linear-system chromatic number

About 3 years old · traced to

For integers k≥3k\ge 3, let f1(e,q,k)f_1(e,q,k) denote the maximum chromatic number of a 11-(q,k)(q,k)-system with ee qq-cliques. The asymptotic chromatic-number conjecture. Fix k≥3k\ge 3. There exists C=Ck>0C=C_k>0 such that if e>qCe>q^C, then

f1(e,q,k)=Θ ⁣(e12k−2q)(q→∞).f_1(e,q,k)=\Theta\!\left(e^{\frac{1}{2k-2}}q\right)\qquad(q\to\infty).

The conjecture predicts the sharp order of magnitude in the large-ee regime, improving the preceding upper and lower bounds. The source describes the problem as wide open for smaller values of ee and gives no resolution of this asserted asymptotic statement.

References

Primary source

Dhruv Mubayi and Jacques Verstraete, “Coloring hypergraphs that are the union of nearly disjoint cliques”, arXiv:2304.04855 (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.