Combinatorial Theory Seminar

We say that a sequence $\{\Pi_i\}$ of permutations is quasirandom if, for each $k\geq 2$ and each $\sigma\in S_k$, the probability that a uniformly chosen $k$-set of entries of $\Pi_i$ induces $\sigma$ tends to $1/k!$ as $i$ tends to infinity. It is known that a much weaker condition already forces $\{\Pi_i\}$ to be quasirandom; namely, if the above property holds for all $\sigma\in S_4$. We further weaken this condition by exhibiting sets $S\subseteq S_4$, such that if a randomly chosen $k$-set of entries of $\Pi_i$ induces an element of $S$ with probability tending to $|S|/24$, then $\{\Pi_i\}$ is quasirandom. Moreover, we are able to completely characterise the sets $S$ with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. 
This is joint work with Timothy Chan, Daniel Kráľ, Jon Noel, Maryam Sharifzadeh and Jan Volec.

The r-​colour size-​Ramsey number of a graph G is the minimum number of edges of a graph H such that any r-​colouring of the edges of H has a monochromatic G-​copy. Random graphs play an important role in the study of size-​Ramsey numbers. Using random graphs, we establish a new bound on the size-​Ramsey number of D-​degenerate graphs with bounded maximum degree.

In the talk I will summarise what is known about size-​Ramsey numbers, explain the connection to random graphs and their so-​called partition universality, and outline which methods we use in our proof.

Based on joint work with Peter Allen.  
 

Given a collection of subsets of a set X, the basic problem in combinatorial discrepancy theory is to find an assignment of 1,-1 to the elements of X so that the sums over each of the given sets is as small as possible. I will discuss how the sort of combinatorial reasoning used to think about problems in combinatorial discrepancy can be used to solve an old conjecture of J.E. Littlewood on the existence of ``flat Littlewood polynomials''.

This talk is based on joint work with Paul Balister, Bela Bollobas, Rob Morris and Marius Tiba.
 

How many monochromatic paths, cycles or general trees does one need to cover all vertices of a given r-edge-colored graph G? Such questions go back to the 1960's and have been studied intensively in the past 50 years. In this talk, I will discuss what we know when G is the random graph G(n,p). The problem turns out to be related to the following question of Erdős, Hajnal and Tuza: What is the largest possible cover number of an r-uniform hypergraph where any k edges have a cover of size l.

The results I mention give new bounds for these problems, and answer some questions by Bal and DeBiasio, and others. The talk is based on collaborations with Bucić, Mousset, Nenadov, Škorić and Sudakov.

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence? 

Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for 
the number of graphs with a given degree sequence, for a range of degree sequences that is wide enough to deduce asymptotic formulae for the second 
question for p =o(1/o(\sqrt(n))) and p = Theta(1).  

McKay and Wormald showed that the formulae for the sparse case and the 
dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent 
binomial variables Bin(n − 1, p'). 

In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings. 

A classic result of Shamir and Spencer states that for any function $p=p(n)$, the chromatic number of $G(n,p)$ is whp concentrated on a sequence of intervals of length about $\sqrt{n}$. For $p<n^{-\frac{1}{2} -\epsilon}$, much more is known: here, the chromatic number is concentrated on two consecutive values.

Until now, there have been no non-trivial cases where $\chi(G(n,p))$ is known not to be extremely narrowly concentrated. In 2004, Bollob\'as asked for any such examples, particularly in the case $p=\frac{1}{2}$, in a paper in the problem section of CPC. 

In this talk, we show that the chromatic number of $G(n, 1/2)$ is not whp concentrated on $n^{\frac{1}{4}-\epsilon}$ values

In this talk, we will discuss various results around Brooks' theorem: a graph has chromatic number at most its maximum degree, unless it is a clique or an odd cycle. We will consider stronger variants and local versions, as well as the structure of the solution space of all corresponding colorings.

Given positive integers n,r,k, the Erdős-Rothschild problem asks to determine the largest number of r-edge-colourings without monochromatic k-cliques a graph on n vertices can have. In the case of triangles, i.e. when k=3, the solution is known for r = 2,3,4. We investigate the problem for five and six colours.

The Hales–Jewett Theorem states that any r–colouring of [m]^n contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.