A minimum-change version of the Chung-Feller theorem for Dyck paths

• Published in: Electronic notes in discrete mathematics 2017-08, Vol.61, p.901-907
• Main Authors: Mütze, Torsten, Standke, Christoph, Wiechert, Veit
• Format: Article
• Language: English
• Subjects: Catalan number; Chung-Feller theorem; Dyck path; middle levels graph; odd graph
• ISSN: 1571-0653; 1571-0653
• DOI: 10.1016/j.endm.2017.07.052

A Dyck path of length 2k with e flaws is a path in the integer lattice that starts at the origin and consists of k many ↗-steps and k many ↘-steps that change the current coordinate by (1, 1) or (1, −1), respectively, and that has exactly e many ↘-steps below the line y=0. Denoting by D2ke the set of Dyck paths of length 2k with e flaws, the well-known Chung-Feller theorem asserts that the sets D2k0,D2k1,…,D2kk all have the same cardinality 1k+1(2kk)=Ck, the k-th Catalan number. The standard combinatorial proof of this classical result establishes a bijection f′ between D2ke and D2ke+1 that swaps certain parts of the given Dyck path x, with the effect that x and f′(x) may differ in many positions. In this work we strengthen the Chung-Feller theorem by presenting a simple bijection f between D2ke and D2ke+1 which has the additional feature that x and f(x) differ in only two positions (the least possible number). We also present an algorithm that allows to compute a sequence of applications of f in constant time per generated Dyck path. As an application, we use our minimum-change bijection f to construct cycle-factors in the odd graph O2k+1 and the middle levels graph M2k+1 — two intensively studied families of vertex-transitive graphs — that consist of Ck many cycles of the same length.