Testability and repair of hereditary hypergraph properties
From MaRDI portal
Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)
Abstract: Recent works of Alon-Shapira and R"odl-Schacht have demonstrated that every hereditary property of undirected graphs or hypergraphs is testable with one-sided error; informally, this means that if a graph or hypergraph satisfies that property "locally" with sufficiently high probability, then it can be perturbed (or "repaired") into a graph or hypergraph which satisfies that property "globally". In this paper we make some refinements to these results, some of which may be surprising. In the positive direction, we strengthen the results to cover hereditary properties of multiple directed polychromatic graphs and hypergraphs. In the case of undirected graphs, we extend the result to continuous graphs on probability spaces, and show that the repair algorithm is "local" in the sense that it only depends on a bounded amount of data; in particular, the graph can be repaired in a time linear in the number of edges. We also show that local repairability also holds for monotone or partite hypergraph properties (this latter result is also implicitly in work of Ishigami). In the negative direction, we show that local repairability breaks down for directed graphs, or for undirected 3-uniform hypergraphs. The reason for this contrast in behavior stems from (the limitations of) Ramsey theory.
Recommendations
Cites work
- 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
- Efficient testing of large graphs
- Every Monotone 3‐Graph Property is Testable
- Every monotone graph property is testable
- scientific article; zbMATH DE number 3609704 (Why is no real title available?)
- scientific article; zbMATH DE number 2086691 (Why is no real title available?)
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Integer sets containing no arithmetic progressions
- Limits of dense graph sequences
- Locally testable codes and PCPs of almost-linear length
- On exchangeable random variables and the statistics of large graphs and hypergraphs
- On the efficiency of local decoding procedures for error-correcting codes
- Property testing and its connection to learning and approximation
- Quasi-random graphs
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Regular Partitions of Hypergraphs: Regularity Lemmas
- Regularity Lemma for k-uniform hypergraphs
- Representations for partially exchangeable arrays of random variables
- Robust Characterizations of Polynomials with Applications to Program Testing
- Symmetries on random arrays and set-indexed processes
- The counting lemma for regular k‐uniform hypergraphs
Cited in
(31)- 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
- Online containers for hypergraphs, with applications to linear equations
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Testable and untestable classes of first-order formulae
- A measure-theoretic approach to the theory of dense hypergraphs
- The inducibility of blow-up graphs
- 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
- Testing hereditary properties of sequences
- Earthmover Resilience and Testing in Ordered Structures
- Semantic limits of dense combinatorial objects
- The poset of hypergraph quasirandomness
- Quantum invariant families of matrices in free probability
- Testing odd-cycle-freeness in Boolean functions
- Hypergraph regularity and random sampling
- Local-vs-global combinatorics
- Random graphs with a given degree sequence
- Posets are easily testable
- A characterization of testable hypergraph properties
- A polynomial removal lemma for posets (extended abstract)
This page was built for publication: Testability and repair of hereditary hypergraph properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057063)
