A randomized embedding algorithm for trees

DOI10.1007/S00493-010-2422-5MaRDI QIDQ555509zbMATH OpenOpenAlexFDO

Authors Jan Vondrák, Benny Sudakov

Publication date 22 July 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-010-2422-5

zbMATH Keywords

randomized algorithm\(C_4\)-free graphs\(K_{s,t}\)-free graphsembedding a tree to a graphgraphs of fixed girth

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• Embedding spanning trees in random graphs
• Tight bounds for embedding bounded degree trees
• An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
• Embedding nearly-spanning bounded degree trees
• Tree embeddings

Cites work

• scientific article; zbMATH DE number 3693325 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• A Note on Bipartite Graphs Without 2 k -Cycles
• Cycle lengths in sparse graphs
• Embedding nearly-spanning bounded degree trees
• Embedding trees into graphs of large girth
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• Expanding graphs contain all small trees
• Four-cycles in graphs without a given even cycle
• Hamiltonian circuits in random graphs
• Markov chains indexed by trees
• Minimal Regular Graphs of Girths Eight and Twelve
• Minors in expanding graphs
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• On a conjecture about trees in graphs with large girth
• On a problem of K. Zarankiewicz
• Pseudo-random graphs
• The Erdös-Sós conjecture for graphs of girth 5
• The size-Ramsey number of trees
• Tree embeddings
• Trees in sparse random graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• \(C_ 6\)-free bipartite graphs and product representation of squares

Cited in

(9)

• Expanders Are Universal for the Class of All Spanning Trees
• An approximate version of Sumner's universal tournament conjecture
• A geometric theory for hypergraph matching
• Embedding spanning bipartite graphs of small bandwidth
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
• Percolation on random graphs with a fixed degree sequence
• The automorphism group of projective norm graphs
• Expanders are universal for the class of all spanning trees

This page was built for publication: A randomized embedding algorithm for trees

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