IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Hamiltonian Cycles and Symmetric Chains in Boolean Lattices

  • Oct. 31, 2012
  • 3:30 p.m.
  • LeConte 312


This is a paper by Noah Streib and William T. Trotter.
Let $B(n)$ be the subset lattice of $\{1,2,\dots,n\}$. Sperner's theorem states that the width of $B(n)$ is equal to the size of its biggest level. There have been several elegant proofs of this result, including an approach that shows that $B(n)$ has a symmetric chain partition. Another famous result concerning $B(n)$ is that its cover graph is Hamiltonian. Motivated by these ideas and by the Middle Two Levels conjecture, they consider posets that have the Hamiltonian Cycle-Symmetric Chain Partition (HC-SCP) property. A poset of width $w$ has this property if its cover graph has a Hamiltonian cycle which parses into $w$ symmetric chains. They show that the subset lattices have the HC-SCP property. I will demonstrate this proof and look more at open questions in the area.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster