A simple discharging method for forbidden subposet problems

Abstract

The poset $Y_{k+1,2}$ consists of $k+2$ distinct elements $x_1$, $x_2$, \dots, $x_k$, $y_1$,$y_2$, such that $x_1\le x_2\le \cdots \le x_k\le y_1$,~$y_2$. The poset $Y_{k+1,2}^{\prime }$ is the dual of $Y_{k+1,2}$ Let ${\mathrm{La}}^{♯}(\mathrm{n},\{{\mathrm{Y}}_{\mathrm{k}+1,2},{\mathrm{Y}}_{\mathrm{k}+1,2}^{\prime }\})$ be the size of the largest family $\mathcal{F}\subset 2^{[n]}$ that contains neither $Y_{k+1,2}$ nor $Y_{k+1,2}^{\prime }$ as an induced subposet. Methuku and Tompkins proved that ${\mathrm{La}}^{♯}(\mathrm{n},\{{\mathrm{Y}}_{3,2},{\mathrm{Y}}_{3,2}^{\prime }\})=\mathrm{\Sigma }(\mathrm{n},2)$ for $n\ge 3$ and they conjectured the generalization that if $k\ge 2$ is an integer and $n\ge k+1$, then ${\mathrm{La}}^{♯}(\mathrm{n},\{{\mathrm{Y}}_{\mathrm{k}+1,2},{\mathrm{Y}}_{\mathrm{k}+1,2}^{\prime }\})=\mathrm{\Sigma }(\mathrm{n},\mathrm{k})$. In this paper, we introduce a simple discharging approach and prove this conjecture.

8 pages

References in corpus (1)

• On an extremal problem involving a pair of forbidden posets

Cited by in corpus (1)

• On an extremal problem involving a pair of forbidden posets