Geodesic
Matrix-free proof of a regularity characterization
The electronic journal of combinatorics, Tome 10 (2003)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
The central concept in Szemerédi's powerful regularity lemma is the so-called $\epsilon$-regular pair. A useful statement of Alon et al. essentially equates the notion of an $\epsilon$-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 $\epsilon$-regular characterization follows from an application of Szemerédi's regularity lemma itself.
DOI : 10.37236/1732
Classification : 05C35, 05C80
Mots-clés : regularity lemma 
A. Czygrinow; B. Nagle. Matrix-free proof of a regularity characterization. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1732
@article{10_37236_1732,
     author = {A. Czygrinow and B. Nagle},
     title = {Matrix-free proof of a regularity characterization},
     journal = {The electronic journal of combinatorics},
     year = {2003},
     volume = {10},
     doi = {10.37236/1732},
     zbl = {1031.05070},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1732/}
}
TY  - JOUR
AU  - A. Czygrinow
AU  - B. Nagle
TI  - Matrix-free proof of a regularity characterization
JO  - The electronic journal of combinatorics
PY  - 2003
VL  - 10
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1732/
DO  - 10.37236/1732
ID  - 10_37236_1732
ER  - 
%0 Journal Article
%A A. Czygrinow
%A B. Nagle
%T Matrix-free proof of a regularity characterization
%J The electronic journal of combinatorics
%D 2003
%V 10
%U http://geodesic.mathdoc.fr/articles/10.37236/1732/
%R 10.37236/1732
%F 10_37236_1732

Cité par Sources :