2009/04/30 by Ishigami, Yoshiyasu
#05C15 #05D40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.0904.4927
The well-known regularity lemma of E. Szemerédi for graphs (i.e. 2-uniform hypergraphs) claims that for any graph there exists a vertex partition with the property of quasi-randomness. We give a simple construction of such a partition. It is done just by taking a constant-bounded number of random vertex samplings only one time (thus, iteration-free). Since it is independent from the definition of quasi-randomness, it can be generalized very naturally to hypergraph regularization. In this expository note, we show only a graph case of the paper [I] on hypergraphs, but may help the reader to access [I].