Packing nearly optimal Ramsey \(R(3,t)\) graphs (Q2182253): Difference between revisions

\textit{J. H. Kim} [Random Struct. Algorithms 7, No. 3, 173--207 (1995; Zbl 0832.05084)] proved the Ramsey bound \(R(3,t)\ge ct^2/\log t\) by constructing an \(n\)-vertex graph that is triangle-free and has independence number at most \(C\sqrt{n\log n}\). The authors extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph \(K_n\) into a packing of such nearly optimal Ramsey \(R(3,t)\) graphs. More precisely, for any \(\epsilon > 0\) it is found an edge-disjoint collection \((G_i)_i\) of \(n\)-vertex graphs \(G_i\subseteq K_n\) such that (i) each \(G_i\) is triangle-free and has independence number at most \(C_\epsilon\sqrt{n\log n}\)\,, and (ii) the union of all the \(G_i\) contains at least \((1-\epsilon)\binom{n}{2}\) edges. Their algorithmic proof proceeds by sequentially choosing the graphs \(G_i\) via a semi-random (i.e., Rödl nibble type) variation of the triangle-free process. As an application, it is proved a conjecture in Ramsey theory by \textit{J. Fox} et al. [J. Comb. Theory, Ser. B 120, 64--82 (2016; Zbl 1337.05076)] (concerning a Ramsey-type parameter introduced by \textit{S. A. Burr} et al. [Ars Comb. 1, 167--190 (1976; Zbl 0333.05120)]). Namely, denoting by \(s_r(H)\) the smallest minimum degree of \(r\)-Ramsey minimal graphs for \(H\), it is closed the existing logarithmic gap for \(H = K_3\) and established that \(s_r(K_3) =\Theta(r^2\log r)\).