Strict Erdős-Ko-Rado for simplicial complexes

EUROCOMB’23

Abstract
We show that the strict Erdős-Ko-Rado property holds for sequentially Cohen-Macaulay near-cones. In particular, this implies that chordal graphs with at least one isolated vertex satisfy the strict Erdős-Ko-Rado property.

Pages:
245–253
References

Peter Borg. Extremal t-intersecting sub-families of hereditary families. J. Lond. Math. Soc. (2), 79(1):167-185, 2009.
https://doi.org/10.1112/jlms/jdn062

Anton Dochtermann and Alexander Engström. Algebraic properties of edge ideals via combinatorial topology. Electron. J. Combin., 16(2, Special volume in honor of Anders Björner):Research Paper 2, 24, 2009.
https://doi.org/10.37236/68

Art M. Duval. Algebraic shifting and sequentially Cohen-Macaulay simplicial complexes. Electron. J. Combin., 3(1):Research Paper 21, approx. 14, 1996.
https://doi.org/10.37236/1245

P. Erdős, Chao Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2), 12:313-320, 1961.
https://doi.org/10.1093/qmath/12.1.313

Christopher A. Francisco and Adam Van Tuyl. Sequentially Cohen-Macaulay edge ideals. Proc. Amer. Math. Soc., 135(8):2327-2337, 2007.
https://doi.org/10.1090/S0002-9939-07-08841-7

Peter Frankl. The shifting technique in extremal set theory. In Surveys in combinatorics 1987 (New Cross, 1987), volume 123 of London Math. Soc. Lecture Note Ser., pages 81-110. Cambridge Univ. Press, Cambridge, 1987.

Peter Frankl. A simple proof of the Hilton-Milner theorem. Mosc. J. Comb. Number Theory, 8(2):97-101, 2019.
https://doi.org/10.2140/moscow.2019.8.97

A. J. W. Hilton and E. C. Milner. Some intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2), 18:369-384, 1967.
https://doi.org/10.1093/qmath/18.1.369

Fred Holroyd, Claire Spencer, and John Talbot. Compression and Erdős-Ko-Rado graphs. Discrete Math., 293(1-3):155-164, 2005.
https://doi.org/10.1016/j.disc.2004.08.041

Fred Holroyd and John Talbot. Graphs with the Erdős-Ko-Rado property. Discrete Math., 293(1-3):165-176, 2005.
https://doi.org/10.1016/j.disc.2004.08.028

Glenn Hurlbert and Vikram Kamat. Erdős-Ko-Rado theorems for chordal graphs and trees. J. Combin. Theory Ser. A, 118(3):829-841, 2011.
https://doi.org/10.1016/j.jcta.2010.11.017

Glenn Hurlbert and Vikram Kamat. New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems. Discrete Math., 341(6):1749-1754, 2018.
https://doi.org/10.1016/j.disc.2018.03.010

A. Johnson and F. C. Holroyd. 'Problem 25', Problems from the Sixteenth British Combinatorial Conference. P.J. Cameron, 1997.

Gil Kalai. Hyperconnectivity of graphs. Graphs Combin., 1(1):65-79, 1985.
https://doi.org/10.1007/BF02582930

Gil Kalai. Algebraic shifting. In Computational commutative algebra and combinatorics (Osaka, 1999), volume 33 of Adv. Stud. Pure Math., pages 121-163. Math. Soc. Japan, Tokyo, 2002.

Younjin Kim. Erdős-Ko-Rado type theorems for simplicial complexes via algebraic shifting. J. Korean Math. Soc., 57(6):1323-1333, 2020.

Susan Morey and Rafael H. Villarreal. Edge ideals: algebraic and combinatorial properties. In Progress in commutative algebra 1, pages 85-126. de Gruyter, Berlin, 2012.
https://doi.org/10.1515/9783110250404.85

Eran Nevo. Algebraic shifting and basic constructions on simplicial complexes. J. Algebraic Combin., 22(4):411-433, 2005.
https://doi.org/10.1007/s10801-005-4626-0

Jorge Alberto Olarte, Francisco Santos, Jonathan Spreer, and Christian Stump. The EKR property for flag pure simplicial complexes without boundary. J. Combin. Theory Ser. A, 172:105205, 29, 2020.
https://doi.org/10.1016/j.jcta.2019.105205

Seyed Amin Seyed Fakhari. Erdős-Ko-Rado type theorems for simplicial complexes. Electron. J. Combin., 24(2):Paper No. 2.38, 11, 2017.
https://doi.org/10.37236/6544

Dean E. Smith. On the Cohen-Macaulay property in commutative algebra and simplicial topology. Pacific J. Math., 141(1):165-196, 1990.
https://doi.org/10.2140/pjm.1990.141.165

John Talbot. Intersecting families of separated sets. J. London Math. Soc. (2), 68(1):37-51, 2003.
https://doi.org/10.1112/S0024610703004356

Larry X. W. Wang. Restricted intersecting families on simplicial complex. Adv. in Appl. Math., 124:Paper No. 102144, 15, 2021.
https://doi.org/10.1016/j.aam.2020.102144

Russ Woodroofe. Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc., 137(10):3235-3246, 2009.
https://doi.org/10.1090/S0002-9939-09-09981-X

Russ Woodroofe. Erdős-Ko-Rado theorems for simplicial complexes. J. Combin. Theory Ser. A, 118(4):1218-1227, 2011.
https://doi.org/10.1016/j.jcta.2010.11.022

Metrics

0

Views

0

PDF views