Ramsey-nice families of graphs

Ron Aharoni, Noga Alon, Michal Amir, Penny Haxell, Dan Hefetz, Zilin Jiang, Gal Kronenberg, Alon Naor

Research output: Contribution to journalArticle

Abstract

For a finite family F of fixed graphs let Rk(F) be the smallest integer n for which every k-coloring of the edges of the complete graph Kn yields a monochromatic copy of some F∈F. We say that F is k-nice if for every graph G with χ(G)=Rk(F) and for every k-coloring of E(G) there exists a monochromatic copy of some F∈F. It is easy to see that if F contains no forest, then it is not k-nice for any k. It seems plausible to conjecture that a (weak) converse holds, namely, for any finite family of graphs F that contains at least one forest, and for all k≥k0(F) (or at least for infinitely many values of k), F is k-nice. We prove several (modest) results in support of this conjecture, showing, in particular, that it holds for each of the three families consisting of two connected graphs with 3 edges each and observing that it holds for any family F containing a forest with at most 2 edges. We also study some related problems and disprove a conjecture by Aharoni et al. (2015) regarding the size of matchings in regular 3-partite 3-uniform hypergraphs.

Original languageEnglish (US)
Pages (from-to)29-44
Number of pages16
JournalEuropean Journal of Combinatorics
Volume72
DOIs
StatePublished - Aug 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Ramsey-nice families of graphs'. Together they form a unique fingerprint.

  • Cite this

    Aharoni, R., Alon, N., Amir, M., Haxell, P., Hefetz, D., Jiang, Z., Kronenberg, G., & Naor, A. (2018). Ramsey-nice families of graphs. European Journal of Combinatorics, 72, 29-44. https://doi.org/10.1016/j.ejc.2018.04.007