New bounds on the generalized Ramsey number \(f(n, 5, 8)\). (English) Zbl 1539.05093
Summary: Let \(f(n, p, q)\) denote the minimum number of colors needed to color the edges of \(K_n\) so that every copy of \(K_p\) receives at least \(q\) distinct colors. In this note, we show \(\frac{6}{7}(n - 1) \leq f(n, 5, 8) \leq n + o(n)\). The upper bound is proven using the “conflict-free hypergraph matchings method” which was recently used by F. Joos and D. Mubayi [“Ramsey theory constructions from hypergraph matchings”, Preprint, arXiv:2208.12563] to prove \(f(n, 4, 5) = \frac{5}{6}n + o(n)\).
MSC:
| 05C55 | Generalized Ramsey theory |
| 05D10 | Ramsey theory |
| 05C65 | Hypergraphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
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] | Axenovich, M.; Füredi, Z.; Mubayi, D., On generalized Ramsey theory: the bipartite case, J. Comb. Theory, Ser. B, 79, 1, 66-86, 2000 · Zbl 1023.05101 |
| [4] | Balogh, J.; English, S.; Heath, E.; Krueger, R. A., Lower bounds on the Erdős-Gyárfás problem via color energy graphs, J. Graph Theory, 103, 2, 378-409, 2023 · Zbl 1522.05090 |
| [5] | 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, 2022 |
| [6] | Bennett, P.; Delcourt, M.; Li, L.; Postle, L., On generalized Ramsey numbers in the sublinear regime, 2022 |
| [7] | Bennett, P.; Dudek, A.; English, S., A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers, 2022 |
| [8] | Bennett, P.; Heath, E.; Zerbib, S., Edge-coloring a graph G so that every copy of a graph H has an odd color class, 2023 |
| [9] | Cameron, A., An explicit edge-coloring of \(k_n\) with six colors on every \(K_5\), Electron. J. Comb., 26, 4, 2017 |
| [10] | 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 |
| [11] | Cameron, A.; Heath, E., New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers, Comb. Probab. Comput., 32, 2, 349-362, 2023 · Zbl 1511.05164 |
| [12] | Conlon, D.; Fox, J.; Lee, C.; Sudakov, B., The Erdős-Gyárfás problem on generalized Ramsey numbers, Proc. Lond. Math. Soc., 110, 1, 1-18, 2015 · Zbl 1306.05148 |
| [13] | Delcourt, M.; Postle, L., Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings, 2022 |
| [14] | Delcourt, M.; Postle, L., The limit in the \((k + 2, k)\)-problem of Brown, Erdős and Sós exists for all \(k \geq 2\), 2022 |
| [15] | Erdős, P., Problems and results on finite and infinite graphs, (Recent Advances in Graph Theory, Proc. Second Czechoslovak Sympos.. Recent Advances in Graph Theory, Proc. Second Czechoslovak Sympos., Prague, 1974, 1975), 183-192 · Zbl 0347.05116 |
| [16] | Erdős, P., Solved and unsolved problems in combinatorics and combinatorial number theory, Eur. J. Comb., 2, 1-11, 1981 |
| [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] | 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 |
| [19] | Glock, S.; Joos, F.; Kim, J.; Kühn, M.; Lichev, L., Conflict-free hypergraph matchings, (Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023, SIAM), 2991-3005 · Zbl 07848075 |
| [20] | Glock, S.; Joos, F.; Kim, J.; Kühn, M.; Lichev, L.; Pikhurko, O., On the \((6, 4)\)-problem of Brown, Erdős and Sós, 2022 |
| [21] | Joos, F.; Mubayi, D., Ramsey theory constructions from hypergraph matchings, 2022 |
| [22] | McDiarmid, C., On the method of bounded differences, Surv. Comb., 141, 1, 148-188, 1989 · Zbl 0712.05012 |
| [23] | Mubayi, D., Edge-coloring cliques with three colors on all 4-cliques, Combinatorica, 18, 2, 293-296, 1998 · Zbl 0910.05035 |
| [24] | Mubayi, D., An explicit construction for a Ramsey problem, Combinatorica, 24, 2, 313-324, 2004 · Zbl 1058.05025 |
| [25] | Pohoata, C.; Sheffer, A., Local properties in colored graphs, distinct distances, and difference sets, Combinatorica, 39, 3, 705-714, 2019 · Zbl 1438.05141 |
| [26] | 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 R9 pp., 2000 · Zbl 0960.05047 |
| [27] | 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 |
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.
