Perhaps the most important structural result about general large dense graphs is the Szemerédi regularity lemma. Here is a standard formulation of that lemma: … 975 more words

## Tags » Szemeredi Regularity Lemma

#### Some ingredients in Szemerédi's proof of Szemerédi's theorem

A few days ago, Endre Szemerédi was awarded the 2012 Abel prize “for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory.” The full citation for the prize may be… 2,556 more words

#### Importing the Szemerédi Regularity Lemma into Machine Learning

*Synopsis of a recent direction of work with Gábor Sárközy, Endre Szemerédi and Fei Song — “The Regularity Lemma is a deep result from extremal graph theory having great utility as a fundamental tool to prove theoretical results, but can it be employed in more “practical” settings?”* 2,714 more words

#### Nonstandard analysis as a completion of standard analysis

Many structures in mathematics are *incomplete* in one or more ways. For instance, the field of rationals or the reals are *algebraically incomplete*, because there are some non-trivial algebraic equations (such as in the case of the rationals, or in the case of the reals) which could… 6,213 more words

#### Szemeredi's regularity lemma via the correspondence principle

In a previous post, we discussed the Szemerédi regularity lemma, and how a given graph could be regularised by partitioning the vertex set into random neighbourhoods. 2,869 more words

#### Szemeredi's regularity lemma via random partitions

In the theory of dense graphs on vertices, where is large, a fundamental role is played by the Szemerédi regularity lemma:

2,025 more wordsLemma 1 (Regularity lemma, standard version) …