Uniform Hypergraphs Containing no Grids

Graphs, Hypergraphs, and Computing

08 May 14:00 - 15:00

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to