{"entities":{"Q782941":{"pageid":784790,"ns":120,"title":"Item:Q782941","lastrevid":64340103,"modified":"2026-04-11T19:11:25Z","type":"item","id":"Q782941","labels":{"en":{"language":"en","value":"Bounded degree spanners of the hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7225780"}},"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":"Q782941$192D6B86-9EED-4EA7-9E5E-77CC192D4CD6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e10b708013bae7cec6f724b15a26322cd00bd999","datavalue":{"value":{"text":"Bounded degree spanners of the hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q782941$CC3C230E-0892-4539-A89B-742ABAC78A6F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e487168e163c76af9cb12fbb899c7d4418e034c2","datavalue":{"value":"1444.05103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$B4BB721E-1FC5-4057-8BB8-D28358D732C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4ca316f0d17e23d6fdb1a6102a2bf05627e5db3","datavalue":{"value":"10.37236/9074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$6488F194-4DC4-4DBC-AB3C-0AEF16045D38","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e6198021e05f1f6cd4ded3ddf48dc9b0b86db1e","datavalue":{"value":{"entity-type":"item","numeric-id":322225,"id":"Q322225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$C9CDB99A-A90A-43D2-9F93-A2B38B6BF62F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e3da441a53aa6d3a4e08623881dc1a503720387","datavalue":{"value":{"entity-type":"item","numeric-id":782939,"id":"Q782939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$C9C7784B-CBB8-4A80-A846-A9AD80B7525F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"892da2c5e775a63c94abe5ed392cda961f9c6547","datavalue":{"value":{"entity-type":"item","numeric-id":782940,"id":"Q782940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$AFDC6B9E-660F-4B14-A7A5-E3057C345D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502bbb6d3842faa7531646862d34737b11134d06","datavalue":{"value":{"entity-type":"item","numeric-id":1584432,"id":"Q1584432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$9F192EF7-DC29-44B7-B187-5485B28080E2","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":"Q782941$ADF18C3C-F490-4350-9987-707F8B3E6953","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"190028e8c6b2870d933bdeb8569c0d0d71bc86f7","datavalue":{"value":{"time":"+2020-07-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q782941$38E7F0E3-D2F8-429B-B8F0-72A10F4FB78F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b9d28ecb752f80a28954b7a070ed1ff9f254f4c","datavalue":{"value":"https://arxiv.org/abs/1910.09868","type":"string"},"datatype":"url"},"type":"statement","id":"Q782941$B1F2EE6D-6083-449A-A7E0-EC636C5AC0D4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"53670669638d5f3e5d6f0b73cc3ab528f167ed67","datavalue":{"value":"Summary: In this short note we study two questions about the existence of subgraphs of the hypercube \\(Q_n\\) with certain properties. The first question, due to \\textit{P. Erd\u0151s} et al. [J. Graph Theory 23, No. 2, 119--128 (1996; Zbl 0857.05027)], asks whether there exists a bounded degree subgraph of \\(Q_n\\) which has diameter \\(n\\). We answer this question by giving an explicit construction of such a subgraph with maximum degree at most 120. The second problem concerns properties of \\(k\\)-additive spanners of the hypercube, that is, subgraphs of \\(Q_n\\) in which the distance between any two vertices is at most \\(k\\) larger than in \\(Q_n\\). Denoting by \\(\\Delta_{k,\\infty}(n)\\) the minimum possible maximum degree of a \\(k\\)-additive spanner of \\(Q_n\\), \\textit{N. Arizumi} et al. [ibid. 57, No. 1, 55--64 (2008; Zbl 1203.05110)] showed that \\[\\frac{n}{\\ln n}e^{-4k}\\leq \\Delta_{2k,\\infty}(n)\\leq 20\\frac{n}{\\ln n}\\ln \\ln n.\\] We improve their upper bound by showing that \\[\\Delta_{2k,\\infty}(n)\\leq 10^{4k} \\frac{n}{\\ln n}\\ln^{(k+1)}n,\\] where the last term denotes a \\(k+1\\)-fold iterated logarithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q782941$F3C594A9-BE75-4037-9FA8-EC81F9BFEFA3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$7289BA0E-D925-44E2-B7DB-186E6E8E1460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$C1D67F24-BA6D-4D3A-83CA-5DE2DC381BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$499E6FA5-DA3F-4C67-BC99-86C99247B7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$D850D994-A18E-4C17-AB1C-D670855D76A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$5C635EAD-DDCE-4391-B7DF-332E33C8AE25","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6ec9cfe74731e1d375a673fe72d36b262126c8d","datavalue":{"value":"7225780","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$3A2EFC93-2A94-4A42-A72F-037B3046CC51","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"958642572c16f2179cfea1065abde1424ca5d83e","datavalue":{"value":"\\(k\\)-additive spanners","type":"string"},"datatype":"string"},"type":"statement","id":"Q782941$C14F343E-9227-4A1B-8D33-EF041AAE98BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c249f664e5144c8c3b859484af9d1fc55ea7a7b","datavalue":{"value":"bounded degree subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q782941$BAA957F3-F676-4BE9-98C2-94D9A0980C2E","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":"Q782941$97340701-E99C-4F00-BF6F-78CA2A28E9D7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0ea80e1275556c3a3a6d091a1cf3d83f1a593d39","datavalue":{"value":"W3042057333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782941$DEE500C7-2CCD-4D9E-A90E-A52D1C25EB1F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9f50e61488397ba86684892de27d36b83d506ce","datavalue":{"value":{"entity-type":"item","numeric-id":4640279,"id":"Q4640279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$B3DFC5C8-A865-40DD-B958-63BB4E00F582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5816b6dd58ebbb5e79873a7664c2115f576c4e71","datavalue":{"value":{"entity-type":"item","numeric-id":2026289,"id":"Q2026289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$FB3CDFD1-9EBF-43AA-9ADC-9020FFD1FB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1569f5530b9747eba4a828270bb888d9d63503e","datavalue":{"value":{"entity-type":"item","numeric-id":4268701,"id":"Q4268701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$39517447-EFFE-4B23-A854-A5E23D0926E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c95d6da9e50b055518923c850dc2483f90deca2","datavalue":{"value":{"entity-type":"item","numeric-id":3539930,"id":"Q3539930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$15726923-BDF1-4737-A5EC-F988DF43DAC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d144c4db073bb7e4f57439effa2f1067f2c756eb","datavalue":{"value":{"entity-type":"item","numeric-id":4873788,"id":"Q4873788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$035E1949-CFD3-447E-9573-E3AAC44C61F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c235443e47cddc88350b3be7a5ad92519d166c6","datavalue":{"value":{"entity-type":"item","numeric-id":1199410,"id":"Q1199410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$6052402B-C17B-4220-811F-945B2D8669C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e26fa18745e67cf36ee16ba993235acc1634018","datavalue":{"value":{"entity-type":"item","numeric-id":1014814,"id":"Q1014814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$31F48DC7-290A-4CFF-8EDB-568E454B78A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b360778e5ee9c2f266782f83d6afc9d8dbfd6091","datavalue":{"value":{"entity-type":"item","numeric-id":1671353,"id":"Q1671353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$CDAA6523-3F61-47F5-8584-5F213459F98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97c7a706f84e3614a2a1f0395a6cbdadb4f108ca","datavalue":{"value":{"entity-type":"item","numeric-id":3188987,"id":"Q3188987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$DB9E82B0-F24B-4A0B-9377-55CA6E1ED21F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c25709354e1a89b6f8183ca50fdffb039c78a8f","datavalue":{"value":{"entity-type":"item","numeric-id":3983256,"id":"Q3983256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$00C5B1C0-65EA-4C5D-9972-6CC90A35DC46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1aadc2b5e913a335322f16c11cb8f8b2fb3d4d0","datavalue":{"value":{"entity-type":"item","numeric-id":359741,"id":"Q359741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$5AA82A4F-BE94-4BEA-B20E-B17B7C8CC0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2bb66cb2fda5a98c72bfac45a0d36f37f442462","datavalue":{"value":{"entity-type":"item","numeric-id":2344775,"id":"Q2344775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$9FFB8651-F4E4-4486-B978-C1043C016F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bbb00cb242018cdf798a0e6ad4a3f526229b4f5","datavalue":{"value":{"entity-type":"item","numeric-id":5741744,"id":"Q5741744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$BCDE4724-7752-4186-99B3-EBCAEE66B836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"feaaf7b3a9939f252f1864c90bf8ddab61bb5662","datavalue":{"value":{"entity-type":"item","numeric-id":4894615,"id":"Q4894615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$5890824A-726B-46D9-A605-976335474F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"346b8498b6a76fafc17f9ba3f7fcebd346c25449","datavalue":{"value":{"entity-type":"item","numeric-id":4210117,"id":"Q4210117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$AE20437C-D042-4703-A0AC-ED2B8F278B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67216ad70118b3cf43ffc0fadf6683962ffc8b2d","datavalue":{"value":{"entity-type":"item","numeric-id":5289379,"id":"Q5289379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$5B60292F-5923-40ED-BF38-F33C7D1F85C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b59ae60faacef2d2dce84df12cf0bea0edd94db9","datavalue":{"value":{"entity-type":"item","numeric-id":4875434,"id":"Q4875434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3522eec13765419db0344909b6b84aac332edb4","datavalue":{"value":{"amount":"+0.7930806875228882","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":"Q782941$4DB289FD-0C3B-4BC2-A85A-64A8228239F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d571f96e752f8c8e4f1214b9e8726d4eda04e5ca","datavalue":{"value":{"entity-type":"item","numeric-id":1570842,"id":"Q1570842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea9c2e309df206958ec31a97b994bdc639d3fd74","datavalue":{"value":{"amount":"+0.7810956239700317","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":"Q782941$57EA1689-5688-4990-A180-187E5E802994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d4062a21a2723b43284631a9873d6c90bd55b59","datavalue":{"value":{"entity-type":"item","numeric-id":1388974,"id":"Q1388974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a71b49e951e269cce850dd16b1576cf405d83288","datavalue":{"value":{"amount":"+0.7793325781822205","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":"Q782941$92C54B4A-F343-4B75-B491-72B2561A89AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a9ea660c1caeae73cfe5eeea82edb4d0a403e9d","datavalue":{"value":{"entity-type":"item","numeric-id":4294594,"id":"Q4294594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30285cc8dc81100c6d32bd0bac76e02cd2798a66","datavalue":{"value":{"amount":"+0.7737999558448792","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":"Q782941$CD203A37-19C6-4672-8D86-919163BCC1E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d023072f10b231c996c2edc94ae0565aed7f82bb","datavalue":{"value":{"entity-type":"item","numeric-id":4229264,"id":"Q4229264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5483485b765b64149dcf7c5077aad3c258512da3","datavalue":{"value":{"amount":"+0.7730796933174133","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":"Q782941$3240EA34-38AD-4733-9B48-50CFB31D3A41","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782941$E38623B1-B674-4FBE-9E9F-2F476E0D4216","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded degree spanners of the hypercube","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_degree_spanners_of_the_hypercube"}}}}}