University of Minnesota Combinatorics Seminar
|
---|
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). |