Gyárfás's extremal conjecture for monochromatic components in Steiner triple systems

Let Sn\mathcal{S}_n be the family of Steiner triple systems on nn points. For a Steiner triple system SS, let α3(S)\alpha^*_3(S) denote the maximum size of a 3-independent set, and let mc3(S)\mathrm{mc}_3(S) denote the minimum, over all 3-edge-colorings of SS, of the order of a largest monochromatic component. Gyárfás's conjecture. For all n1,3mod6n\equiv 1,3 \bmod 6,

maxSSnα3(S)=n31\max_{S\in \mathcal{S}_n} \alpha^*_3(S)=\left\lfloor\frac{n}{3}\right\rfloor-1

and

minSSnmc3(S)=2n3+1.\min_{S\in \mathcal{S}_n} \mathrm{mc}_3(S)=\left\lceil\frac{2n}{3}\right\rceil+1.

The conjecture is best possible in light of the cited lower and upper bounds, and the second assertion is known when n3(mod18)n\equiv 3\pmod {18}; the general case remains open.

Sources & referencesView supporting material

Primary source

Louis DeBiasio and Michael Tait, “Large monochromatic components in 3-edge-colored Steiner triple systems”, arXiv:1908.00837 (2020).

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.