Analytic and Probabilistic Techniques in Combinatorics  Part I
Org:
Jan Volec (Emory University and Universitat Hamburg)
[
PDF]
 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 PoShen 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 2edgecolouring 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 computerassisted flag algebra method or the recent progress on Sidorenko's conjecture. We give a new class of nonbipartite 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 edgedecomposition 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
5Cycles in Graphs [PDF]

5cycles 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.