Miklos Ruszinko: Uniform hypergraphs containing no grids

A hypergraph is called an r × r grid if it is isomorphic to a pattern of r horizontal and r vertical lines, i.e., a family of sets {A₁, ..., A_r, B₁, ..., B_r} such that A_i ∩ A_j = B_i ∩ B_j = ∅ for 1 ≤ i < j ≤ r and |A_i ∩ B_j| = 1 for 1 ≤ i, j ≤ r. Three sets C₁, C₂, C₃ form a triangle if they pairwise intersect in three distinct singletons, |C₁ ∩ C₂| = |C₂ ∩ C₃| = |C₃ ∩ C₁| = 1, C₁ ∩ C₂ ≠ C₁ ∩ C₃. A hypergraph is linear, if |E ∩ F| ≤ 1 holds for every pair of edges.

In this paper we construct large linear r-hypergraphs which contain no grids. Moreover, a similar construction gives large linear r-hypergraphs which contain neither grids nor triangles. Our results are connected to the Brown-Erdős' conjecture (Ruzsa-Szemeredi's (6,3) theorem is a special case) on sparse hypergraphs, and we slightly improve the Erdős-Frankl-Rodl bound. One of the tools in our proof is Behrend's construction on large sets of integers containing no three-term arithmetic progression. These investigations are also motivated by coding theory: we get new bounds for optimal superimposed codes and designs.

This is a joint work with Zoltan Furedi.