Matrix-free proof of a regularity characterization
type: Item
instance of: scholarly article
title: Matrix-free proof of a regularity characterization
zbMATH Open document ID: 1031.05070
author: Andrzej Czygrinow
author: B. Nagle
published in: The Electronic Journal of Combinatorics
publication date: 2004-02-05T00:00:00Z
full work available at URL: https://eudml.org/doc/123236
full work available at URL: v10i1r39.html
review text: Summary: The central concept in Szemerédi's powerful regularity lemma is the so-called \(\varepsilon\)-regular pair. A useful statement of \textit{N. Alon} et al. [J. Algorithms 16, 80-109 (1994; Zbl 0794.05119)] essentially equates the notion of an \(\varepsilon\)-regular pair with degree uniformity of vertices and pairs of vertices. The known proof of this characterization uses a clever matrix argument. This paper gives a simple proof of the characterization without appealing to the matrix argument of Alon et al. We show the \(\varepsilon\)-regular characterization follows from an application of Szemerédi's regularity lemma itself.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 2038337
zbMATH Keywords: regularity lemma
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2038337