Hamilton cycles in random subgraphs of pseudo-random graphs (Q1849919): Difference between revisions

Very crudely speaking, a pseudo-random graph \(G\) on \(n\) vertices is one in which, if every vertex has degree about \(\alpha(n) n\), then every vertex in the subgraph induced by any (not too small) set of \(r\) vertices has degree about \(\alpha(n) r\)---that is, edges are ``evenly spread out'' through the graph. This feature is of course shared by a typical random graph (hence the name). The study of such graphs was initiated in the 1980's; see for example [\textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson}, Quasi-random graphs, Combinatorica 9, 345-362 (1989; Zbl 0715.05057)] and [\textit{A. Thomason}, Random graphs, strongly regular graphs and pseudo-random graphs, Surveys in combinatorics 1987, Lond. Math. Soc. Lect. Note Ser. 123, 173-195 (1987; Zbl 0672.05068)]. It has been known since these papers that (accurate formulations of) pseudo-randomness are equivalent to various other properties: one of these is that \(\lambda\), the maximum of the moduli of all eigenvalues of (the adjacency matrix of) \(G\) other than the largest eigenvalue, should be small compared with that largest eigenvalue. A recent survey of random graphs from this point of view is [\textit{M. Krivelevich} and \textit{B. Sudakov}, Pseudo-random graphs, submitted], a version of which may be viewed at \url{http://www.math.tau.ac.il/~krivelev/prsurvey.ps}. In the paper under review, the notion of a pseudo-random graph used is an \(r(n)\)-regular graph \(G\) on \(n\) vertices where \(\lambda\), the maximum modulus of all eigenvalues of \(G\) other than \(r\) itself, satisfies \(\lambda=o(r(n))\) as \(n\rightarrow\infty\). (Note that this implies we are working with a family of such graphs, for each value of \(n\).) A trite example is the family of complete graphs \(K_{n}\).