Uniform hypergraphs containing no grids

作者：Fueredi Zoltan; Ruszinko Miklos^*

来源：Advances in Mathematics, 2013, 240: 302-324.

DOI：10.1016/j.aim.2013.03.009

• Turan hypergraph problem
• Density problems
• Union free hypergraphs
• Superimposed codes

A hypergraph is called an r x 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) boolean AND A(j) = B-i boolean AND B-j = empty set for 1 <= i , j <= r and \A(i) boolean AND 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 boolean AND C-2\ = \C-2 boolean AND C-3\ = \C-3 boolean AND C-1\ = 1, C-1 boolean AND C-2 not equal C-1 boolean AND C-3. A hypergraph is linear, if \E boolean AND F\ <= 1 holds for every pair of edges E not equal 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.

• 出版日期2013-6-20