Spanning trees in pseudorandom graphs via sorting networks
HTML articles powered by AMS MathViewer
- by Joseph Hyde, Natasha Morrison, Alp Müyesser and Matías Pavez-Signé;
- Proc. Amer. Math. Soc. 153 (2025), 2353-2367
- DOI: https://doi.org/10.1090/proc/17139
- Published electronically: April 3, 2025
- HTML | PDF
Abstract:
We show that $(n,d,\lambda )$-graphs with $\lambda =O(d/\log ^3 n)$ are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang of the form $\lambda =d/\exp {(O(\sqrt {\log n}))}$, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007.
Our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Komlós and Szemerédi. Using this construction, we show that the classical vertex-disjoint paths problem can be solved for a set of vertices fixed in advance.
References
- M. Ajtai, J. Komlós, and E. Szemerédi, An ${O}(n \log n)$ sorting network, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 1983, pp. 1–9.
- 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
- Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov, Rolling backwards can move you forward: on embedding problems in sparse expanders, Trans. Amer. Math. Soc. 375 (2022), no. 7, 5195–5216. MR 4439502, DOI 10.1090/tran/8660
- Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park, Thresholds versus fractional expectation-thresholds, Ann. of Math. (2) 194 (2021), no. 2, 475–495. MR 4298747, DOI 10.4007/annals.2021.194.2.2
- J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71–76. MR 905153, DOI 10.1007/BF02579202
- Stefan Glock, David Munhá Correia, and Benny Sudakov, Hamilton cycles in pseudorandom graphs. part B, Adv. Math. 458 (2024), no. part B, Paper No. 109984, 45. MR 4815049, DOI 10.1016/j.aim.2024.109984
- J. Han and D. Yang, Spanning trees in sparse expanders, arXiv:2211.04758, 2022.
- 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
- Daniel Johannsen, Michael Krivelevich, and Wojciech Samotij, Expanders are universal for the class of all spanning trees, Combin. Probab. Comput. 22 (2013), no. 2, 253–281. MR 3021334, DOI 10.1017/S0963548312000533
- János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Proof of a packing conjecture of Bollobás, Combin. Probab. Comput. 4 (1995), no. 3, 241–255. MR 1356577, DOI 10.1017/S0963548300001620
- Michael Krivelevich, Embedding spanning trees in random graphs, SIAM J. Discrete Math. 24 (2010), no. 4, 1495–1500. MR 2746703, DOI 10.1137/100805753
- Michael Krivelevich and Benny Sudakov, Sparse pseudo-random graphs are Hamiltonian, J. Graph Theory 42 (2003), no. 1, 17–33. MR 1943104, DOI 10.1002/jgt.10065
- 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
- Daniela Kühn, John Lapinskas, Deryk Osthus, and Viresh Patel, Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Proc. Lond. Math. Soc. (3) 109 (2014), no. 3, 733–762. MR 3260292, DOI 10.1112/plms/pdu019
- Anita Liebenau and Nick Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, J. Eur. Math. Soc. (JEMS) 26 (2024), no. 1, 1–40. MR 4705645, DOI 10.4171/jems/1355
- Richard Montgomery, Spanning trees in random graphs, Adv. Math. 356 (2019), 106793, 92. MR 3998769, DOI 10.1016/j.aim.2019.106793
- R. Montgomery, A. Pokrovskiy, and B. Sudakov, A proof of Ringel’s conjecture, Geom. Funct. Anal. 31 (2021), no. 3, 663–720. MR 4311581, DOI 10.1007/s00039-021-00576-2
- P. Morris, Clique factors in pseudorandom graphs, 2023, to appear in J. Eur. Math. Soc.
- A. Müyesser and A. Pokrovskiy, A random Hall-Paige conjecture, Invent. Math. (2025), DOI 10.1007/s00222-025-01328-x.
- M. Pavez-Signé, Spanning trees in the square of pseudorandom graphs, arXiv:2307.00322, 2023.
Bibliographic Information
- Joseph Hyde
- Affiliation: Department of Mathematics, King’s College London, Strand Building, Strand Campus, Strand, London WC2R 2LS, United Kingdom
- MR Author ID: 1344391
- Email: joseph.hyde@kcl.ac.uk
- Natasha Morrison
- Affiliation: Department of Mathematics and Statistics, University of Victoria, 3800 Finnerty Road, Victoria, British Columbia V8P 5C2, Canada
- MR Author ID: 1079525
- Email: nmorrison@uvic.ca
- Alp Müyesser
- Affiliation: New College, University of Oxford, United Kingdom
- Email: alp.muyesser@new.ox.ac.uk
- Matías Pavez-Signé
- Affiliation: Centro de Modelamiento Matemático (CNRS IRL2807), Universidad de Chile, Santiago, Chile
- Email: mpavez@dim.uchile.cl
- Received by editor(s): November 15, 2023
- Received by editor(s) in revised form: August 13, 2024, October 22, 2024, and October 30, 2024
- Published electronically: April 3, 2025
- Additional Notes: Research of the second author was supported by NSERC Discovery Grant RGPIN-2021-02511 and NSERC Early Career Supplement DGECR-2021-00047.
The fourth author was supported by ANID-FONDECYT Regular grant No. 1241398, by ANID Basal Grant CMM FB210005, and by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement No. 947978). - Communicated by: Isabella Novik
- © Copyright 2025 by the authors
- Journal: Proc. Amer. Math. Soc. 153 (2025), 2353-2367
- MSC (2020): Primary 05D40, 05C48; Secondary 05C05
- DOI: https://doi.org/10.1090/proc/17139
- MathSciNet review: 4892612