Date
Tue, 14 Nov 2023
Time
14:00 - 15:00
Location
Online
Speaker
Paul Bastide
Organisation
LaBRI/Utrecht

We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$ (as induced subposet), but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use $\textrm{sat}^{\ast}(n,k)$ to denote the smallest size of such a family. With more work we pinpoint the exact value of $\textrm{sat}^{\ast}(n,k)$, for all $k$ and sufficiently large $n$. Previously, exact values for $\textrm{sat}^{\ast}(n,k)$ were only known for $k$ up to 6. We also show that for any poset $\mathcal{P}$, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: $\textrm{sat}^{\ast}(n, \mathcal{P})=O(n^c)$, where $c \leq |\mathcal{P}|^2/4+1$. This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Please contact us with feedback and comments about this page. Last updated on 27 Oct 2023 10:56.