{"entities":{"Q1648667":{"pageid":1659408,"ns":120,"title":"Item:Q1648667","lastrevid":68134974,"modified":"2026-04-12T21:40:23Z","type":"item","id":"Q1648667","labels":{"en":{"language":"en","value":"Extending perfect matchings to Gray codes with prescribed ends"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6895339"}},"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":"Q1648667$19D14FD3-F8F6-4BED-832A-D925171AC165","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e49399f21740e96047b692bbcd42d484956d3c62","datavalue":{"value":{"text":"Extending perfect matchings to Gray codes with prescribed ends","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1648667$B8E6BC57-363C-4E12-8F31-8CB41CC94875","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"73e8ba166bb0f18141db42f8a0f719ce6f5d4fda","datavalue":{"value":"1391.05145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$892366DF-7A02-4D3D-B784-3B69F5A06DC4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7371863d74d7748be96f842909a66fecfc2118d9","datavalue":{"value":{"entity-type":"item","numeric-id":313800,"id":"Q313800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$6DF8144E-16CE-4998-9680-DB3450BBB3DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f19b3589474c6c0aabb75192a38fd5bfd57589d","datavalue":{"value":{"entity-type":"item","numeric-id":1648666,"id":"Q1648666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$DBBDAC2F-4C90-4F64-83B6-29EEE3D03461","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e5a7d23e1fff54ee9ed9fd3c409e41120ec5166","datavalue":{"value":{"entity-type":"item","numeric-id":181824,"id":"Q181824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$9022693D-58AD-43D4-A433-345EEDDBCC1A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$7AA1F346-6421-47AE-B7D7-BAA192500586","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c8a780e74b0fc20f5c27aee56d09c8997e1b03d9","datavalue":{"value":{"time":"+2018-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1648667$2611F877-E357-404E-9A90-E07777383DB1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"17831a718cb5833069adbb9deb16eaec10e8d689","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p56","type":"string"},"datatype":"url"},"type":"statement","id":"Q1648667$132219AB-6AD2-4B18-AF16-128EC4E481CA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6f2394ff0c8813c3e3e49d68272b0a83093afb2","datavalue":{"value":"Summary: A \\textit{binary (cyclic) Gray code} is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube. Fink showed that every perfect matching in the \\(n\\)-dimensional hypercube \\(Q_n\\) can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the ``path version'' of this problem. Namely, we characterize when a perfect matching in \\(Q_n\\) extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in \\(Q_n\\) with two faulty vertices extends to a Hamiltonian cycle. In both cases we show that for all dimensions \\(n\\geq 5\\) the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras' conjecture with an additional edge, or with two faulty vertices. The proof for the case \\(n=5\\) is computer-assisted.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1648667$0734E5A1-1AD5-4692-B808-1EF652E5CA7E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$45958E57-93A5-49D7-87D1-BCA6B74513E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$F04AD388-5D4D-4183-9213-D918D8BBC08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$BD99C5E6-785A-463C-B17F-2BFFC68088DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c3cdafa68da1cd8441c02cae1d4f7b344a92c14","datavalue":{"value":"94B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$FD280BE1-DD3D-4030-B307-08B85319FD25","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"78d09fffd591735d9d36925256c7b92774c2205a","datavalue":{"value":"6895339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$4B455819-9BDC-4826-B953-27DC67027CE5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c6a30f1d61ad21ecc700783ee1edecda48647b4","datavalue":{"value":"gray code","type":"string"},"datatype":"string"},"type":"statement","id":"Q1648667$DCB4AFD1-CA39-478A-9FCB-43BBB2C4A156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1648667$435726A3-058F-4BB3-B114-7072D35B4C00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1648667$D4AC9470-ABC4-4D0A-88F4-44361D8EB90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1648667$43C687F4-2A27-47A9-A3CF-2A168D5365AE","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":"Q1648667$D628C344-93A5-4C3C-A97A-315038867F84","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9facd6bf179c09abf58a2aca3f4f679895da64d8","datavalue":{"value":{"entity-type":"item","numeric-id":5249239,"id":"Q5249239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$9E752908-6325-4174-8F49-9C348DFDDC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d33977161aafb5869d729cab0760b9e6e3424f0","datavalue":{"value":{"entity-type":"item","numeric-id":3575463,"id":"Q3575463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$8F500414-11D8-4BEC-B0A8-72C5793F526B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4302eb5386efa60e8366f1bf0fdd12fb6197e7c0","datavalue":{"value":{"entity-type":"item","numeric-id":2965984,"id":"Q2965984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$0FB4F4E8-1CB8-4FB2-A3CB-633A986D676C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1d147f9b3490dfcb11ddf26a42015d1ed8f279","datavalue":{"value":{"entity-type":"item","numeric-id":5317603,"id":"Q5317603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$BD560164-6754-4338-BF55-73757A0E843D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc71e372b22dcdf0d97f4235d5ed7340c6b95c5e","datavalue":{"value":{"entity-type":"item","numeric-id":2370437,"id":"Q2370437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$CCD121E7-B2FC-432B-BD90-46614229BCE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78279e73072d78cce6073bf61221318bc46e9e23","datavalue":{"value":{"entity-type":"item","numeric-id":3503505,"id":"Q3503505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$EDC71279-44DB-4465-A225-147D3AE0EA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c492f05ca7a2d3e759cd24ceebdf9cf80e7d3f0e","datavalue":{"value":{"entity-type":"item","numeric-id":4995564,"id":"Q4995564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$2D3B03DE-E6CE-46D9-ABF9-E00EED9B1C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c16c74707e58e9a17e7e18d05765e77f5b5f601e","datavalue":{"value":{"entity-type":"item","numeric-id":2384812,"id":"Q2384812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$B8B964DB-2645-476D-A6FE-BE6AE57C40B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a8c5c5ab4906faa639434c5044072a34e9ae41d","datavalue":{"value":{"entity-type":"item","numeric-id":2416511,"id":"Q2416511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$2DC893F0-42E1-4642-A866-971E09F9287F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c79e0895cef6511a66f2f69942b4b62dbc4d4823","datavalue":{"value":{"entity-type":"item","numeric-id":2957449,"id":"Q2957449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$58EE4EC2-A6B3-4298-9B9E-32669069876A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68041717de1564ba012c3c208c67edde4ad3853a","datavalue":{"value":{"entity-type":"item","numeric-id":4881930,"id":"Q4881930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$AC09702D-749A-4EB0-8F0F-4E2495A5D703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b34f9ed40602bc2d4d97a5dd99fa2168dd1771ee","datavalue":{"value":{"entity-type":"item","numeric-id":2809275,"id":"Q2809275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$F396E550-6671-401A-811A-E0DB8F06B086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2acab5496037dde549c2eaf86963c22cab5772d2","datavalue":{"value":{"entity-type":"item","numeric-id":5285944,"id":"Q5285944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$86C79F46-8D79-40BB-B696-B4BB79524A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d676e7da7d14f9f76edbc14b8dcd731caa5f6a5c","datavalue":{"value":{"entity-type":"item","numeric-id":4376203,"id":"Q4376203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$89939381-B16B-43EB-823F-E3D8CD510437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f579190918e5c18124d34994d1e771d8f6ab506","datavalue":{"value":{"entity-type":"item","numeric-id":3583324,"id":"Q3583324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$D7E9F8BC-A014-4284-ACD3-F73B8000F387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a6ad199dd3f593b95670cce3461b252537c4be","datavalue":{"value":{"entity-type":"item","numeric-id":394540,"id":"Q394540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$9990D50B-55FD-4C0E-A8F3-DE5DA5D59438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dfbf73412638994d8a2e6fee9a6b1a410952695","datavalue":{"value":{"entity-type":"item","numeric-id":2360872,"id":"Q2360872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$919AC02F-559A-495D-9ED0-CBC445ACB018","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1be78fecce1324515fcc380cdd6d83dc1b033da2","datavalue":{"value":"bafkreiepv6qpib5mbsnitx3ddssxexl32ep57iz5jgkcmqerhbg74wa7zq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1648667$455DB80E-0A58-46C8-8F9B-67511FAA615D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8bf42d0fd66acf369e3d5d44d7ebef6adc7ae452","datavalue":{"value":{"entity-type":"item","numeric-id":56651,"id":"Q56651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1648667$B0A2B486-7D0E-4224-B87B-3CA6EB4CA103","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f660dd93352e771e0a163b51b95c77a47c0214a5","datavalue":{"value":{"entity-type":"item","numeric-id":3575463,"id":"Q3575463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db12f713e93be67eb02dcda3d90067606d85d756","datavalue":{"value":{"amount":"+0.8950788974761963","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":"Q1648667$B1A5EB82-5E5C-4235-ACEF-9DDCCEBD6597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"866edea512f85f03c6510b7b49e2f743cc7a00f4","datavalue":{"value":{"entity-type":"item","numeric-id":4995564,"id":"Q4995564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c3377fb37b58eaaa7d769dfbeffdf335a6e0aac","datavalue":{"value":{"amount":"+0.8784961104393005","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":"Q1648667$1DC4B393-9946-42DB-A3BD-A07F8F9EA681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab66bc32536a27450a84fd922457fd20dda4300c","datavalue":{"value":{"entity-type":"item","numeric-id":3466243,"id":"Q3466243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"143922adec8f5e4fc525ff04dab1d889ae308ffb","datavalue":{"value":{"amount":"+0.8370165824890137","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":"Q1648667$7A4741B6-AA0A-4B6B-B22D-75BCBB17344D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706497c02c2e4c8f2aa974f306b25511b4890aff","datavalue":{"value":{"entity-type":"item","numeric-id":394540,"id":"Q394540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f73e35e695dc6acdd5f5ecda67182b49db5ea03","datavalue":{"value":{"amount":"+0.8341642022132874","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":"Q1648667$12D5DC35-FD0E-4E24-AFC5-2F34632B5A97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5fd36baa33f6bbf92a3a9bc0f752a9abad9f67b","datavalue":{"value":{"entity-type":"item","numeric-id":2189829,"id":"Q2189829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71255c28e21b2d31a9a63f434db430f86a30c9bb","datavalue":{"value":{"amount":"+0.8274387717247009","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":"Q1648667$16434143-2D96-4033-ABB5-03D3594CDEDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extending perfect matchings to Gray codes with prescribed ends","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extending_perfect_matchings_to_Gray_codes_with_prescribed_ends"}}}}}