The Library
Supersaturation in posets and applications involving the container method
Tools
Tools
Tools
Noel, Jonathan A., Scott, Alex and Sudakov, Benny (2018) Supersaturation in posets and applications involving the container method. Journal of Combinatorial Theory, Series A, 154 . pp. 247-284. doi:10.1016/j.jcta.2017.08.019 ISSN 0097-3165.
|
PDF
WRAP-supersaturation-posets-applications-involving-Noel-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (856Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jcta.2017.08.019
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 F n q 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 [23]. 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 [6]. We also state a number of open problems regarding supersaturation in posets and counting antichains.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Ordered sets, Lattice theory, Boundary value problems -- Asymptotic theory | ||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory, Series A | ||||||||
| Publisher: | Elsevier BV | ||||||||
| ISSN: | 0097-3165 | ||||||||
| Official Date: | February 2018 | ||||||||
| Dates: |
|
||||||||
| Volume: | 154 | ||||||||
| Page Range: | pp. 247-284 | ||||||||
| DOI: | 10.1016/j.jcta.2017.08.019 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 12 July 2018 | ||||||||
| Date of first compliant Open Access: | 14 September 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
