Discussiones Mathematicae Graph Theory 32(2) (2012) 379-382
doi: 10.7151/dmgt.1620

[BIBTex] [PDF] [PS]

Erdös--Ko--Rado from Intersecting Shadows

Gyula O.H. Katona and Ákos Kisvölcsey

Alfréd Rényi Institute of Mathematics,
Hungarian Academy of Sciences
1053 Budapest, Reáltanoda u. 13--15, Hungary

Abstract

A set system is called t-intersecting if every two members meet each other in at least t elements. Katona determined the minimum ratio of the shadow and the size of such families and showed that the Erdős-Ko-Rado theorem immediately follows from this result. The aim of this note is to reproduce the proof to obtain a slight improvement in the Kneser graph. We also give a brief overview of corresponding results.

Keywords: Kneser graph, coclique, intersecting family, shadow

2010 Mathematics Subject Classification: 05C35, 05D05.

References

[1]P. Borg, A short proof of a cross-interscting theorem of Hilton, Discrete Math. 309 (2009) 4750--4753, doi: 10.1016/j.disc.2008.05.051.
[2]D.E. Daykin, Erdös--Ko--Rado from Kruskal--Katona, J. Combin. Theory (A) 17 (1974) 254--255, doi: 10.1016/0097-3165(74)90013-2.
[3]P. Erdös, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math., Oxford 12 (1961) 313--320.
[4]A.J.W. Hilton, An intersection theorem for a collection of families of subsets of a finite set, J. London Math. Soc. (2) 15 (1977) 369--376, doi: 10.1112/jlms/s2-15.3.369.
[5]G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Hungar. 15 (1964) 329--337, doi: 10.1007/BF01897141.
[6]G.O.H. Katona, A theorem of finite sets in: Theory of Graphs, Proc. Colloq. Tihany, 1966, P. Erdös and G.O.H. Katona (Eds.) (Akadémiai Kiadó, 1968) 187--207.
[7]J.B. Kruskal, The number of simplicies in a complex in: Math. Optimization Techniques, R. Bellman (Ed.) (Univ. of Calif. Press, Berkeley, 1963) 251--278.
[8]J. Wang and H.J. Zhang, Cross-intersecting families and primitivity of symmetric systems, J. Combin. Theory (A) 118 (2011) 455--462, doi: 10.1016/j.jcta.2010.09.005.
[9]H.J. Zhang, Primitivity and independent sets in direct products of vertex-transitive graphs, J. Graph Theory 67 (2011) 218--225, doi: 10.1002/jgt.20526.

Received 28 April 2011
Revised 6 August 2011
Accepted 8 August 2011