Testing hereditary properties of ordered graphs and matrices

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

We consider properties of edge-colored vertex-ordered graphs} - graphs with a totally ordered vertex set and a finite set of possible edge colors - showing that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of two-dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS05; SICOMP08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP07] concerning testing of matrix properties.The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that if such a graph is far enough from satisfying a certain hereditary property, then most of its induced vertex-ordered subgraphs on a certain (large enough) constant number of vertices do not satisfy the property as well.The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for multipartite graphs with undesirable edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph.

Original languageEnglish (US)
Title of host publicationProceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
PublisherIEEE Computer Society
Pages848-858
Number of pages11
ISBN (Electronic)9781538634646
DOIs
StatePublished - Nov 10 2017
Externally publishedYes
Event58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States
Duration: Oct 15 2017Oct 17 2017

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
Volume2017-October
ISSN (Print)0272-5428

Other

Other58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
Country/TerritoryUnited States
CityBerkeley
Period10/15/1710/17/17

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Ramsey
  • hereditary properties
  • ordered graphs
  • property testing
  • removal lemma

Fingerprint

Dive into the research topics of 'Testing hereditary properties of ordered graphs and matrices'. Together they form a unique fingerprint.

Cite this