Abstract:

 For a fixed k-uniform hypergraph D (k-graph for short, k > 2), we say
that a k-graph H satisfies property P_D (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 P_D and
P*_D whose query complexity is polynomial in 1/\epsilon. For such
k-graphs, we say that P_D (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 and k-graphs.

 For P_D, we show that for any k-partite k-graph D, P_D is easily
testable,  by giving an efficient one-sided error-property tester, which
improves  previous results. 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 P_D is not easily
testable. Though our results  do not supply a complete characterization
of the k-graphs for which P_D is  easily testable, they are a natural
extension of the previous results about  graphs.

 Our proofs combine results and arguments from additive number theory,
linear  algebra and extremal hypergraph theory. We also develop new
techniques which  we believe are of independent interest. The first is a
construction of a  large set of integers, which does not contain a small
set of integers that  satisfy 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, Erdos and Sos in
1973.

Joint work with Noga Alon.