Séminaire Philippe Flajolet

(ANNULÉ) Skipless chain decompositions and antichain saturation

by Carla Groenland (Université d'Utrecht)




The Boolean lattice is the poset $\{0,1\}^n$ ordered via set inclusion. We show that given disjoint chains $C_1,\dots,C_m$ in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the elements in $\cup_{i=1}^m C_i$ (where we call a chain skipless if any two consecutive elements differ in size by exactly one). This strengthens a result of Lehman-Ron [JCT-A, 2001]. We find a simple proof for the asymptotics of antichain saturation numbers as corollary (resolving various conjectures), and with additional work can even pinpoint most values exactly. This is based on joint work with Paul Bastide, Hugo Jacob and Tom Johnston.