Testability and repair of hereditary hypergraph properties

Tim Austin, Terence Tao

Research output: Contribution to journalArticle

Abstract

Recent works of Alon-Shapira (A characterization of the (natural) graph properties testable with one-sided error. Available at: http://www.math.tau.ac.il/~nogaa/PDFS/heredit2.pdf) and Rödl-Schacht (Generalizations of the removal lemma, Available at: http://www.informatik.huberlin.de/~schacht/pub/preprints/gen_removal.pdf) 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 (Ishigamis work Removal lemma for infinitelymany forbidden hypergraphs and property testing. Available at: arXiv.org: math.CO/0612669)). 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.

Original languageEnglish (US)
Pages (from-to)373-463
Number of pages91
JournalRandom Structures and Algorithms
Volume36
Issue number4
DOIs
StatePublished - Jul 2010

Keywords

  • Exchangeable processes
  • Hypergraph regularity lemma
  • Local testability
  • de Finetti's theorem

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Testability and repair of hereditary hypergraph properties'. Together they form a unique fingerprint.

  • Cite this