CanaDAM 2017
Ryerson University, June 12 - 16, 2017

Extremal Combinatorics
Org: Sergey Norine (McGill)

STEFAN GLOCK, Birmingham

Finite reflection groups and graph norms  [PDF]

For any given graph $H$, we may define a natural corresponding functional $\|.\|_H$. We then say that $H$ is norming if $\|.\|_H$ is a semi-norm. A similar notion $\|.\|_{r(H)}$ is defined by $\|f\|_{r(H)}:= \||f|\|_H$ and $H$ is said to be weakly norming if $\|.\|_{r(H)}$ is a norm. Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. Using results from the theory of finite reflection groups, we identify a much larger class of weakly norming graphs. We also discuss several applications of our results on Sidorenko's conjecture and forcing hypergraphs. Joint work with David Conlon.

Minimum number of edges that occur in odd cycles  [PDF]

An~$n$-vertex graph~$G$ with~more than~$n^2/4$ edges contains a~copy of~a~$(2k+1)$-cycle. But can we guarantee more than a~single copy? In~1992, Erdős,~Faudree~and~Rousseau showed the~number of~edges of~$G$ occurring in~triangles is at~least~$2\lfloor\frac{n+2}2\rfloor$, which is tight, and for~any~$k>1$, the~number of~edges in~$G$ in~$(2k+1)$-cycles is at~least~$11n^2/144$. However, they conjectured~$G$ must contain at~least~$2n^2/9$ such edges.

Very recently, Füredi~and~Maleki disproved the~conjecture for~$k=2$ and showed $G$ might have only~$\frac{(2+\sqrt{2}+o(1))n^2}{16}<0.2134n^2$ edges occurring in~$5$-cycles. They also proved the~asymptotically matching lower-bound under the~additional assumption that~$G$ has at~least~$(1/4+\varepsilon)n^2$ edges. We present a~flag algebra approach to~this problem and prove that every $n$-vertex graph with~more than~$n^2/4$ edges contains at~least~$\frac{(2+\sqrt{2}-o(1))n^2}{16}$ edges in~$5$-cycles. This settles a~conjecture of~Füredi~and~Maleki.

Supersaturation result for linear cycles in linear hypergraphs  [PDF]

A classic result of Bondy and Simonovits from 70's says that the maximum number of edges in an $n$-vertex graph not containing $C_{2k}$, the $2k$-cycle, is $O(n^{1+1/k})$. Simonovits obtained the corresponding supersaturation result, that is, there is a constant $c$ such that every $n$-vertex graph with $e>cn^{1+1/k}$ edges contains $\Omega((e/n)^{2k})$ many $C_{2k}$'s. We develop a more general supersaturation result on linear cycles of even lengths in linear $r$-graphs. Our result is self-contained and includes the case $r=2$. We develop general reduction theorems for supersaturation problems and use ideas from earlier work of Faudree and Simonovits. Joint work with Tao Jiang.

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 Ryerson University Office of Naval Research Science and Technology