Uniform hypergraphs containing no grids

Abstract 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 1 , … , A r , B 1 , … , B r } such that A i ∩ A j = B i ∩ B j = 0 for 1 ≤ i j ≤ r and | A i ∩ B j | = 1 for 1 ≤ i , j ≤ r . Three sets C 1 , C 2 , C 3 form a triangle if they pairwise intersect in three distinct singletons, | C 1 ∩ C 2 | = | C 2 ∩ C 3 | = | C 3 ∩ C 1 | = 1 , C 1 ∩ C 2 ≠ C 1 ∩ C 3 . A hypergraph is linear , if | E ∩ F | ≤ 1 holds for every pair of edges E ≠ F . 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. For r ≥ 4 our constructions are almost optimal. These investigations are motivated by coding theory: we get new bounds for optimal superimposed codes and designs.