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

DOI10.1090/TRAN/8660zbMATH Open1492.05084arXiv2007.08332OpenAlexW3042354966MaRDI QIDQ5082387FDOQ5082387

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)

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).

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

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

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)

Cites Work

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

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)