@article{GlockMunhaCorreiaSudakov2024, author = {Glock, Stefan and Munh{\´a} Correia, David and Sudakov, Benny}, title = {Hamilton cycles in pseudorandom graphs}, series = {Advances in Mathematics}, volume = {2024}, journal = {Advances in Mathematics}, number = {458 B}, publisher = {Elsevier}, address = {Amsterdam}, doi = {10.1016/j.aim.2024.109984}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-19151}, pages = {45 Seiten}, year = {2024}, abstract = {Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well-known conjecture in the area states that any d-regular n-vertex graph G whose second largest eigenvalue in absolute value λ(G) is at most d/C, for some universal constant C > 0, has a Hamilton cycle. In this paper, we obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree d is at least a small power of n. Secondly, in the general case we show that λ(G) ≤ d/C(log n)1/3 implies the existence of a Hamilton cycle, improving the 20-year old bound of d/ log1-o(1) n of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust P{\´o}sa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications. In particular, they imply the currently best-known bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lov{\´a}sz. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups.}, language = {en} }