On the sizes of t-intersecting k-chain-free families

EUROCOMB’23

József Balogh William Linz Balazs Patkos

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-014

PDF
Abstract
A set system ${\mathcal F}$ is $t$-intersecting, if the size of the intersection of every pair of its elements has size at least $t$. A set system ${\mathcal F}$ is $k$-Sperner, if it does not contain a chain of length $k+1$. Our main result is the following: Suppose that $k$ and $t$ are fixed positive integers, where $n+t$ is even and $n$ is large enough. If ${\mathcal F}\subseteq 2^{[n]}$ is a $t$-intersecting $k$-Sperner family, then ${\mathcal F}$ has size at most the size of the sum of $k$ layers, of sizes $(n+t)/2,\ldots, (n+t)/2+k-1$. This bound is best possible. The case when $n+t$ is odd remains open.

Pages:
101–106
References

József Balogh, William B Linz, and Balázs Patkós. On the sizes of t-intersecting k-chain-free families. arXiv preprint arXiv:2209.01656, 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-014

Paul Erdős. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc., 51:898-902, 1945.
https://doi.org/10.1090/S0002-9904-1945-08454-7

Peter Frankl. Canonical antichains on the circle and applications. SIAM Journal on Discrete Mathematics, 3(3):355-363, 1990.
https://doi.org/10.1137/0403031

Peter Frankl. Analogues of Milner's theorem for families without long chains and of vector spaces. European Journal of Combinatorics, 93:103279, 2021.
https://doi.org/10.1016/j.ejc.2020.103279

Dániel Gerbner. Profile polytopes of some classes of families. Combinatorica, 33:199-216, 2013.
https://doi.org/10.1007/s00493-013-2917-y

Dániel Gerbner, Abhishek Methuku, and Casey Tompkins. Intersecting P -free families. Journal of Combinatorial Theory, Series A, 151:61-83, 2017.
https://doi.org/10.1016/j.jcta.2017.04.009

Gyula Katona. Intersection theorems for systems of finite sets. Acta Mathematica Academiae Scientiarum Hungaricae, 15(3-4):329-337, 1964.
https://doi.org/10.1007/BF01897141

Eric C Milner. A combinatorial theorem on systems of sets. Journal of the London Mathematical Society, 1(1):204-206, 1968.
https://doi.org/10.1112/jlms/s1-43.1.204

Emanuel Sperner. Ein satz über untermengen einer endlichen menge. Mathematische Zeitschrift, 27(1):544-548, 1928.
https://doi.org/10.1007/BF01171114

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 József Balogh, William Linz, Balazs Patkos

PDF