Stručni rad

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

Sažetak

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.

Ključne riječi

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

Hrčak ID:

184160

URI

https://hrcak.srce.hr/184160

Datum izdavanja:

10.7.2017.

Podaci na drugim jezicima: hrvatski

Posjeta: 1.760 *