Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2024 MCQ for Transactions of the American Mathematical Society is 1.48 .

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Rolling backwards can move you forward: On embedding problems in sparse expanders
HTML articles powered by AMS MathViewer

by Nemanja Draganić, Michael Krivelevich and Rajko Nenadov PDF
Trans. Amer. Math. Soc. 375 (2022), 5195-5216 Request permission

Abstract:

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique and its algorithmic version, enhanced with a roll-back idea allowing a sequential retracing of 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 [Proceedings of the thirteenth annual ACMSIAM symposium on discrete algorithms (SODA’02), 2002, pp. 321-328].
  • We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of a prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo [48th annual IEEE symposium on foundations of computer science (FOCS’07), 2007, pp. 518-524].
  • We show that relatively weak bounds on the spectral ratio $\lambda /d$ 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(\sqrt {d})$. This answers a question of Fountoulakis, Kühn and Osthus [Random Structures Algorithms 35 (2009), pp. 444-463].
  • References
    Similar Articles
    Additional Information
    • Nemanja Draganić
    • Affiliation: Department of Mathematics, ETH, 8092 Zürich, Switzerland
    • Email: nemanja.draganic@math.ethz.ch
    • Michael Krivelevich
    • Affiliation: School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel
    • MR Author ID: 355932
    • Email: krivelev@tauex.tau.ac.il
    • Rajko Nenadov
    • Affiliation: Department of Mathematics, ETH, Zurich, Switzerland
    • Address at time of publication: Google, Zurich, Switzerland
    • MR Author ID: 940533
    • Email: rajkon@gmail.com
    • Received by editor(s): April 5, 2021
    • Received by editor(s) in revised form: January 13, 2022
    • Published electronically: April 26, 2022
    • Additional Notes: The first author was supported in part by SNSF Grant 200021_196965.
      The second author was supported in part by USA-Israel BSF grant 2018267, and by ISF grant 1261/17.
    • © Copyright 2022 American Mathematical Society
    • Journal: Trans. Amer. Math. Soc. 375 (2022), 5195-5216
    • MSC (2020): Primary 05C48, 05C83, 05C85, 05C55; Secondary 05C38, 05C05
    • DOI: https://doi.org/10.1090/tran/8660
    • MathSciNet review: 4439502