|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 listsStem Cell Seminars and Events in Cambridge Cancer Research UK Cambridge Institute (CRUK CI) Seminars in Cancer Cambridge Conversations in Translation
Other talksDesign and Evolution of New Biocatalysts for Organic Synthesis Embracing Complexity: A Fly-to-Bedside Approach to Cancer Therapies A rose by any other name Security and Privacy in Machine Learning De-identified electronic mental health records for research and recruitment Heat Rises: 100 Years of Rayleigh-Bénard Convection (Rouse Ball Lecture)