<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs
András Gyárfás1, Gábor N. Sárközy1, 2†, and Endre Szemerédi3
1Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, P.O. Box 63, Budapest H-1518, Hungary
2Computer Science Department,Worcester Polytechnic Institute,Worcester, MA 01609, USA
3Department of Computer Science, Rutgers University, New Brunswick, NJ 08903, USA
Annals of Combinatorics 14 (2) pp.245-249 Summer, 2010
AMS Subject Classification: 05C15, 05C55, 05C65
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) 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 , the complete r-uniform hypergraph on n vertices.
Keywords: colored complete uniform hypergraphs, monochromatic matchings


1. Berge, C.: Graphs and Hypergraphs. American Elsevier Pub. Co., New York (1973)

2. Figaj, A., Luczak, T.: The Ramsey number for a triple of long even cycles. J. Combin. Theory Ser. B 97(4), 584–596 (2007)

3. Gyárfás, A., Lehel, J., Sárközy, G.N., Schelp, R.H.: Monochromatic Hamiltonian Bergecycles in colored complete uniform hypergraphs. J. Combin. Theory Ser. B 98(2), 342–358 (2008)

4. Gyárfás, A., Ruszinkó, M., Sárközy, G.N., Szemerédi, E.: Three-color Ramsey numbers for paths. Combinatorica 27(1), 35–69 (2007)

5. Gyárfás, A., Sárközy, G.N.: The 3-color Ramsey number of a 3-uniform Berge-cycle. Combin. Probab. Comput. (to appear)

6. Haxell, P., Luczak, T., Peng, Y., R¨odl, V., Rucinski, A., Simonovits, M., Skokan, J.: The Ramsey number for hypergraph cycles I. J. Combin. Theory Ser. A 113(1), 67–83 (2006)

7. Haxell, P., Luczak, T., Peng, Y., Ródl, V., Rucinski, A., Skokan, J.: The Ramsey number for 3-uniform tight hypergraph cycles. Combin. Probab. Comput. 18(1-2), 16 5–203 (2009)

8. Luczak, T.: R(Cn, Cn, Cn)≤(4+o(1))n. J. Combin. Theory Ser. B 75(2), 174–187 (1999)