The Erdős-Gyárfás function f(n,4,5)=56n+o(n)f(n, 4, 5) = \frac 56 n + o(n) -- so Gyárfás was right

preprint2022arXivOpen access

Abstract

A (4,5)(4, 5)-coloring of KnK_n is an edge-coloring of KnK_n where every 44-clique spans at least five colors. We show that there exist (4,5)(4, 5)-colorings of KnK_n using 56n+o(n)\frac 56 n + o(n) colors. This settles a disagreement between Erdős and Gyárfás 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ás and Erdős, and analyzed by Bohman, Frieze and Lubetzky.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.