|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Families with few k-chains
If you have a question about this talk, please contact Andrew Thomason.
A central theorem in combinatorics is Sperner’s Theorem, which determines the maximum size of a family in the Boolean lattice that does not contain a 2-chain. Erdos later extended this result and determined the largest family not containing a k-chain. Erdos and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result.
This question was resolved for 2-chains by Kleitman in 1966, who showed that amongst families of size M in the Boolean lattice, the number of 2-chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all k, not just 2. The best result on this question is due to Das, Gan and Sudakov who showed roughly that Kleitman’s conjecture holds for families whose size is at most the size of the k+1 middle layers of the Boolean lattice. Our main result is that for every fixed k and epsilon, if n is sufficiently large then Kleitman’s conjecture holds for families of size at most (1-epsilon)2^n, thereby establishing Kleitman’s conjecture asymptotically. Our proof is based on ideas of Kleitman and Das, Gan and Sudakov.
Joint work with Jozsi Balogh.
This talk is part of the Combinatorics Seminar series.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsChanging Health CamCREES seminars (Cambridge Committee for Russian and East European Studies) Medieval Economic and Social History Seminars
Other talksRambling in NE Mexico TBC Masterclass: The health impacts of volcanic gases Professor Caroline Hill - Title tbc Contributions of the APC protein to mechanisms regulating normal epithelial tissue organisation in the intestine Understanding Angiogenesis through Modeling and Asymptotics