Testability and repair of hereditary hypergraph properties
From MaRDI portal
Publication:3057063
DOI10.1002/rsa.20300zbMath1208.05093arXiv0801.2179OpenAlexW3083751883MaRDI QIDQ3057063
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
Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Testing graphs against an unknown distribution, Online containers for hypergraphs, with applications to linear equations, σ-algebras for quasirandom hypergraphs, Hypergraph regularity and random sampling, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Unnamed Item, Local-vs-global combinatorics, Testable and untestable classes of first-order formulae, Random graphs with a given degree sequence, Estimating and understanding exponential random graph models, A measure-theoretic approach to the theory of dense hypergraphs, The inducibility of blow-up graphs, Semantic limits of dense combinatorial objects, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, An analytic approach to sparse hypergraphs: hypergraph removal, A removal lemma for systems of linear equations over finite fields, Quantum invariant families of matrices in free probability, Testing Linear-Invariant Non-linear Properties: A Short Report, Local Property Reconstruction and Monotonicity, Green’s Conjecture and Testing Linear Invariant Properties, Earthmover Resilience and Testing in Ordered Structures, Minimum number of edges that occur in odd cycles, A unified framework for testing linear‐invariant properties, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Unnamed Item, Differential calculus on graphon space, The poset of hypergraph quasirandomness, Lower bounds for testing triangle-freeness in Boolean functions
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
