The Erd\H{o}s-Gy\'arf\'as function f(n, 4, 5) = \frac 56 n + o(n) -- so Gy\'arf\'as was right

MaRDI QIDQ6404207zbMATH OpenFDO

Authors Patrick Bennett, Ryan Cushman, Andrzej Dudek, Paweł Prałat

Publication date 6 July 2022

Abstract: A $(4,5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique spans at least five colors. We show that there exist $(4,5)$-colorings of $K_n$ using $frac56n+o(n)$ colors. This settles a disagreement between ErdH{o}s and Gy'arf'as reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollob'as and ErdH{o}s, and analyzed by Bohman, Frieze and Lubetzky.

This page was built for publication: The Erd\H{o}s-Gy\'arf\'as function $f(n, 4, 5) = \frac 56 n + o(n)$ -- so Gy\'arf\'as was right

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404207)