Supersaturation in posets and applications involving the container method

DOI10.1016/J.JCTA.2017.08.019zbMATH Open1373.05197arXiv1610.01521OpenAlexW2964193988MaRDI QIDQ1679331FDOQ1679331

Alex Scott, Jonathan A. Noel, Benny Sudakov

Publication date: 9 November 2017

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

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.

Full work available at URL: https://arxiv.org/abs/1610.01521

zbMATH Keywords

partially ordered setantichaincontainer methodsupersaturation

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

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

Cited In (6)

• On the number of high‐dimensional partitions
• Structure and supersaturation for intersecting families
• Rado's criterion over squares and higher powers
• Families in posets minimizing the number of comparable pairs
• Subsets of posets minimising the number of chains
• Supersaturation, counting, and randomness in forbidden subposet problems

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)