Computer Science/Discrete Mathematics Seminar I

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).