Theory of Computing
-------------------
Title     : Linear Equations, Arithmetic Progressions and Hypergraph Property Testing
Authors   : Noga Alon and Asaf Shapira
Volume    : 1
Number    : 9
Pages     : 177-216
URL       : http://www.theoryofcomputing.org/articles/v001a009

Abstract
--------
For a fixed k-uniform hypergraph D (k-graph for short, k >= 3), 
we say that a k-graph H satisfies property P_D (or property P^*_D)
if it contains no copy (or no 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 property P_D (or property 
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. 
We further show that for large k, one can use more sophisticated 
techniques in order to obtain better lower bounds for any large 
enough k-graph. These results extend and improve the authors' 
previous results about graphs (SODA 2004) and results by 
Kohayakawa, Nagle and Ro"dl on k-graphs (ICALP 2002).

For P_D, we show that for any k-partite k-graph D, property P_D is 
easily testable. This is established by giving an efficient 
one-sided-error property-tester for P_D, which improves the one 
obtained by Kohayakawa et al.  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 
(Alon, 2002).

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 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. These techniques have already been applied in
two papers under publication by the authors.