Balázs Patkós: Supersaturation, counting, and randomness in forbidden subposet problems

Abstract:

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 talk, we formulate three strengthenings of this conjecture and prove them for some specific

classes of posets.

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

\end{itemize}

(The parameters $x(P)$ and $d(P)$ are defined in the paper.)

 

 

Joint work with D. Gerbner, D. Nagy, and M. Vizer