TY - JOUR

T1 - Ramsey-nice families of graphs

AU - Aharoni, Ron

AU - Alon, Noga

AU - Amir, Michal

AU - Haxell, Penny

AU - Hefetz, Dan

AU - Jiang, Zilin

AU - Kronenberg, Gal

AU - Naor, Alon

N1 - Publisher Copyright:
© 2018 Elsevier Ltd

PY - 2018/8

Y1 - 2018/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85046810243&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046810243&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2018.04.007

DO - 10.1016/j.ejc.2018.04.007

M3 - Article

AN - SCOPUS:85046810243

SN - 0195-6698

VL - 72

SP - 29

EP - 44

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -