A characterization for sparse \(\varepsilon\)-regular pairs
type: Item
instance of: scholarly article
title: A characterization for sparse \(\varepsilon\)-regular pairs
zbMATH Open document ID: 1112.05089
author: Stefanie Gerke
author: Angelika Steger
published in: The Electronic Journal of Combinatorics
publication date: 2007-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/127342
full work available at URL: v14i1r4.html
review text: Summary: We are interested in (\(\varepsilon\))-regular bipartite graphs which are the central objects in the regularity lemma of Szeméredi for sparse graphs. A bipartite graph \(G=(A\uplus B,E)\) with density \(p=|E|/(|A||B|)\) is (\(\varepsilon\))-regular if for all sets \(A'\subseteq A\) and \(B'\subseteq B\) of size \(|A'|\geq \varepsilon|A|\) and \(|B'|\geq \varepsilon |B|\), it holds that \(|e_G(A',B')/(|A'||B'|)- p| \leq \varepsilon p\). In this paper we prove a characterization for (\(\varepsilon\))-regularity. That is, we give a set of properties that hold for each (\(\varepsilon\))-regular graph, and conversely if the properties of this set hold for a bipartite graph, then the graph is \(f(\varepsilon\))-regular for some appropriate function \(f\) with \(f(\varepsilon)\to 0\) as \(\varepsilon\rightarrow 0\). The properties of this set concern degrees of vertices and common degrees of vertices with sets of size \(\Theta(1/p)\) where \(p\) is the density of the graph in question.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 5132838
zbMATH Keywords: regularity lemma
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5132838