A simple regularization of graphs
| dc.creator | Ishigami, Yoshiyasu | |
| dc.date | 2009-04-30 | |
| dc.date.accessioned | 2026-07-07T13:10:39Z | |
| dc.date.available | 2026-07-07T13:10:39Z | |
| dc.description | 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]. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0904.4927 | |
| dc.identifier | http://arxiv.org/abs/0904.4927 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/229063 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D40, 05C15 | |
| dc.title | A simple regularization of graphs | |
| dc.type | text |