Professional paper

Probabilistic regularity lemma and its applications in combinatorics

Filip Bosnić ; Fakultät für Mathematik, Universität Bielefeld
Vjekoslav Kovač ; †Matematički odsjek, Prirodoslovno-matematički fakultet, Sveučilište u Zagrebu, Zagreb

Abstract

This paper begins with two well-known theorems from additive combinatorics, which are then reduced to a result from graph theory. A further generalization is formulated in the language of probability
theory, in order to be established using the probabilistic variant of the Szemerédi regularity lemma. This lemma provides a decomposition of an arbitrary random variable into a structured part, a seudorandom part, and an error, and the paper presents its complete proof.

Keywords

arithmetic progression; Roth’s theorem; corner; undirected graph; pseudorandomness; conditional expectation

Hrčak ID:

184160

URI

https://hrcak.srce.hr/184160

Publication date:

10.7.2017.

Article data in other languages: croatian

Visits: 2.282 *