Supersaturation, counting, and randomness in forbidden subposet problems

DOI10.37236/9715MaRDI QIDQ2656893zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Dániel T. Nagy, Balázs Patkós, Máté Vizer

Publication date 17 March 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

forbidden inclusion patternforbidden subposet problems

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: In the area of forbidden subposet problems we look for the largest possible size $La(n,P)$ of a family $mathcalFsubseteq{2}^{[n]}$ that does not contain a forbidden inclusion pattern described by $P$. The main conjecture of the area states that for any finite poset $P$ there exists an integer $e(P)$ such that $$. In this paper, we formulate three strengthenings of this conjecture and prove them for some specific classes of posets. (The parameters $x(P)$ and $d(P)$ are defined in the paper.) $$ For any finite connected poset $P$ and $varepsilon>0$, there exists $delta>0$ and an integer $x(P)$ such that for any $n$ large enough, and $mathcalFsubseteq{2}^{[n]}$ of size $$, $mathcalF$ contains at least $$ copies of $P$. $$ The number of $P$-free families in $2^{[n]}$ is $$. $$ For any finite poset $P$, there exists a positive rational $d(P)$ such that if $p=omega(n^{-d(P)})$, then the size of the largest $P$-free family in $mathcalP(n,p)$ is $$ with high probability.

Review text

Summary: In the area of forbidden subposet problems we look for the largest possible size \(La(n,P)\) of a family \(\mathcal{F}\subseteq 2^{[n]}\) that does not contain a forbidden inclusion pattern described by \(P\). The main conjecture of the area states that for any finite poset \(P\) there exists an integer \(e(P)\) such that \(La(n,P)=(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor} \). In this paper, we formulate three strengthenings of this conjecture and prove them for some specific classes of posets. (The parameters \(x(P)\) and \(d(P)\) are defined in the paper.) \par i) For any finite connected poset \(P\) and \(\varepsilon>0\), there exists \(\delta>0\) and an integer \(x(P)\) such that for any \(n\) large enough, and \(\mathcal{F}\subseteq 2^{[n]}\) of size \((e(P)+\varepsilon)\binom{n}{\lfloor n/2\rfloor}\), \(\mathcal{F}\) contains at least \(\delta n^{x(P)}\binom{n}{\lfloor n/2\rfloor}\) copies of \(P\). \par ii) The number of \(P\)-free families in \(2^{[n]}\) is \(2^{(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor}} \). \par iii) Let \(\mathcal{P}(n,p)\) be the random subfamily of \(2^{[n]}\) such that every \(F\in 2^{[n]}\) belongs to \(\mathcal{P}(n,p)\) with probability \(p\) independently of all other subsets \(F^\prime\in 2^{[n]} \). For any finite poset \(P\), there exists a positive rational \(d(P)\) such that if \(p=\omega(n^{-d(P)})\), then the size of the largest \(P\)-free family in \(\mathcal{P}(n,p)\) is \((e(P)+o(1))p\binom{n}{\lfloor n/2\rfloor}\) with high probability.

Recommendations

• Supersaturation and stability for forbidden subposet problems.
• Supersaturation for Ramsey-Turán problems
• Generalized forbidden subposet problems
• Forbidden subposet problems with size restrictions
• Induced and non-induced forbidden subposet problems
• Supersaturation for subgraph counts
• Supersaturation in posets and applications involving the container method
• Forbidden subposet problems for traces of set families
• On families of subsets with a forbidden subposet
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT

Cites work

• A random version of Sperner's theorem
• Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
• Diamond-free families
• scientific article; zbMATH DE number 3845613 (Why is no real title available?)
• scientific article; zbMATH DE number 3825713 (Why is no real title available?)
• Induced and non-induced forbidden subposet problems
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Maximum-size antichains in random set-systems
• On a lemma of Littlewood and Offord
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• On families of subsets with a forbidden subposet
• Set families with a forbidden subposet
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Subsets of posets minimising the number of chains
• Supersaturation and stability for forbidden subposet problems.
• Supersaturation in the Boolean lattice
• The partition method for poset-free families

Cited in

(11)

• Supersaturation in posets and applications involving the container method
• Forbidden subposet problems with size restrictions
• Induced and non-induced poset saturation problems
• Forbidden subposet problems in the grid
• On the number of containments in \(P\)-free families
• A simple proof for a forbidden subposet problem
• Progress on poset-free families of subsets
• Supersaturation and stability for forbidden subposet problems.
• On some extremal and probabilistic questions for tree posets
• On the number of P-free set systems for tree posets P
• Generalized forbidden subposet problems

This page was built for publication: Supersaturation, counting, and randomness in forbidden subposet problems

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