Szemerédi's regularity lemma via martingales

MaRDI QIDQ311501zbMATH OpenFDO

Authors Pandelis Dodos, Vassilis Kanellopoulos, Thodoris Karageorgos

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.5966, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

normsemiringmartingale difference sequencesSzemerédi's regularity lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10)

Abstract: We prove a variant of the abstract probabilistic version of Szemer'edi's regularity lemma, due to Tao, which applies to a number of structures (including graphs, hypergraphs, hypercubes, graphons, and many more) and works for random variables in $L_p$ for any $p>1$. Our approach is based on martingale difference sequences.

Recommendations

• Szemerédi's regularity lemma revisited
• scientific article; zbMATH DE number 2086426
• Regularity lemmas for hypergraphs and quasi-randomness
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Hypergraph regularity and the multidimensional Szemerédi theorem

Cites work

• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• A concentration inequality for product spaces
• A density version of the Carlson-Simpson theorem
• A new proof of the density Hales-Jewett theorem
• A noncommutative martingale convexity inequality
• A simple proof of the density Hales-Jewett theorem
• A variant of the hypergraph removal lemma
• Additive combinatorics
• An Abstract Szemerédi Regularity Lemma
• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• An epsilon of room. II: Pages from year three of a mathematical blog
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Large networks and graph limits
• Primitive Recursive Bounds for Van Der Waerden Numbers
• Probability. Theory and examples.
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Quick approximation to matrices and applications
• Ramsey theory for product spaces
• Sharp uniform convexity and smoothness inequalities for trace norms
• Szemerédi's lemma for the analyst
• Szemerédi's regularity lemma revisited

Cited in

(7)

• An Abstract Szemerédi Regularity Lemma
• An algorithmic regularity lemma for \(L_p\) regular sparse matrices
• A concentration inequality for product spaces
• Szemerédi's lemma for the analyst
• Szemerédi's regularity lemma revisited
• An Explicit Croot-Łaba-Sisask Lemma Free of Probabilistic Language
• Concentration estimates for functions of finite high‐dimensional random arrays

This page was built for publication: Szemerédi's regularity lemma via martingales

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311501)