Erdös-Ko-Rado from intersecting shadows
Gyula O.H. Katona; Ákos Kisvölcsey
Discussiones Mathematicae Graph Theory (2012)
- Volume: 32, Issue: 2, page 379-382
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topGyula O.H. Katona, and Ákos Kisvölcsey. "Erdös-Ko-Rado from intersecting shadows." Discussiones Mathematicae Graph Theory 32.2 (2012): 379-382. <http://eudml.org/doc/271070>.
@article{GyulaO2012,
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.},
author = {Gyula O.H. Katona, Ákos Kisvölcsey},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Kneser graph; coclique; intersecting family; shadow},
language = {eng},
number = {2},
pages = {379-382},
title = {Erdös-Ko-Rado from intersecting shadows},
url = {http://eudml.org/doc/271070},
volume = {32},
year = {2012},
}
TY - JOUR
AU - Gyula O.H. Katona
AU - Ákos Kisvölcsey
TI - Erdös-Ko-Rado from intersecting shadows
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 2
SP - 379
EP - 382
AB - 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.
LA - eng
KW - Kneser graph; coclique; intersecting family; shadow
UR - http://eudml.org/doc/271070
ER -
References
top- [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. Zbl1187.05074
- [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. Zbl0100.01902
- [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. Zbl0364.05002
- [5] G.O.H. Katona, Intersection theorems for systems of finite sets, Acta Math. Hungar. 15 (1964) 329-337, doi: 10.1007/BF01897141. Zbl0134.25101
- [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. Zbl1220.05130
- [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. Zbl1232.05177
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.