{"entities":{"Q949756":{"pageid":951604,"ns":120,"title":"Item:Q949756","lastrevid":65610669,"modified":"2026-04-12T03:46:55Z","type":"item","id":"Q949756","labels":{"en":{"language":"en","value":"A phase transition for the metric distortion of percolation on the hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5355068"}},"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":"Q949756$172A53FF-2588-49FF-A1B6-B8435979049C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1d230ea93d98738ef7de15f0dbe3bc2a8906847","datavalue":{"value":{"text":"A phase transition for the metric distortion of percolation on the hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q949756$2AE6DC19-5F8A-40D8-A0EF-3EC185CA34CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d4333a6f68c99885a1799f399941a2f588ad22a","datavalue":{"value":"1164.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$0E0775D0-020B-42EA-A59F-95D36A0D3050","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6a6159b9019d31998b7baa29d0f1460aaf902b1","datavalue":{"value":{"entity-type":"item","numeric-id":341497,"id":"Q341497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$1269EF26-71E2-42E3-97BE-58D0870A8A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fa1f63e797b90acb322b2504762950abb751fe1","datavalue":{"value":{"entity-type":"item","numeric-id":177916,"id":"Q177916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$510DE470-2321-477D-9B48-CB8882F59E1E","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":"Q949756$E4DFC3D8-4BEE-48DB-9BE1-E67EC6BAEF8D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b4a05105c8454225903df775b1ba3fdbda7455a","datavalue":{"value":{"time":"+2008-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q949756$D4F86086-0DE5-4A4D-882F-B0D51EA05EE3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f956c08e344f4e4a81647f8eb5dcf146e6b4abc4","datavalue":{"value":"https://arxiv.org/abs/math/0306355","type":"string"},"datatype":"url"},"type":"statement","id":"Q949756$CFF8561B-BC3C-493E-995C-D9414F1B41D3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba38b5a482479ef98910b617c9f38bf9f99640bb","datavalue":{"value":"The metric distortion between the hypercube \\(H_n\\) and its random subgraphs are investigated. Let \\(H_{n,p}\\) be a graph that one gets by keeping each edge of \\(H_n\\) with probability \\(p\\), independently of each other. It was shown by \\textit{M.~Ajtai, J.~Komlos} and \\textit{E.~Szemer\u00e9di} [Combinatorica 2, 1-7 (1982; Zbl 0489.05053)] that for \\(p=a/n\\) if \\(a<1\\) then all connected components of \\(H_{n,p}\\) have size \\(poly(n)\\), while if \\(a>1\\) there is a giant component of both size and diameter \\(\\theta(n)\\) with probability tending to 1. \\textit{Hastad et al} [Proc. of the 19th ACM Symp. on Theory of Comp. 274-284 (1987)] showed that for constant \\(p\\) the distortion between \\(H_n\\) and \\(H_{n,p}\\) is constant with probability tending to 1. They define the distortion of a map \\(f\\) between two metric spaces \\((X,d_X)\\), \\((Y,d_Y)\\) as \\(D(f)=D_+(f)/D_-(f)\\), where   \\[ \\begin{aligned} D_+(f) &= 1 \\vee \\left(\\sup_{a, b \\in X} d_Y\\left(f(a), f(b)/d_X(a, b)\\right)\\right),\\\\ D_-(f)&=\\inf_{a, b \\in X} \\left(1 \\vee d_Y\\left(f(a), f(b)\\right)\\right)/d_X(a, b)).\\end{aligned} \\]   The distortion between the spaces \\(X,Y\\) is \\(D(X,Y)=\\inf_{f:X \\rightarrow Y}D(f)\\).      Then in Theorem 1 they prove the following: Fix \\(\\alpha\\in [0,1]\\), and let \\(p=n^{-\\alpha}\\). If \\(\\alpha<1/2\\), then there is some constant \\(c=c(\\alpha)\\) such that \\(\\text{Pr}(D(H_n,H_{n,p})<c) \\longrightarrow 1\\), when \\(n\\rightarrow\\infty\\). If \\(\\alpha>1/2\\), then there is some constant \\(\\beta=\\beta(\\alpha)\\) such that \\(\\text{Pr}(D(H_n,H_{n,p})< n^{\\beta}) \\longrightarrow 1\\), when \\(n\\rightarrow\\infty\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q949756$52C7FD1E-9FD6-42CE-B0D3-C43847F16DCA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$CACA023B-2FC9-45C3-A867-02167A4E1118","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$0D7B20BA-FB79-4630-807D-D7D810056B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$4B883616-78D0-4094-A198-3E9995B8EF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"671a9141f7533e3d7d525a297ffd04f047259a12","datavalue":{"value":"60D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$0B4089E8-F0C4-4B00-B477-6EFE936E9EEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9ecafa3861882b9ed77fe93bded39fc6955a78c9","datavalue":{"value":"5355068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$B4ED18AD-4902-406A-BEEB-ACD8FC7CCF1B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"539be726cb8dfa54cd0c12914c99488c7ea42ea5","datavalue":{"value":"percolation","type":"string"},"datatype":"string"},"type":"statement","id":"Q949756$82858871-CE09-4241-B4D2-1BEE025BECF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"011292841bfecc5a96af7eefb5f2207525532434","datavalue":{"value":"phase transition","type":"string"},"datatype":"string"},"type":"statement","id":"Q949756$7954A345-1622-4F14-9F65-8681D94D68DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f3ec7c9b794cf0f8c84bdc151069b97a4e24ee7","datavalue":{"value":"metric distortion","type":"string"},"datatype":"string"},"type":"statement","id":"Q949756$0CF2A8CA-9149-48A4-9547-19C7E274CBA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q949756$5F9F2859-654A-486C-816A-510B12222F69","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":"Q949756$D2A2E851-087C-4C9D-B08B-7A135797069E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9c60cb71e46b32b9db6f11d4bae0b142d35b3020","datavalue":{"value":"W2033177258","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$28779B68-D89C-4961-AC0B-6B4D57D38155","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5bff64035e95e51feabb12a3769bc6707593128","datavalue":{"value":{"entity-type":"item","numeric-id":1166544,"id":"Q1166544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$720AF73E-37AC-4067-AF82-796C64F6AD26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$7F404666-48C6-44CC-831E-C2E6AD5132EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37b4b6c31b154f34cc9573ac2d657c21f3c8c944","datavalue":{"value":{"entity-type":"item","numeric-id":1878979,"id":"Q1878979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$335C012E-FB58-40C5-955C-B6506B56D478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa03daa11a48cd68d47753174515ba2950ab0f5e","datavalue":{"value":{"entity-type":"item","numeric-id":1380243,"id":"Q1380243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$4345E78D-A683-4A9C-B0DA-1560CEBF2C7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b83f5197857092b75833f238f4a2bca6995dbfd","datavalue":{"value":{"entity-type":"item","numeric-id":5318244,"id":"Q5318244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$FA5CF5BD-BBBE-4970-A047-66F47E1993ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff83cf2de30e0d5c1f6d13cb7c82035c932c7587","datavalue":{"value":{"entity-type":"item","numeric-id":4549227,"id":"Q4549227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$F5EC7F5B-CD64-4F18-A3E9-4366E9997C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a70e7a82f2ba368b3e3008cf126903ed2de09b5a","datavalue":{"value":{"entity-type":"item","numeric-id":2737866,"id":"Q2737866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949756$2A442122-7631-4B22-8DD0-165FB62DB822","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eff093de7d7ba65806fc81174e6682ae43bb0b2a","datavalue":{"value":"10.1007/S00493-007-2241-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949756$73AA50AE-25F7-4780-A6E6-932236438A28","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9263ff984b2d0501310ee1c9a0810f1e3f4bce4d","datavalue":{"value":{"entity-type":"item","numeric-id":520736,"id":"Q520736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46c60015f0f749a6a5f6d8b6b57c6184c94d6ae8","datavalue":{"value":{"amount":"+0.7460196018218994","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":"Q949756$EAD92B61-EBEC-4B00-BE47-BAC647F8C581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a253a61185972073329156a72f6060f722240e10","datavalue":{"value":{"entity-type":"item","numeric-id":2105142,"id":"Q2105142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baa3db49b2f6b3372a1a3a088e137564e40a2f42","datavalue":{"value":{"amount":"+0.7436936497688293","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":"Q949756$FFE3830A-7635-499F-A854-341A91762DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3df9d8fdb8556e04987699a3e983223054b564d8","datavalue":{"value":{"entity-type":"item","numeric-id":4696229,"id":"Q4696229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ff9a0913f8f8b3aa0a4287468a5d2a42d584a05","datavalue":{"value":{"amount":"+0.7416142225265503","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":"Q949756$60BEC644-F4A0-4F3F-A26E-32FA0E0BE569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27769dc41805e35fc207c99c448b602590f15180","datavalue":{"value":{"entity-type":"item","numeric-id":3165461,"id":"Q3165461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a26345d42e120f7559d4d28541139723081224f","datavalue":{"value":{"amount":"+0.7376424670219421","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":"Q949756$095662A1-C93D-4788-945A-50488A1893E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1facc540620a326d62c81a77cffc1f5ffb226a09","datavalue":{"value":{"entity-type":"item","numeric-id":858140,"id":"Q858140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca63cfaaea51341e2c1da3614c02e141f02b22d3","datavalue":{"value":{"amount":"+0.7349144816398621","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":"Q949756$3A3B3E99-09FD-4AB7-986E-BC9F4AB0E919","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A phase transition for the metric distortion of percolation on the hypercube","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_phase_transition_for_the_metric_distortion_of_percolation_on_the_hypercube"}}}}}