×

Construction of 2-factors in the middle layer of the discrete cube. (English) Zbl 1246.05133

Summary: Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length \(2n+1\) that have exactly \(n\) or \(n+1\) entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit. In this work we present an inductive construction of a large family of 2-factors in the middle layer graph for all \(n\geqslant 1\). We also investigate how the choice of certain parameters used in the construction affects the number and lengths of the cycles in the resulting 2-factor.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

References:

[1] Aigner, M., Lexicographic matching in Boolean algebras, J. Combin. Theory Ser. B, 14, 187-194 (1973) · Zbl 0274.05003
[2] Buck, M.; Wiedemann, D., Gray codes with restricted density, Discrete Math., 48, 2-3, 163-171 (1984) · Zbl 0572.05042
[3] Duffus, D.; Kierstead, H.; Snevily, H., An explicit 1-factorization in the middle of the Boolean lattice, J. Combin. Theory Ser. A, 65, 2, 334-342 (1994) · Zbl 0795.05111
[4] Duffus, D.; Sands, B.; Woodrow, R., Lexicographic matchings cannot form Hamiltonian cycles, Order, 5, 2, 149-161 (1988) · Zbl 0657.05055
[5] Greene, C.; Kleitman, D., Strong versions of Spernerʼs theorem, J. Combin. Theory Ser. A, 20, 1, 80-88 (1976) · Zbl 0361.05015
[6] Havel, I., Semipaths in directed cubes, (Graphs and Other Combinatorial Topics. Graphs and Other Combinatorial Topics, Prague, 1982. Graphs and Other Combinatorial Topics. Graphs and Other Combinatorial Topics, Prague, 1982, Teubner-Texte Math., vol. 59 (1983), Teubner: Teubner Leipzig), 101-108 · Zbl 0528.05030
[7] A. Heindl, Properties of certain 2-factors in the middle layer graph, Bachelor thesis, ETH Zürich, Switzerland, 2011.; A. Heindl, Properties of certain 2-factors in the middle layer graph, Bachelor thesis, ETH Zürich, Switzerland, 2011.
[8] Johnson, J., Long cycles in the middle two layers of the discrete cube, J. Combin. Theory Ser. A, 105, 2, 255-271 (2004) · Zbl 1051.05056
[9] Kierstead, H.; Trotter, W., Explicit matchings in the middle levels of the Boolean lattice, Order, 5, 2, 163-171 (1988) · Zbl 0668.05045
[10] Lovász, L., Problem 11, (Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications Held at the University of Calgary, Calgary, Alberta, Canada, June. Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications Held at the University of Calgary, Calgary, Alberta, Canada, June, Combin. Struct. Appl., vol. 1969 (1970), Gordon and Breach Science Publishers: Gordon and Breach Science Publishers New York), xvi+508 pp
[11] The on-line encyclopedia of integer sequences, sequence A000108 (2011)
[12] The on-line encyclopedia of integer sequences, sequence A002995 (2011)
[13] The on-line encyclopedia of integer sequences, sequence A005354 (2011)
[14] Shimada, M.; Amano, K., A note on the middle levels conjecture (September 2011)
[15] Shields, I.; Shields, B.; Savage, C., An update on the middle levels problem, Discrete Math., 309, 17, 5271-5277 (2009) · Zbl 1178.05058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.