{"entities":{"Q4796015":{"pageid":6825595,"ns":120,"title":"Item:Q4796015","lastrevid":109021196,"modified":"2026-11-11T04:45:52Z","type":"item","id":"Q4796015","labels":{"en":{"language":"en","value":"A Sharp Threshold  for Network Reliability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1874607"}},"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":"Q4796015$9027B5C8-9667-41D6-9BD5-D516C8738B08","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"06bae57b37406d680b41b566a69f5159469b4fb3","datavalue":{"value":{"text":"A Sharp Threshold  for Network Reliability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4796015$E3941CAE-CCEE-425A-837A-C92BFF21A5EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5db5c9c83e9b662c550bc19070561d71597b0c60","datavalue":{"value":"1009.05125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$29911878-73E9-46AB-8BBD-9DA560EFC017","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aec0f6790c97b37c40f19a275734818231edb6af","datavalue":{"value":"10.1017/S0963548302005199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$AF070443-E4A6-4613-BAC3-4D40B5185C51","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4796015$426E039B-D2E2-4D5F-A88D-D65B896BCA4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ac20003147c5e8ffc37ced247b8446bd4defdc1","datavalue":{"value":{"entity-type":"item","numeric-id":178484,"id":"Q178484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4796015$93432F7E-C48E-4B7E-A23E-B53C31763C2E","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":"Q4796015$46AA1FC2-582A-44C0-9CCB-4953653FFFF7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc98aa839a361f8a72b00376d60e99225cffa57","datavalue":{"value":{"entity-type":"item","numeric-id":2703019,"id":"Q2703019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4796015$D42BCE34-627C-45E1-A17A-BE43988B9AEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"12ae802659d41c4900d55387b70770b7595bc963","datavalue":{"value":{"time":"+2003-04-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4796015$DF545319-66B2-40B3-99CC-C11190C44AE4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$C55FD925-F2D4-408B-8587-96E4B1F8A1E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$5786FF96-5A80-4698-A346-D04367BEEF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0f04c159386ffa0dca53c7806240943adbdfdea4","datavalue":{"value":"90B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$B4AE484E-17BC-4915-9529-1566481736E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92da2862b8d81cb7ded37c09cb3fbbcfa92be73e","datavalue":{"value":"1874607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$74CCF8EB-1131-495C-99FA-1C5FCB6AE0DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"493ce1f22be4b5e97f592b530102597d7df81db4","datavalue":{"value":"reliability function","type":"string"},"datatype":"string"},"type":"statement","id":"Q4796015$24C964B9-AB6A-4916-B923-A94C4395E695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf6a9ea7aaa991a5b0305cfe2785ff6725cc33ef","datavalue":{"value":"sharp threshold","type":"string"},"datatype":"string"},"type":"statement","id":"Q4796015$2434E11F-2181-485B-A442-25695FCF6B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cad1213d5a60b90c3c163e0ed7153fac704f8b7","datavalue":{"value":"random matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q4796015$FCAE2837-F312-4352-89C0-46AF8537FE3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4796015$22880B38-69CA-4B34-B4A5-826DBE14F08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4796015$A2B1446D-C5D6-4B13-9A05-8A5201ADEDCA","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":"Q4796015$E92E9FAE-FC9B-4D0D-B1FC-7D346B4D46AC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c50b0077a7004fb7b3485504ac6954fd243b9897","datavalue":{"value":"https://doi.org/10.1017/s0963548302005199","type":"string"},"datatype":"url"},"type":"statement","id":"Q4796015$2ED75F73-0DAE-47AB-A0DB-E60AA04D8654","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c3248b1500986dccfeab7490c3c59af6520f2a1c","datavalue":{"value":"W2141899664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4796015$D574FA83-E827-4AE0-B86B-56376DC5ADB0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6f088bf0931b5cf72ee2ac1da90b86777573011","datavalue":{"value":{"entity-type":"item","numeric-id":4257709,"id":"Q4257709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e58f5811db09496bda53c5f746c9e1469fd9836","datavalue":{"value":{"amount":"+0.7996656894683838","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":"Q4796015$125D97C9-ECAA-4CB1-8CDB-81887EA84FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aec511f433586386a69a966400288da2c24e900e","datavalue":{"value":{"entity-type":"item","numeric-id":803174,"id":"Q803174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8562cbbf5b04a86e223680898a228086abd63494","datavalue":{"value":{"amount":"+0.7924416661262512","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":"Q4796015$D12EFA98-99F8-4ED4-8079-E3AD107BBA82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e49f018a94dd2e1e2e51845c553d0731f87bd1b","datavalue":{"value":{"entity-type":"item","numeric-id":5746306,"id":"Q5746306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47a78b37db414c4ea0e00276081920df07546c70","datavalue":{"value":{"amount":"+0.7924265265464783","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":"Q4796015$6F0009C8-D438-4124-A015-71686D724684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"576e0ff76dee887c1ebc4ec6f352f02006dc2b6c","datavalue":{"value":{"entity-type":"item","numeric-id":3286850,"id":"Q3286850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10b188408fa2c2eed043077854a7925e94f5f954","datavalue":{"value":{"amount":"+0.7923387289047241","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":"Q4796015$043E0868-5D2A-4519-A3E5-0C8F3B1DD1A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07ae48b35a9980efe3ca253fc55c20a30cb8ebf1","datavalue":{"value":{"entity-type":"item","numeric-id":4717065,"id":"Q4717065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dadaa41b863abffe4d78d51ffcc62b21050681f","datavalue":{"value":{"amount":"+0.7914447784423828","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":"Q4796015$89E96C4A-6C0C-4184-9299-726A0D506CC4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18033a0965dc8d409e03b2a080f7d5110a3b4058","datavalue":{"value":"Let \\(G\\) be a finite simple graph with \\(n\\) vertices. A random subgraph \\(G_{p}\\) of \\(G\\) is obtained by keeping each edge of \\(G\\) in with probability \\(p\\), independent of all other edges. The reliability polynomial of \\(G\\), denoted \\(f(G,p)\\), is then the probability that \\(G_{p}\\) is connected. There is an obvious application to reliability of various networks (computers, etc.). Let \\(p_{x}\\) be the (unique) value of \\(p\\) where \\(f(G,p_{x})=x\\). A family of graphs \\((G_{i})_{i=1}^{\\infty}\\) is said to have the sharp threshold property if, for any \\(0<\\varepsilon \\leq 1/2\\), we have \\[ \\lim_{i\\rightarrow\\infty} \\frac{p_{\\varepsilon}(G_{i})} {p_{1-\\varepsilon}(G_{i})}=1. \\] That is, the transition from being connected with very small probability to being connnected with very high probability happens with only a \\` small' increase in \\(p\\) -- informally, we can substantially increase the probability of connectedness at comparatively little cost. It is thus natural to ask which families of graphs possess the sharp threshold property. The first steps on this problem were taken by \\textit{G. A. Margulis} [Probabilistic properties of graphs with large connectivity (Russian), Probl. Peredaci Inform. 10, 101-109 (1974; Zbl 0322.05147)]. If we let \\(k(G)\\) be the number of edges of \\(G\\) one has to remove in order to disconnect \\(G\\) (i.e. its edge-connectivity), he showed that, if \\(\\lim_{i\\rightarrow\\infty}k(G_{i})=\\infty\\), then, for any \\(0<\\varepsilon\\leq 1/2\\), we have \\[ \\lim_{i\\rightarrow\\infty}p_{1-\\varepsilon}(G_i)-p_{\\varepsilon}(G_{i})=0, \\] which implies the sharp threshold property if \\(k(G_{i})\\rightarrow\\infty\\) and \\(p_{1-\\varepsilon}(G_{i})\\) is bounded below by a positive constant. However it gives no insight when \\(p_{1-\\varepsilon}(G_{i})\\rightarrow 0\\). The main result of the paper under review addresses this deficiency in Margulis' result by showing that if \\(0<\\varepsilon<1/2\\) then, for every \\(\\gamma>0\\), there exist \\(K(\\gamma)\\) and \\(n_{0}(\\gamma)\\) such that if \\(G\\) is a graph on \\(n>n_{0}(\\gamma)\\) vertices with average degree \\(d\\) and edge-connectivity \\(k(G)\\geq K(\\gamma)\\frac{d}{\\ln(n)}+1\\), then \\[ \\frac{p_{\\varepsilon}(G)}{p_{1-\\varepsilon}(G)}\\geq 1-\\gamma. \\] In particular, if the \\(G_{i}\\) are distinct, with \\(G_{i}\\) having \\(n_{i}\\) vertices, maximum degreee \\(d-{i}\\) and \\(K(G_{i})=k_{i}\\), then if \\[ \\lim_{i\\rightarrow\\infty}\\frac{k_{i}\\ln(n_{i})}{d_{i}}=\\infty, \\] the family \\((G_{i})\\) has the sharp threshold property. The proof technique is very different from that of Margulis, who used ideas from percolation theory. Instead the authors first observe that it suffices to prove that, for all \\(\\alpha\\) with \\(\\varepsilon\\leq \\alpha\\leq 1-\\varepsilon\\), we have \\[ p_{\\alpha}f{'}(p_{\\alpha})\\geq 1/\\gamma \\] where \\(f{'}\\) denotes the derivative of \\(f(G,p)\\). A recent powerful result of J. Bourgain [appendix to \\textit{E. Friedgut}, Sharp thresholds of graph properties, and the \\(k\\)-SAT problem, J. Am. Math. Soc. 12, 1017-1054 (1999; Zbl 0932.05084)] shows that if this property does not hold, so that \\(pf{'}(G,p)<c\\) for some \\(c>0\\), then there is a fixed set of edges whose addition to the random graph \\(G_{p}\\) increases the probability of connectivity by a constant. This does not fit with the idea that, when the threshold is not sharp, the addition of a large number of random edges to \\(G_{p}\\) does not affect the connectivity to any significant extent. To turn this rough idea into correct mathematics requires, in the case when \\(p_{\\alpha}\\) is bounded below by a positive constant, a lower bound on the threshold probability for the graph connectivity property, which is established using Chebychev's inequality (the `second moment method'). In the case when \\(p_{\\alpha}=o(1)\\), they define a cleverly chosen class \\(B\\) of sugraphs of \\(G\\) and show that for any such graph adding only a `few' more edges makes the graph very likely to be connected, thus contradicting the assumption that the threshold is not sharp. It is natural to ask how close to optimal the result is. The authors show it is not far off optimal by showing that for any constant \\(a>1\\), there is \\(0<\\varepsilon(a)<1/2\\) such that, for all sufficiently large \\(n\\), there is a graph on \\(2n\\) vertices with maximum degree \\(n\\) and \\(k(G)=\\frac{ad}{\\ln(n)}\\) for which \\[ \\frac{p_{\\varepsilon}(G)}{p_{1-\\varepsilon}(G)}\\leq \\frac{1}{2}. \\] Next, the authors let \\(X\\) be a matroid (i.e. a set with a collection of subsets satisfying natural axioms generalising the notion of an independent set of vectors). For a subset \\(A\\) of \\(X\\), the size of a maximal independent subset of \\(A\\) is \\(r(A)\\); \\(\\eta(M)\\) is the size of the smallest \\(Y\\subseteq X\\) such that \\(r(X\\backslash Y)<r(M)\\). This invariant \\(\\eta\\) generalises edge-connectivity of a graph. They then show, by proof techniques similar to those in the main theorem, that if \\(X_{p}\\) is a subset obtained by including each element of \\(X\\) with probability \\(p\\), independently of all other elements, then the probability that \\(X\\) is spanning (that is, contains an independent set of maximal size) has a sharp threshold under two conditions. These are firstly that \\(p_{\\alpha}\\), the unique \\(p\\) such that \\(P(X_{p_{\\alpha}}{\\text{ is spanning}})=\\alpha\\), satisfies \\((1-p_{\\alpha})^\\eta(M)=o(1)\\) for any constant \\(\\alpha\\) and secondly that \\(r(M)\\) goes to infinity. Finally the authors observe that there is considerable scope for using Bourgain's criterion to investigate sharp threshold properties in various other contexts.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4796015$4CBB4C9D-175A-437A-8D29-41B73655EF08","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A Sharp Threshold for Network Reliability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_Sharp_Threshold_for_Network_Reliability"}}}}}