CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Extremal Combinatorics
Organizer and Chair: Dhruv Mubayi (University of Illinois at Chicago)

PENNY HAXELL, University of Waterloo
Extremal hypergraphs for packing and covering  [PDF] [SLIDES]

A packing in a hypergraph $H$ is a set of pairwise disjoint edges. A cover is a set $C$ of vertices that meets all edges. A famous open problem known as Ryser's Conjecture states that every $r$-partite $r$-uniform hypergraph has a cover of size at most $(r-1)\nu(H)$, where $\nu(H)$ denotes the size of a largest packing in $H$. This was proved by Aharoni in 2001 for the case $r=3$. Here we show that if equality holds in this case then $H$ belongs to a special class of hypergraphs we call ``home base hypergraphs''.

(joint with L. Narins and T. Szab\'o)

JOHN LENZ, University of Illinois at Chicago
Hypergraph Quasirandomness  [PDF] [SLIDES]

Pseudorandom or quasirandom graphs or hypergraphs are explicitly constructed graphs which behave similar to the Erd\H{o}s-R\'{e}nyi random graph, and have applications throughout combinatorics and computer science. In this talk, I will give an overview of recent work on quasirandom hypergraphs. In particular, $k$-uniform hypergraphs for $k \geq 3$ enjoy a variety of distinct but related notions of hypergraph quasirandomness and I will discuss these quasirandom properties and their implications, which include edge discrepency, counting subhypergraphs, and eigenvalue conditions.

SERGEY NORIN, McGill University
Forcing multidimensional graphons  [PDF]

Recently, Lovasz and Szegedy have initiated investigation of limits of convergent sequences of dense graphs which are determined by finitely many subgraph densities, called {\em finitely forcible graphons}. They have also introduced a notion of a topological space of typical points of a graphon.

We will present examples of finitely forcible graphons for which the corresponding space has arbitrary finite dimension. For all previously known examples this dimension was equal to 0 or 1. We will also show that the infinite lexicographic power of any prime graph is finitely forcible, partially answering a question of Lovasz and Szegedy.

MATHIAS SCHACHT, Universität Hamburg
Sharp threshold vor van der Waerden's theorem  [PDF]

It was shown by Rödl and Ruciński that for $m=C_rn^{\frac{k-2}{k-1}}$ almost every $m$-element subset $M$ of the first $n$ integers has the property that every $r$-colouring of $M$ yields a monochromatic arithmetic progression of length $k$, while sets of size $o(n^{\frac{k-2}{k-1}})$ fail to have this property. We discuss sharp thresholds for this an related properties. This is joint work with E. Friedgut, H. Hàn, and Y. Person.

JACQUES VERSTRAETE, University of California, San Diego
Random Independent Sets in Hypergraphs  [PDF]

In this talk I will survey some recent results on finding large independent sets in hypergraphs, mainly via probabilistic techniques. Applications to Ramsey Theory, Combinatorial Geometry and Finite Geometry will be discussed, along with some new constructions of dense hypergraphs without large independent sets. This work is in part joint with Alexandr Kostochka, Dhruv Mubayi, and in part with Jeroen Schillewaert.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland