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

Ramsey Theory and Extremal Combinatorics
Chair: Steve Butler (Iowa State University)

STEVE BUTLER, Iowa State University
Unrolling residues to avoid progressions  [PDF] [SLIDES]

A result of van der Waerden states given any $k$ there is some $N_0$ that for any $n\ge N_0$ and any coloring of the numbers from $1$ to $n$ with two colors, there will be $k$ of the numbers which were assigned the same color and lie in an arithmetic progression. This can be extended further to show that not only must there be one such monochromatic progression but there must be many. We consider the problem of finding a ``good'' coloring which has relatively few of these monochromatic progressions and give the best known colorings for some small cases.

On generalized Ramsey numbers of Erd\H{o}s and Rogers  [PDF]

Extending the concept of Ramsey numbers, Erd{\H o}s and Rogers introduced the following function. For given integers $2\le s<t$ let $$ f_{s,t}(n)=\min \{ \max \{ |W| : W\subseteq V(G) \mbox{ and } G[W] \mbox{ contains no } K_s\} \}, $$ where the minimum is taken over all $K_t$-free graphs~$G$ of order~$n$. In this talk, we present some old and recent developments concerning this function. In particular, we partially confirm an old conjecture of Erd\H{o}s by showing that $\lim_{n\to \infty} \frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=\infty$ for any~$s\ge 4$. This is a joint work with John Retter and Vojta R\"odl.

NANA LI, Georgia State University
Union Closed Conjecture  [PDF]

Piotr W$\acute{o}$jcik introduced normalized union closed family and showed that the Frankl's union closed conjecture is equivalent to: for any normalized union closed family $\mathcal{F}$, there is a generator $G$ of $\mathcal{F}$ with $|G|\geq \frac{|\mathcal{F}|}{2}$. We showed that if the family $\mathcal{F}$ is the minimal counter example to the W$\acute{o}$jcik's statement, then $|\mathcal{F}|$ is odd and it has a generator with size $\frac{|\mathcal{F}|-1}{2}$. Additionally, for any normalized union closed family $\mathcal{F}$, we proved that the number of generators in $\mathcal{F}$ being at least $\frac{ |\mathcal{F}|-1 }{2}$ is sufficient for the existance of a generator $G$ in $\mathcal{F}$ with $|G|\geq \frac{|\mathcal{F}|}{2}$.

STANISŁAW RADZISZOWSKI, Rochester Institute of Technology
New Computational Bounds for Ramsey Numbers $R(3,K_k-e)$  [PDF] [SLIDES]

Using computational techniques, we prove that the Ramsey number $R(3,K_{10}-e)$ is equal to 37 and we derive bounds for the next 5 cases. Let $e(3,K_k-e,n)$ denote the minimum number of edges in any triangle-free graph on $n$ vertices, which in the complement does not contain $K_k-e$. The new results on $R(3,K_k-e)$ were obtained by completing the computation of all values of $e(3,K_k-e,n)$ for $k \leq 10$, establishing new lower bounds on $e(3,K_k-e,n)$ for $11 \le k \le 15$ (for the previously open cases), and by other computations.

This is joint work with Jan Goedgebeur from Ghent University, Belgium.

LIANA YEPREMYAN, McGill University
Sparse halves in dense triangle-free graphs  [PDF]

A well-known conjectures of Erd\H{o}s states that every triangle-free graph \(G\) on \(n\) vertices should contain a set of \(n/2\) vertices that spans at most \(n^2 /50\) edges. Krivelevich has established this conjecture for graphs with minimum degree $\geq 2n/5$. We strengthen his result by proving the conjecture for all triangle-free graphs with minimum degree $\geq 5/14n$. Further, we establish the conjecture for graphs which are "close" to the known tight examples - the "blow-ups" of the $5$-cycle and the Petersen graph. Joint work with Sergey Norin.

Event Sponsors

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