Symmetric Chains and Hamilton Cycles in Graph Theory
On symmetric chains and
Hamilton cycles
The Boolean lattice
The Boolean lattice
Chain decompositions
Symmetric chain decompositions
Parenthesis matching
Edge-disjoint and orthogonal SCDs
Edge-disjoint and orthogonal SCDs
Our results
The central levels problem
The central levels problem
Our results
The central levels problem
Open problems
Thank you!
The n-cube is the poset obtained by ordering all subsets of {1,2,...,n} by inclusion. A symmetric chain is a sequence of subsets A_k\subseteq A_{k+1}\subseteq ... \subseteq A_{n-k} with |A_i|=i for all i=k,...,n-k, and a symmetric chain decomposition, or SCD for short, of the n-cube is a partition of all its elements into symmetric chains. There are several known descriptions of SCDs in the n-cube for any n>=1, going back to works by De Bruijn, Aigner, Kleitman and several others. All those constructions, however, yield the very same SCD.
In this talk I will present several new constructions of SCDs in the n-cube.
Specifically, we construct five pairwise edge-disjoint SCDs in the n-cube for all n>=90, and four pairwise orthogonal SCDs for all n>=60, where orthogonality is a slightly stronger requirement than edge-disjointness. Specifically, two SCDs are called orthogonal if any two chains intersect in at most a single element, except the two longest chains, which may only intersect in the unique minimal and maximal element (the empty set and the full set).
This improves the previous best lower bound of three orthogonal SCDs due to Spink, and is another step towards an old problem of Shearer and Kleitman from the 1970s, who conjectured that the n-cube has \lfloor n/2\rfloor+1 pairwise orthogonal SCDs.
We also use our constructions to prove some new results on the central levels problem, a far-ranging generalization of the well-known middle two levels conjecture (now theorem), on Hamilton cycles in subgraphs of the (2n+1)-cube induced by an even number of levels around the middle. Specifically, we prove that there is a Hamilton cycle through the middle four levels of the (2n+1)-cube, and a cycle factor through any even number of levels around the middle of the (2n+1)-cube.
This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively.
Delve into the study of symmetric chains, Hamilton cycles, and Boolean lattices in graph theory. Discover the relationships between chain decompositions, Boolean lattices, and edge-disjoint symmetric chain decompositions, exploring construction methods and properties such as orthogonality. Uncover the significance of these concepts in various applications within the realm of posets and combinatorial mathematics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
On symmetric chains and Hamilton cycles Torsten M tze (based on joint work with Karl D ubel, Sven J ger, Petr Gregor, Joe Sawada, Manfred Scheucher, and Kaja Wille)
The Boolean lattice consider all subsets of ordered by inclusion a fundamental and widely studied poset called -cube -th level := all subsets of cardinality its size is 4-cube
The Boolean lattice consider all subsets of ordered by inclusion a fundamental and widely studied poset called -cube -th level := all subsets of cardinality its size is odd even middle level(s)
Chain decompositions Theorem [Sperner 28]: The width (=size of a maximum antichain) of the -cube is given by the size of its middle level(s) . Theorem [Dilworth 50]: Any poset into can be decomposed many chains. 4-cube chain decomposition
Symmetric chain decompositions useful for applications: symmetric chains, i.e., if a chain starts at level , then it ends at level known constructions of SCDs for the -cube due to [De Bruijn, van Ebbenhorst Tengbergen, Kruiswijk 51], [Lewin 72], [Aigner 73], [White and Williamson 77], [Greene, Kleitman 76] all constructions yield the same SCD not symmetric . 4-cube symmetric chain decomposition (SCD)
Parenthesis matching useful for applications: symmetric chains, i.e., if a chain starts at level , then it ends at level known constructions of SCDs for the -cube due to [De Bruijn, van Ebbenhorst Tengbergen, Kruiswijk 51], [Lewin 72], [Aigner 73], [White and Williamson 77], [Greene, Kleitman 76] all constructions yield the same SCD . parenthesis matching description by [Greene, Kleitman 76] 1001110111 1001110110 1001110100 1001100100 0001100100
Edge-disjoint and orthogonal SCDs Question: Are there other constructions? Definition: Two SCDs are edge-disjoint, if they do not share any edges Definition: Two SCDs are orthogonal, if any two chains intersect in at most one element, except the two longest chains that may only intersect in and 4-cube 4-cube Observe: orthogonal edge-disjoint
Edge-disjoint and orthogonal SCDs Question: How many pairwise edge-disjoint/orthogonal SCDs can we hope for? is an upper bound: even every SCD uses exactly one of those edges Conjecture [Shearer, Kleitman 79]: The -cube has pairwise orthogonal SCDs. Theorem [Shearer, Kleitman 79]: The standard construction and its complements are two orthogonal SCDs. Theorem [Spink 17]: The -cube has three pairwise orthogonal SCDs for .
Our results Theorem 1: The -cube has four pw. orthogonal SCDs for . Theorem 2: The -cube has five pw. edge-disjoint SCDs for . Proof of Theorem 2: Product lemma: If the -cube and -cube have SCDs each, then the -cube has edge-disjoint SCDs. find five edge-disjoint SCDs for dimensions Fact: If and are coprime, then every negative integer multiple of and . edge-disjoint and is a non- computer search in the necklace poset Proof of Theorem 1: similar, but more complicated product lemma due to [Spink 17] find four orthogonal SCDs for dimensions and
The central levels problem -cube Middle levels conjecture: The subgraph of the -cube induced by the middle two levels and has a Hamilton cycle. problem with a long history answered positively in [M. 16] Central levels conjecture: The subgraph of the -cube induced by the middle levels has a Hamilton cycle for any . raised by [Savage 93], [Gregor, krekovski 10], [Shen, Williams 15]
The central levels problem -cube known results: Central levels conjecture: The subgraph of the -cube induced by the middle [Gray 53] [El-Hashash, Hassan 01], [Locke, Stong 03] levels has a Hamilton cycle for any . [Gregor, krekovski 10] ??? [M. 16]
Our results Theorem 3: The -cube has a Hamilton cycle through the middle four levels ( ) for all . Theorem 4: The -cube has a cycle factor through the middle for all and . levels spanning collection of disjoint cycles
The central levels problem Proof: Theorem 4: The -cube has a cycle factor through the middle for all and . levels consider two edge-disjoint SCDs as the dimension is odd, all chains have odd length, even after restricting to middle levels taking every second edge yields two edge-disjoint perfect matchings their union is a cycle factor
Open problems Conjecture [Shearer, Kleitman 79]: The -cube has pairwise orthogonal SCDs. known: four we conjecture that the -cube has pairwise edge- disjoint SCDs. known: five central levels problem: Can the cycles in the factor be joined to a single Hamilton cycle? Structure of the cycle factor? efficient algorithms to generate those cycles first open case: middle six levels exploit new SCD constructions in other applications (Venn diagrams etc.)
