Symmetric chain decompositions of products of posets with long chains

Stefan David¹ ; Hunter Spink² ; Marius Tiba³

¹Trinity College, Cambridge University
²Harvard University
³Trinity Hall, Cambridge University

The electronic journal of combinatorics, Tome 25 (2018) no. 1

Résumé

We ask if there exists a symmetric chain decomposition of the cuboid $Q_k \times n$ such that no chain is taut, i.e. no chain has a subchain of the form $(a_1,\ldots, a_k,0)\prec \cdots\prec (a_1,\ldots,a_k,n-1)$. In this paper, we show this is true precisely when $k \ge 5$ and $n\ge 3$. This question arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this paper unexpectedly resolves the most difficult case of previous work by the second author on almost orthogonal symmetric chain decompositions (2017), making progress on a conjecture of Shearer and Kleitman (1979). In general, we show that for a finite graded poset $P$, there exists a canonical bijection between symmetric chain decompositions of $P \times m$ and $P \times n$ for $m, n\ge rk(P) + 1$, that preserves the existence of taut chains. If $P$ has a unique maximal and minimal element, then we also produce a canonical $(rk(P) +1)$ to $1$ surjection from symmetric chain decompositions of $P \times (rk(P) + 1)$ to symmetric chain decompositions of $P \times rk(P)$ which sends decompositions with taut chains to decompositions with taut chains.

Détail

DOI : 10.37236/7124

Classification : 06A06, 06A07
Mots-clés : symmetric chain decompositions, posets, hypercubes