Ramsey-nice families of graphs. (August 2018)

• Record Type: Journal Article
• Authors: Aharoni, Ron; Alon, Noga; Amir, Michal; Haxell, Penny; Hefetz, Dan; Jiang, Zilin; Kronenberg, Gal; Naor, Alon
• Is Part Of: European journal of combinatorics. Volume 72(2018)
• Page Start: 29
• Page End: 44
• Publication Date: 2018-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.04.007
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For a finite family F of fixed graphs let R k ( F ) be the smallest integer n for which every k -coloring of the edges of the complete graph K n yields a monochromatic copy of some F ∈ F . We say that F is k - nice if for every graph G with χ ( G ) = R k ( 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 ≥ k 0 ( 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.