Hamilton cycles in random subgraphs of pseudo-random graphs
type: Item
instance of: scholarly article
title: Hamilton cycles in random subgraphs of pseudo-random graphs
zbMATH Open document ID: 1007.05071
DOI: 10.1016/S0012-365X(01)00464-2
author: Michael Krivelevich
author: Alan Frieze
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: 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}\).
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1838916
zbMATH Keywords: pseudo-random graph
zbMATH Keywords: Hamilton cycle
reviewed by: David B. Penman
MaRDI profile type: Publication
Wikidata QID: Q57401524
DBLP publication ID: journals/dm/FriezeK02
description: scientific article; zbMATH DE number 1838916