A New Combinatorial Gray Code for Balanced Combinations
This research work by Torsten Mütze, Christoph Standke, and Veit Wiechert introduces a new combinatorial Gray code for balanced combinations, focusing on a-element subsets and flaws in Dyck path representation. The study explores various aspects of balanced combinations, their flaws, and the relationship with Catalan numbers. Additionally, it delves into the Chung-Feller theorem, different proofs, and the application of these combinatorial concepts in graph theory to determine the existence of Hamilton cycles in certain vertex-transitive graphs.
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
A new combinatorial Gray code for balanced combinations Torsten M tze joint work with Christoph Standke, Veit Wiechert (TU Berlin)
Balanced combinations balanced combination := a -element subset of Example: bitstring representation: Dyck path representation: flaws = 3
Balanced combinations flaws = 0
Balanced combinations flaws =
Balanced combinations total number = flaws the k-th Catalan number
The Chung-Feller theorem := set of all Dyck paths with 2k steps and e flaws Theorem [Chung, Feller 49]: For any we have . Various alternative proofs (combinatorial, analytic, ) and generalizations appeared over the years: [Hodges 55], [Narayana 67], [Woan 01], [Eu, Fu, Yeh 05], [Chen 08], [Ma, Yeh 09], [Ruckavicka 11],
Proving Chung-Feller [Hodges 55], [Chen 08] Establish a bijection (#flaws increases by 1) Note: differ in many positions and may Is there a simpler proof?
Our results Theorem: There is a bijection such that and differ in only two positions.
Our results Theorem: There is a bijection such that and differ in only two positions. flaws
Our results simple and explicit Theorem: There is a bijection such that and differ in only two positions. simple Theorem: There is an algorithm which for given computes each Dyck path in in time .
Applications Hamilton cycles in certain vertex-transitive graphs: the odd graph and the middle levels graph More generally: For which values of do they have a -factor? Only one general positive answer known: middle levels conjecture [M. 14] This work: two more positive answers Theorem: The odd graph has a -factor. Theorem: The middle levels graph has a -factor. # cycles = (Catalan number)
Combinatorial Gray codes Goal: Generate all objects in a combinatorial class (permutations, subsets, strings, trees, Dyck paths, etc.) such that consecutive objects differ only a little bit Ideally: Generate each new object in time Fundamental task in combinatorial algorithms [Nijenhuis, Wilf 75] [Knuth TAOCP Vol. 4, 11]
Combinatorial Gray codes Examples: Generate all permutations of such that consecutive permutations differ only in one transposition [Johnson 63], [Trotter 62], [Sedgewick 77] Generate all subsets of such that consecutive sets differ in adding/removing one element [Gray 53], [Tootill 56], [Bitner, Ehrlich, Reingold 76], [Wagner, West 91], [Savage, Winkler 95], [Bhat, Savage 96] Generate all many -element subsets of s.t. consecutive sets differ in exchanging one element [Tang, Liu 73], [Bitner, Ehrlich, Reingold 76], [Eades, Hickey, Read 84], [Eades, McKay 84], [Ruskey 88], [Chase 89], [Jenkyns, McCarthy 95], [Ruskey, Williams 09]
Combinatorial Gray codes Examples: Special case : balanced combinations {1, 4,5 } (1,0,0,1,1,0) Generate all many -element subsets of s.t. consecutive sets differ in exchanging one element Only swaps of the form [Eades, McKay 84] 1,0,0,0,0,0 0,0,0,0,0,1 Only distance- 2 swaps [Chase 89], [Jenkyns, McCarthy 95] Only distance-1 swaps [Eades, Hickey, Read 84], [Ruskey 88] (possible iff even and odd, or Constant-time generation [Ehrlich 73], [Bitner, Ehrlich, Reingold 76] 1,0,0 0,0,1 1,0 0,1 )
Combinatorial Gray codes Examples: 1,0 0,1 Only distance-1 swaps [Eades, Hickey, Read 84], [Ruskey 88] (possible iff even and odd, or )
Combinatorial Gray codes Examples: Generate only rooted trees, (=parenthesis expressions, triangulations, binary trees see [Stanley 15]) i i iii iii v v ii ii iv iv ()(()) ()()() (())() (()()) ((())) Constant-time generation [Ruskey, Proskurowski 90], [Walsh 98] Only distance-1 swaps [Bultena, Ruskey 98] (possible iff even or less than 5)
Combinatorial Gray codes i i iii iii v v ii ii iv iv
Combinatorial Gray codes Our minimum-change bijection f is orthogonal to Gray codes from before (01-20 and i-v) i i iii iii v v ii ii iv iv
Definition of Count downsteps starting at Flip -th downstep touching the line Flip first upstep to the left of d touching the line 2 4 3 5 1 d u
Definition of Count downsteps starting at Flip -th downstep touching the line Flip first upstep to the left of d touching the line d u
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d d u u
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d u
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d d u u
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d u
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d u
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d u
Definition of Count downsteps starting at Flip -th downstep touching the line Flip first upstep to the left of d touching the line Definition of Count downsteps starting at Flip -th downstep touching the line Flip first upstep to the right of d touching the line
Definition of Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line Definition of Repeat: Flip first downstep to the left of u touching the line Flip first upstep to the right of d touching the line
Efficient computation Repeat: Flip first downstep to the right of u touching the line Flip first upstep to the left of d touching the line d u Idea: bidirectional pointers Fast navigation along Dyck path to reposition u and d Compute each application of in time below hills and above valleys
