Document Open Access Logo

On the Central Levels Problem

Authors Petr Gregor, Ondřej Mička, Torsten Mütze

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.60.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Petr Gregor
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic
Ondřej Mička
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic
Torsten Mütze
  • Department of Computer Science, University of Warwick, Coventry, UK
  • Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic

Funding

This work was supported by the Czech Science Foundation grant GA19-08554S.
  • Mütze, Torsten: was also supported by DFG grant 413902284.

Acknowledgements

We thank Jiří Fink for several valuable discussions about symmetric chain decompositions, and for feedback on an earlier draft of this paper.

Cite AsGet BibTex

Petr Gregor, Ondřej Mička, and Torsten Mütze. On the Central Levels Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.60

Abstract

The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-𝓁 many 1s and at most m+𝓁 many 1s, i.e., the vertices in the middle 2𝓁 levels, has a Hamilton cycle for any m ≥ 1 and 1 ≤ 𝓁 ≤ m+1. This problem was raised independently by Savage, by Gregor and Škrekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case 𝓁 = 1, and classical binary Gray codes, namely the case 𝓁 = m+1. In this paper we present a general constructive solution of the central levels problem. Our results also imply the existence of optimal cycles through any sequence of 𝓁 consecutive levels in the n-dimensional hypercube for any n ≥ 1 and 1 ≤ 𝓁 ≤ n+1. Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the n-dimensional hypercube, n≥ 2, that contains the symmetric chain decomposition constructed by Greene and Kleitman in the 1970s, and we provide a loopless algorithm for computing the corresponding Gray code.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Matchings and factors
Keywords
  • Gray code
  • Hamilton cycle
  • hypercube
  • middle levels
  • symmetric chain decomposition

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. M. Aigner. Lexicographic matching in Boolean algebras. J. Combin. Theory Ser. B, 14:187-194, 1973. Google Scholar
  2. J. Bitner, G. Ehrlich, and E. Reingold. Efficient generation of the binary reflected Gray code and its applications. Comm. ACM, 19(9):517-521, 1976. Google Scholar
  3. B. Bollobás. Combinatorics: set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge University Press, Cambridge, 1986. Google Scholar
  4. M. Buck and D. Wiedemann. Gray codes with restricted density. Discrete Math., 48(2-3):163-171, 1984. URL: https://doi.org/10.1016/0012-365X(84)90179-1.
  5. The Combinatorial Object Server: URL: http://www.combos.org/chains.
  6. N. de Bruijn, C. van Ebbenhorst Tengbergen, and D. Kruyswijk. On the set of divisors of a number. Nieuw Arch. Wiskunde (2), 23:191-193, 1951. Google Scholar
  7. M. El-Hashash and A. Hassan. On the Hamiltonicity of two subgraphs of the hypercube. In Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001), volume 148, pages 7-32, 2001. Google Scholar
  8. P. Erdős and R. K. Guy. Crossing number problems. Amer. Math. Monthly, 80:52-58, 1973. URL: https://doi.org/10.2307/2319261.
  9. L. Faria, C. M. H. de Figueiredo, O. Sýkora, and I. Vrt'o. An improved upper bound on the crossing number of the hypercube. J. Graph Theory, 59(2):145-161, 2008. URL: https://doi.org/10.1002/jgt.20330.
  10. T. Feder and C. Subi. On hypercube labellings and antipodal monochromatic paths. Discrete Appl. Math., 161(10-11):1421-1426, 2013. URL: https://doi.org/10.1016/j.dam.2012.12.025.
  11. J. Fink. Perfect matchings extend to Hamilton cycles in hypercubes. J. Combin. Theory Ser. B, 97(6):1074-1076, 2007. URL: https://doi.org/10.1016/j.jctb.2007.02.007.
  12. J. Fink. Matchings extend into 2-factors in hypercubes. Combinatorica, 39(1):77-84, 2019. URL: https://doi.org/10.1007/s00493-017-3731-8.
  13. Z. Füredi. Problem session. In Kombinatorik geordneter Mengen, Oberwolfach, BRD, 1985. Google Scholar
  14. F. Gray. Pulse code communication, 1953. March 17, 1953 (filed Nov. 1947). U.S. Patent 2,632,058. Google Scholar
  15. C. Greene and D. J. Kleitman. Strong versions of Sperner’s theorem. J. Combin. Theory Ser. A, 20(1):80-88, 1976. Google Scholar
  16. P. Gregor, S. Jäger, T. Mütze, J. Sawada, and K. Wille. Gray codes and symmetric chains. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 66:1-66:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.66.
  17. P. Gregor, O. Mička, and T. Mütze. On the central levels problem. https://arxiv.org/abs/1912.01566. Full preprint version of the present article, 2019. URL: https://arxiv.org/abs/1912.01566.
  18. P. Gregor and T. Mütze. Trimming and gluing Gray codes. Theoret. Comput. Sci., 714:74-95, 2018. URL: https://doi.org/10.1016/j.tcs.2017.12.003.
  19. P. Gregor, T. Mütze, and J. Nummenpalo. A short proof of the middle levels theorem. Discrete Analysis, 2018:8:12 pp., 2018. Google Scholar
  20. P. Gregor and R. Škrekovski. On generalized middle-level problem. Inform. Sci., 180(12):2448-2457, 2010. URL: https://doi.org/10.1016/j.ins.2010.02.009.
  21. J. Griggs, C. E. Killian, and C. D. Savage. Venn diagrams and symmetric chain decompositions in the Boolean lattice. Electron. J. Combin., 11(1):Paper 2, 30 pp., 2004. URL: http://www.combinatorics.org/Volume_11/Abstracts/v11i1r2.html.
  22. I. Havel. Semipaths in directed cubes. In Graphs and other combinatorial topics (Prague, 1982), volume 59 of Teubner-Texte Math., pages 101-108. Teubner, Leipzig, 1983. Google Scholar
  23. H. Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. of Math. (2), 190(3):949-955, 2019. URL: https://doi.org/10.4007/annals.2019.190.3.6.
  24. H. A. Kierstead and W. T. Trotter. Explicit matchings in the middle levels of the Boolean lattice. Order, 5(2):163-171, 1988. URL: https://doi.org/10.1007/BF00337621.
  25. D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011. Google Scholar
  26. S. Locke and R. Stong. Problem 10892: Spanning cycles in hypercubes. Amer. Math. Monthly, 110:440-441, 2003. Google Scholar
  27. T. Mütze. Proof of the middle levels conjecture. Proc. Lond. Math. Soc., 112(4):677-713, 2016. URL: https://doi.org/10.1112/plms/pdw004.
  28. T. Mütze and J. Nummenpalo. A constant-time algorithm for middle levels Gray codes. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2238-2253. SIAM, Philadelphia, PA, 2017. URL: https://doi.org/10.1137/1.9781611974782.147.
  29. N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301-313, 1994. Special issue on circuit complexity (Barbados, 1992). URL: https://doi.org/10.1007/BF01263419.
  30. S. Norine. Edge-antipodal colorings of cubes. The Open Problem Garden. Available at http://www.openproblemgarden.org/op/edge_antipodal_colorings_of_cubes, 2008. URL: http://www.openproblemgarden.org/op/edge_antipodal_colorings_of_cubes.
  31. O. Pikhurko. On edge decompositions of posets. Order, 16(3):231-244 (2000), 1999. URL: https://doi.org/10.1023/A:1006419611661.
  32. F. Ruskey and C. Savage. Hamilton cycles that extend transposition matchings in Cayley graphs of S_n. SIAM J. Discrete Math., 6(1):152-166, 1993. URL: https://doi.org/10.1137/0406012.
  33. F. Ruskey, C. D. Savage, and S. Wagon. The search for simple symmetric Venn diagrams. Notices Amer. Math. Soc., 53(11):1304-1312, 2006. Google Scholar
  34. C. D. Savage. Long cycles in the middle two levels of the Boolean lattice. Ars Combin., 35(A):97-108, 1993. Google Scholar
  35. C. D. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997. URL: https://doi.org/10.1137/S0036144595295272.
  36. C. D. Savage and P. Winkler. Monotone Gray codes and the middle levels problem. J. Combin. Theory Ser. A, 70(2):230-248, 1995. URL: https://doi.org/10.1016/0097-3165(95)90091-8.
  37. J. Shearer and D. J. Kleitman. Probabilities of independent choices being ordered. Stud. Appl. Math., 60(3):271-276, 1979. URL: https://doi.org/10.1002/sapm1979603271.
  38. X. S. Shen and A. Williams. A middle levels conjecture for multiset permutations with uniform-frequency. Williams College Technical Report CSTR-201901. Available at http://tmuetze.de/papers/multiset.pdf, 2019. URL: http://tmuetze.de/papers/multiset.pdf.
  39. H. Spink. Orthogonal symmetric chain decompositions of hypercubes. SIAM J. Discrete Math., 33(2):910-932, 2019. URL: https://doi.org/10.1137/18M1187179.
  40. N. Streib and W. T. Trotter. Hamiltonian cycles and symmetric chains in Boolean lattices. Graphs Combin., 30(6):1565-1586, 2014. URL: https://doi.org/10.1007/s00373-013-1350-8.
  41. I. Tomon. On a conjecture of Füredi. European J. Combin., 49:1-12, 2015. URL: https://doi.org/10.1016/j.ejc.2015.02.026.
  42. D. E. White and S. G. Williamson. Recursive matching algorithms and linear orders on the subset lattice. J. Combin. Theory Ser. A, 23(2):117-127, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact