Supersaturation in posets and applications involving the container method

DOI10.1016/J.JCTA.2017.08.019MaRDI QIDQ1679331zbMATH OpenOpenAlexFDO

Authors Jonathan A. Noel, Alex Scott, Benny Sudakov

Publication date 9 November 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01521, http://wrap.warwick.ac.uk/104264/1/WRAP-supersaturation-posets-applications-involving-Noel-2018.pdf

zbMATH Keywords

partially ordered setantichaincontainer methodsupersaturation

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: We consider 'supersaturation' problems in partially ordered sets (posets) of the following form. Given a finite poset $P$ and an integer $m$ greater than the cardinality of the largest antichain in $P$, what is the minimum number of comparable pairs in a subset of $P$ of cardinality $m$? We provide a framework for obtaining lower bounds on this quantity based on counting comparable pairs relative to a random chain and apply this framework to obtain supersaturation results for three classical posets: the boolean lattice, the collection of subspaces of $mathbb{F}_q^n$ ordered by set inclusion and the set of divisors of the square of a square-free integer under the 'divides' relation. The bound that we obtain for the boolean lattice can be viewed as an approximate version of a known theorem of Kleitman. In addition, we apply our supersaturation results to obtain (a) upper bounds on the number of antichains in these posets and (b) asymptotic bounds on the cardinality of the largest antichain in $p$-random subsets of these posets which hold with high probability (for $p$ in a certain range). The proofs of these results rely on a 'container-type' lemma for posets which generalises a result of Balogh, Mycroft and Treglown. We also state a number of open problems regarding supersaturation in posets and counting antichains.

Recommendations

• Supersaturation, counting, and randomness in forbidden subposet problems
• Supersaturation in the Boolean lattice
• Supersaturation and stability for forbidden subposet problems.
• The saturation number of induced subposets of the Boolean lattice
• Packing posets in the Boolean lattice.

Cites work

• scientific article; zbMATH DE number 3825713 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 3465294 (Why is no real title available?)
• scientific article; zbMATH DE number 3256524 (Why is no real title available?)
• scientific article; zbMATH DE number 3065933 (Why is no real title available?)
• A random version of Sperner's theorem
• A short proof of Sperner's lemma
• A variance method in combinatorial number theory
• Applications of graph containers in the Boolean lattice
• Combinatorial theorems in sparse random sets
• Concentration of Measure for the Analysis of Randomized Algorithms
• Counting independent sets in graphs
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• Extremal results for random discrete structures
• Families in posets minimizing the number of comparable pairs
• Hypergraph containers
• Independent sets in hypergraphs
• Maximum-size antichains in random set-systems
• On a theorem of Rademacher-Turán
• On the Divisors of a Number
• On the number of graphs without 4-cycles
• On the number of monotone sequences
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Subsets of posets minimising the number of chains
• Supersaturated graphs and hypergraphs
• Supersaturation and stability for forbidden subposet problems.
• Supersaturation in the Boolean lattice
• The clique density theorem
• The minimum number of disjoint pairs in set systems and related problems
• The number of additive triples in subsets of abelian groups
• Three problems in combinatorial asymptotics

Cited in

(10)

• Applications of graph containers in the Boolean lattice
• On the number of high‐dimensional partitions
• Families in posets minimizing the number of comparable pairs
• Improved bounds for induced poset saturation
• Subsets of posets minimising the number of chains
• Rado's criterion over squares and higher powers
• Supersaturation in the Boolean lattice
• Structure and supersaturation for intersecting families
• Supersaturation, counting, and randomness in forbidden subposet problems
• The saturation number of induced subposets of the Boolean lattice

This page was built for publication: Supersaturation in posets and applications involving the container method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679331)