Linear equations, arithmetic progressions and hypergraph property testing

DOI10.4086/TOC.2005.V001A009MaRDI QIDQ3002762zbMATH OpenOpenAlexFDO

Authors Noga Alon, Asaf Shapira

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2005.v001a009

zbMATH Keywords

additive number theoryextremal problemshypergraphslinear algebralower boundsproperty testing

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Linear equations, arithmetic progressions and hypergraph property testing
• scientific article; zbMATH DE number 2086691
• scientific article; zbMATH DE number 1754615
• Every Monotone 3‐Graph Property is Testable
• Density and regularity theorems for semi-algebraic hypergraphs

Cited in

(13)

• Linear equations, arithmetic progressions and hypergraph property testing
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• A proof of Green's conjecture regarding the removal properties of sets of linear equations
• scientific article; zbMATH DE number 2086691 (Why is no real title available?)
• Polynomial removal lemmas for ordered graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Every Monotone 3‐Graph Property is Testable
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• On 3‐graphs with no four vertices spanning exactly two edges
• Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
• A characterization of testable hypergraph properties
• Hypergraph removal with polynomial bounds
• Complete 3-term arithmetic progression free sets of small size in vector spaces and other abelian groups

This page was built for publication: Linear equations, arithmetic progressions and hypergraph property testing

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