Geodesic
Matrix-free proof of a regularity characterization
The electronic journal of combinatorics, Tome 10 (2003)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
A. Czygrinow; B. Nagle. Matrix-free proof of a regularity characterization. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1732

Cité par Sources :