Decompositions of the Boolean lattice into rank-symmetric chains.

MaRDI QIDQ2629495zbMATH OpenFDO

Authors István Tomon

Publication date 6 July 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.07346, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p53

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Boolean latticeschain decompositionsFüredi conjecturenumbers of symmetric chain partitions

Mathematics Subject Classification ID

Partitions of sets (05A18) Combinatorics of partially ordered sets (06A07) Structure theory of Boolean algebras (06E05)

Abstract: The Boolean lattice $2^{[n]}$ is the power set of $[n]$ ordered by inclusion. A chain $c_{0}subset\mathrm{...}subset{c}_k$ in $2^{[n]}$ is rank-symmetric, if $|c_i|+|c_{k-i}|=n$ for $i=0,\mathrm{...},k$; and it is symmetric, if $|c_i|=(n-k)/2+i$. We show that there exist a bijection ${\displaystyle }$p: [n]^{(geq n/2)} ightarrow [n]^{(leq n/2)}${\displaystyle }$ and a partial ordering $<$ on $[n{]}^{(geqn/2)}$ satisfying the following properties: (i) $subset$ is an extension of $<$ on $[n{]}^{(geqn/2)}$; (ii) if $Csubset[n{]}^{(geqn/2)}$ is a chain with respect to $<$, then $p(C)cupC$ is a rank-symmetric chain in $2^{[n]}$, where $p(C)=p(x):xinC$; (iii) the poset $([n{]}^{(geqn/2)},<)$ has the so called normalized matching property. We show two applications of this result. A conjecture of F"{u}redi asks if $2^{[n]}$ can be partitioned into $$ 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 $$ rank-symmetric chains, each of size $Theta(sqrtn)$.

Review text

Summary: 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\colon [n]^{(\geq n/2)}\to [n]^{(\leq n/2)}\) and a partial ordering \(<\) on \([n]^{(\geq n/2)}\) satisfying the following properties: \(\bullet\) \(\subset\) is an extension of \(<\) on \([n]^{(\geq n/2)}\); \(\bullet\) 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\}\); \(\bullet\) 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 sizes 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.

Recommendations

• On the existence of symmetric chain decompositions in a quotient of the Boolean lattice
• Symmetric Chain Decompositions of Linear Lattices
• Venn diagrams and symmetric chain decompositions in the Boolean lattice
• scientific article; zbMATH DE number 3557853
• Symmetric chain decomposition for cyclic quotients of Boolean algebras and relation to cyclic crystals
• Explicit semisymmetric chain decomposition of the partition lattice
• Long symmetric chains in the Boolean lattice
• scientific article; zbMATH DE number 1873418
• Partitioning Boolean lattices into chains of subsets
• Hamiltonian cycles and symmetric chains in Boolean lattices.

Cites work

• A decomposition theorem for partially ordered sets
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 3065933 (Why is no real title available?)
• Improved bounds on the partitioning of the Boolean lattice into chains of equal size.
• On a conjecture of Füredi.
• On a lemma of Littlewood and Offord on the distribution of certain sums
• Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size
• Partitioning the Boolean lattice into chains of large minimum size
• Proof of a conjecture on partitions of a Boolean lattice
• Some remarks on normalized matching
• Strong versions of Sperner's theorem
• Sufficient Conditions for a Symmetric Chain Order
• The necklace poset is a symmetric chain order

Cited in

(11)

• On the existence of symmetric chain decompositions in a quotient of the Boolean lattice
• Boolean packings in Dowling geometries
• Venn diagrams and symmetric chain decompositions in the Boolean lattice
• Partitioning the Boolean lattice into chains of large minimum size
• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• A note on Boolean lattices and Farey sequences
• Bit complexity of breaking and achieving symmetry in chains and rings
• Symmetric chain decomposition for cyclic quotients of Boolean algebras and relation to cyclic crystals
• Uniform chain decompositions and applications
• The number of symmetric chain decompositions
• The generalized Füredi conjecture holds for finite linear lattices

This page was built for publication: Decompositions of the Boolean lattice into rank-symmetric chains.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629495)