Embedding spanning trees in random graphs

DOI10.1137/100805753zbMATH Open1221.05283OpenAlexW2026053156MaRDI QIDQ3013142FDOQ3013142

Authors Michael Krivelevich

Publication date 18 July 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spanning treesembeddingrandom graphs

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We prove that if T is a tree on n vertices wih maximum degree D and the edge probability p(n) satisfies: np>c*max{D*logn,n^{epsilon}} for some constant epsilon>0, then with high probability the random graph G(n,p) contains a copy of T. The obtained bound on the edge probability is shown to be essentially tight for D=n^{Theta(1)}.

Recommendations

• Spanning trees in random graphs
• Embedding nearly-spanning bounded degree trees
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Embedding large graphs into a random graph
• scientific article; zbMATH DE number 747032

Cited in

(44)

• Almost spanning universality in random graphs
• A note on universal graphs for spanning trees
• The threshold for combs in random graphs
• On the Erdős–Sós conjecture for trees with bounded degree
• Spanning structures and universality in sparse hypergraphs
• The total acquisition number of random graphs
• Universality of random graphs and rainbow embedding
• Spanning trees in random graphs
• A randomized embedding algorithm for trees
• Nonvertex-balanced factors in random graphs
• Fast embedding of spanning trees in biased maker-breaker games
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• An accurate, scalable and verifiable protocol for federated differentially private averaging
• Fast strategies in maker-breaker games played on random boards
• Thresholds versus fractional expectation-thresholds
• Counting spanning trees in self-similar networks by evaluating determinants
• On the performance of randomized embedding of reproduction trees in static networks
• Building spanning trees quickly in maker-breaker games
• Ramsey goodness of bounded degree trees
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• Packing trees of unbounded degrees in random graphs
• Random perturbation of sparse graphs
• Embedding nearly-spanning bounded degree trees
• Edge-disjoint spanning trees and eigenvalues of regular graphs
• Cycle factors and renewal theory
• Expanders via Random Spanning Trees
• Maximal planar subgraphs of fixed girth in random graphs
• Expanders are universal for the class of all spanning trees
• On the probability that a random subtree is spanning
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Embedding large graphs into a random graph
• Local resilience of almost spanning trees in random graphs
• Uniform linear embeddings of spatial random graphs
• Spanning trees in graphs without large bipartite holes
• Random Trees in Random Graphs
• Large bounded degree trees in expanding graphs
• Fast strategies in Waiter-Client games
• Sharp threshold for embedding balanced spanning trees in random geometric graphs
• Optimal threshold for a random graph to be 2-universal
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Expanders Are Universal for the Class of All Spanning Trees
• Ramsey goodness of trees in random graphs
• Spanning trees in randomly perturbed graphs

This page was built for publication: Embedding spanning trees in random graphs

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