zbMATH — the first resource for mathematics

Efficient removal lemmas for matrices. (English) Zbl 07204026
Summary: It was recently proved in Alon et al. (2017) that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing the following ordered matrix removal lemma: For any finite alphabet \(\Gamma \), any hereditary property \(\mathcal{P}\) of matrices over \(\Gamma \), and any \(\varepsilon > 0\), there exists \(f_{\mathcal{P}}(\epsilon )\) such that for any matrix \(M\) over \(\Gamma\) that is \(\varepsilon \)-far from satisfying \(\mathcal{P} \), most of the \(f_{\mathcal{P}}(\epsilon ) \times f_{\mathcal{P}}(\epsilon )\) submatrices of \(M\) do not satisfy \(\mathcal{P} \). Here being \(\varepsilon \)-far from \(\mathcal{P}\) means that one needs to modify at least an \(\varepsilon \)-fraction of the entries of \(M\) to make it satisfy \(\mathcal{P} \). However, in the above general removal lemma, \(f_{\mathcal{P}}(\epsilon )\) grows very quickly as a function of \(\varepsilon^{- 1} \), even when \(\mathcal{P}\) is characterized by a single forbidden submatrix. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following, which can be seen as an efficient binary matrix analogue of the triangle removal lemma: For any fixed \(s \times t\) binary matrix \(A\) and any \(\varepsilon > 0\) there exists \(\delta > 0\) polynomial in \(\varepsilon \), such that for any binary matrix \(M\) in which less than a \(\delta \)-fraction of the \(s \times t\) submatrices are equal to \(A\), there exists a set of less than an \(\varepsilon \)-fraction of the entries of \(M\) that intersects every copy of \(A\) in \(M\). We generalize the work of Alon et al. (2007) and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas.
06-XX Order, lattices, ordered algebraic structures
Full Text: DOI
[1] Alon, N., Testing subgraphs in large graphs, Proc. 42th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 2001, 434-441; also Random Structures & Algorithms, 21, 359-370 (2002) · Zbl 1027.68095
[2] Alon, N., Ben-Eliezer, O., Fischer, E.: Testing hereditary properties of ordered graphs and matrices. In: Proc. 58th Annu. Symp. Foundations of Computer Science (FOCS), pp 848-858. IEEE (2017)
[3] Alon, N.; Duke, RA; Lefmann, H.; Rödl, V.; Yuster, R., The algorithmic aspects of the regularity lemma, Proc. 33th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1992, 473-481; also Journal of Algorithms, 16, 80-109 (1994) · Zbl 0794.05119
[4] Alon, N.; Fischer, E.; Krivelevich, M.; Szegedy, M., Efficient testing of large graphs, Proc. 40th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1999, 656-666; also Combinatorica, 20, 451-476 (2000) · Zbl 1052.68096
[5] Alon, N.; Fischer, E.; Newman, I., Efficient testing of bipartite graphs for forbidden induced subgraphs, SIAM J. Comput, 37, 959-976 (2007) · Zbl 1141.05073
[6] Alon, N.; Fox, J., Easily testable graph properties, Combin. Probab. Comput., 24, 646-657 (2015) · Zbl 1371.05136
[7] Alon, N.; Krivelevich, M.; Newman, I.; Szegedy, M., Regular languages are testable with a constant number of queries, Proc. 40th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1999, 645-655; also SIAM J. Comput., 30, 1842-1862 (2001) · Zbl 0992.68064
[8] Alon, N.; Shapira, A., A characterization of easily testable induced subgraphs, Combin. Probab. Comput., 15, 791-805 (2006)
[9] Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error, SIAM J. Comput. 37 (2008), 1703-1727; also Proc. 46th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 429-438 (2005)
[10] Behrend, F., On sets of integers which contain no three terms in arithmetic progression, Proc. Nat. Acad. Sci., 32, 331-332 (1946) · Zbl 0060.10302
[11] Ben-Eliezer, O., Fischer, E.: Earthmover resilience and testing in ordered structures. In: Proc. IEEE 33rd Computational Complexity Conference (CCC), pp 18:1-18:35 (2018)
[12] Ben-Eliezer, O., Fischer, E., Levi, A., Yoshida, Y.: Limits of ordered graphs and images. arXiv:1811.02023
[13] Ben-Eliezer, O., Korman, S., Reichman, D.: Deleting and testing forbidden patterns in multi-dimensional arrays. In: Proc. 44th Int. Colloq. Automata Languages Programming (ICALP), pp 9:1-9:14 (2017)
[14] Conlon, D.; Fox, J., Bounds for graph regularity and removal lemmas, Geom. Funct. Anal., 22, 1191-1256 (2012) · Zbl 1256.05114
[15] Conlon, D.; Fox, J., Graph Removal Lemmas, Surveys in Combinatorics 2013, 1-49, London Math. Soc Lecture Note Ser, vol. 409 (2013), Cambridge: Cambridge University Press, Cambridge · Zbl 1301.05309
[16] Fischer, E.; Newman, I., Testing of matrix-poset properties, Combinatorica, 27, 293-327 (2007) · Zbl 1164.94004
[17] Fischer, E., Rozenberg, E.: Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects. Proc. RANDOM, 464-478 (2007) · Zbl 1171.05374
[18] Fox, J., A new proof of the graph removal lemma, Ann. of Math., 174, 561-579 (2011) · Zbl 1231.05133
[19] Gishboliner, L., Shapira, A.: Removal lemmas with polynomial bounds. In: Proc. 49th ACM SIGACT Symp Theory of Computing (STOC), pp 510-522 (2017) · Zbl 1370.68323
[20] Goldreich, O.; Goldwasser, S.; Ron, D., Property testing and its connection to learning and approximation, Proc. 37th Annu. Symp. Foundations of Computer Science (FOCS), IEEE, 1996, 339-348; also J. ACM, 45, 653-750 (1998) · Zbl 1065.68575
[21] Gowers, T., A new proof of Szemerédi’s theorem, Geom. Funct. Anal., 11, 465-588 (2001) · Zbl 1028.11005
[22] Lovász, L., Szegedy, B.: Regularity partitions and the topology of graphons, in An irregular mind, 415-445, Bolyai Soc. Math. Stud. 21, János Bolyai Math. Soc., Budapest (2010) · Zbl 1242.05188
[23] Nagle, B.; Rődl, V.; Schacht, M., The counting lemma for regular k-uniform hypergraphs, Random Struct. Algoritm., 28, 113-179 (2006) · Zbl 1093.05045
[24] Rödl, V.; Skokan, J., Regularity lemma for uniform hypergraphs, Random Struct. Algoritm., 25, 1-42 (2004) · Zbl 1046.05042
[25] Rubinfeld, R.; Sudan, M., Robust characterizations of polynomials with applications to program testing, Siam. J. Comput., 25, 252-271 (1996) · Zbl 0844.68062
[26] Ruzsa, I.Z., Szemerédi, E.: Triple Systems with No Six Points Carrying Three Triangles, Combinatorics, Vol. II, 939-945, Coll. Math. Soc. J. Bolyai 18, North-Holland, Amsterdam-New York (1978) · Zbl 0393.05031
[27] Sudan, M.: Invariance in property testing. In: Goldreich, O. (ed.) Property Testing: Current Research and Surveys. Vol. 6390 of Lecture Notes in Computer Science, pp 211-227. Springer (2010) · Zbl 1309.68055
[28] Szemerédi, E.: Regular partitions of graphs, in problèmes Combinatoires et théorie des Graphes, Colloq. Internat. CNRS 260, Orsay, 399-401 (1976)
[29] Tao, T., A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A, 113, 1257-1280 (2006) · Zbl 1105.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.