Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs |
| |
Authors: | András Gyárfás Gábor N. Sárközy Endre Szemerédi |
| |
Affiliation: | 1. Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, P.O. Box 63, Budapest, H-1518, Hungary 2. Computer Science Department, Worcester Polytechnic Institute, Worcester, MA, 01609, USA 3. Department of Computer Science, Rutgers University, New Brunswick, NJ, 08903, USA
|
| |
Abstract: | Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least (1-e)( *20c nr)(1-varepsilon)left( {begin{array}{*{20}c} n r end{array}}right) edges, the 2-shadow has a monochromatic matching covering all but at most o(n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1))n in every (r – 1)-coloring of the edges of K(r)n{K^{(r)}_{n}}, the complete r-uniform hypergraph on n vertices. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|