{"entities":{"Q1025930":{"pageid":1027778,"ns":120,"title":"Item:Q1025930","lastrevid":66569496,"modified":"2026-04-12T11:00:27Z","type":"item","id":"Q1025930","labels":{"en":{"language":"en","value":"Large components in random induced subgraphs of \\(n\\)-cubes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5569057"}},"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":"Q1025930$0187B117-26B3-4FE5-96D4-EE07A087396C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b597ea881b0cb6560a39afa3e2feae2db88be9d0","datavalue":{"value":{"text":"Large components in random induced subgraphs of \\(n\\)-cubes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1025930$4CEC973E-B89B-4BCD-96F7-3342F9F75139","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8519cb9a3f037942bbcd807b9fb0e9c2a426f5a1","datavalue":{"value":"1183.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025930$464B1A89-411D-40A1-98BB-5A05FF1D489C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9690eb3737a3086604943e44fd38f145d857872","datavalue":{"value":{"entity-type":"item","numeric-id":172385,"id":"Q172385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$09E533EC-55F6-47EE-BF67-0113592D2E1C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$CD5431E1-13E2-458C-BE74-93C86DFB1540","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f66a2f08b182488ffaf8c1a4c74cdffeb2d3409b","datavalue":{"value":{"time":"+2009-06-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1025930$06F81475-E90E-49F7-923E-7AB9A7AFE3AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a978293a42beaa5d9d17980f90f097fd5bd2cc21","datavalue":{"value":"https://arxiv.org/abs/0704.2868","type":"string"},"datatype":"url"},"type":"statement","id":"Q1025930$E67D6D21-B474-42CF-B9B3-E54A5CC3BC19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"96c3e87359cf93c088154796717f5f4203612ee8","datavalue":{"value":"In this paper, a random subgraph of the \\(n\\)-dimensional cube \\(Q_{n}\\) (vertices all 0-1 vectors with \\(n\\) components, edges between two such vectors if and only if they differ in exactly one component) is formed by retaining each vertex with probability \\(\\lambda_{n}\\) independently of all other vertices, and then taking the subgraph induced by the retained vertices. (Thus the resulting graph has expected number of vertices \\(\\lambda_{n}2^{n}\\).) Such subgraphs have some applications in biology, described in the paper. The main focus of this paper is on \\(C_{n}^{(1)}\\), the largest component of this graph (which will, in the situations we are studying, be unique). Let \\(\\lambda_{n}=(1+\\chi_{n})/n\\). It had previously been known that if \\(\\chi>0\\) is constant, then there is \\(\\kappa(\\chi)>0\\) such that  \\[ \\lim_{n\\rightarrow\\infty} P(| C_{n}^{(1)}| =(1+o(1))\\kappa(\\chi) \\lambda_{n}2^{n})=1. \\]  In other words, the largest component with high probability contains a positive proportion of the expected number of vertices. (It had also long been known that for \\(\\lambda_{n}=(1-\\chi)/n\\) where \\(\\chi>0\\) is constant, the largest component would be of order \\(O(n^{10})\\), which is of course polylogarithmic relative to the number of vertices \\(2^{n}\\)).  The main result of the paper somewhat refines the result `inside the phase transition'. In detail, suppose given \\(\\epsilon>0\\) and \\(\\delta>0\\). Suppose that \\(\\lambda_{n}=(1+\\chi_{n})/n\\) where \\(\\epsilon\\geq \\chi_{n}\\geq n^{-1/3+\\delta}\\). Then there is a function \\(\\alpha(\\epsilon)>0\\) such that for \\(\\chi_{n}=\\epsilon\\) we have  \\[ \\lim_{n\\rightarrow\\infty}P\\left(| C_{n}^{(1)}| \\sim \\alpha(\\epsilon)\\frac{1+\\epsilon}{n}2^{n}\\text{ and }C_{n}^{(1)}\\text{ is unique}\\right)=1. \\]  And for \\(o(1)=\\chi_{n}\\geq n^{-1/3+\\epsilon}\\), we have  \\[ \\lim_{n\\rightarrow\\infty}P\\left(| C_{n}^{(1)}| \\sim 2\\chi_{n}\\frac{1+\\chi_{n}}{n}2^{n}\\text{ and }C_{n}^{(1)}\\text{ is unique}\\right)=1. \\]   The rough idea of the proof is to show first, using branching processes, that there is a good chance that each vertex of the random subgraph of \\(Q_{n}\\) is in a component of size at least \\(\\lfloor n^{2/3}/4\\rfloor\\), and to get a (smaller, but still decent) probability it is in a rather larger component. One also shows that the number of vertices not in one of these rather larger components is tightly concentrated: this leads, via more branching arguments, to the size of these rather larger components being pinned down asymptotically. A well-known group theoretic lemma shows existence of many short vertex-disjoint paths connecting the vertex boundaries of the rather larger components. These results, together with a process of selecting vertices in two rounds, give the result.  The author states that the result generalises to \\(n\\)-cubes over any finite alphabet, rather than just a 2-letter one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025930$D2A8BFAE-482F-4ECD-8004-99704287EFDC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$1D272C76-62E3-41A7-95FB-B95B44D29CF8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025930$F7214C86-5844-4C53-BB19-E437F84271F7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c38b026569ae3b486b4d0b0c827f4c9d35b696b","datavalue":{"value":"5569057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025930$380ED6EA-E4CB-404C-BCA8-8A1F9241D40D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025930$EA00C3E9-6492-4AEC-AC3A-0C02025577DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"110bad8468c3dd234026be364e4f4fc4c97a436c","datavalue":{"value":"\\(n\\)-cube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025930$C94BD8B5-FD5D-4685-8685-64C458BC9EC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c55c72c24793d1364203e42c9735e5db2f5f362","datavalue":{"value":"giant component: vertex boundary","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025930$1FA5BA8D-68FC-4D1A-A8DD-95E22CA76437","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":"Q1025930$2F923B11-3182-4513-B191-D4FBD1DCC872","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa9a16d22dc5a5c59ace5df26e5279e791df9f63","datavalue":{"value":"W2009216260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025930$31B03169-8ECB-42E4-952A-D36CBD1B22B6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"40c1cdb3383f36963aa0f6761abacda27dc57cfc","datavalue":{"value":{"entity-type":"item","numeric-id":1822422,"id":"Q1822422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$46EE8B9D-6141-45F8-9B55-0A8D918273ED","rank":"normal"},{"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":"Q1025930$AFE282EA-5F24-4BAD-936E-D1E79098DDD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2bdf1072b8dec0c0c73c62238d18a3a718be8b8","datavalue":{"value":{"entity-type":"item","numeric-id":1094756,"id":"Q1094756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$86D679FA-CE9D-4A58-9D0C-6B2295A8C97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a8d60c975c0d3f7e50a663df7a48724e432a788","datavalue":{"value":{"entity-type":"item","numeric-id":1063041,"id":"Q1063041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$A857E374-7EAE-49AA-B3D9-F6A1A2809A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1c094fbdc68877216dbbc591ed9484c6af11ec7","datavalue":{"value":{"entity-type":"item","numeric-id":4326633,"id":"Q4326633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$86E3A01B-5F46-476B-89B6-3727D223618E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a397bdb25835045daa7666c6c80cc98be35fcbb9","datavalue":{"value":{"entity-type":"item","numeric-id":3989741,"id":"Q3989741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$D2F99CEA-CE85-4334-949B-E4A7C08C831B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74cc3aa0045ef796874e3e638894a0d985afdd19","datavalue":{"value":{"entity-type":"item","numeric-id":858140,"id":"Q858140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$4DA01568-1AB6-4295-B775-CBEDCD007612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$06B4EAE7-CF49-4B3C-B934-8E09B0F88B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae5cda9e213842dabd185b6c9fe503a5a73ef770","datavalue":{"value":{"entity-type":"item","numeric-id":1254259,"id":"Q1254259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$EDA7849D-D5EE-4B13-ABC7-28EE11CD5245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd4bdec64cdd0d7edddc5db2537238e86b0f4a3","datavalue":{"value":{"entity-type":"item","numeric-id":5593806,"id":"Q5593806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$5E0A7AF4-7BF1-4D08-84C4-DB1764201522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b1eb74dc35961dcb1e6adfe219fc2b66bf91b11","datavalue":{"value":{"entity-type":"item","numeric-id":5727090,"id":"Q5727090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$85AA278B-9537-4DCB-B5D6-0F355DF19804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b3d91a2342c07364b59456d61bb7b5ba8073134","datavalue":{"value":{"entity-type":"item","numeric-id":4729076,"id":"Q4729076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$498557CA-7BF0-4802-A0D6-CB726B801E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1aa610b7524ca55644f63fd08d7b23a2da14e08","datavalue":{"value":{"entity-type":"item","numeric-id":4722983,"id":"Q4722983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$05AF5B5C-FA29-4542-A1B0-76A273C6554C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a46b3ce000246ab1af2509c7346ed33d3e9c72b","datavalue":{"value":{"entity-type":"item","numeric-id":4228206,"id":"Q4228206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$C3DE91E6-4166-4DFF-BF6A-6FA4D3F146B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a5b4e7f3de73c10ab7feeb3af6cff6ab6954d61","datavalue":{"value":{"entity-type":"item","numeric-id":1361441,"id":"Q1361441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025930$66172786-2102-4913-A042-3460D31366C7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c342bc8c329faa787256051ceef4ec1fb35f6db2","datavalue":{"value":"10.1016/J.DISC.2008.08.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025930$520719A5-5C99-42BE-A5A5-460C1E244E02","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"858a91c0de793dc11d456bb30b2a844a29d9d00a","datavalue":{"value":{"entity-type":"item","numeric-id":4697468,"id":"Q4697468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b849a59c086395af2a46767e7ad2d583347a0bb5","datavalue":{"value":{"amount":"+0.8843917846679688","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":"Q1025930$AE759065-CF8E-45B3-B103-FE37BCFC1744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37628c1010dbc09d630d63f6c30fd128b18b2708","datavalue":{"value":{"entity-type":"item","numeric-id":4326633,"id":"Q4326633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afbf2fbc30e365d5bb040ac6bfc35f705ab2f724","datavalue":{"value":{"amount":"+0.8834258317947388","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":"Q1025930$82A7E724-48BA-4B55-A2EB-971EA6690FDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6a0be3a8f15adc962503b577ec769784b00c485","datavalue":{"value":{"entity-type":"item","numeric-id":3734446,"id":"Q3734446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab2be74f62ecc79fcd11e42eaa8c6bd580bb9492","datavalue":{"value":{"amount":"+0.8799868226051331","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":"Q1025930$C15BD96C-16A5-4415-B481-64E98F980BEA","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":"0af78a6fa73fa9637ddc4bc7a12bb6c202c6ba3e","datavalue":{"value":{"amount":"+0.8672515153884888","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":"Q1025930$AB5E6C04-94AC-478C-A048-11139274D371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b48c108f009a3f789c4086ed8dd6417c565ddf62","datavalue":{"value":{"entity-type":"item","numeric-id":3760582,"id":"Q3760582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a54e45d8449155e0dd04dcd37d168be7d1a7835","datavalue":{"value":{"amount":"+0.864191472530365","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":"Q1025930$01E02EA5-A53C-4E0B-97FF-BB6E0A9FC4FD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Large components in random induced subgraphs of \\(n\\)-cubes","badges":[]}}}}}