January 30 - February 17 | L. Thoma | Tutorial: Regularity, Szemeredi's lemma, and applications. (7 lectures) | |
April 4 | A. Gilbert | Representing Asteroidal Sets on Subdivisions of Stars | |
April 25 | P. Horn | Isomorphic subgraphs in graphs and hypergraphs | |
Abstract: We show that any $k$-uniform hypergraph with $n$ edges contains two edge disjoint subgraphs of size $\tilde{\Omega}(n^{2/(k+1)})$ for $k=4,5$ and $6$. This is best possible up to a logarithmic factor due to a upper bound construction of Erd\H{o}s, Pach, and Pyber who show there exist $k$-uniform hypergraphs with $n$ edges and with no two edge disjoint isomorphic subgraphs with size larger than $\tilde{O}(n^{2/(k+1)})$. Furthermore, our result extends results Erd\H{o}s, Pach and Pyber who also established the lower bound for $k=2$ (ie. for graphs), and of Gould and R\"odl who established the result for $k=3$. In this talk, we'll discuss some of the main ideas of the proof, which is probabilistic, and the obstructions which prevent us from establishing the result for higher values of $k$. We'll also briefly talk about the a connected version of this problem on both graphs and uniform hypergraphs. |
November 30 | A. Armstrong | Ramsey numbers of Cycles (M.S. presentation) Reporting on: The Ramsey number for a triple of long even cycles by A. Figaj, T. Luczak, JCTB 2007(97). |
Past semesters: Spring 2011 Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008 Fall 2007 Spring 2007 Journals in Discrete Mathematics and related fields |