Rolling backwards can move you forward: on embedding problems in sparse expanders

DOI10.1090/TRAN/8660MaRDI QIDQ5082387zbMATH OpenOpenAlexFDO

Authors Nemanja Draganić, Michael Krivelevich, Rajko Nenadov

Publication date 16 June 2022

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Friedman-Pippenger tree embedding technique

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Graph minors (05C83) Expander graphs (05C48)

Abstract: We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. We use this method to obtain the following results. -We show that the size-Ramsey number of logarithmically long subdivisions of bounded degree graphs is linear in their number of vertices, settling a conjecture of Pak (2002). -We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo (2007). -We show that relatively weak bounds on the spectral ratio of $d$-regular graphs force the existence of a topological minor of $K_t$ where $t=(1-o(1))d$. We also exhibit a construction which shows that the theoretical maximum $t=d+1$ cannot be attained even if $lambda=O(sqrtd)$. This answers a question of Fountoulakis, K"uhn and Osthus (2009).

Recommendations

• An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
• Large bounded degree trees in expanding graphs
• Finding and using expanders in locally sparse graphs
• Embedding nearly-spanning bounded degree trees
• Edge-disjoint paths in expander graphs

Cites work

• scientific article; zbMATH DE number 3883622 (Why is no real title available?)
• scientific article; zbMATH DE number 3815534 (Why is no real title available?)
• scientific article; zbMATH DE number 16104 (Why is no real title available?)
• scientific article; zbMATH DE number 3494449 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1301961 (Why is no real title available?)
• scientific article; zbMATH DE number 2119679 (Why is no real title available?)
• scientific article; zbMATH DE number 871922 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• A new upper bound for diagonal Ramsey numbers
• A note on the Size-Ramsey number of long subdivisions of graphs
• An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
• An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
• Efficient routing in optical networks
• Eigenvalues and expanders
• Embedding nearly-spanning bounded degree trees
• Expander graphs and their applications
• Expanders -- how to find them, and what to find in them
• Expanding graphs contain all small trees
• Explicit construction of linear sized tolerant networks
• Graph minors. XIII: The disjoint paths problem
• Large bounded degree trees in expanding graphs
• Local resilience of almost spanning trees in random graphs
• Logarithmically small minors and topological minors
• Minors in random regular graphs
• On size Ramsey number of paths, trees, and circuits. I
• On size Ramsey numbers of graphs with bounded degree
• On the combinatorial problems which I would most like to see solved
• On the conjecture of Hajos
• Pseudo-random graphs
• Ramanujan graphs
• Ramsey's theorem - a new lower bound
• Recent developments in graph Ramsey theory
• Small complete minors above the extremal edge density
• Spanning trees in random graphs
• Sparse partition universal graphs for graphs of bounded degree
• Subdivided graphs have linear ramsey numbers
• Subdivisions of digraphs in tournaments
• The Induced Size-Ramsey Number of Cycles
• The size Ramsey number
• The size Ramsey number of short subdivisions of bounded degree graphs
• The size-Ramsey number of powers of bounded degree trees
• The size‐Ramsey number of short subdivisions
• The threshold for combs in random graphs
• Tree embeddings
• Wide-Sense Nonblocking Networks

Cited in

(5)

• Finding and using expanders in locally sparse graphs
• An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
• On the size-Ramsey number of grids
• Hamilton cycles in pseudorandom graphs
• Almost spanning distance trees in subsets of finite vector spaces

This page was built for publication: Rolling backwards can move you forward: on embedding problems in sparse expanders

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