IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Packing nearly optimal Ramsey R(3,t) graphs

  • Sept. 11, 2020
  • 2:30 p.m.


In 1995 Kim famously proved the Ramsey bound $R(3,t) \geq c t^2/\log t$ by constructing an $n$-vertex graph that is triangle-free and has independence number at most $C \sqrt{n \log n}$. We 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$ we find an edge-disjoint collection $(G _ i) _ i$ of $n$-vertex graphs $G _ i \subseteq K _ n$ such that (a) each $G _ i$ is triangle-free and has independence number at most $C _ \epsilon \sqrt{n \log n}$, and (b) the union of all the $G _ i$ contains at least $(1-\epsilon)\binom{n}{2}$ edges. Our 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, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo (concerning a Ramsey-type parameter introduced by Burr, Erdos, Lovasz in 1976). Namely, denoting by $s _ r(H)$ the smallest minimum degree of $r$-Ramsey minimal graphs for $H$, we close the existing logarithmic gap for $H=K _ 3$ and establish that $s _ r(K _ 3) = \Theta(r^2 \log r).$

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster