Skipless chain decompositions and improved poset saturation bounds
Time: 14:00 -- Location: LRI, 445
summary: 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 F
of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k (as induced
subposet), but adding any set to F creates an antichain of size k. We use sat(n,k) to denote the smallest
size of such a family. With more work we pinpoint the exact value of sat(n, k), for all k and sufficiently
large n. Previously, exact values for sat(n,k) were only known for k up to 6.
We also show that for any poset P, its induced saturation number (which is defined similar as for the antichain)
grows at most polynomially: sat(n, P)=O(n^c), where c <= |P|²/4+1.
This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.