Linear equations, arithmetic progressions and hypergraph property testing

ABSTRACT

For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H satisfies property PD (resp. P*D) if it contains no copy (resp. induced copy) of D. Our goal in this paper is to classify the k-graphs D for which there are property-testers for testing PD and P*D whose query complexity is polynomial in 1/ε. For such k-graphs, we say that PD (or P*D) is easily testable.For P*D, we prove that aside from a single 3-graph, P*D is easily testable if and only if D is a single k-edge. For large k, we obtain stronger lower bounds than those obtained for the general case on the query complexity of testing P*D for any D other than the single k-edge. These bounds are proved by applying a more sophisticated technique than the basic one that works for all k. These results extend and improve previous results about graphs [5] and k-graphs [18].For PD, we show that for any k-partite k-graph D, PD, is easily testable, by giving an efficient one-sided error-property tester, which improves the one obtained by [18]. We further prove a nearly matching lower bound on the query complexity of such a property-tester. Finally, we give a sufficient condition for inferring that PD is not easily testable. Though our results do not supply a complete characterization of the k-graphs for which PD is easily testable, they are a natural extension of the previous results about graphs [1].Our proofs combine results and arguments from additive number theory, linear algebra and extremal hypergraph theory. We also develop new techniques, which are of independent interest. The first is a construction of a dense set of integers, which does not contain a subset that satisfies a certain set of linear equations. The second is an algebraic construction of certain extremal hypergraphs. We demonstrate the applicability of this last construction by resolving several cases of an open problem raised by Brown, Erdös and Sós in 1973. These two techniques have already been applied in two recent subsequent papers [6], [27].

REFERENCES

• 1: N. Alon, Testing Subgraphs in Large Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.434, October 14-17, 2001
• 2: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 3: N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451--476.
• 4: Noga Alon , Asaf Shapira, Testing subgraphs in directed graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780644]
• 5: Noga Alon , Asaf Shapira, A characterization of easily testable induced subgraphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: N. Alon and A. Shapira, On an extremal hypergraph problem of Brown, Erdös and Sós, submitted.
• 7: F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc. National Academy of Sciences USA 32 (1946), 331--332.
• 8: W. G. Brown, P. Erdö;s and V. T. Sós, Some extremal problems on r-graphs, New Direction in the Theory of Graphs, Proc. 3rd Ann Arbor Conference on Graph Theory, Academic Press, New York, 1973, 55--63.
• 9: W. G. Brown, P. Erdös and V. T. Sós. On the existence of triangulated spheres in 3-graphs and related problems, Period. Math. Hung., 3 (1973), 221--228.
• 10: P. Erdös, P. Frankl and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986) 113--121.
• 11: E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The BEATCS 75 (2001), 97--126.
• 12: Peter Frankl , Vojtech Rödl, Extremal problems on set systems, Random Structures & Algorithms, v.20 n.2, p.131-164, March 2002 [doi>10.1002/rsa.10017.abs]
• 13: O. Goldreich, Combinatorial property testing - a survey, In: Randomization Methods in Algorithm Design, AMS-DIMACS (1998), 45--60.
• 14: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 15: Oded Goldreich , Luca Trevisan, Three theorems regarding testing graph properties, Random Structures & Algorithms, v.23 n.1, p.23-57, August 2003 [doi>10.1002/rsa.10078]
• 16: I. S. Gradshteyn and I. M. Ryzhik, Tables of Integrals, Series, and Products, 6th Edition, Academic Press (2000), p. 1110.
• 17: W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, manuscript.
• 18: Yoshiharu Kohayakawa , Brendan Nagle , Vojtech Rödl, Efficient Testing of Hypergraphs, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.1017-1028, July 08-13, 2002
• 19: I. Laba and M. Lacey, On sets of integers not containing long arithmetic progressions, unpublished manuscript.
• 20: Brendan Nagle , Vojtêch Rödl, Regularity properties for triple systems, Random Structures & Algorithms, v.23 n.3, p.264-332, October 2003 [doi>10.1002/rsa.10094]
• 21: B. Nagle, V. Rödl and M. Schacht, The counting lemma for regular k-uniform hypegraphs, manuscript.
• 22: Vojtěch Rödl , Jozef Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms, v.25 n.1, p.1-42, August 2004 [doi>10.1002/rsa.20017]
• 23: D. Ron, Property testing, in: Handbook of Randomized Computing, Vol. II, Kluwer Acad. Pub., 2001, 597--649.
• 24: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 25: I.Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II. 939--945.
• 26: G.N. Sárközy and S. M. Selkow, On a Turán-type hypegraph problem of Brown, Erdős and T. Sós, submitted.
• 27: A. Shapira, Behrend-type constructions for sets of linear equations, submitted.
• 28: E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS, 1978, 399--401.
• 29: E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), 199--245.