Testability and repair of hereditary hypergraph properties

DOI10.1002/rsa.20300zbMath1208.05093arXiv0801.2179MaRDI QIDQ3057063

Terence C. Tao, Tim D. Austin

Publication date: 24 November 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

de Finetti's theorem; local testability; exchangeable processes; hypergraph regularity Lemma

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

60C05: Combinatorial probability

68W20: Randomized algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Testing Linear-Invariant Non-linear Properties: A Short Report, Local Property Reconstruction and Monotonicity, Green’s Conjecture and Testing Linear Invariant Properties, Testable and untestable classes of first-order formulae, A measure-theoretic approach to the theory of dense hypergraphs, Quantum invariant families of matrices in free probability, Random graphs with a given degree sequence, A removal lemma for systems of linear equations over finite fields, Estimating and understanding exponential random graph models, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

Cites Work

• Unnamed Item
• Unnamed Item
• Limits of dense graph sequences
• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Representations for partially exchangeable arrays of random variables
• Symmetries on random arrays and set-indexed processes
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Integer sets containing no arithmetic progressions
• Property testing and its connection to learning and approximation
• On the efficiency of local decoding procedures for error-correcting codes
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Locally testable codes and PCPs of almost-linear length
• Every monotone graph property is testable
• Regularity Lemma for k-uniform hypergraphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Every Monotone 3‐Graph Property is Testable
• The counting lemma for regular k‐uniform hypergraphs
• Quasi-random graphs
• Efficient testing of large graphs