{"entities":{"Q654001":{"pageid":655850,"ns":120,"title":"Item:Q654001","lastrevid":63353667,"modified":"2026-04-11T12:18:18Z","type":"item","id":"Q654001","labels":{"en":{"language":"en","value":"Binary subtrees with few labeled paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990955"}},"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":"Q654001$F62897D4-C419-4ACE-8FDF-2C60E0FC08D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"01f64e8e7ae242fd422bd78b6d526931ff9b649e","datavalue":{"value":{"text":"Binary subtrees with few labeled paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q654001$AD4A2082-6B08-4F6C-8901-FAEB4F7202D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f7dc71c1c4f7136bcb04e9fd81caedb5028e932","datavalue":{"value":"1265.05593","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654001$50299492-F396-4606-A10F-3C06F49FF500","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8aa819e8a26b7e07cf0d79026024c3692da5103","datavalue":{"value":{"entity-type":"item","numeric-id":277527,"id":"Q277527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$9F8F3F5C-471E-4316-8A7B-5716020308DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0b22c597c8b573856274c0b9425ef5e44cb3896","datavalue":{"value":{"entity-type":"item","numeric-id":654000,"id":"Q654000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$BEF75CFB-9E29-4A7B-B5B4-27F1515D46EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bda6634bd9b704666aafb27971d31fe0a008c4ad","datavalue":{"value":{"entity-type":"item","numeric-id":405188,"id":"Q405188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$56D50F0D-8E79-437C-84F4-AD1833E1938C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2356fe1f1f6d7960e11f0114cbd6aa7fe05024f7","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$5C132961-0824-4596-A305-D8B98A72B6A4","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":"Q654001$BFF54343-2C9C-4778-A747-9B2283118ED3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9a9ebdc8bdc44c407c473bf89fbe244ce057f32","datavalue":{"value":{"time":"+2011-12-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":"Q654001$7481B204-A891-4FCF-BD8C-4A740FE0DEDD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb67b0db74b77e1a6de9587e97d42177ca4b76b3","datavalue":{"value":"If \\(T\\) is a complete ternary tree of depth \\(n\\), let \\({\\mathcal{B}}(T)\\) to be the set of all binary subtrees of \\(T\\) that are complete with depth \\(n\\). A tree \\(T\\) is said to be edge-labeled if each edge in \\(T\\) is assigned a label from the set \\(\\{0,1\\}\\). Let \\({\\mathcal{T}}_{n}\\) be the set of all ternary, complete, edge-labeled trees of depth \\(n\\). If \\(T \\in {\\mathcal{T}}_{n}\\), \\(r\\) is the root of \\(T\\), and \\(\\sigma \\) is a leaf in \\(T\\), then reading the elements along the path from \\( r\\) to \\(\\sigma\\) in \\(T\\) gives a path-label \\(x \\in \\{0,1\\}^{n}\\), and it is said that \\(\\sigma\\) has path-label \\(x\\). Let \\(L(T)\\) to be the set of all path-labels in \\(T\\). For each \\(T \\in {\\mathcal{T}}_{n}\\), let \\(f(T) = \\min\\{| L(S)| : S\\in {\\mathcal{B}}(T)\\}\\), and for each \\(n\\), let \\(f(n) = \\max\\{f(T): T\\in {\\mathcal{T}}_{n}\\}\\). The purpose of this paper is to study the behavior of \\(f(n)\\) as \\(n \\rightarrow \\infty\\). It is shown that \\(f(n) \\geq 2^{(n-3)/\\log_{2}3}\\), \\(\\lim_{n\\rightarrow \\infty}(f(n))^{1/n}\\) exists and this limit has a value between \\(2^{1/\\log_{2 }3}\\) and 2. Also, if \\(c<\\sqrt{\\log_{2}(4/3)}\\), then there is a constant \\(\\gamma\\) such that \\( f(n)\\leq \\gamma 2^{n-c\\sqrt{n}}\\). Consequently, the ratio \\(f(n)/2^{n}\\) tends to zero as \\(n\\) grows. The following Ramsey interpretation is deduced: for large \\(n\\), every edge-labeled complete ternary tree of depth \\(n\\) admits a complete binary subtree of depth \\( n\\) whose path-labels constitute an arbitrarily small fraction of the space of all possible path-labels. These results lead to a solution of a problem in computability theory and effective randomness: the class of Kurtz random reals is not Medvedev reducible to \\( DNR_{3}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$7E92C226-7430-44A1-A5D0-2479E7204CDC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$4E332C0A-F4D0-4C10-9CBD-7E8FBFAF72FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b02a47bb3e6ffda6ae8940845178eca3854c8d36","datavalue":{"value":"05D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654001$5CC24181-5A86-4C26-94B1-157093C95ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654001$AAB7879B-6189-47B1-B9BB-E7E42E5EC53C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7f57b3af2824030a0677e12e477659fc85a14b7d","datavalue":{"value":"5990955","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654001$4ABE2813-23D8-4828-BD4F-C7047463F045","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38725f9219d508cd94fcb3ec037f6d7bdf69e471","datavalue":{"value":"binary subtree","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$815B278C-BE40-42FA-91E3-B36D97BE964E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f562780dd4bd216dca4bad3fb5c99e56f89569b","datavalue":{"value":"ternary edge-labeled tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$56CBB938-6F85-4649-A30C-146B2252445B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f401dd9c1f566772595ae85ebc3ea4d1157a2c3d","datavalue":{"value":"computability theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$45E0D935-2EB4-494F-93B3-77F723363A5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce0bd33ca8bacc2bf5819c9314876b21df544ed5","datavalue":{"value":"Medvedev degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$5B94B44B-D90D-4F26-9B02-4202EC989683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d278d91d33134d454caac0cb9b809519edd50f5","datavalue":{"value":"Baire space","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$3F8ED2C8-EC3E-4EAA-9350-FAA40157C97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08f1124b1f4453113a28d664ddf4824eea31b856","datavalue":{"value":"Cantor space","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$DD154A42-5F0D-4A50-9B4F-957A6F29BA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"690abfc928f31a3551acba0990d55326b703905d","datavalue":{"value":"strong reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$2DF80360-98B0-4F90-B83A-BDABC9131567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2dded5edaf18c1c6f0a01be782925e8006e48f2","datavalue":{"value":"Kurtz random set","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$54D4C5F7-1BE2-4241-8395-BAB61A926170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"496fb62b5fbbae0889439900bccaa24ccd7b815b","datavalue":{"value":"randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q654001$E9B83C61-A7BF-4C1B-94D4-37AC450D7004","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":"Q654001$1F3EAE48-6B45-4E2E-99AB-5FB0ABC7A2B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0bbef1a48c289dc73dfb6e114c16db38cd0b05e","datavalue":{"value":"https://doi.org/10.1007/s00493-011-2634-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q654001$7688D2ED-C7E0-494F-8B09-19490ED26346","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"31533eb727106488cfcfa0241744de7add96f05b","datavalue":{"value":"W2120482717","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654001$04BD2DFE-113E-4D40-8E13-919B0BD76037","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45131a38ff53f12b9952d52e2962c28740fef2f7","datavalue":{"value":{"entity-type":"item","numeric-id":3161424,"id":"Q3161424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$B5972435-1784-4E38-BCE1-2CDD67F73F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c83bb9a587b1a1188c83783608b4c6f3d5a8b0f9","datavalue":{"value":{"entity-type":"item","numeric-id":3412463,"id":"Q3412463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$9504F445-B82F-47FC-86A1-CBEE7EE6EBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8be609764dd2d275e4df6130aecc8af12a11e68","datavalue":{"value":{"entity-type":"item","numeric-id":1912753,"id":"Q1912753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$B4D7A4F0-2FC4-4D48-ACCE-E892EF03A340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf4d20630b0bd7dc58b969242e7c24eca5d6be14","datavalue":{"value":{"entity-type":"item","numeric-id":3984429,"id":"Q3984429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$0B2303AC-1DE6-4E10-8074-C51EA0063350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1793805264b30efd5068033ba495233ed5ba2e15","datavalue":{"value":{"entity-type":"item","numeric-id":5199325,"id":"Q5199325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$198243A6-A71E-49E9-B994-E0239BF81648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de43f3e978a9ce24db65e773f8fff3d02c7dc139","datavalue":{"value":{"entity-type":"item","numeric-id":3944587,"id":"Q3944587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$3B306CE9-8A55-4A24-9968-90B6A76CCAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f43e39da6413b4900316472ef3eb3724afe78dfe","datavalue":{"value":{"entity-type":"item","numeric-id":5437596,"id":"Q5437596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$B8A166A6-0096-428F-A722-BD11BFEC1F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afa198449e94216f6426cad818b0afbe610455fc","datavalue":{"value":{"entity-type":"item","numeric-id":3594486,"id":"Q3594486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$A08DBF6A-92B3-4CB6-8A59-1CD86D95F11F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$4148EFA0-5202-4FD3-8E16-F7712F2A0595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60d69dd101cdf0dbd1af9cf92f3c97d42448b678","datavalue":{"value":{"entity-type":"item","numeric-id":3976908,"id":"Q3976908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$9DBE3A1D-91A5-40DC-8FA4-3B534988351B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4048e028f0bc35874857035c76f559321e287a3","datavalue":{"value":{"entity-type":"item","numeric-id":3370625,"id":"Q3370625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$6DE28BB3-3774-4E93-9B95-ABDA95DF10AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5030ce0dec8b952b1f920f03a2d7a8346535490f","datavalue":{"value":{"entity-type":"item","numeric-id":818514,"id":"Q818514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654001$DD2FFC82-3A67-44CD-AECD-94B20D696A04","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d6aeab2b17093eedb7b7396151ac3eeb822a5b9","datavalue":{"value":"10.1007/S00493-011-2634-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654001$42BEC4BA-4B36-475C-8F92-56FB4FD67DA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b414a540982894dd8e3c4a03ed39e6de3066e4e","datavalue":{"value":{"entity-type":"item","numeric-id":1076401,"id":"Q1076401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"966be6fa8caadd95336af313d71b766856941224","datavalue":{"value":{"amount":"+0.7250583171844482","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":"Q654001$B391CDB3-CA46-44A2-A338-A876CF5811BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59f6dedf56fe0dea6c6c1a27ac7f65824113101b","datavalue":{"value":{"entity-type":"item","numeric-id":810523,"id":"Q810523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d055d63789d95364886c6d3b83dac5bdee4437ea","datavalue":{"value":{"amount":"+0.7229615449905396","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":"Q654001$04A4FE56-61B2-4219-9714-C7870B1FD1CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a67c32587480b70ce9572cd64be060d429a8dbd","datavalue":{"value":{"entity-type":"item","numeric-id":2274085,"id":"Q2274085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d291a08c859ef50eda14678bf96e9c0f129897c2","datavalue":{"value":{"amount":"+0.7176382541656494","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":"Q654001$42B03555-07B1-46C8-8FD5-70445B766766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"427452204c92cd0968945b6765354539eee3a230","datavalue":{"value":{"entity-type":"item","numeric-id":3616350,"id":"Q3616350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33e2e50f3fed319b5883da3f54fa399d1830cebf","datavalue":{"value":{"amount":"+0.7151191830635071","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":"Q654001$5B943315-35B8-41E3-9C88-A907740733EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce7e96090430b9ea5c6edbcfec4e7edf8747e020","datavalue":{"value":{"entity-type":"item","numeric-id":293237,"id":"Q293237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3da871860b8e9cedb5f9e98ff2e434506b295e88","datavalue":{"value":{"amount":"+0.7148189544677734","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":"Q654001$711A1CF4-81EA-47AD-AC3C-3C6726F3338B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Binary subtrees with few labeled paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Binary_subtrees_with_few_labeled_paths"}}}}}