Decompositions of the Boolean lattice into rank-symmetric chains.

István Tomon¹

¹University of Cambridge

The electronic journal of combinatorics, Tome 23 (2016) no. 2

Résumé

The Boolean lattice $2^{[n]}$ is the power set of $[n]$ ordered by inclusion. A chain $c_{0}\subset\cdots\subset c_{k}$ in $2^{[n]}$ is rank-symmetric, if $|c_{i}|+|c_{k-i}|=n$ for $i=0,\ldots,k$; and it is symmetric, if $|c_{i}|=(n-k)/2+i$. We show that there exist a bijection $$p: [n]^{(\geq n/2)}\rightarrow [n]^{(\leq n/2)}$$ and a partial ordering $<$ on $[n]^{(\geq n/2)}$ satisfying the following properties:$\subset$ is an extension of $<$ on $[n]^{(\geq n/2)}$;if $C\subset [n]^{(\geq n/2)}$ is a chain with respect to $<$, then $p(C)\cup C$ is a rank-symmetric chain in $2^{[n]}$, where $p(C)=\{p(x): x\in C\}$;the poset $([n]^{(\geq n/2)},<)$ has the so called normalized matching property.We show two applications of this result.A conjecture of Füredi asks if $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ chains such that the size of any two chains differ by at most 1. We prove an asymptotic version of this conjecture with the additional condition that every chain in the partition is rank-symmetric: $2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ rank-symmetric chains, each of size $\Theta(\sqrt{n})$.Our second application gives a lower bound for the number of symmetric chain partitions of $2^{[n]}$. We show that $2^{[n]}$ has at least $2^{\Omega(2^{n}\log n/\sqrt{n})}$ symmetric chain partitions.

Détail

DOI : 10.37236/5328

Classification : 06A07, 05A18, 06E05
Mots-clés : chain decompositions, Boolean lattices, numbers of symmetric chain partitions, Füredi conjecture