A simple proof for a forbidden subposet problem

Ryan R. Martin¹ ; Abhishek Methuku² ; Andrew Uzzell³ ; Shanise Walker¹

¹Iowa State University
²Central European University
³Grinnell College

The electronic journal of combinatorics, Tome 27 (2020) no. 1

Résumé

The poset $Y_{k, 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, 2}$ is the dual poset of $Y_{k, 2}$. The sum of the $k$ largest binomial coefficients of order $n$ is denoted by $\Sigma(n,k)$. Let $\mathrm{La}^{\sharp}(n,\{Y_{k, 2}, Y'_{k, 2}\})$ be the size of the largest family $\mathcal{F} \subset 2^{[n]}$ that contains neither $Y_{k,2}$ nor $Y'_{k,2}$ as an induced subposet. Methuku and Tompkins proved that $\mathrm{La}^{\sharp}(n, \{Y_{2,2}, Y'_{2,2}\}) = \Sigma(n,2)$ for $n \ge 3$ and conjectured the generalization that if $k \ge 2$ is an integer and $n \ge k+1$, then $\mathrm{La}^{\sharp}(n, \{Y_{k,2}, Y'_{k,2}\}) = \Sigma(n,k)$. On the other hand, it is known that $\mathrm{La}^{\sharp}(n, Y_{k,2})$ and $\mathrm{La}^{\sharp}(n, Y'_{k,2})$ are both strictly greater than $\Sigma(n,k)$. In this paper, we introduce a simple approach, motivated by discharging, to prove this conjecture.

Détail

DOI : 10.37236/7680

Classification : 05D05
Mots-clés : forbidden subposet, extremal set theory, cycle method, Sperner theory