2020/07/16 by Nemanja Draganić, Michael Krivelevich, Draganić, Nemanja +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2007.08332
openalex publication_date 2020/07/16 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
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 Kt 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 λ=O(√(d)). This answers a question of Fountoulakis, Kühn and Osthus (2009).