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
Datum izdavanja:
10.7.2017.
Posjeta: 1.852 *