On the Number of Hamilton Cycles in Psdueo-Random Graphs

Computer Science/Discrete Mathematics Seminar I
Topic:On the Number of Hamilton Cycles in Psdueo-Random Graphs
Speaker:Michael Krivelevich
Affiliation:Tel Aviv University
Date:Monday, October 17
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/hcprg

A pseudo-random graph is a graph G resembling a typical random graph of the same edge density. Pseudo-random graphs are expected naturally to share many properties of their random counterparts. In particular, many of their enumerative properties should be similar to those of random graphs. In this work we study the number of Hamilton cycles in pseudo-random graphs. We use the so called (n,d,\lambda)-graphs as a model of pseudo-random graphs, these are d-regular graphs on n vertices, all of whose non-trivial eigenvalues are at most \lambda in their absolute values. We prove that under some rather mild assumptions on the vertex degree d=d(n) and the so called eigenvalue ratio d/\lambda, every (n,d,\lambda)-graph G contains n!*(d/n)^n*(1+o(1))^n Hamilton cycles, in accordance with (the expected value of) this count for a binomial random graph G(n,d/n).