Expanding graphs contain all small trees
From MaRDI portal
Publication:1092058
DOI10.1007/BF02579202zbMath0624.05028OpenAlexW2086253307WikidataQ105583321 ScholiaQ105583321MaRDI QIDQ1092058
Nicholas J. 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
Related Items
The vertex size-Ramsey number, Degree Ramsey Numbers of Graphs, On the size-Ramsey number of grid graphs, The size‐Ramsey number of trees, Induced-universal graphs for graphs with bounded maximum degree, Explicit construction of linear sized tolerant networks, Finding cycles and trees in sublinear time, Isoperimetric inequalities in simplicial complexes, Rolling backwards can move you forward: On embedding problems in sparse expanders, Deterministic Graph Games and a Probabilistic Intuition, Tree embeddings, Degree Ramsey numbers for even cycles, The electrical resistance of a graph captures its commute and cover times, On an anti‐Ramsey property of Ramanujan graphs, Spectrum and combinatorics of two-dimensional Ramanujan complexes, On Universal Threshold Graphs, Global maker-breaker games on sparse graphs, 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, The size Ramsey number of trees with bounded degree, The size Ramsey number of a directed path, Turán‐type problems for long cycles in random and pseudo‐random graphs, Fast embedding of spanning trees in biased maker-breaker games, The multicolour size-Ramsey number of powers of paths, Sparse partition universal graphs for graphs of bounded degree, Manipulative Waiters with Probabilistic Intuition, Mixing in High-Dimensional Expanders, Ramsey Goodness of Cycles, The cover time of a regular expander is O(n log n), A lower bound on the area of permutation layouts, Sparse networks tolerating random faults., Embedding Graphs into Larger Graphs: Results, Methods, and Problems, The size Ramsey number of short subdivisions of bounded degree graphs, Ramsey Goodness of Bounded Degree Trees, Degree bipartite Ramsey numbers, Sparse multipartite graphs as partition universal for graphs with bounded degree, Embedding nearly-spanning bounded degree trees, Expanders Are Universal for the Class of All Spanning Trees, A randomized embedding algorithm for trees, Explicit construction of linear sized tolerant networks. (Reprint), A note on the Size-Ramsey number of long subdivisions of graphs, Regular pairs in sparse random graphs I, Explicit sparse almost-universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$, The size-Ramsey number of trees, Cycle lengths in expanding graphs, Local resilience of almost spanning trees in random graphs, A Ramsey type problem concerning vertex colourings, Constructing disjoint paths on expander graphs, On edge‐ordered Ramsey numbers, Long paths and cycles in random subgraphs of graphs with large minimum degree, Optimal threshold for a random graph to be 2-universal, Size Ramsey Number of Bounded Degree Graphs for Games, Spanning trees in random graphs, The size‐Ramsey number of powers of bounded degree trees, The Size Ramsey Number of Graphs with Bounded Treewidth, Unnamed Item, The multicolor size-Ramsey numbers of cycles, Shallow grates, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition, Sharp threshold for the appearance of certain spanning trees in random graphs, Diameters and Eigenvalues
Cites Work
