Supersaturation, counting, and randomness in forbidden subposet problems

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

¹Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences

The electronic journal of combinatorics, Tome 28 (2021) no. 1

Résumé

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.) 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$. The number of $P$-free families in $2^{[n]}$ is $2^{(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor}}$. 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'\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.

Détail

DOI : 10.37236/9715

Classification : 05D05
Mots-clés : forbidden subposet problems, forbidden inclusion pattern