{"entities":{"Q1850485":{"pageid":1861227,"ns":120,"title":"Item:Q1850485","lastrevid":74152668,"modified":"2026-04-14T18:37:23Z","type":"item","id":"Q1850485","labels":{"en":{"language":"en","value":"Kneser graphs are Hamiltonian for \\(n\\geq 3k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1843716"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$7C0D19F0-A67E-4186-AB19-74C87FB1F9C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e5cd772cf8f8a46918f2426fed8eabdaf2c3c334","datavalue":{"value":{"text":"Kneser graphs are Hamiltonian for \\(n\\geq 3k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1850485$9D8DA76B-EFB1-465D-A8FB-747E956E56A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85f7d96cf50dccb2f4d5f24131acafa5d8ec37df","datavalue":{"value":"1024.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$9231626C-9407-4B32-8C42-E8CAB80EBE77","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5930602292af1440790a50816317fede1b408e76","datavalue":{"value":{"entity-type":"item","numeric-id":844221,"id":"Q844221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$2F5344AD-B0E5-47FC-AE7E-37C31C58B009","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$2E582B64-0C26-40B6-89DD-EB240019DDD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41f50e6d48cb83c0777ccfeab26a53b6ee6f8dc2","datavalue":{"value":{"time":"+2002-12-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1850485$3AABE891-11C5-4B17-80F9-489EB4DC3CF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0128adccf29b65e400506636fdda7748fa68777f","datavalue":{"value":"The Kneser graph \\(K(n, k)\\) has as vertices the \\(k\\)-subsets of \\([n]= \\{1,2,\\dots, n\\}\\). Two vertices are adjacent if the \\(k\\)-subsets are disjoint. The Kneser graph \\(K(2k- 1, k-1)\\) is also called the odd graph \\(O_k\\) for \\(k\\geq 2\\). Meredith and Lloyd showed that \\(O_k\\) is Hamiltonian for \\(4\\leq k\\leq 7\\). They conjectured that \\(O_k\\) for \\(k\\neq 3\\) is an edge-disjoint union of Hamiltonian cycles plus, perhaps, a 1-factor. We prove that the Kneser graph \\(K(n, k)\\) is Hamiltonian for \\(n\\geq 3k\\).   The bipartite Kneser graph \\(H(n, k)\\) has as its partite sets the \\(k\\)- and \\((n-k)\\)-subsets of \\([n]\\), respectively. Two vertices from different partite sets are adjacent if the \\(k\\)-subset is contained in the \\((n- k)\\)-subset. Consider a hotel with \\(k\\) customers in the lobby and \\((k+1)\\) customers outside, separated by a revolving door. One customer can pass through the door at a time. P. Erd\u0151s (also H\u00e1vel, Kelly) conjectured that by adding or removing one customer at a time, it is possible to cycle through the subsets consisting of \\(k\\) or \\(k+ 1\\) customers in the lobby. Each subset occurs exactly once, and then the last transition restores the original subset.   Savage and Shields showed that \\(H(2k+ 1, k)\\) is Hamiltonian for \\(k\\leq 15\\), and that \\(H(2k+ 1, k)\\) has a cycle of length at least as large as 86\\% of the number of vertices. We prove that the bipartite Kneser graph \\(H(n, k)\\) is Hamiltonian for \\(n> 3k\\), and \\(H(3k, k)\\) is Hamiltonian when \\({3k\\choose k}\\) is odd.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850485$B025B32E-3F40-47EB-9631-96D3772F6221","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"39a7d342c26e9c51a26b2dd58ca05e7a15147f88","datavalue":{"value":{"entity-type":"item","numeric-id":844221,"id":"Q844221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$A3876285-766C-4B4F-B0BA-8E8BEB554528","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$89BAB3BB-80E0-4F0E-9B31-A3567C74E312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$647DEE67-04AB-4EFE-ACA4-F9DA7667C196","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9b312ae286341bfa51698d2ceab42da5e6ec2a7a","datavalue":{"value":"1843716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$6F522B3F-A500-4DB7-A276-648398CB1B80","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab5133c5e6da555003290f59935b056e1363b07e","datavalue":{"value":"antipodal layer problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850485$8F4AE00C-E307-48CE-B2BA-63639D8BA994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa8a30ad74939d539f91080a0dfdc10278d4afb1","datavalue":{"value":"Gray code","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850485$606AC77B-FE88-4549-A9AD-E1896186769D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c629efb8ad2bf5dc8114e1f507b7ab98beaca6b1","datavalue":{"value":"uniform subset graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850485$19C3C944-1018-420C-A5AB-4BEFE7F517E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"862b3f9bd3562fb19afcb46cb40fc8fc3f64ed24","datavalue":{"value":"Hamiltonian cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850485$3F44AB2B-C0CF-4F27-93B8-D7B47F2B605A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9108b096adbf91d4835ead26c01d87ae0286031a","datavalue":{"value":"Erd\u0151s revolving door problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850485$13F80649-C6D8-42A9-9214-93277D72A3DD","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$8866187D-0D8A-444B-BC22-A758B86AE80D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"209d33d70f9b9fb8dfae78e4b42981b592de8bfc","datavalue":{"value":"https://doi.org/10.1006/jctb.2000.1969","type":"string"},"datatype":"url"},"type":"statement","id":"Q1850485$9274EAD6-F4A2-4BDD-9AF5-C68E27B9C9C9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"72b9933566e83e58d8533dbb8e2cbae22a888ac4","datavalue":{"value":"W1973089617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$3BD8BE76-FCEE-4038-B974-CA5122EA9BCF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a1486c1e496ecec6ff9fb8b7df9d7223380b3b11","datavalue":{"value":"Q29398606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$830407EF-01E7-4643-9497-417BD4D67758","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8701f054f591313fb9dd2b97ec59f53b967bbb0","datavalue":{"value":{"entity-type":"item","numeric-id":4063504,"id":"Q4063504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$13E0FFFE-9F44-44FA-8510-11E36F471B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05bb930a3df0b5a385982d39656a3ae0d7229c9a","datavalue":{"value":{"entity-type":"item","numeric-id":1071032,"id":"Q1071032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$9AD38803-E62F-41CE-9925-AB2D407A7D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ee4b5aec7c57f1369b27ad508e8d6185d4489d","datavalue":{"value":{"entity-type":"item","numeric-id":2551113,"id":"Q2551113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$77B37295-9357-4CD4-93FF-5A94EBD66999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0059b76c404e7903b11727066f797ec0819c4754","datavalue":{"value":{"entity-type":"item","numeric-id":1924237,"id":"Q1924237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$1DFFC3D4-D2EC-4EE6-8DF0-4CD528C571C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"189f5d02b4be4ac87cc8f90e4616676e6faedcd8","datavalue":{"value":{"entity-type":"item","numeric-id":1112063,"id":"Q1112063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$79CEEA0B-26E5-4CC5-AAF4-F59CF532BDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6bb1e230c3abec46120c825d9adb061eba817d3","datavalue":{"value":{"entity-type":"item","numeric-id":3691702,"id":"Q3691702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$353FDAB1-1DCA-49FE-BD79-DEE2C23DAAFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"463fb07a6cc778b3635ec98c9fa6bfdff90c2dbd","datavalue":{"value":{"entity-type":"item","numeric-id":3309859,"id":"Q3309859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$1181B7DE-094C-4279-84C1-E4A6225E8514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4fb422bf00986ef8bf56a35baa7941aba1bf640","datavalue":{"value":{"entity-type":"item","numeric-id":4166784,"id":"Q4166784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$95D39CED-968F-4C09-9FBE-BDE946019246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05a712983657eae1c618a992c9f42063a2ca4fdc","datavalue":{"value":{"entity-type":"item","numeric-id":1322186,"id":"Q1322186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$AE748432-6FEA-4985-836E-7433F7FEDF09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04f6b48c7d40d583870fce57ac9f2f9f5dee7100","datavalue":{"value":{"entity-type":"item","numeric-id":1844854,"id":"Q1844854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$8476A37E-F3EB-4D59-904B-B50DC5C458A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe1c181ee737cb3d296b4e4aa677f751364b7c40","datavalue":{"value":{"entity-type":"item","numeric-id":4949820,"id":"Q4949820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$84F3823B-2872-48F8-8795-CD37EAD03E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f93c05d1ab03356b0078a69599ea1c75bbf98953","datavalue":{"value":{"entity-type":"item","numeric-id":1805053,"id":"Q1805053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$2DC273D5-B6FE-4000-907F-3924F4F2AF45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b6c7ff177ef70c7cb6f4da0013ad16eadd3ebe","datavalue":{"value":{"entity-type":"item","numeric-id":4305546,"id":"Q4305546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850485$1258FC28-CAE4-494D-8835-9DDBFDC12868","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"e09d4ddafbd816e550cd0d7d5c1ec4e876724020","datavalue":{"value":"journals/jct/Chen00a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$A3FF4B9A-32EA-4396-94F1-DA54FED5971B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"98d5b368ef0a97358a7033c7e28f8ed48fe8e432","datavalue":{"value":"10.1006/JCTB.2000.1969","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850485$03F1379F-3279-4795-9CA5-F37E78500F94","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7675d62f2de29bb6047bc415ebb8500ad084122","datavalue":{"value":{"entity-type":"item","numeric-id":5890906,"id":"Q5890906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a08b1b06efecbbf868ac65dc1f586f7dd3f6d3e8","datavalue":{"value":{"amount":"+0.904930591583252","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1850485$41E914CA-0D0B-423E-B9A7-429EADDDFFC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9abddc2d0b9293c601d922b0e7c2ab08672094d6","datavalue":{"value":{"entity-type":"item","numeric-id":5006324,"id":"Q5006324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e96e44e24de72834ac4a64031d6c15689bce454","datavalue":{"value":{"amount":"+0.9022971391677856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1850485$4437727A-BF38-4904-8C19-3155BB16B005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6d7d297f25a1c52d22143ad684a242a92348be7","datavalue":{"value":{"entity-type":"item","numeric-id":5230348,"id":"Q5230348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c922d0b4a275879a9ecb701936190aecdf37cf48","datavalue":{"value":{"amount":"+0.8880805373191833","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1850485$2F946EE1-60CA-4D1D-904F-4447E68BE237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b669b57c63acd5637ebbe2589f9e1c2339bff43","datavalue":{"value":{"entity-type":"item","numeric-id":1603265,"id":"Q1603265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79ca7ae282e9373550204e643c1f86c1123a9cf4","datavalue":{"value":{"amount":"+0.8827060461044312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1850485$ED801653-3A5E-4EB5-9C71-56E49F96DF97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd0b90a6a5a5c0c92d70cbb537934c3fd6526048","datavalue":{"value":{"entity-type":"item","numeric-id":2032752,"id":"Q2032752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79ca7ae282e9373550204e643c1f86c1123a9cf4","datavalue":{"value":{"amount":"+0.8827060461044312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1850485$1B11824A-D4FE-49F0-9785-765847AA6339","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Kneser graphs are Hamiltonian for \\(n\\geq 3k\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Kneser_graphs_are_Hamiltonian_for_%5C(n%5Cgeq_3k%5C)"}}}}}