## Well-mixing vertices and almost expanders

HTML articles powered by AMS MathViewer

- by Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim, Minki Kim and Hong Liu PDF
- Proc. Amer. Math. Soc.
**150**(2022), 5097-5110 Request permission

## Abstract:

We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and has no small separator. This answers a question of Pak [*SODA: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics*, Philadelphia, PA, 2002, pp. 321–328]. As a corollary, it shows that sparse (constant degree) regular graphs with many well-mixing vertices have a long cycle, improving a result of Pak. Furthermore, such cycle can be found in polynomial time.

Secondly, we show that if the random walks from a positive fraction of vertices are well-mixing, then the random walks from almost all vertices are well-mixing (with a slightly worse mixing time).

## References

- Jeff Cheeger,
*A lower bound for the smallest eigenvalue of the Laplacian*, Problems in analysis (Papers dedicated to Salomon Bochner, 1969) Princeton Univ. Press, Princeton, N. J., 1970, pp. 195–199. MR**0402831** - Reinhard Diestel,
*Graph theory*, 2nd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, New York, 2000. MR**1743598**, DOI 10.1007/b100033 - A. Dress and I. Gutman,
*The number of walks in a graph*, Appl. Math. Lett.**16**(2003), no. 5, 797–801. MR**1986053**, DOI 10.1016/S0893-9659(03)00085-5 - J. Erde, M. Kang, and M. Krivelevich,
*Expansion in supercritical random subgraphs of the hypercube and its consequences*, Preprint, arXiv:2111.06752, 2021. - P. Erdős and M. Simonovits,
*Compactness results in extremal graph theory*, Combinatorica**2**(1982), no. 3, 275–288. MR**698653**, DOI 10.1007/BF02579234 - Tomas Feder, Rajeev Motwani, and Carlos Subi,
*Finding long paths and cycles in sparse Hamiltonian graphs*, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 524–529. MR**2115289**, DOI 10.1145/335305.335368 - A. Frieze, G. Miller, and S. Teng,
*Separator based parallel divide and conquer in computational geometry*, Proc. 4th ACM Symposium on Parallel Algorithms and Architecture (SPAA ’92), 1992, pp. 420–429. - Irene Gil Fernández, Jaehoon Kim, Younjin Kim, and Hong Liu,
*Nested cycles with no geometric crossings*, Proc. Amer. Math. Soc. Ser. B**9**(2022), 22–32. MR**4377266**, DOI 10.1090/bproc/107 - I. Gil Fernández and H. Liu,
*How to build a pillar: a proof of Thomassen’s conjecture*, Preprint, arXiv:2201.07777, 2022. - R. G. Gallager,
*Low-density parity-check codes*, IRE Trans.**IT-8**(1962), 21–28. MR**0136009**, DOI 10.1109/tit.1962.1057683 - 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** - O. Goldreich,
*A sample of samplers – a computational perspective on sampling (survey)*, Technical Report TR97-020, Electronic Colloquium on Computational Complexity (ECCC), 1997. - O. Goldreich and D. Ron,
*On testing expansion in bounded-degree graphs*, Technical Report TR00-020, Electronic Colloquium on Computational Complexity (ECCC), Potsdam, Germany, 2000. - J. Haslegrave, J. Hu, J. Kim, H. Liu, B. Luan, and G. Wang,
*Crux and long cycles in graphs*, Preprint, arXiv:2107.02061, 2021. - J. Haslegrave, J. Hyde, J. Kim, and H. Liu,
*Ramsey numbers of cycles versus general graphs*, Preprint, arXiv:2112.03893, 2021. - J. Haslegrave, J. Kim, and H. Liu,
*Extremal density for sparse minors and subdivisions*, Int. Math. Res. Not. IMRN, To appear. - 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 - S. Im, J. Kim, Y. Kim, and H. Liu,
*Topological cliques in sublinear expanders*, Preprint. - Satyen Kale and C. Seshadhri,
*An expansion tester for bounded degree graphs*, SIAM J. Comput.**40**(2011), no. 3, 709–720. MR**2810912**, DOI 10.1137/100802980 - Ravi Kannan, Santosh Vempala, and Adrian Vetta,
*On clusterings: good, bad and spectral*, J. ACM**51**(2004), no. 3, 497–515. MR**2145863**, DOI 10.1145/990308.990313 - D. Karger, R. Motwani, and G. D. S. Ramkumar,
*On approximating the longest path in a graph*, Algorithmica**18**(1997), no. 1, 82–98. MR**1432030**, DOI 10.1007/BF02523689 - Jaehoon Kim, Hong Liu, Maryam Sharifzadeh, and Katherine Staden,
*Proof of Komlós’s conjecture on Hamiltonian subsets*, Proc. Lond. Math. Soc. (3)**115**(2017), no. 5, 974–1013. MR**3733557**, DOI 10.1112/plms.12059 - János Komlós and Endre Szemerédi,
*Topological cliques in graphs*, Combin. Probab. Comput.**3**(1994), no. 2, 247–256. MR**1288443**, DOI 10.1017/S0963548300001140 - Michael Krivelevich,
*Finding and using expanders in locally sparse graphs*, SIAM J. Discrete Math.**32**(2018), no. 1, 611–623. MR**3769697**, DOI 10.1137/17M1128721 - 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** - Michael Krivelevich and Rajko Nenadov,
*Complete minors in graphs without sparse cuts*, Int. Math. Res. Not. IMRN**12**(2021), 8996–9015. MR**4276311**, DOI 10.1093/imrn/rnz086 - A. Kumar, C. Seshadhri and A. Stolen,
*Random walks and forbidden minors I: An $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs*, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., 2018, pp. 509–520, DOI 10.1109/FOCS.2018.00055 - David A. Levin and Yuval Peres,
*Markov chains and mixing times*, American Mathematical Society, Providence, RI, 2017. Second edition of [ MR2466937]; With contributions by Elizabeth L. Wilmer; With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. MR**3726904**, DOI 10.1090/mbk/107 - Richard J. Lipton and Robert Endre Tarjan,
*A separator theorem for planar graphs*, SIAM J. Appl. Math.**36**(1979), no. 2, 177–189. MR**524495**, DOI 10.1137/0136016 - Hong Liu and Richard Montgomery,
*A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs*, J. Lond. Math. Soc. (2)**95**(2017), no. 1, 203–222. MR**3653090**, DOI 10.1112/jlms.12019 - H. Liu and R. H. Montgomery,
*A solution to Erdős and Hajnal’s odd cycle problem*, Preprint, arXiv:2010.15802, 2020. - H. Liu, G. Wang, and D. Yang,
*Clique immersion in graphs without fixed bipartite graph*, Preprint, arXiv:2011.10961, 2020. - B. Louf and F. Skerman,
*Finding large expanders in graphs: from topological minors to induced subgraphs*, Preprint, arXiv:2012.15722, 2020. - B. Louf,
*Large expanders in high genus unicellular maps*, Preprint, arXiv:2102.11680, 2021. - L. Lovász,
*Combinatorial problems and exercises*, North-Holland Publishing Co., Amsterdam-New York, 1979. MR**537284** - L. Lovász,
*Random walks on graphs: a survey*, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353–397. MR**1395866** - Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters,
*LDPC codes achieve list decoding capacity*, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, [2020] ©2020, pp. 458–469. MR**4232058**, DOI 10.1109/FOCS46700.2020.00050 - H. P. Mulholland and C. A. B. Smith,
*An inequality arising in genetical theory*, Amer. Math. Monthly**66**(1959), 673–683. MR**110721**, DOI 10.2307/2309342 - I. Pak,
*Mixing time and long paths in graphs*, SODA: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002, pp. 321–328. - Serge Plotkin, Satish Rao, and Warren D. Smith,
*Shallow excluded minors and improved graph decompositions*, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994) ACM, New York, 1994, pp. 462–470. MR**1285188**

## Additional Information

**Debsoumya Chakraborti**- Affiliation: Discrete Mathematics Group (DIMAG), Institute for Basic Science (IBS), Daejeon, South Korea
- MR Author ID: 1382502
- Email: debsoumya@ibs.re.kr
**Jaehoon Kim**- Affiliation: Department of Mathematical Sciences, KAIST, South Korea
- MR Author ID: 973739
- ORCID: 0000-0002-5735-7321
- Email: jaehoon.kim@kaist.ac.kr
**Jinha Kim**- Affiliation: Discrete Mathematics Group (DIMAG), Institute for Basic Science (IBS), Daejeon, South Korea
- MR Author ID: 1319262
- ORCID: 0000-0001-5982-7836
- Email: jinhakim@ibs.re.kr
**Minki Kim**- Affiliation: Division of Liberal Arts and Sciences, Gwangju Institute of Science and Technology, Gwangju, South Korea
- MR Author ID: 1183004
- ORCID: 0000-0002-9390-7255
- Email: minkikim@gist.ac.kr
**Hong Liu**- Affiliation: Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea
- ORCID: 0000-0002-5735-7321
- Email: hongliu@ibs.re.kr
- Received by editor(s): August 29, 2021
- Received by editor(s) in revised form: September 3, 2021, and February 5, 2022
- Published electronically: June 16, 2022
- Additional Notes: The first, third, and fourth authors were supported by the Institute for Basic Science (IBS-R029-C1). The second author was supported by the POSCO Science Fellowship of POSCO TJ Park Foundation and by the KAIX Challenge program of KAIST Advanced Institute for Science-X. The fifth author was supported by the Institute for Basic Science (IBS-R029-C4) and the UK Research and Innovation Future Leaders Fellowship MR/S016325/1.
- Communicated by: Isabella Novik
- © Copyright 2022 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**150**(2022), 5097-5110 - MSC (2020): Primary 05C81, 05C48, 05C85
- DOI: https://doi.org/10.1090/proc/16090