Seminar

Uniform Hypergraphs Containing no Grids

Miklos Ruszinko - Alfred Renyi Institute of Mathematics

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 sets $\{A_1, \dots ,A_r, B_1,\dots ,B_r\}$ such that $A_i\cap A_j=B_i\cap B_j=\emptyset$ for $1\le i 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-Erdos' conjecture (Ruzsa-Szemeredi's (6,3) theorem is a special case) on sparse hypergraphs, and we slightly improve the Erdos-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.
Organizers
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski