Umeå University's logo

umu.sePublications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Long paths and connectivity in 1-independent random graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
2020 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 57, no 4, p. 1007-1049Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
John Wiley & Sons, 2020. Vol. 57, no 4, p. 1007-1049
Keywords [en]
extremal graph theory, local lemma, percolation, random graphs
National Category
Probability Theory and Statistics
Identifiers
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
Available from: 2020-11-04 Created: 2020-11-04 Last updated: 2023-03-24Bibliographically approved

Open Access in DiVA

fulltext(1141 kB)415 downloads
File information
File name FULLTEXT01.pdfFile size 1141 kBChecksum SHA-512
9605df04c4de73c05b49a7177ab06ffaf7967aef7d764b07f14e75917dff5ba0371055665dc9cce40e8d70177edb2ae6c42be5bd0e047edac42bd4187ceb8e12
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Day, A. NicholasFalgas-Ravry, Victor

Search in DiVA

By author/editor
Day, A. NicholasFalgas-Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Random structures & algorithms (Print)
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 415 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 550 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf