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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1620,
author = {Gyula O.H. Katona and \'Akos Kisv\"olcsey},
title = {Erd\"os-Ko-Rado from intersecting shadows},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {379-382},
zbl = {1255.05103},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1620}
}
Gyula O.H. Katona; Ákos Kisvölcsey. Erdös-Ko-Rado from intersecting shadows. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 379-382. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1620/
[000] [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. | Zbl 1187.05074
[001] [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.
[002] [3] P. Erdös, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math., Oxford 12 (1961) 313-320. | Zbl 0100.01902
[003] [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. | Zbl 0364.05002
[004] [5] G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Hungar. 15 (1964) 329-337, doi: 10.1007/BF01897141. | Zbl 0134.25101
[005] [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.
[006] [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.
[007] [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. | Zbl 1220.05130
[008] [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. | Zbl 1232.05177