Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-14T03:28:03.508Z 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: [email protected])
DAVID HOWARD
Affiliation:
Department of Mathematics, Colgate University, 13 Oak Drive, Hamilton, NY 13346, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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