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.References
- Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, and Madhu Sudan, Efficient routing in optical networks, J. ACM 43 (1996), no. 6, 973–1001. MR 1434909, DOI 10.1145/235809.235812
- N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
- Noga Alon, Subdivided graphs have linear Ramsey numbers, J. Graph Theory 18 (1994), no. 4, 343–347. MR 1277513, DOI 10.1002/jgt.3190180406
- N. Alon and M. Capalbo, Finding disjoint paths in expanders deterministically and online, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), 2007, pp. 518–524.
- N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), 1988, pp. 15–19. MR 975519, DOI 10.1016/0012-365X(88)90189-6
- Noga Alon, Michael Krivelevich, and Benny Sudakov, Embedding nearly-spanning bounded degree trees, Combinatorica 27 (2007), no. 6, 629–644. MR 2384408, DOI 10.1007/s00493-007-2182-z
- S. Arora, T. Leighton, and B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC’90), 1990, pp. 149–158.
- József Balogh, Béla Csaba, Martin Pei, and Wojciech Samotij, Large bounded degree trees in expanding graphs, Electron. J. Combin. 17 (2010), no. 1, Research Paper 6, 9. MR 2578901
- József Balogh, Béla Csaba, and Wojciech Samotij, Local resilience of almost spanning trees in random graphs, Random Structures Algorithms 38 (2011), no. 1-2, 121–139. MR 2768886, DOI 10.1002/rsa.20345
- József Beck, On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory 7 (1983), no. 1, 115–129. MR 693028, DOI 10.1002/jgt.3190070115
- József Beck, On size Ramsey number of paths, trees and circuits. II, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 34–45. MR 1083592, DOI 10.1007/978-3-642-72905-8_{4}
- Sören Berger, Yoshiharu Kohayakawa, Giulia Satiko Maesaka, Taísa Martins, Walner Mendonça, Guilherme Oliveira Mota, and Olaf Parczyk, The size-Ramsey number of powers of bounded degree trees, J. Lond. Math. Soc. (2) 103 (2021), no. 4, 1314–1332. MR 4273470, DOI 10.1112/jlms.12408
- Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal, An efficient algorithm for the vertex-disjoint paths problem in random graphs, Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996) ACM, New York, 1996, pp. 261–268. MR 1381942
- S. A. Burr and P. Erdős, On the magnitude of generalized Ramsey numbers for graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 215–240. MR 0371701
- David Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. (2) 170 (2009), no. 2, 941–960. MR 2552114, DOI 10.4007/annals.2009.170.941
- David Conlon, Jacob Fox, and Benny Sudakov, Recent developments in graph Ramsey theory, Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 49–118. MR 3497267
- D. Conlon, R. Nenadov, and M. Trujić, The size-Ramsey number of cubic graphs, Preprint, arXiv:2110.01897, 2021.
- Domingos Dellamonica Jr. and Yoshiharu Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings and applications, Electron. J. Combin. 15 (2008), no. 1, Research Paper 127, 14. MR 2448877
- Jair Donadelli, Penny E. Haxell, and Yoshiharu Kohayakawa, A note on the size-Ramsey number of long subdivisions of graphs, Theor. Inform. Appl. 39 (2005), no. 1, 191–206. MR 2132587, DOI 10.1051/ita:2005019
- Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov, The size-Ramsey number of short subdivisions, Random Structures Algorithms 59 (2021), no. 1, 68–78. MR 4270995, DOI 10.1002/rsa.20995
- N. Draganić, D. Munhá Correia, B. Sudakov, and R. Yuster, Ramsey number of 1-subdivisions of transitive tournaments, Preprint, arXiv:2110.06919, 2021.
- P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42. MR 602413, DOI 10.1007/BF02579174
- Paul Erdős and Siemion Fajtlowicz, On the conjecture of Hajós, Combinatorica 1 (1981), no. 2, 141–143. MR 625546, DOI 10.1007/BF02579269
- P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), no. 1-2, 145–161. MR 479691, DOI 10.1007/BF02018930
- P. Feldman, J. Friedman, and N. Pippenger, Non-blocking networks, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC’86), 1986, pp. 247–254.
- Paul Feldman, Joel Friedman, and Nicholas Pippenger, Wide-sense nonblocking networks, SIAM J. Discrete Math. 1 (1988), no. 2, 158–173. MR 941347, DOI 10.1137/0401018
- Nikolaos Fountoulakis, Daniela Kühn, and Deryk Osthus, Minors in random regular graphs, Random Structures Algorithms 35 (2009), no. 4, 444–463. MR 2571779, DOI 10.1002/rsa.20285
- J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71–76. MR 905153, DOI 10.1007/BF02579202
- Alan M. Frieze, Disjoint paths in expander graphs via random walks: a short survey, Randomization and approximation techniques in computer science (Barcelona, 1998) Lecture Notes in Comput. Sci., vol. 1518, Springer, Berlin, 1998, pp. 1–14. MR 1729157, DOI 10.1007/3-540-49543-6_{1}
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
- António Girão, Kamil Popielarz, and Richard Snyder, Subdivisions of digraphs in tournaments, J. Combin. Theory Ser. B 146 (2021), 266–285. MR 4155283, DOI 10.1016/j.jctb.2020.09.006
- P. E. Haxell, Tree embeddings, J. Graph Theory 36 (2001), no. 3, 121–130. MR 1814529, DOI 10.1002/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U
- P. E. Haxell, Y. Kohayakawa, and T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), no. 3, 217–239. MR 1356576, DOI 10.1017/S0963548300001619
- Dorit S. Hochbaum, An exact sublinear algorithm for the max-flow, vertex disjoint paths and communication problems on random graphs, Oper. Res. 40 (1992), no. 5, 923–935. MR 1189065, DOI 10.1287/opre.40.5.923
- Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
- D. Johannsen, Personal communication.
- Jeff Kahn, Eyal Lubetzky, and Nicholas Wormald, The threshold for combs in random graphs, Random Structures Algorithms 48 (2016), no. 4, 794–802. MR 3508728, DOI 10.1002/rsa.20614
- Yoshiharu Kohayakawa, Troy Retter, and Vojtěch Rödl, The size Ramsey number of short subdivisions of bounded degree graphs, Random Structures Algorithms 54 (2019), no. 2, 304–339. MR 3912099, DOI 10.1002/rsa.20783
- Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, and Endre Szemerédi, Sparse partition universal graphs for graphs of bounded degree, Adv. Math. 226 (2011), no. 6, 5041–5065. MR 2775894, DOI 10.1016/j.aim.2011.01.004
- Michael Krivelevich, Expanders—how to find them, and what to find in them, Surveys in combinatorics 2019, London Math. Soc. Lecture Note Ser., vol. 456, Cambridge Univ. Press, Cambridge, 2019, pp. 115–142. MR 3967294
- M. Krivelevich and B. Sudakov, Pseudo-random graphs, More sets, graphs and numbers, Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 2006, pp. 199–262. MR 2223394, DOI 10.1007/978-3-540-32439-3_{1}0
- S. Letzter, A. Pokrovskiy, and L. Yepremyan, Size-Ramsey numbers of powers of hypergraph trees and long subdivisions, Preprint, arXiv:2103.01942, 2021.
- László Lovász, Combinatorial problems and exercises, 2nd ed., AMS Chelsea Publishing, Providence, RI, 2007. MR 2321240, DOI 10.1090/chel/361
- A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
- Richard Montgomery, Spanning trees in random graphs, Adv. Math. 356 (2019), 106793, 92. MR 3998769, DOI 10.1016/j.aim.2019.106793
- Richard Montgomery, Logarithmically small minors and topological minors, J. Lond. Math. Soc. (2) 91 (2015), no. 1, 71–88. MR 3338609, DOI 10.1112/jlms/jdu063
- R. Montgomery, Spanning trees in random graphs, Advances in Mathematics, 356:106793, 2019.
- I. Pak, Mixing time and long paths in graphs, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02), 2002, pp. 321–328.
- N. Pippenger, Telephone switching networks, Proc. of Sympos. Appl. Math. 26 (1982), 101–133.
- F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc. (2) 30 (1929), no. 4, 264–286. MR 1576401, DOI 10.1112/plms/s2-30.1.264
- Vojtěch Rödl and Endre Szemerédi, On size Ramsey numbers of graphs with bounded degree, Combinatorica 20 (2000), no. 2, 257–262. MR 1767025, DOI 10.1007/s004930070024
- Neil Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995), no. 1, 65–110. MR 1309358, DOI 10.1006/jctb.1995.1006
- Eli Shamir and Eli Upfal, A fast parallel construction of disjoint paths in networks, Topics in the theory of computation (Borgholm, 1983) North-Holland Math. Stud., vol. 102, North-Holland, Amsterdam, 1985, pp. 141–153. MR 849367
- Asaf Shapira and Benny Sudakov, Small complete minors above the extremal edge density, Combinatorica 35 (2015), no. 1, 75–94. MR 3341141, DOI 10.1007/s00493-015-3013-2
- Joel Spencer, Ramsey’s theorem—a new lower bound, J. Combinatorial Theory Ser. A 18 (1975), 108–115. MR 366726, DOI 10.1016/0097-3165(75)90071-0
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