Online workshop “Developments in Combinatorics”

There has been a recent tread in finding spanning subgraphs in (host) graphs with sublinear independence number. In this talk we study the H-factors problem in such a setting. That is, given a graph H, what is the best possible minimum degree condition forcing an H-factor in a graph G with independence number o(|G|)? Joint work with Ming Chen, Guanghui Wang and Donglei Yang.

A graph $H$ is \emph{common} if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is asymptotically minimised by the random colouring, or equivalently, $t_H(W)+t_H(1-W)\ge 2^{1-e(H)}$ holds for every graphon $W:[0,1{]}^2\to [0,1]$, where $t_H(.)$ denotes the homomorphism density of the graph $H$. Paths and cycles being common is one of the earliest cornerstones in extremal graph theory, due to Mulholland and Smith (1959), Goodman (1959), and Sidorenko (1989).

We prove a graph homomorphism inequality that extends the commonality of paths and cycles.
Namely, $t_H(W)+t_H(1-W)\ge t_{K_2}(W{)}^{e(H)}+t_{K_2}(1-W{)}^{e(H)}$ whenever $H$ is a path or a cycle and $W:[0,1{]}^2\to \mathbb{R}$ is a bounded symmetric measurable function.

This answers a question of Sidorenko from 1989, who proved a slightly weaker result for even-length paths to prove the commonality of odd cycles.
Furthermore, it also settles a recent conjecture of Behague, Morrison, and Noel in a strong form, who asked if the inequality holds for graphons $W$ and odd cycles $H$. Our proof uses Schur convexity of complete homogeneous symmetric functions, which may be of independent interest.

Joint work with Jang Soo Kim.

The removal lemma is a cornerstone of extremal graph theory. It has many generalizations and extensions to other combinatorial structures, such as induced subgraphs, hypergraphs, digraphs and matrices. A general open question is to characterize the cases in which the removal lemma has polynomial bounds. I will survey the state of knowledge on this general problem and present some new results.

Based on joint works with A. Shapira and I. Tomon.

For an oriented graph D and a set X of vertices of D, the inversion of X in D is the digraph obtained from D by reversing the orientations of all edges with both endpoints in X. The inversion number of D is the minimum number of inversions required to turn D into an acyclic digraph.

We answer several questions of Bang-Jensen, da Silva, and Havet: (1) We show that for each fixed k, it is possible to decide in quadratic time whether a tournament T has inversion number at most k. This exponent is optimal for all k. (2) Building on their work, we prove their conjecture that for every k the problem is NP-complete for digraphs. (3) We construct digraphs with inversion number equal to twice their cycle transversal number; and (4) we disprove their conjecture concerning the inversion number of so-called `dijoin’ digraphs.

Joint work with Emil Powierski, Michael Savery and Elizabeth Wilmer.

We prove that for $n\in \mathbb{N}$ and an absolute constant $C$, if $p\ge C{\log }^{2}n/n$ and $L_{i,j}\subseteq [n]$ is a random subset of $[n]$ where each $k\in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in [n]$, then asymptotically almost surely there is an order-$n$ Latin square in which the entry in the $i$th row and $j$th column lies in $L_{i,j}$. The problem of determining the threshold probability for the existence of an order-$n$ Latin square was raised independently by Johansson, by Luria and Simkin, and by Casselgren and H{\”a}ggkvist; our result provides an upper bound which is tight up to a factor of $\log n$ and strengthens the bound recently obtained by Sah, Sawhney, and Simkin. We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a $1$-factorization of a nearly complete regular bipartite graph.

This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

Abstract: Consider an $r$-uniform hypergraph: 

1. it is called $t$-cover-free if for any $t+1$ distinct edges $A_1,\dots ,A_t,B$, it holds that $B⊈{\cup }_{i=1}^t{A}_i$;

2. it is called $t$-union-free if for any two distinct subsets $\mathcal{A},\mathcal{B}$, each consisting of at most $t$ edges, it holds that ${\cup }_{A\in \mathcal{A}}A\ne {\cup }_{B\in \mathcal{B}}B$;

3. it is called $t$-cancellative if for any $t+2$ distinct edges $A_1,\dots ,A_t,B,C$, it holds that $({\cup }_{i=1}^t{A}_i)\cup B\ne ({\cup }_{i=1}^t{A}_i)\cup C$.

Let $F_t(n,r),C_t(n,r),U_t(n,r)$ denote the maximum number of edges of these hypergraphs, respectively. In this talk, we will introduce the best known lower and upper bounds on these functions. Several interesting problems are left open.

(joint work with Bojan Mohar)

Many important results on chromatic number of graphs drawn on surfaces have been obtained by studying k-critical graphs, i.e., minimal obstructions for (k-1)-colorability. The theory of critical graphs for the dual notion of nowhere-zero flows is much less developed. For an abelian group A, a graph G is said to be A-flow-critical if G does not admit a nowhere-zero A-flow, but for each edge e, the contraction G/e has a nowhere-zero A-flow. We give a bound on the density of Z_3-flow-critical graphs drawn on a fixed surface, generalizing the bound on the density of 4-critical graphs by Kostochka and Yancey.

We consider a problem of determining the asymptotic behavior of the maximal number of directed cycles of a given length in oriented graphs. Settling a conjecture of Bartley and Day, we prove that for cycle lengths not divisible by 4 the maximum value is the same as in the random tournament, additionally providing a characterization of extremal examples. For the remaining cycle lengths we provide asymptotically tight bounds.

We also consider the same problem in the setting where an oriented cycle of a given length is forbidden. We prove the correct order of magnitude for all cycle lengths, as well as exact answers in some special cases, showing the variety of possible extremal structures.

Based on joint works with Daniel Král’, László M. Lovász, Jan Volec, and Justyna Jaworska, Bartłomiej Kielak, Tomasz Ślusarczyk.

The famous conjecture of Erdos, Graham, Montgomery, Rothschild, Spencer and Straus is that a set is Ramsey if and only if it embeds in a sphere. Here as usual “Ramsey” means that for every k there is an n such that whenever we k-colour real n-dimensional space there is a copy of the set that is monochromatic. We propose a “rival” conjecture, that a set is Ramsey if and only if it embeds into a (finite) transitive set. We will discuss the motivation for this conjecture, as well as how it relates to the original conjecture.

(Joint work with Paul Russell and Mark Walters).

Let $\mathcal{F}$ be a fixed family of graphs. The homomorphism threshold of $\mathcal{F}$ is the infimum of those $\alpha$ for which there exists an $\mathcal{F}$-free graph $H=H(\mathcal{F},\alpha )$, such that every $\mathcal{F}$-free graph on $n$ vertices of minimum degree $\alpha n$ is homomorphic to $H$.

Letzter and Snyder showed that the homomorphism threshold of $\{C_3,C_5\}$ is $1/5$. They also found explicit graphs $H(\mathcal{F},\alpha )$, for $\alpha \ge 1/5+\epsilon$, which were in addition $3$-colourable. Thus, their result also implies that $\{C_3,C_5\}$-free graphs of minimum degree at least $(1/5+\epsilon )n$ are $3$-colourable. For longer cycles, Ebsen and Schacht showed that the homomorphism threshold of $\{C_3,C_5,\dots ,C_{2\ell -1}\}$ is $1/(2\ell -1)$.  However, their proof does not imply a good bound on the chromatic number of $\{C_3,C_5,\dots ,C_{2\ell -1}\}$-free graphs of minimum degree $(1/(2\ell -1)+\epsilon )n$. Answering a question of Letzter and Snyder, we prove that such graphs are 3-colourable.