Hamilton cycles in random subgraphs of pseudo-random graphs
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}\).
- Hamilton cycles in the line graph of a random graph
- On packing Hamilton cycles in \(\varepsilon\)-regular graphs
- Hamiltonicity in prime sum graphs
- Discrepancy and eigenvalues of Cayley graphs
- Embedding cycles in finite planes
- On the number of Hamilton cycles in pseudo-random graphs
- Sparse pseudo‐random graphs are Hamiltonian
- Expanders Are Universal for the Class of All Spanning Trees
- Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
- Powers of Hamilton cycles in pseudorandom graphs
- On covering expander graphs by Hamilton cycles
- Pseudo-random graphs
- Expanders are universal for the class of all spanning trees
- Hamilton cycles in highly connected and expanding graphs
- Hamilton cycles in pseudorandom graphs
- Hamilton cycles in pseudorandom graphs (extended abstract)
This page was built for publication: Hamilton cycles in random subgraphs of pseudo-random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849919)
