An analogue of the Szemeredi Regularity Lemma for bounded degree graphs
Abstract
Description
We show that a sufficiently large graph of bounded degree can be decomposed into quasi-homogeneous pieces. The result can be viewed as a "finitarization" of the classical Farrell-Varadarajan Ergodic Decomposition Theorem.
Corrected an error in the proof of the Homogeneity Lemma. A new result is proved about edge-colorings of convergent graph sequences
Corrected an error in the proof of the Homogeneity Lemma. A new result is proved about edge-colorings of convergent graph sequences