Independent Sets in Hypergraphs

Graphs, Hypergraphs, and Computing

10 April 15:30 - 16:30

Dhruv Mubayi - University of Illinois at Chicago

The problem of determining the independence number of (hyper)graphs has tight connections to questions in discrete geometry, coding theory, number theory, theoretical computer science and combinatorics. One of the most famous early examples is the result of Komlos-Pintz-Szemeredi from 1982 on the independence number of 3-uniform hypergraphs which made important progress on the decades old Heilbronn problem. I will begin by explaining this result and some of these connections. I will then describe recent work in this area which shows that hypergraphs have a significantly different behavior than graphs when it comes to independent sets. This answers a question posed by Ajtai-Erdos-Komlos-Szemeredi (1981), and disproves conjectures of deCaen (1986), Frieze and the speaker (2007), and several others.
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