{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:53Z","timestamp":1750221233197,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/17\/D\/ST1\/00585"],"award-info":[{"award-number":["2015\/17\/D\/ST1\/00585"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188834","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"912-919","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Sparse Kneser graphs are Hamiltonian"],"prefix":"10.1145","author":[{"given":"Torsten","family":"M\u00fctze","sequence":"first","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Jerri","family":"Nummenpalo","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Poland"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"3","article-title":"Chemical graphs. XIII. Combinatorial patterns","volume":"17","author":"Balaban A. T.","year":"1972","unstructured":"A. T. Balaban . 1972 . Chemical graphs. XIII. Combinatorial patterns . Rev. Roumain Math. Pures Appl. 17 , 1 (1972), 3 \u2013 16 . A. T. Balaban. 1972. Chemical graphs. XIII. Combinatorial patterns. Rev. Roumain Math. Pures Appl. 17, 1 (1972), 3\u201316.","journal-title":"Rev. Roumain Math. Pures Appl."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90023-7"},{"key":"e_1_3_2_2_3_1","volume-title":"Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday)","author":"Baranyai Zs.","year":"1975","unstructured":"Zs. Baranyai . 1975 . On the factorization of the complete uniform hypergraph. In Infinite and finite sets (Colloq ., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday) , Vol. I . North-Holland, Amsterdam, 91\u2013108. Colloq. Math. Soc. J\u00e1nos Bolyai , Vol. 10. Zs. Baranyai. 1975. On the factorization of the complete uniform hypergraph. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. I. North-Holland, Amsterdam, 91\u2013108. Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 10."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32775.x"},{"key":"e_1_3_2_2_5_1","unstructured":"M. \u010cadek M. Kr\u010d\u00e1l J. Matou\u0161ek F. Sergeraert L. Vok\u0159\u00ednek and U. Wagner. 2014.  M. \u010cadek M. Kr\u010d\u00e1l J. Matou\u0161ek F. Sergeraert L. Vok\u0159\u00ednek and U. Wagner. 2014."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597629"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488683"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90044-X"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1969"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00040-6"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200007"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.0089"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"crossref","unstructured":"P. Erd\u0151s C. Ko and R. Rado. 1961. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) 12 (1961) 313\u2013320.  P. Erd\u0151s C. Ko and R. Rado. 1961. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) 12 (1961) 313\u2013320.","DOI":"10.1093\/qmath\/12.1.313"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2002.11919930"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"P. Gregor T. M\u00fctze and J. Nummenpalo. 2017. A short proof of the middle levels theorem. (2017).  P. Gregor T. M\u00fctze and J. Nummenpalo. 2017. A short proof of the middle levels theorem. (2017).","DOI":"10.19086\/da.3659"},{"key":"e_1_3_2_2_16_1","unstructured":"To appear in Discrete Analysis. arXiv:1710.08249.  To appear in Discrete Analysis. arXiv:1710.08249."},{"key":"e_1_3_2_2_17_1","unstructured":"K. Heinrich and W. D. Wallis. 1978.  K. Heinrich and W. D. Wallis. 1978."},{"key":"e_1_3_2_2_18_1","volume-title":"89\u201398","author":"Austral J.","year":"1978","unstructured":"Hamiltonian cycles in certain graphs. J. Austral . Math. Soc. Ser. A 26, 1 ( 1978 ), 89\u201398 . Hamiltonian cycles in certain graphs. J. Austral. Math. Soc. Ser. A 26, 1 (1978), 89\u201398."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2620160"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118237.3118550"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2003.11.004"},{"key":"e_1_3_2_2_22_1","unstructured":"J. R. Johnson. 2009.  J. R. Johnson. 2009."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.11.004"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"J. R. Johnson. 2011.  J. R. Johnson. 2011.","DOI":"10.1002\/ltl.466"},{"key":"e_1_3_2_2_25_1","volume-title":"Paper 189, 12 pages","author":"Combin J.","year":"2011","unstructured":"An inductive construction for Hamilton cycles in Kneser graphs. Electron. J. Combin . 18, 1 ( 2011 ), Paper 189, 12 pages . An inductive construction for Hamilton cycles in Kneser graphs. Electron. J. Combin. 18, 1 (2011), Paper 189, 12 pages."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-004-3344-x"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_2_28_1","unstructured":"D. E. Knuth. 2011.  D. E. Knuth. 2011."},{"volume-title":"Combinatorial Algorithms. Part 1","author":"A.","key":"e_1_3_2_2_29_1","unstructured":"The Art of Computer Programming. Vol. 4 A. Combinatorial Algorithms. Part 1 . Addison-Wesley , Upper Saddle River, NJ. xv+883 pages. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ. xv+883 pages."},{"key":"e_1_3_2_2_30_1","volume-title":"Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf.","author":"Lov\u00e1sz L.","year":"1970","unstructured":"L. Lov\u00e1sz . 1970 . Problem 11 . In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf. , Calgary, Alberta , 1969). Gordon and Breach, New York. L. Lov\u00e1sz. 1970. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alberta, 1969). Gordon and Breach, New York."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90066-6"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0011-1"},{"key":"e_1_3_2_2_34_1","volume-title":"Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst.","author":"Meredith G. H. J.","year":"1972","unstructured":"G. H. J. Meredith and E. K. Lloyd . 1972. The Hamiltonian graphs O 4 to O 7 . In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst. , Oxford , 1972 ). Inst. Math. Appl., Southend-on-Sea, 229\u2013236. G. H. J. Meredith and E. K. Lloyd. 1972. The Hamiltonian graphs O 4 to O 7. In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Inst. Math. Appl., Southend-on-Sea, 229\u2013236."},{"key":"e_1_3_2_2_35_1","unstructured":"G. H. J. Meredith and E. K. Lloyd. 1973.  G. H. J. Meredith and E. K. Lloyd. 1973."},{"key":"e_1_3_2_2_36_1","volume-title":"Theory Ser. B 15","author":"Combin J.","year":"1973","unstructured":"The footballers of Croam. J. Combin . Theory Ser. B 15 ( 1973 ), 161\u2013166. The footballers of Croam. J. Combin. Theory Ser. B 15 (1973), 161\u2013166."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdw004"},{"volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. 2238\u20132253","author":"M\u00fctze T.","key":"e_1_3_2_2_38_1","unstructured":"T. M\u00fctze and J. Nummenpalo . 2017. A constant-time algorithm for middle levels Gray codes . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. 2238\u20132253 . T. M\u00fctze and J. Nummenpalo. 2017. A constant-time algorithm for middle levels Gray codes. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. 2238\u20132253."},{"key":"e_1_3_2_2_39_1","unstructured":"T. M\u00fctze J. Nummenpalo and B. Walczak. 2017.  T. M\u00fctze J. Nummenpalo and B. Walczak. 2017."},{"key":"e_1_3_2_2_40_1","unstructured":"Sparse Kneser graphs are Hamiltonian. (Nov 2017). arXiv:1711.01636.  Sparse Kneser graphs are Hamiltonian. (Nov 2017). arXiv:1711.01636."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.11.003"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3434-6"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175307"},{"key":"e_1_3_2_2_45_1","first-page":"13","article-title":"A note on Hamilton cycles in Kneser graphs","volume":"40","author":"Shields I.","year":"2004","unstructured":"I. Shields and C. D. Savage . 2004 . A note on Hamilton cycles in Kneser graphs . Bull. Inst. Combin. Appl. 40 (2004), 13 \u2013 22 . I. Shields and C. D. Savage. 2004. A note on Hamilton cycles in Kneser graphs. Bull. Inst. Combin. Appl. 40 (2004), 13\u201322.","journal-title":"Bull. Inst. Combin. Appl."},{"key":"e_1_3_2_2_46_1","unstructured":"R. P. Stanley. 1999.  R. P. Stanley. 1999."},{"volume-title":"Cambridge Studies in Advanced Mathematics","key":"e_1_3_2_2_47_1","unstructured":"Enumerative combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics , Vol. 62 . Cambridge University Press , Cambridge . xii+581 pages. Enumerative combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics, Vol. 62. Cambridge University Press, Cambridge. xii+581 pages."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188834","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":47,"alternative-id":["10.1145\/3188745.3188834","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188834","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}