Linear equations, arithmetic progressions arid hypergraph property testing

Noga Mordechai Alon, Asaf Shapira

Research output: Contribution to conferencePaper

2 Scopus citations

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. PD*) 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 P D and PD* whose query complexity is polynomial in 1/ε. For such k-graphs, we say that PD (or PD*) is easily testable. For PD*, we prove that aside from a single 3-graph, PD* 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 PD* 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].

Original languageEnglish (US)
Pages708-717
Number of pages10
StatePublished - Jul 1 2005
Externally publishedYes
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Linear equations, arithmetic progressions arid hypergraph property testing'. Together they form a unique fingerprint.

  • Cite this

    Alon, N. M., & Shapira, A. (2005). Linear equations, arithmetic progressions arid hypergraph property testing. 708-717. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.