Asymptotic formula for linear-system chromatic number

For integers k3k\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 k3k\ge 3. There exists C=Ck>0C=C_k>0 such that if e>qCe>q^C, then

f1(e,q,k)=Θ ⁣(e12k2q)(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.

Sources & referencesView supporting material

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.