Sparse quasi-random graphs
type: Item
instance of: scholarly article
title: Sparse quasi-random graphs
zbMATH Open document ID: 0997.05090
author: Ron Graham
author: Fan Chung
published in: Combinatorica
publication date: 2002-11-03T00:00:00Z
review text: Let \(G_{1/2}(n)\) denote a random graph with \(n\) vertices in which each pair is selected to be an edge independently with probability \(1/2\). Almost all of them satisfy several basic properties which turn out to be equivalent. Families of graphs satisfying this equivalence class of properties are called quasi-random, see e.g. \textit{F. R. K. Chung}, textit{R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345--362 (1989; Zbl 0715.05057)]. So far most of the results dealt with dense quasi-random graphs (having \(cn^2\) edges for some \(c>0\) as \(n \rightarrow \infty\)). This article studies quasi-random graphs with \(o(n^2)\) edges for analogous results, which are more difficult, due for example to the possible absence of certain local structures, such as 4-cycles.
reviewed by: András Recski
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1822336
zbMATH Keywords: random graphs
MaRDI profile type: Publication
full work available at URL: s004930200010
OpenAlex ID: W2134981701
Wikidata QID: Q105584592
DOI: 10.1007/S004930200010
Recommended article: Quasi-random graphs
Recommended article: Random Subgraphs in Sparse Graphs
Recommended article: Random perturbation of sparse graphs
Recommended article: Q4697461
Recommended article: Quasirandomness in Graphs
Recommended article: Sparse graphs: Metrics and random models
Recommended article: Dismantling Sparse Random Graphs
Recommended article: Countable sparse random graphs
description: scientific article; zbMATH DE number 1822336