Long paths and connectivity in 1-independent random graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00118537" target="_blank" >RIV/00216224:14330/20:00118537 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1002/rsa.20972" target="_blank" >https://doi.org/10.1002/rsa.20972</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/rsa.20972" target="_blank" >10.1002/rsa.20972</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Long paths and connectivity in 1-independent random graphs
Popis výsledku v původním jazyce
A probability measure.. on the subsets of the edge set of a graph G is a 1-independent probability measure (1-ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1-ipm denote by G.. the associated random graph model. Let. 1,.p(G) denote the collection of 1-ipms.. onGforwhich each edge is included inG.. with probability at least p. For G = Z2, Balister and Bollobas asked for the value of the least p. such that for all p > p. and al mu epsilon M1 >= p(G)(mu) (G).. almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on p.. We also determine the 1-independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs G we study f 1,G(p), the infimum over all mu epsilon M (1)>=(p)(G) of the probability that G.. is connected. We determine f 1,G(p) exactly when G is a path, a complete graph and a cycle of length at most 5.
Název v anglickém jazyce
Long paths and connectivity in 1-independent random graphs
Popis výsledku anglicky
A probability measure.. on the subsets of the edge set of a graph G is a 1-independent probability measure (1-ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1-ipm denote by G.. the associated random graph model. Let. 1,.p(G) denote the collection of 1-ipms.. onGforwhich each edge is included inG.. with probability at least p. For G = Z2, Balister and Bollobas asked for the value of the least p. such that for all p > p. and al mu epsilon M1 >= p(G)(mu) (G).. almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on p.. We also determine the 1-independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs G we study f 1,G(p), the infimum over all mu epsilon M (1)>=(p)(G) of the probability that G.. is connected. We determine f 1,G(p) exactly when G is a path, a complete graph and a cycle of length at most 5.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Random Structures & Algorithms
ISSN
1042-9832
e-ISSN
—
Svazek periodika
57
Číslo periodika v rámci svazku
4
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
43
Strana od-do
1007-1049
Kód UT WoS článku
000577434000001
EID výsledku v databázi Scopus
2-s2.0-85092609413