CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Analytic and Probabilistic Techniques in Combinatorics - Part I
Org: Jan Volec (Emory University and Universitat Hamburg)

DEBSOUMYA CHAKRABORTI, Carnegie Mellon University
Extremal Graphs With Local Covering Conditions  [PDF]

Extremal graph theory considers problems of maximizing or minimizing graph parameters in graph classes of interest. We study a natural minimization problem: determine the minimum number of edges in an $n$-vertex graph such that each vertex is in a copy of a fixed graph $H$. Our starting point is an observation that when $H$ is a complete graph, then the extremal graphs take a particularly nice form. We systematically study the question of which $H$ achieve similar form, and resolve the answer for dense regular graphs $H$ and random graphs. Joint work with Po-Shen Loh.

JOONKYUNG LEE, Universitat Hamburg
On triangulated common graphs  [PDF]

A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of $K_N$ is minimised by the random colouring. Collecting new examples for common graphs had not seen much progress since 1990s, although very recently, a few more graphs are verified to be common by the computer-assisted flag algebra method or the recent progress on Sidorenko's conjecture. We give a new class of non-bipartite common graphs without using computers. In particular, we prove that triangle trees and octahedrons are common. Joint work with Jan Volec.

JON NOEL, University of Warwick
Cycles of length three and four in tournaments  [PDF]

Given a tournament with $d\binom{n}{3}$ cycles of length three, how many cycles of length four must there be? Linial and Morgenstern (2016) conjectured that the minimum is asymptotically attained by ``blowing up'' a transitive tournament and orienting the edges randomly within the parts. This is reminiscent of the tight examples for the famous Triangle and Clique Density Theorems. We prove the conjecture for $d\geq 1/36$ using spectral methods. We also show that the family of tight examples is more complex than expected and fully characterise it for $d\geq 1/16$. Joint work with Timothy Chan, Andrzej Grzesik and Daniel Král'.

YANITSA PEHOVA, University of Warwick
Decomposing graphs into edges and triangles  [PDF]

In 1966 Erdős, Goodman and Pósa showed that every graph $G$ of order $n$ has an edge-decomposition into at most $n^2/4$ cliques (and, in fact, edges and triangles are enough). If one seeks to minimise the sum of the sizes of the cliques in a decomposition, the corresponding minimum is $n^2/2$ (a result due to Győri, Kostochka; Chung; Kahn). It was conjectured by Győri and Tuza that edges and triangles suffice here too, up to a constant. We give a proof of this conjecture using the flag algebra method of Razborov, and consider some extensions to arbitrary linear cost functions.

FLORIAN PFENDER, University of Colorado Denver
5-Cycles in Graphs  [PDF]

5-cycles appear as extremal examples in graphs in many forms. I will talk about a few problems where they play a prominent role, and where flag algebras have been successfully used for a resolution.