CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Extremal combinatorics
Org: Joonkyung Lee (University of Oxford, UK)

FELIX LAZEBNIK, University of Delaware
Graphs defined by systems of multivariate polynomial equations  [PDF]

In this talk we survey results, both old and new, on families of graphs defined by certain systems of multivariate polynomial equations. The results are concerned with explicit constructions for Tur\'an-type problems for graphs of even girth, expansion properties of the graphs, presence of cycles of certain lengths in these graphs, and their automorphisms. Several open problems concerning these graphs will be stated.

EOIN LONG, University of Oxford
Cycle-complete Ramsey numbers  [PDF]

In 1978, Erdős, Faudree, Rousseau and Schelp conjectured that the two-colour Ramsey number $r(C_{\ell },K_n)$ satisfies $r(C_{\ell},K_n) = (\ell-1)(n-1)+1$ provided $\ell \geq n\geq 3$ and $(\ell,n) \neq (3,3)$. In this talk I will discuss a recent proof of this conjecture for large $\ell$, and a strong form due to Nikiforov, showing that $r(C_{\ell},K_n) = (\ell-1)(n-1)+1$ provided $\ell \geq \frac {C\log n}{\log \log n}$, for some absolute constant $C>0$. Up to the value of $C$ this is tight, and answers two further questions of Erdős et al. up to multiplicative constants.

Joint work with Peter Keevash and Jozef Skokan.

A bipartite Turán problem for quadruples  [PDF]

Let ${\mathcal P}$ be a set of pairs $(a,b)$ with $a,b\geq 2$. Let $A$ and $B$ be disjoint sets with $|A|=n$ and $|B|=m$. We consider the problem of finding the minimum number of quadruples with $2$ elements from $A$ and $2$ from $B$ such that for every $(a,b)\in{\mathcal P}$, every $(a+b)$-set with $a$ elements from $A$ and $b$ from $B$ contains at least one of the quadruples. We solve asymptotically this problem for ${\mathcal P} = \{(2,k+1),(k+1,2)\}$, as well as for even $k$ and ${\mathcal P} = \{(2,k+1),(3,k),(k,3),(k+1,2)\}$.

MAYA STEIN, Universidad de Chile
Clique immersions and independence number  [PDF]

We determine bounds for the order of the largest clique immersion in a graph with fixed independence number. The motivation for this problem comes from the immersion conjecture (an analogue of Hadwiger's conjecture for immersions), which, if true, would imply that every n-vertex graph with independence number $\alpha$ has a clique immersion of order at least $n/\alpha$. Our bounds improve previous results of Gauthier, Le and Wollan.

This is joint work with S. Bustamante, D. Quiroz and J. Zamora.

Generalized Tur\'{a}n Numbers for Hypergraphs  [PDF]

We denote by $\mbox{ex}(G,F)$ the maximum number of edges in an $F$-free subgraph of an $r$-graph $G$, and these quantities are collectively referred to as generalized Tur\'{a}n numbers. The known results for graphs use probabilistic arguments and the method of containers, and have been studied extensively. For hypergraphs, we give a general theorem, which applies to a number of interesting cases.

Joint work with Sam Spiro