Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T09:03:49.516Z Has data issue: false hasContentIssue false
  • English
  • Français

On r-Cross Intersecting Families of Sets

Published online by Cambridge University Press:  18 August 2011

PETER FRANKL  and
NORIHIDE TOKUSHIGE
PETER FRANKL
Affiliation:
3-12-25 Shibuya, Shibuya-ku, Tokyo 150-0002, Japan (e-mail: peter.frankl@gmail.com)
NORIHIDE TOKUSHIGE
Affiliation:
College of Education, Ryukyu University, Nishihara, Okinawa 903-0213, Japan (e-mail: hide@edu.u-ryukyu.ac.jp)
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 (r−1)n ≥ rk and let $\FF_1,\ldots,\FF_r\subset\binom{[n]}k$. Suppose that F1 ∩ ⋅⋅⋅ ∩ Fr ≠ ∅ holds for all Fi ∈ i, 1 ≤ i ≤ r. Then we show that $\prod_{i=1}^r|\FF_i|\leq\binom{n-1}{k-1}^r$.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 5 , September 2011 , pp. 749 - 752
Copyright
Copyright © Cambridge University Press 2011

References

[1]Bey, C. (2005) On cross-intersecting families of sets. Graphs Combin. 21 161–168.CrossRefGoogle Scholar
[2]Bollobás, B. (1965) On generalized graphs. Acta Math. Acad. Sci. Hungar 16 447–452.CrossRefGoogle Scholar
[3]Chowdhury, A. and Patkós, B. (2010) Shadows and intersections in vector spaces. J. Combin. Theory Ser. A 117 1095–1106.CrossRefGoogle 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.CrossRefGoogle Scholar
[5]Frankl, P. (1976) On Sperner families satisfying an additional condition. J. Combin. Theory Ser. A 20 1–11.CrossRefGoogle Scholar
[6]Frankl, P. (1991) Multiply-intersecting families. J. Combin. Theory Ser. B 53 195–234.CrossRefGoogle Scholar
[7]Gronau, H.-D. O. F. (1982) On Sperner families in which no k sets have an empty intersection III. Combinatorica 2 25–36.CrossRefGoogle Scholar
[8]Matsumoto, M. and Tokushige, N. (1989) The exact bound in the Erdős–Ko–Rado theorem for cross-intersecting families. J. Combin. Theory Ser. A 52 90–97.CrossRefGoogle Scholar
[9]Mubayi, D. and Verstraëte, J. (2005) Proof of a conjecture of Erdős on triangles in set-systems. Combinatorica 25 599–614.CrossRefGoogle Scholar
[10]Pyber, L. (1986) A new generalization of the Erdős–Ko–Rado theorem. J. Combin. Theory Ser. A 43 85–90.CrossRefGoogle Scholar