Infinite paths and cliques in random graphs

DOI10.4064/FM216-2-6MaRDI QIDQ3112380zbMATH OpenOpenAlexFDO

Authors Alessandro Berarducci, Pietro Majer, M. Novaga

Publication date 13 January 2012

Published in Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.2335

zbMATH Keywords

percolation thresholdprobabilityRamsey theoryrandom graphs

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05)

Abstract: We study some percolation problems on the complete graph over $mathbfN$. In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability, such as independency, is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.

Recommendations

• Ramsey goodness of clique versus paths in random graphs
• scientific article; zbMATH DE number 3168330
• Monotone paths in random hypergraphs
• Cliques in random graphs
• Subgraphs of Random Graphs

Cited in

(4)

• Extremal paths in inhomogenous random graphs
• Paths and animals in infinite graphs with tempered degree growth
• Monotone paths in random hypergraphs
• Which subsets of an infinite random graph look random?

This page was built for publication: Infinite paths and cliques in random graphs

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