Expanding graphs contain all small trees

DOI10.1007/BF02579202MaRDI QIDQ1092058zbMATH OpenOpenAlexWikidataFDO

Authors Nicholas Pippenger, Joel Friedman

Publication date 1987

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579202

zbMATH Keywords

treemaximum degree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Recommendations

• Large bounded degree trees in expanding graphs
• Embedding nearly-spanning bounded degree trees
• On graphs which contain each tree of given size
• A note on graphs containing all trees of a given size.
• Subtrees and subforests of graphs

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• Explicit construction of linear sized tolerant networks
• Hamiltonian circuits in random graphs
• On size Ramsey number of paths, trees, and circuits. I

Cited in

(87)

• Ramsey numbers of bounded degree trees versus general graphs
• Induced-universal graphs for graphs with bounded maximum degree
• scientific article; zbMATH DE number 1104337 (Why is no real title available?)
• Spectrum and combinatorics of two-dimensional Ramanujan complexes
• Ramsey goodness of bounded degree trees
• The size‐Ramsey number of cubic graphs
• Spanning trees in pseudorandom graphs via sorting networks
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• The vertex size-Ramsey number
• scientific article; zbMATH DE number 4070927 (Why is no real title available?)
• The size Ramsey number of a directed path
• The cover time of a regular expander is O(n log n)
• The electrical resistance of a graph captures its commute and cover times
• Degree Ramsey numbers of graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Local resilience of almost spanning trees in random graphs
• Diameters and Eigenvalues
• Sparse partition universal graphs for graphs of bounded degree
• Expanders Are Universal for the Class of All Spanning Trees
• Embedding nearly-spanning bounded degree trees
• Ramsey numbers of cycles in random graphs
• A randomized embedding algorithm for trees
• The size-Ramsey number of trees
• Degree Ramsey numbers for even cycles
• Universality for graphs of bounded degeneracy
• Size-Ramsey numbers of structurally sparse graphs
• Fast embedding of spanning trees in biased maker-breaker games
• Degree bipartite Ramsey numbers
• A lower bound on the area of permutation layouts
• Effective bounds for induced size-Ramsey numbers of cycles (extended abstract)
• Partition universality for hypergraphs of bounded degeneracy and degree (extended abstract)
• The size‐Ramsey number of short subdivisions
• On Universal Threshold Graphs
• Sparse networks tolerating random faults.
• A Ramsey type problem concerning vertex colourings
• Algebraic and combinatorial expansion in random simplicial complexes
• The size-Ramsey number of powers of bounded degree trees
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Universality for graphs with bounded density
• Explicit construction of linear sized tolerant networks
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• The size Ramsey number of short subdivisions of bounded degree graphs
• Regular pairs in sparse random graphs I
• The size-Ramsey number of trees
• An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Deterministic Graph Games and a Probabilistic Intuition
• Global maker-breaker games on sparse graphs
• Spanning trees in random graphs
• Manipulative waiters with probabilistic intuition
• Shallow grates
• The size-Ramsey number of powers of bounded degree trees
• Large bounded degree trees in expanding graphs
• On the size-Ramsey number of grids
• Spanning trees in graphs without large bipartite holes
• Mixing in high-dimensional expanders
• Tree embeddings
• Hamilton cycles in pseudorandom graphs
• Cycle lengths in expanding graphs
• On edge-ordered Ramsey numbers
• Optimal threshold for a random graph to be 2-universal
• On the size-Ramsey number of grid graphs
• The multicolor size-Ramsey numbers of cycles
• Isoperimetric inequalities in simplicial complexes
• A note on the Size-Ramsey number of long subdivisions of graphs
• Hamiltonicity of sparse pseudorandom graphs
• Finding cycles and trees in sublinear time
• Unique subgraphs are rare
• Ramsey goodness of trees in random graphs
• Size Ramsey number of bounded degree graphs for games
• The multicolour size-Ramsey number of powers of paths
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Almost spanning distance trees in subsets of finite vector spaces
• Eigenvalue asymptotics and unique continuation of eigenfunctions on planar graphs
• Constructing disjoint paths on expander graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Ramsey goodness of cycles
• The size Ramsey number of trees with bounded degree
• Induced Ramsey problems for trees and graphs with bounded treewidth
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Size-Ramsey numbers of graphs with maximum degree three
• Explicit sparse almost-universal graphs for G (n, kn)
• On an anti‐Ramsey property of Ramanujan graphs
• Explicit construction of linear sized tolerant networks. (Reprint)
• Strong 2-degenerate graph embeddings
• Expanders are universal for the class of all spanning trees
• A note on graphs containing all trees of a given size.

This page was built for publication: Expanding graphs contain all small trees

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