Well-mixing vertices and almost expanders

Chakraborti, Debsoumya; Kim, Jaehoon; Kim, Jinha; Kim, Minki; Liu, Hong

doi:10.1090/proc/16090

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