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

An analytic approach to sparse hypergraphs: hypergraph removal, Testing Linear-Invariant Non-linear Properties: A Short Report, Local Property Reconstruction and Monotonicity, Green’s Conjecture and Testing Linear Invariant Properties, A unified framework for testing linear‐invariant properties, The poset of hypergraph quasirandomness, Unnamed Item, Online containers for hypergraphs, with applications to linear equations, Testable and untestable classes of first-order formulae, A measure-theoretic approach to the theory of dense hypergraphs, The inducibility of blow-up graphs, 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, Minimum number of edges that occur in odd cycles, Differential calculus on graphon space, Lower bounds for testing triangle-freeness in Boolean functions, Estimating and understanding exponential random graph models, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, σ-algebras for quasirandom hypergraphs, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing

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