Szemerédi's regularity lemma via martingales

zbMATH Open1344.05076arXiv1410.5966MaRDI QIDQ311501FDOQ311501

Vassilis Kanellopoulos, Pandelis Dodos, Thodoris Karageorgos

Publication date: 13 September 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1410.5966

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

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

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)

Cites Work

• Title not available (Why is that?)
• Probability
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sharp uniform convexity and smoothness inequalities for trace norms
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• A noncommutative martingale convexity inequality
• Quick approximation to matrices and applications
• Ramsey theory for product spaces
• A simple proof of the density Hales-Jewett theorem
• Title not available (Why is that?)
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• An Abstract Szemerédi Regularity Lemma
• Primitive Recursive Bounds for Van Der Waerden Numbers
• A new proof of the density Hales-Jewett theorem
• A density version of the Carlson-Simpson theorem
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• Title not available (Why is that?)
• Title not available (Why is that?)
• A variant of the hypergraph removal lemma
• Szemerédi's lemma for the analyst
• A concentration inequality for product spaces

Cited In (4)

• An Abstract Szemerédi Regularity Lemma
• A concentration inequality for product spaces
• Concentration estimates for functions of finite high‐dimensional random arrays
• An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices

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)