Hamiltonicity of sparse pseudorandom graphs

DOI10.1017/S0963548325000070MaRDI QIDQ6879467zbMATH OpenFDO

Authors Asaf Ferber, Jie Han, Dingjia Mao, Roman Vershynin

Publication date 30 December 2025

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/S0963548325000070

zbMATH Keywords

expander graphHamilton cycle

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45) Expander graphs (05C48) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Cites work

• A survey on Hamilton cycles in directed graphs
• Dirac's theorem for random graphs
• Embedding nearly-spanning bounded degree trees
• Expander graphs and their applications
• Expanding graphs contain all small trees
• Extremal results in sparse pseudorandom graphs
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamilton cycles in pseudorandom graphs
• Hamiltonian circuits in random graphs
• Hamiltonicity in random graphs is born resilient
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• Introduction to Random Graphs
• Large bounded degree trees in expanding graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience of graphs
• Norms of random submatrices and sparse approximation
• Powers of Hamilton cycles in pseudorandom graphs
• Principal submatrices. IX: Interlacing inequalities for singular values of submatrices
• Probability Inequalities for Sums of Bounded Random Variables
• Pseudo-random graphs
• Reducibility among combinatorial problems
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Sampling from large matrices
• Some Theorems on Abstract Graphs
• Sparse pseudo‐random graphs are Hamiltonian
• The probabilistic method
• The random paving property for uniformly bounded matrices
• The spectral gap of a random subgraph of a graph
• Triangle‐factors in pseudorandom graphs
• Turán's theorem for pseudo-random graphs

This page was built for publication: Hamiltonicity of sparse pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6879467)