2016/09/21 by Marcello Pelillo, Pelillo, Marcello, Ismail Elezi +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computer Vision and Pattern Recognition (cs.CV) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1609.06583
openalex publication_date 2016/09/21 · openalex created_date 2022/08/14 · openalex updated_date 2026/07/28
Introduced in the mid-1970's as an intermediate step in proving a\nlong-standing conjecture on arithmetic progressions, Szemer 'edi's regularity\nlemma has emerged over time as a fundamental tool in different branches of\ngraph theory, combinatorics and theoretical computer science. Roughly, it\nstates that every graph can be approximated by the union of a small number of\nrandom-like bipartite graphs called regular pairs. In other words, the result\nprovides us a way to obtain a good description of a large graph using a small\namount of data, and can be regarded as a manifestation of the all-pervading\ndichotomy between structure and randomness. In this paper we will provide an\noverview of the regularity lemma and its algorithmic aspects, and will discuss\nits relevance in the context of pattern recognition research.\n