### 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 |

Publisher | IEEE Computer Society |

Pages | 848-858 |

Number of pages | 11 |

ISBN (Electronic) | 9781538634646 |

DOIs | |

State | Published - Nov 10 2017 |

Externally published | Yes |

Event | 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States Duration: Oct 15 2017 → Oct 17 2017 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science - Proceedings |
---|---|

Volume | 2017-October |

ISSN (Print) | 0272-5428 |

### Other

Other | 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 |
---|---|

Country | United States |

City | Berkeley |

Period | 10/15/17 → 10/17/17 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### 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

*Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017*(pp. 848-858). [8104115] (Annual Symposium on Foundations of Computer Science - Proceedings; Vol. 2017-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2017.83