Testing hereditary properties of ordered graphs and matrices

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

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

10 Scopus citations


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
Number of pages11
ISBN (Electronic)9781538634646
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
ISSN (Print)0272-5428


Other58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science


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


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

Cite this