Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Long paths and connectivity in 1-independent random graphs
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.ORCID-id: 0000-0001-8631-4745
2020 (Engelska)Ingår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 57, nr 4, s. 1007-1049Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

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 the associated random graph model. Let denote the collection of 1‐ipms on G for which each edge is included in with probability at least p. For , Balister and Bollobás asked for the value of the least p such that for all p > p and all , 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 f1, G(p), the infimum over all of the probability that is connected. We determine f1, G(p) exactly when G is a path, a complete graph and a cycle of length at most 5.

Ort, förlag, år, upplaga, sidor
John Wiley & Sons, 2020. Vol. 57, nr 4, s. 1007-1049
Nyckelord [en]
extremal graph theory, local lemma, percolation, random graphs
Nationell ämneskategori
Sannolikhetsteori och statistik
Identifikatorer
URN: urn:nbn:se:umu:diva-176307DOI: 10.1002/rsa.20972ISI: 000577434000001Scopus ID: 2-s2.0-85092609413OAI: oai:DiVA.org:umu-176307DiVA, id: diva2:1497171
Tillgänglig från: 2020-11-04 Skapad: 2020-11-04 Senast uppdaterad: 2023-03-24Bibliografiskt granskad

Open Access i DiVA

fulltext(1141 kB)314 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1141 kBChecksumma SHA-512
9605df04c4de73c05b49a7177ab06ffaf7967aef7d764b07f14e75917dff5ba0371055665dc9cce40e8d70177edb2ae6c42be5bd0e047edac42bd4187ceb8e12
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Day, A. NicholasFalgas-Ravry, Victor

Sök vidare i DiVA

Av författaren/redaktören
Day, A. NicholasFalgas-Ravry, Victor
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Random structures & algorithms (Print)
Sannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 314 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 407 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf