Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-06T18:39:43.006Z Has data issue: false hasContentIssue false
  • English
  • Français

A Rainbow r-Partite Version of the Erdős–Ko–Rado Theorem

Part of: Extremal combinatorics

Published online by Cambridge University Press:  23 January 2017

RON AHARONI  and
DAVID HOWARD
RON AHARONI
Affiliation:
Department of Mathematics, Technion, Haifa 32000, Israel (e-mail: raharoni@gmail.com)
DAVID HOWARD
Affiliation:
Department of Mathematics, Colgate University, 13 Oak Drive, Hamilton, NY 13346, USA (e-mail: dmhoward@colgate.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let [n]r be the complete r-partite hypergraph with vertex classes of size n. It is an easy exercise to show that every set of more than (k−1)nr−1 edges in [n]r contains a matching of size k. We conjecture the following rainbow version of this observation: if F1,F2,. . .,Fk ⊆ [n]r are of size larger than (k−1)nr−1 then there exists a rainbow matching, that is, a choice of disjoint edges fi ∈ Fi. We prove this conjecture for r=2 and r=3.

MSC classification

Primary: 05D05: Extremal set theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 3 , May 2017 , pp. 321 - 337
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Aharoni, R. and Howard, D. Cross-intersecting pairs of hypergraphs. To appear in J. Combin. Th. Ser. A.Google Scholar
[2] Akiyama, J. and Frankl, P. (1985) On the size of graphs with complete-factors. J. Graph Theory 9 197–201.Google Scholar
[3] Erdős, P. and Gallai, T. (1961) On the minimal number of vertices representing the edges of a graph. Publ. Math. Inst. Hungar. Acad. Sci. 6 181–203.Google Scholar
[4] Erdős, P., Ko, C. and Rado, R. (1961) Intersection theorems for systems of finite sets. Quart. J. Math Oxford (2) 12 313–320.Google Scholar
[5] Frankl, P. (1987) The shifting technique in extremal set theory. In Surveys in Combinatorics, Vol. 123 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 81–110.Google Scholar
[6] Füredi, Z. (1988) Matchings and covers in hypergraphs. Graphs Combin. 4 115–206.Google Scholar
[7] Howard, D. and Yehudayoff, A. Rainbow Erdős–Ko–Rado. Unpublished.Google Scholar
[8] Huang, H., Loh, P. and Sudakov, B. (2012) The size of a hypergraph and its matching number. Combin. Probab. Comput. 21 442–450.Google Scholar
[9] Matsumoto, M. and Tokushige, N. (1989) The exact bound in the Erdos–Ko–Rado theorem for cross-intersecting families. J. Combin. Theory Ser. A 52 90–97.Google Scholar
[10] Meshulam, R. Private communication.Google Scholar
[11] Pyber, L. (1986) A new generalization of the Erdos–Ko–Rado theorem. J. Combin. Theory Ser. A 43 85–90.CrossRefGoogle Scholar