An algorithmic regularity lemma for L_p regular sparse matrices

DOI10.1137/16M1086558MaRDI QIDQ5371027zbMATH OpenWikidataFDO

Authors Silouanos Brazitikos, Thodoris Karageorgos

Publication date 24 October 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic regularity lemmaregularity lemmasparse graphssparse matrices

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Classical Banach spaces in the general theory (46B25) Martingales with discrete parameter (60G42)

Abstract: We prove an algorithmic regularity lemma for $L_p$ regular matrices $(1<pleqinfty),$ a class of sparse $0,1$ matrices which obey a natural pseudorandomness condition. This extends a result of Coja-Oghlan, Cooper and Frieze who treated the case of $L_{infty}$ regular matrices. We also present applications of this result for tensors and MAX-CSP instances.

Recommendations

• Szemerédi's regularity Lemma for matrices and sparse graphs
• A unified view of graph regularity via matrix decompositions
• Szemerédi’s Regularity Lemma for Sparse Graphs
• An efficient sparse regularity concept
• L_p regular sparse hypergraphs

Cites work

• L_p regular sparse hypergraphs
• \(L_p\) regular sparse hypergraphs: box norms
• A concentration inequality for product spaces
• A noncommutative martingale convexity inequality
• Additive combinatorics
• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• An efficient sparse regularity concept
• Approximating the cut-norm via Grothendieck's inequality
• Gadgets, Approximation, and Linear Programming
• Grothendieck’s Theorem, past and present
• scientific article; zbMATH DE number 1944144 (Why is no real title available?)
• Quick approximation to matrices and applications
• Some optimal inapproximability results
• Szemerédi's regularity lemma via martingales
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The phase transition in inhomogeneous random graphs

Cited in

(1)

• A unified view of graph regularity via matrix decompositions

This page was built for publication: An algorithmic regularity lemma for \(L_p\) regular sparse matrices

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