{"entities":{"Q5936455":{"pageid":8113257,"ns":120,"title":"Item:Q5936455","lastrevid":47630713,"modified":"2026-01-02T06:36:16Z","type":"item","id":"Q5936455","labels":{"en":{"language":"en","value":"Embedding complete trees into the hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1613394"}},"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":"Q5936455$5F338058-1D5D-4FF5-A4E1-027A0A3BFFB7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ba3d7aff3beaca07c52bc1ac7505ba796ccbc44","datavalue":{"value":{"text":"Embedding complete trees into the hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936455$B134F7F4-774A-460D-A00B-3D5EB2F45BC2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f71c82dd5f66317e2452ebceaa88d87bd78dffc","datavalue":{"value":"0980.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$C58AB982-B18D-49D0-8111-2975E07B28C1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48172406603c97823f3259b853c55fb95ef03fd8","datavalue":{"value":"10.1016/S0166-218X(00)00256-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$5C22939D-7F8E-4990-B5CE-882B7F5A44E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf876d5ad6eef9728ef751040433c72acf680125","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$D01815B6-06F7-4B29-8463-ACF7F8E2E16C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$EAD4C937-EC27-48DF-A962-0D933D78CBC8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"76612000aa94052c36e81d46e1cd5cad6b75e5fe","datavalue":{"value":{"time":"+2002-02-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936455$F9082454-F3F4-4EBA-99CC-5D0FD103AC1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf552a6496a70699f2802e7f7eff6309238b43f4","datavalue":{"value":{"entity-type":"item","numeric-id":383766,"id":"Q383766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$C1FF0E1E-57BE-4A10-B64F-FCD64D61501C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$89460B47-0DFE-46B3-AC0F-A9306FF72CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$83573851-E359-4B7B-B1C8-07007A4B0140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$2555AFE1-F072-44D8-A402-DA882840C59E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$B796C772-4ECD-43E2-A372-7C111EBCBFAB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c1723aa50587a2e025fa384cefd05a921a0b56a2","datavalue":{"value":"1613394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936455$EDA5D4C3-2236-43B6-B035-2748D53670AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936455$795A0B25-8B37-4312-A2F6-BB8177F756A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada8d30f2ef08fc8cb2c5d1f7da969abbc27918a","datavalue":{"value":"dilation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936455$7C953034-0173-4930-B4C2-CCB1EB612622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9b7926138c2d4ed5ad793d9e70e76ca2a719ef3","datavalue":{"value":"complete tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936455$AD56052D-8A54-43EC-8565-3EC951D7B7A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936455$F033BA85-2BC6-461E-8446-9F8C7A0E578E","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":"Q5936455$48F890ED-0002-4D0A-9602-A3D82B29BE3C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d8ea20102dd1b4026e32a688dae666f6e3c82a","datavalue":{"value":{"entity-type":"item","numeric-id":4306429,"id":"Q4306429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$63ECB132-FD7C-41AF-A30D-210CCB459BD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$EE198340-8988-4F54-9FD2-6A785D1B3271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f16d613e8d10c798bfd11f0a470bbd295d5b594c","datavalue":{"value":{"entity-type":"item","numeric-id":3669436,"id":"Q3669436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$1A59FF8C-E9DE-46F4-8FA6-92277C152D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df0bd7d6eedf1dc63c9de6ed0e2e0929be44e69","datavalue":{"value":{"entity-type":"item","numeric-id":5636914,"id":"Q5636914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$F94CF2AC-8CBF-4ABD-A82A-EE1774EF2D1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e364d03f678565d83145181556d64418a5e3200b","datavalue":{"value":{"entity-type":"item","numeric-id":5181389,"id":"Q5181389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$315A019C-4CF4-4C5A-9800-9F05FB5F2BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"802833deb74c8bb6fdd15d7e976e3ca238f3075d","datavalue":{"value":{"entity-type":"item","numeric-id":1843433,"id":"Q1843433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$712C4762-A2DA-4FEB-9CC4-6F9FE09B13C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61137da8a33ed9fbce885a0d4c4da534b29a6b65","datavalue":{"value":{"entity-type":"item","numeric-id":4401956,"id":"Q4401956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$C5DEFC71-9B2A-4766-B967-F54213683594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936455$583ABBF2-7D75-4838-A693-DD5796FA5345","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b164b6716491cd87ba9ae03b1c21145b39177f8","datavalue":{"value":"For given tree \\(T\\), the dimension of \\(T\\) (denoted by \\(\\text{dim}(T)\\)) is the minimum \\(n\\) such that \\(T\\) is a subgraph of the \\(n\\)-dimensional hypercube. In the paper, the dimension of complete \\(t\\)-ary trees \\(T^{k,t}\\) of depth \\(k\\) is considered. It is known that \\(\\frac{kt}{e} \\leq \\dim(T^{k,t}) \\leq \\frac{(k+1)t}{2}+k-1\\) [see \\textit{F. Oll\u00e9}, M. Sci. Thesis, Math. Inst. Prague (1972)], \\(\\dim(T^{k,2})=k+2\\), \\(k \\geq 2\\) and \\(\\dim(T^{2,t})=\\lceil \\frac{3t+1}{2}\\rceil\\), \\(t \\geq 1\\) [see \\textit{I. Havel} and \\textit{P. Liebl}, \u010cas. P\u011bst. Mat. 97, 201-205 (1972; Zbl 0229.05109) and \u010cas. P\u011bst. Mat. 98, 307-314 (1973; Zbl 0274.05101)]. For the next open cases \\(k=3\\) and \\(t=3\\), it is known that \\(\\dim(T^{3,t}) \\leq 2t+2\\), \\(\\dim(T^{k,3}) \\leq 2k +1\\) (H.-D. O. F. Gronau and J.-M. Laborde (1994)). The author improves the leading coefficients 2 in these upper bounds, showing that NEWLINE\\[NEWLINE\\lim_{k \\to \\infty}\\frac{\\dim(T^{k,3})}{k} \\leq \\frac{5}{3}\\quad\\text{and}\\quad\\lim_{t \\to \\infty}\\frac {\\dim(T^{3,t})}{t} = \\frac{227}{120}.NEWLINE\\]NEWLINE Also, the general upper bound is improved asymptotically by showing that NEWLINE\\[NEWLINE\\lim_{k,t \\to \\infty} \\frac{\\dim(T^{k,t})}{kt} \\leq \\frac{307}{640}.NEWLINE\\]NEWLINE As a co-result, an exact formula for the dimension of arbitrary trees of depth 2 as a function of their vertex degrees is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936455$4B6CC268-0CC2-4692-9904-58C86DDE78B5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf5cd22d1b6214c40792cf09b9f47f3fbfafe9b5","datavalue":{"value":{"entity-type":"item","numeric-id":3633839,"id":"Q3633839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df532ae5f2b2a8f200515bea6a3de39d7c1b88fa","datavalue":{"value":{"amount":"+0.8529476523399353","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":"Q5936455$5A8CBFB4-E622-4038-B6E4-9DCA18F1C1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f401744afda72f2a78b0551d7e8a1b6aadeba298","datavalue":{"value":{"entity-type":"item","numeric-id":1178228,"id":"Q1178228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eaa22b8ccffbca2d6c438dd07c53cf6b6568df4","datavalue":{"value":{"amount":"+0.8420678377151489","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":"Q5936455$D998878F-6FAB-4A25-98A1-A27FF4DA2359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4c9d463cfc1758479c8a996361cc07eebc4accb","datavalue":{"value":{"entity-type":"item","numeric-id":396672,"id":"Q396672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30a460351bd7e9dccd5a585aad425fa8a4383ac5","datavalue":{"value":{"amount":"+0.8413761258125305","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":"Q5936455$0AC429D9-B1B9-4C28-95B4-F0DE530BC574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10307b40177599f33b0a38401e59dcc74714ac32","datavalue":{"value":{"entity-type":"item","numeric-id":1398807,"id":"Q1398807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79f49f3f8812733c042e2f9aafb7cf93c426d6a5","datavalue":{"value":{"amount":"+0.8183656930923462","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":"Q5936455$265BF96E-F476-42B0-AE03-F42E6FAD5867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b3dc22ad2bae3e87b5100d2a81f8e6ddfa725de","datavalue":{"value":{"entity-type":"item","numeric-id":1325976,"id":"Q1325976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03f6861573d4eeb9b758f51b280e408ee870cf5e","datavalue":{"value":{"amount":"+0.8012563586235046","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":"Q5936455$4DA9C99B-350F-4268-A89E-6ABE97E6CB0F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936455","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936455"}}}}}