The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) – So Gyárfás was right. (English) Zbl 07923451
Summary: 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 \(\frac{5}{6} n + o(n)\) colors. This settles a disagreement between Erdős and Gyárfás reported in their 1997 paper [P. Erdős and A. Gyárfás, Combinatorica 17, No. 4, 459–467 (1997; Zbl 0910.05034)]. 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 (see [B. Bollobás, Am. Math. Mon. 105, No. 3, 209–237 (1998; Zbl 0921.01027)]), and analyzed by T. Bohman et al. [Adv. Math. 280, 379–438 (2015; Zbl 1312.05123)].
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05D10 | Ramsey theory |
| 60F05 | Central limit and other weak theorems |
References:
| [1] | Alon, N.; Spencer, J. H., The Probabilistic Method, Wiley Series in Discrete Mathematics and Optimization., 2016, John Wiley & Sons, Inc.: John Wiley & Sons, Inc. Hoboken, NJ · Zbl 1333.05001 |
| [2] | Axenovich, M., A generalized Ramsey problem, Discrete Math., 222, 1-3, 247-249, 2000 · Zbl 0969.05042 |
| [3] | Balogh, J.; English, S.; Heath, E.; Krueger, R. A., Lower Bounds on the Erdős-Gyárfás Problem via Color Energy Graphs, 2022 |
| [4] | Bennett, P.; Cushman, R.; Dudek, A.; Prałat, P., The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{ 5}{ 6} n + o(n)\) — so Gyárfás was right |
| [5] | Bennett, P.; Dudek, A., A gentle introduction to the differential equation method and dynamic concentration, Discrete Math., 345, 12, Article 113071 pp., 2022 · Zbl 1497.05241 |
| [6] | Bohman, T.; Frieze, A.; Lubetzky, E., A note on the random greedy triangle-packing algorithm, J. Comb., 1, 3-4, 477-488, 2010 · Zbl 1244.05213 |
| [7] | Bohman, T.; Frieze, A.; Lubetzky, E., Random triangle removal, Adv. Math., 280, 379-438, 2015 · Zbl 1312.05123 |
| [8] | Bollobás, B., To prove and conjecture: Paul Erdős and his mathematics, Am. Math. Mon., 105, 3, 209-237, 1998 · Zbl 0921.01027 |
| [9] | Bollobás, B., Wolf Prize in Mathematics, Vol. 1, 2000, World Scientific Publishing Co. Inc.: World Scientific Publishing Co. Inc. River Edge, NJ · Zbl 0972.01032 |
| [10] | Cameron, A., An explicit edge-coloring of \(K_n\) with six colors on every \(K_5\), Electron. J. Comb., 26, 4, Article 4.13 pp., 2019 · Zbl 1422.05067 |
| [11] | Cameron, A.; Heath, E., A \((5, 5)\)-colouring of \(K_n\) with few colours, Comb. Probab. Comput., 27, 6, 892-912, 2018 · Zbl 1402.05145 |
| [12] | Cameron, A.; Heath, E., New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers, 2020 |
| [13] | Conlon, D.; Fox, J.; Lee, C.; Sudakov, B., The Erdős-Gyárfás problem on generalized Ramsey numbers, Proc. Lond. Math. Soc. (3), 110, 1, 1-18, 2015 · Zbl 1306.05148 |
| [14] | Delcourt, M.; Postle, L., Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings, 2022 |
| [15] | Erdős, P., Problems and results on finite and infinite graphs, (Recent Advances in Graph Theory. Recent Advances in Graph Theory, Proc. Second Czechoslovak Sympos., Prague, 1974, 1975), 183-192, (loose errata) · Zbl 0347.05116 |
| [16] | Erdős, P., Solved and unsolved problems in combinatorics and combinatorial number theory, Congr. Numer., 32, 49-62, 1981 · Zbl 0486.05002 |
| [17] | Erdős, P.; Gyárfás, A., A variant of the classical Ramsey problem, Combinatorica, 17, 4, 459-467, 1997 · Zbl 0910.05034 |
| [18] | Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470, 1935 · JFM 61.0651.04 |
| [19] | Fish, S.; Pohoata, C.; Sheffer, A., Local properties via color energy graphs and forbidden configurations, SIAM J. Discrete Math., 34, 1, 177-187, 2020 · Zbl 1431.05144 |
| [20] | Fox, J.; Sudakov, B., Ramsey-type problem for an almost monochromatic \(K_4\), SIAM J. Discrete Math., 23, 1, 155-162, 2008/2009 · Zbl 1190.05085 |
| [21] | Freedman, D. A., On tail probabilities for martingales, Ann. Probab., 3, 100-118, 1975 · Zbl 0313.60037 |
| [22] | Glock, S.; Joos, F.; Kim, J.; Kühn, M.; Lichev, L., Conflict-free hypergraph matchings, 2022 · Zbl 07848075 |
| [23] | Guo, H.; Patton, K.; Warnke, L., Prague dimension of random graphs, 2020 |
| [24] | Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization., 2000, Wiley-Interscience: Wiley-Interscience New York · Zbl 0968.05003 |
| [25] | Joos, F.; Mubayi, D., Ramsey theory constructions from hypergraph matchings, 2022 |
| [26] | Kurtz, T. G., Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab., 7, 49-58, 1970 · Zbl 0191.47301 |
| [27] | Lefmann, H., A note on Ramsey numbers, Studia Sci. Math. Hung., 22, 1-4, 445-446, 1987 · Zbl 0561.05003 |
| [28] | Mubayi, D., Edge-coloring cliques with three colors on all 4-cliques, Combinatorica, 18, 2, 293-296, 1998 · Zbl 0910.05035 |
| [29] | Mubayi, D., An explicit construction for a Ramsey problem, Combinatorica, 24, 2, 313-324, 2004 · Zbl 1058.05025 |
| [30] | Pohoata, C.; Sheffer, A., Local properties in colored graphs, distinct distances, and difference sets, Combinatorica, 39, 3, 705-714, 2019 · Zbl 1438.05141 |
| [31] | Sárközy, G. N.; Selkow, S., On edge colorings with at least q colors in every subset of p vertices, Electron. J. Comb., 8, 1, Article 9 pp., 2001 · Zbl 0960.05047 |
| [32] | Sárközy, G. N.; Selkow, S. M., An application of the regularity lemma in generalized Ramsey theory, J. Graph Theory, 44, 1, 39-49, 2003 · Zbl 1031.05087 |
| [33] | Warnke, L., On Wormald’s differential equation method, Comb. Probab. Comput., 2024, in press |
| [34] | Wormald, N. C., Differential equations for random processes and random graphs, Ann. Appl. Probab., 5, 4, 1217-1235, 1995 · Zbl 0847.05084 |
| [35] | Wormald, N. C., The differential equation method for random graph processes and greedy algorithms, (Lectures on Approximation and Randomized Algorithms, 1999, PWN: PWN Warsaw), 73-155 · Zbl 0943.05073 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
