University of Minnesota Combinatorics Seminar
Friday, November 4, 2011
3:35pm in 570 Vincent Hall



Superimposed codes and hypergraphs containing no grids

Zoltán Füredi

UIUC and Renyi Institute


Abstract

We discuss connections between classical coding theory problems and Turan type problems of hypergraphs. We construct large linear r-hypergraphs which contain no grids (for r at least 4). The case r=3 remains open.

Although our construction is basically algebraic these investigations have a number of connections to the theory of sparse hypergraphs (Ruzsa-Szemeredi theorem, Brown-Erdos-Sos conjectures), the theory of sparse Steiner systems, union-free and superimposed codes and designs. We are using tools from discrete geometry and combinatorial number theory, like generalized Sidon sets.

(A hypergraph is called an r times r grid if it is isomorphic to a pattern of r horizontal and r vertical lines, i.e., a family of r-element sets {A_1, ... ,A_r, B_1, ... ,B_r} such that the A_i's are pairwise disjoint, the B_j's are pairwise dispoint, however each A_i meets each B_j in a singleton. A hypergraph is linear, if the pairwise intersections of its edges have at most one element.)

This is a joint work with Miklos Ruszinko (SzTAKI, Budapest).