TY - GEN

T1 - Testing hereditary properties of ordered graphs and matrices

AU - Alon, Noga

AU - Ben-Eliezer, Omri

AU - Fischer, Eldar

N1 - Publisher Copyright:
© 2017 IEEE.

PY - 2017/11/10

Y1 - 2017/11/10

N2 - 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.

AB - 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.

KW - Ramsey

KW - hereditary properties

KW - ordered graphs

KW - property testing

KW - removal lemma

UR - http://www.scopus.com/inward/record.url?scp=85041115245&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041115245&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.83

DO - 10.1109/FOCS.2017.83

M3 - Conference contribution

AN - SCOPUS:85041115245

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 848

EP - 858

BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

PB - IEEE Computer Society

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

Y2 - 15 October 2017 through 17 October 2017

ER -