CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Extremal Graph Theory
Org: Penny Haxell (University of Waterloo)

M. DEVOS, Simon Fraser University
Edge Expansion  [PDF]

Given a simple connected regular graph $G$, we are interested in finding good lower bounds on the number of edges in the graph $G^k$. I will discuss tight bounds for the average degree of $G^3$ and $G^4$, and an essentially tight bound for $G^k$ when $k$ is congruent to 2 modulo 3. This represents joint work with Stephan Thomasse and with Jessica McDonald and Diego Scheide.

A. KOSTOCHKA, University of Illinois at Urbana-Champaign
Packing hypergraphs with few edges  [PDF]

Two $n$-vertex hypergraphs $G$~and $H$ pack~if there is~a bijection $f\,:\,V(G)\to~V(H)$ such that for every edge $A\in~E(G)$, $f(A)$ is not an edge. Our result: If $n\geq10$ and two $n$-vertex hypergraphs $G$ and $H$ with no $1$-,$(n-1)$-, and $n$-edges satisfy $|E(G)|\leq|E(H)|$ and $|E(G)|+|E(H)|\leq2n-3$, then $G$~and~$H$ fail to~pack if and only if every vertex of $G$ is incident to a $2$-edge, and $H$ has~a~vertex incident to~$n-1\quad$ $2$-edges. The~result generalizes Bollob\'{a}s--Eldridge Theorem. This~is joint work~with C.~Stocker and P.~Hamburger.

D. MUBAYI, University of Illinois at Chicago
Lower bounds for the independence number of hypergraphs  [PDF]

We use probabilistic methods to improve the known lower bounds for the independence number of locally sparse graphs and hypergraphs. As a consequence, we answer some old questions of Caro and Tuza. This is joint work with K. Dutta and C.R. Subramanian.

O. PIKHURKO, Carnegie Mellon University
Turan function of even cycles  [PDF]

The Turan function $ex(n,F)$ is the maximum number of edges in an $F$-free graph on $n$ vertices. Let $C_{k}$ denote the cycle of length $k$. We prove that if $k$ is fixed and $n$ tends to infinity, then $ex(n,C_{2k})\le (k-1-o(1))\, n^{1+1/k}$, improving the previously best known general upper bound of Verstraete (2000) by a factor $8+o(1)$ when $n\gg k$.

J. VERSTRAETE, University of California San Diego
Recent progress on bipartite Turan numbers  [PDF]

For a family ${\cal F}$ of graphs, the Tur\'an number ex$(n,{\cal F})$ is the maximum number of edges in an $n$-vertex graph that has no graph in ${\cal F}$ as a subgraph. Determining ex$(n,{\cal F})$ when ${\cal F}$ contains a bipartite graph is a notoriously difficult problem. We discuss recent progress on several conjectures of Erd\H os and Simonovits from 1982 about bipartite Tur\'an numbers. (Partly joint with Peter Keevash and Benny Sudakov.)

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria