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