On connectivity in random graph models with limited dependencies

DOI10.1002/RSA.21220MaRDI QIDQ6596388zbMATH OpenFDO

Authors Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, Emo Welzl

Publication date 2 September 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/RSA.21220

zbMATH Keywords

connectivitydependencyrandom graphs

Mathematics Subject Classification ID

Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• When are random graphs connected
• On the connectedness of a random graph
• Local connectivity of a random graph
• On the connectivity of configuration graphs
• scientific article; zbMATH DE number 15665

Cites work

• 1‐independent percolation on ℤ2×Kn
• A multipartite version of the Turan problem - density conditions and eigenvalues
• An algebraic construction of a class of one-dependent processes
• Asymptotic lower bounds for Ramsey functions
• Complete subgraphs in multipartite graphs
• Connected components in random graphs with given expected degree sequences
• Critical probabilities of 1-independent percolation models
• Density conditions for triangles in multipartite graphs
• Domination by product measures
• Finitely dependent coloring
• Geometric inhomogeneous random graphs
• Graph Theory and Probability
• Long paths and connectivity in 1-independent random graphs
• On 1-dependent processes and k-block factors
• On a problem of Spencer
• Random Geometric Graphs
• Random transceiver networks
• Scale-free percolation
• The density Turán problem
• The isoperimetric number of random regular graphs
• The list chromatic number of graphs with small clique number
• The Lovász Local Lemma and Satisfiability
• The probabilistic method
• Weighted sums of certain dependent random variables
• Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen.

Cited in

(2)

• Connecting probability for random bounded-range one-dimensional network
• On density conditions for transversal trees in multipartite graphs

This page was built for publication: On connectivity in random graph models with limited dependencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6596388)