{"entities":{"Q1343173":{"pageid":1353912,"ns":120,"title":"Item:Q1343173","lastrevid":70196124,"modified":"2026-04-13T13:05:31Z","type":"item","id":"Q1343173","labels":{"en":{"language":"en","value":"Covering the hypercube with a bounded number of disjoint snakes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 716347"}},"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":"Q1343173$A0ED4A7B-AE18-40ED-9073-C3704B258FBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"70c2617c27174a2ae40e86a976d4cb91e0595905","datavalue":{"value":{"text":"Covering the hypercube with a bounded number of disjoint snakes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1343173$C840F863-64D5-45FD-980F-B18167B5289C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1cc5e7e6b62664a090bf9811eecb7c7fa77dd30d","datavalue":{"value":"0816.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$C708BC9D-C274-4EC6-82AD-64A1699DF78B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"111abe7f23440bb713f22737fe8b0417e685cfa2","datavalue":{"value":"10.1007/BF01302970","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$9FD6092D-A6CC-4749-8C66-F31DB56DA9D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1fd484f2af753c26a429a14d9fe77eacab579226","datavalue":{"value":{"entity-type":"item","numeric-id":178335,"id":"Q178335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1343173$83B504DF-166A-4645-BE27-5AF91921BB58","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1343173$C330AA99-70CB-47B1-828E-4A8821C55ABD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3500a4e46fbb352dfc230edc76ff040b3b0cc153","datavalue":{"value":{"time":"+1995-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1343173$3587FC2E-F31D-4B53-832B-1F65FBDB9336","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fdceb9676e056fabcec06372286b7e2a7c2137dd","datavalue":{"value":"For any integer \\(d\\geq 2\\), \\(S(d)\\) is the maximum length of an induced cycle -- called a snake -- in the graph of the \\(d\\)-dimensional cube, \\(I[d]\\); the vertex-set of \\(I[d]\\) is endowed in the obvious way with the structure of an additive group \\({\\mathbf Z}^ d_ 2= ({\\mathbf Z}/2{\\mathbf Z})^ d\\). ``An extensive literature has evolved concerning the problem of estimating \\(S(d)\\),'' for which the author presents known bounds. The present paper is concerned with resolving a problem posed by P. Erd\u0151s, of deciding whether there exists an integer \\(k\\) such that, for every \\(d\\geq 2\\), the vertices of \\(I[d]\\) can be covered by at most \\(k\\) snakes; and, if that is the case, whether it an be done in such a way that the snakes are vertex-disjoint.   Theorem 1: For every \\(n\\geq 2\\) there is a subgroup \\({\\mathfrak H}_ n\\subset I[n]\\) and a snake \\(C_ n\\subset I[n]\\), such that \\(|{\\mathfrak H}_ n|\\leq 16\\), and that \\(C_ n\\) contains exactly one element of every coset of \\({\\mathfrak H}_ n\\).   The following corollary solves Erd\u0151s' problem. Corollary 1: For every \\(n\\geq 2\\) the vertices of \\(I[n]\\) can be covered using at most 16 pairwise vertex-disjoint snakes.   Theorem 2: Let \\(k_ 0\\), \\(k_ 1\\), \\(k_ 2\\) respectively be the smallest integers such that, for every \\(n\\geq 2\\), the graph \\(I[n]\\) can be vertex covered by at most \\(k_ 0\\) snakes, by at most \\(k_ 1\\) pairwise vertex- disjoint snakes, and by at most \\(k_ 2\\) pairwise vertex-disjoint snakes of equal length, respectively; let \\(k_ 3\\) be the smallest integer such that, for every \\(n\\geq 2\\), there exist a subgroup \\({\\mathfrak C}_ n\\) and a snake \\(C_ n\\) in \\(I[n]\\), such that \\(|{\\mathfrak H}_ n| \\leq k_ 3\\), where \\(C_ n\\) contains exactly one element of every coset of \\({\\mathfrak H}_ n\\). Then \\(3\\leq k_ 0\\leq k_ 1\\leq k_ 2\\leq k_ 3\\leq 16\\) and \\(k_ 2, k_ 3\\in \\{4,8,16\\}\\). ``The question of determining the exact values of \\(k_ 0\\), \\(k_ 1\\), \\(k_ 2\\), \\(k_ 3\\) remains open''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1343173$742DEB8C-E789-4E80-B49A-EA9E50A09DBA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$1D94052E-87E5-456D-A69F-FAD51A22C778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$A01D639D-658E-4A50-8992-76BE88661ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$61EA44F8-8D57-4B13-B2A2-E61B90B3F3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c3cdafa68da1cd8441c02cae1d4f7b344a92c14","datavalue":{"value":"94B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$29CA694E-89C4-4A34-BC0D-97AF58CC2AB3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0d4ae722794048b526b8eb0c291322c558f200cc","datavalue":{"value":"716347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1343173$B8E07759-7280-40D9-9B94-BDA576D0CDB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e5eae9e3cce2367ef4d7830b1c4c94e17e14744","datavalue":{"value":"snake-in-the-box","type":"string"},"datatype":"string"},"type":"statement","id":"Q1343173$20E6B1BE-E9D6-4707-8E11-93EA456B8D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fbc67145f7e7418c138c0d2a9c7da92fac0589a","datavalue":{"value":"spanned subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1343173$99C0A464-B1A0-4759-9390-3D7058D32826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"993e5ab269789a976ee7a4b9a806b32fe2da4aa9","datavalue":{"value":"spanned cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1343173$1080B0C9-7F84-412E-8CCB-C72636A8346A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9da0149d0c319d7c1f1a71918a64230b4cd4896b","datavalue":{"value":"snake","type":"string"},"datatype":"string"},"type":"statement","id":"Q1343173$5CABC98B-A8BF-49EE-90F5-FE4CE3865A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fe0bbd971503b8d4079e8826b865f9684d8e8a3","datavalue":{"value":"Erd\u0151s' problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1343173$781C1ECE-73E3-4F05-A84B-6D022FF22FC9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1343173$A77F697A-1934-4DBE-8212-400655E6389C","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":"Q1343173$63751CE9-188A-4F5E-B8C5-0B4EBF8369F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"baa415cea0c7c9bbd40a0a1f00bcde9f44ef67e4","datavalue":{"value":{"entity-type":"item","numeric-id":1113920,"id":"Q1113920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1343173$A4FA273A-EAC9-4B95-986E-029BBFC013CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3d796cf1cc76077d411bb067cf5c844a9302d9c","datavalue":{"value":{"entity-type":"item","numeric-id":3991258,"id":"Q3991258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1343173$84CA716B-4933-4957-BC9B-08964FFFA94A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cc5d0d1477bb9a7abe6ccc98f3517c71799a5e7","datavalue":{"value":{"entity-type":"item","numeric-id":1120544,"id":"Q1120544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1343173$21D9E09B-B23D-4E0E-963A-D30BC9ACEEEC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffee4d356355b50d7d25af898aa6abcb5510f6c7","datavalue":{"value":{"entity-type":"item","numeric-id":4261811,"id":"Q4261811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da46397f5793f7b9818c480d5be680cf61f1b139","datavalue":{"value":{"amount":"+0.8683571815490723","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":"Q1343173$27C532B7-F94B-45CD-A1E4-AAC82B25B033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5a9b25ff98c9878a19ef81e4460b31fa386b1b2","datavalue":{"value":{"entity-type":"item","numeric-id":4552238,"id":"Q4552238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86f3952e433364b92bfe036e098e8abb0e0c0c14","datavalue":{"value":{"amount":"+0.864115297794342","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":"Q1343173$2EA5FD83-4EEB-49D0-9231-EAAC460DE249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d92a7df678884e3dfa02c80bda15eb9101c318a6","datavalue":{"value":{"entity-type":"item","numeric-id":1009043,"id":"Q1009043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3025e96f7c6aca8345d4a3a086cbd254ef2fb3f","datavalue":{"value":{"amount":"+0.829104483127594","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":"Q1343173$433760C1-B33D-4415-BECF-221D0BB5F6F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1f4eec7d0a7abf6f530ef238468c52e05b5810c","datavalue":{"value":{"entity-type":"item","numeric-id":4888929,"id":"Q4888929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83f3edd056a399c2f5b9d00be37fadb01a58ce59","datavalue":{"value":{"amount":"+0.8069427013397217","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":"Q1343173$7AC1D763-05DD-4A7A-BF28-78EFE799412A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66032fed1fe0c588be24555ad42a9e05be77b43b","datavalue":{"value":{"entity-type":"item","numeric-id":3991258,"id":"Q3991258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71bc9a017d35ab3b08459f6fa2872ebcb84c96fb","datavalue":{"value":{"amount":"+0.8039534091949463","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":"Q1343173$90250E6A-5F63-49EF-93BD-17E1F301CA0F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Covering the hypercube with a bounded number of disjoint snakes","badges":[]}}}}}