Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T11:57:10.168Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved Upper Bounds Concerning the Erdős-Ko-Rado Theorem

Published online by Cambridge University Press:  12 September 2008

A. R. Calderbank  and
P. Frankl
A. R. Calderbank
Affiliation:
Mathematical Sciences Research Center, AT&T Bell Laboratories, Murray Hill, NJ 07974
P. Frankl
Affiliation:
CNRS, 15 Quai Anatole France, F–75007 Paris, France
Get access Rights & Permissions [Opens in a new window]

Abstract

A family ℱ of k-element sets of an n-set is called t-intersecting if any two of its members overlap in at least t-elements. The Erdős-Ko-Rado Theorem gives a best possible upper bound for such a family if n ≥ n0(k, t). One of the most exciting open cases is when t = 2, n = 2k. The present paper gives an essential improvement on the upper bound for this case. The proofs use linear algebra and yield more general results.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 2 , June 1992 , pp. 115 - 122
Copyright
Copyright © Cambridge University Press 1992

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]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
[2]Frankl, P. (1978) The Erdős-Ko-Rado theorem is true for n = ckt, in: Combinatorics, Proc. Fifth Hungarian Coll. Combinatorics, Keszthely, 1976, North-Holland, Amsterdam, 365–375.Google Scholar
[3]Füredi, Z. (1991) Personal communication, Conference on Extremal Problems for Finite Sets, Visegrád, Hungary.Google Scholar
[4]Katona, G. O. H. (1964) Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15, 329–337.CrossRefGoogle Scholar
[5]Lovász, L. (1979) On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25, 1–7.CrossRefGoogle Scholar
[6]Ray-Chaudhuri, D. K. and Wilson, R. M. (1975) On t-designs, Osaka J. Math. 12, 737–744.Google Scholar
[7]Wilson, R. M. (1984) The exact bound in the Erdős-Ko-Rado Theorem, Combinatorica 4 (2–3), 247–257.CrossRefGoogle Scholar