Past Combinatorial Theory Seminar

Ramsey classes may be viewed as the top of the line of Ramsey properties. Classical and not so classical examples of Ramsey classes of finite structures were recently extended by many new examples which make the characterisation of Ramsey classes  realistic (and in many cases known). Particularly I will cover recent  joint work with J. Hubicka.
 

The size Ramsey number r'(H) of a graph H is the smallest number of edges in a graph G which is Ramsey with respect to H, that is, such that any 2-colouring of the edges of G contains a monochromatic copy of H. A famous result of Beck states that the size Ramsey number of the path with n vertices is at most bn for some fixed constant b > 0. An extension of this result to graphs of maximum degree ∆ was recently given by Kohayakawa, Rödl, Schacht and Szemerédi, who showed that there is a constant b > 0 depending only on ∆ such that if H is a graph with n vertices and maximum degree ∆ then r'(H) < bn^{2 - 1/∆} (log n)^{1/∆}. On the other hand, the only known lower-bound on the size Ramsey numbers of bounded-degree graphs is of order n (log n)^c for some constant c > 0, due to Rödl and Szemerédi.

Together with David Conlon, we make a small step towards improving the upper bound. In particular, we show that if H is a ∆-bounded-degree triangle-free graph then r'(H) < s(∆) n^{2 - 1/(∆ - 1/2)} polylog n. In this talk we discuss why 1/∆ is the natural "barrier" in the exponent and how we go around it, why we need the triangle-free condition and what are the limits of our approach.

There is an obvious product-free subset of the symmetric group of density 1/2, but what about the alternating group? An argument of Gowers shows that a product-free subset of the alternating group can have density at most n^(-1/3), but we only know examples of density n^(-1/2 + o(1)). We'll talk about why in fact n^(-1/2 + o(1)) is the right answer, why
Gowers's argument can't prove that, and how this all fits in with a more general 'product mixing' phenomenon. Our tools include some nonabelian Fourier analysis, a version of entropy subadditivity adapted to the symmetric group, and a concentration-of-measure result for rearrangements of inner products.

The chromatic number of the Erdős–Rényi random graph G(n,p) has been an intensely studied subject since at least the 1970s. A celebrated breakthrough by Bollobás in 1987 first established the asymptotic value of the chromatic number of G(n,1/2), and a considerable amount of effort has since been spent on refining Bollobás' approach, resulting in increasingly accurate bounds. Despite this, up until now there has been a gap of size O(1) in the denominator between the best known upper and lower bounds for the chromatic number of dense random graphs G(n,p) where p is constant. In contrast, much more is known in the sparse case.

In this talk, new upper and lower bounds for the chromatic number of G(n,p) where p is constant will be presented which match each other up to a term of size o(1) in the denominator. In particular, they narrow down the optimal colouring rate, defined as the average colour class size in a colouring with the minimum number of colours, to an interval of length o(1). These bounds were obtained through a careful application of the second moment method rather than a variant of Bollobás' method. Somewhat surprisingly, the behaviour of the chromatic number changes around p=1-1/e^2, with a different limiting effect being dominant below and above this value.

Fix some positive integer r. A famous theorem of Schur states that if you partition Z/pZ into r colour classes then, provided p > p_0(r) is sufficiently large, there is a monochromatic triple {x, y, x + y}. By essentially the same argument there is also a monochromatic triple {x', y', x'y'}. Recently, Tom Sanders and I showed that in fact there is a
monochromatic quadruple {x, y, x+y, xy}. I will discuss some aspects of the proof.

A "hole" in a graph is an induced subgraph which is a cycle of length > 3. The perfect graph theorem says that if a graph has no odd holes and no odd antiholes (the complement of a hole), then its chromatic number equals its clique number; but unrestricted graphs can have clique number two and arbitrarily large chromatic number. There is a nice question half-way between them - for which classes of graphs is it true that a bound on clique number implies some (larger) bound on chromatic number? Call this being "chi-bounded".

Gyarfas proposed several conjectures of this form in 1985, and recently there has been significant progress on them. For instance, he conjectured

• graphs with no odd hole are chi-bounded (this is true);
• graphs with no hole of length >100 are chi-bounded (this is true);
• graphs with no odd hole of length >100 are chi-bounded; this is still open but true for triangle-free graphs.

We survey this and several related results. This is joint with Alex Scott and partly with Maria Chudnovsky.

It is easy to see that if a tournament (a complete oriented graph) has a directed cycle then it has a directed 3-cycle. We investigate the analogous question for 3-tournaments, and more generally for oriented 3-graphs.

Cycles are fundamental objects in graph theory. A spanning cycle in a graph is also called a Hamiltonian cycle. The celebrated Dirac's Theorem in 1952 shows that every graph on $n\ge 3$ vertices with minimum degree at least $n/2$ contains a Hamiltonian cycle. In recent years, there has been a strong focus on extending Dirac’s Theorem to hypergraphs. We survey the results along the line and mention some recent progress on this problem. Joint work with Yi Zhao.

What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor? In this talk, I will discuss some recent progress on this problem.

Already the order in the exponent of the tail probability was a long standing open problem until several years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (sparse setting), this large deviations problem reduces to a natural variational problem. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for p > 1/n^c for some c > 0.

Based on joint work with Bhaswar Bhattacharya, Shirshendu Ganguly, and Eyal Lubetzky.

We discuss a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of $G(n,p)$ in order to typically find a subgraph possessing a certain structure. More specifically, given a monotone property of graphs $P$, we consider $G(n,p)$ where $p$ is above the threshold probability for $P$ and look for adaptive algorithms which query significantly less than all pairs of vertices in order to reveal that the property $P$ holds with high probability. In this talk we focus particularly on the properties of containing a Hamilton cycle and containing paths of linear size. The talk is based on joint work with Asaf Ferber, Michael Krivelevich and Benny Sudakov.

The Erdős–Ko–Rado theorem is a central result in extremal set theory which tells us how large uniform intersecting families can be. In this talk, I shall discuss some recent results concerning the 'stability' of this result. One possible formulation of the Erdős–Ko–Rado theorem is the following: if $n \ge 2r$, then the size of the largest independent set of the Kneser graph $K(n,r)$ is $\binom{n-1}{r-1}$, where $K(n,r)$ is the graph on the family of $r$-element subsets of $\{1,\dots,n\}$ in which two sets are adjacent if and only if they are disjoint. The following will be the question of interest. Delete the edges of the Kneser graph with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? I shall discuss an affirmative answer to this question in a few different regimes. Joint work with Bollobás and Raigorodskii, and Balogh and Bollobás.

A system of linear equations with integer coefficients is partition regular if, whenever the natural numbers are finitely coloured, there is a monochromatic solution. The finite partition regular systems were completely characterised by Rado in terms of a simple property of their matrix of coefficients. As a result, finite partition regular systems are very well understood.

Much less is known about infinite systems. In fact, only a very few families of infinite partition regular systems are known. I'll explain a relatively new method of constructing infinite partition regular systems, and describe how it has been applied to settle some basic questions in the area.

A graph is quasirandom if its edge distribution is similar (in a well defined quantitative way) to that of a random graph with the same edge density. Classical results of Thomason and Chung-Graham-Wilson show that a variety of graph properties are equivalent to quasirandomness. On the other hand, in some known proofs the error terms which measure quasirandomness can change quite dramatically when going from one property to another which might be problematic in some applications.

Simonovits and Sós proved that the property that all induced subgraphs have about the expected number of copies of a fixed graph $H$ is quasirandom. However, their proof relies on the regularity lemma and gives a very weak estimate. They asked to find a new proof for this result with a better estimate. The purpose of this talk is to accomplish this.

Joint work with D. Conlon and J. Fox

It has become possible in recent years to provide unconditional lower bounds on the time needed to perform a number of basic computational operations. I will briefly discuss some of the main techniques involved and show how one in particular, the information transfer method, can be exploited to give  time lower bounds for computation on streaming data.

I will then go on to present a simple looking mathematical conjecture with a probabilistic combinatorics flavour that derives from this work.  The conjecture is related to the classic "coin weighing with a spring scale" puzzle but has so far resisted our best efforts at resolution.

An edge (vertex) coloured graph is rainbow-connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colours. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colours needed for a rainbow edge (vertex) colouring of G. We propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several new and known results, focusing on random regular graphs. This is joint work with Michael Krivelevich and Benny Sudakov.

Phylogenies, or evolutionary histories, play a central role in modern biology, illustrating the interrelationships between species, and also aiding the prediction of structural, physiological, and biochemical properties. The reconstruction of the underlying evolutionary history from a set of morphological characters or biomolecular sequences is difficult since the optimality criteria favored by biologists are NP-hard, and the space of possible answers is huge. Phylogenies are often modeled by trees with n leaves, and the number of possible phylogenetic trees is $(2n-5)!!$. Due to the hardness and the large number of possible answers, clever searching techniques and heuristics are used to estimate the underlying tree.

We explore the combinatorial structure of the underlying space of trees, under different metrics, in particular the nearest-neighbor-interchange (NNI), subtree- prune-and-regraft (SPR), tree-bisection-and-reconnection (TBR), and Robinson-Foulds (RF) distances.  Further, we examine the interplay between the metric chosen and the difficulty of the search for the optimal tree.

How many $H$-free graphs are there on $n$ vertices? What is the typical structure of such a graph $G$? And how do these answers change if we restrict the number of edges of $G$? In this talk I will describe some recent progress on these basic and classical questions, focusing on the cases $H=K_{r+1}$ and $H=C_{2k}$. The key tools are the hypergraph container method, the Janson inequalities, and some new "balanced" supersaturation results. The techniques are quite general, and can be used to study similar questions about objects such sum-free sets, antichains and metric spaces.

I will mention joint work with a number of different coauthors, including Jozsi Balogh, Wojciech Samotij, David Saxton, Lutz Warnke and Mauricio Collares Neto. 

Let $G(n,d)$ be a random $d$-regular graph on $n$ vertices. In 2004 Kim and Vu showed that if $d$ grows faster than $\log n$ as $n$ tends to infinity, then one can define a joint distribution of $G(n,d)$ and two binomial random graphs $G(n,p_1)$ and $G(n,p_2)$ -- both of which have asymptotic expected degree $d$ -- such that with high probability $G(n,d)$ is a supergraph of $G(n,p_1)$ and a subgraph of $G(n,p_2)$. The motivation for such a coupling is to deduce monotone properties (like Hamiltonicity) of $G(n,d)$ from the simpler model $G(n,p)$. We present our work with A. Dudek, A. Frieze and A. Rucinski on the Kim-Vu conjecture and its hypergraph counterpart.

Graphons and permutons are analytic objects associated with convergent sequences of graphs and permutations, respectively. Problems from extremal combinatorics and theoretical computer science led to a study of graphons and permutons determined by finitely many substructure densities, which are referred to as finitely forcible. The talk will contain several results on finite forcibility, focusing on the relation between finite forcibility of graphons and permutons. We also disprove a conjecture of Lovasz and Szegedy about the dimension of the space of typical vertices of finitely forcible graphons. The talk is based on joint work with Roman Glebov, Andrzej Grzesik and Dan Kral.

A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$ (and $F$-divisibility is a trivial necessary condition for this). We extend Wilson's theorem to graphs which are allowed to be far from complete (joint work with B. Barber, D. Kuhn, A. Lo).

I will also discuss some results and open problems on decompositions of dense graphs and hypergraphs into Hamilton cycles and perfect matchings.

Dellamonica, Kohayakawa, Rödl and Ruciński showed that for $p=C(\log n/n)^{1/d}$ the random graph $G(n,p)$ contains asymptotically almost surely all spanning graphs $H$ with maximum degree $d$ as subgraphs. In this talk I will discuss a resilience version of this result, which shows that for the same edge density, even if a $(1/k-\epsilon)$-fraction of the edges at every vertex is deleted adversarially from $G(n,p)$, the resulting graph continues to contain asymptotically almost surely all spanning $H$ with maximum degree $d$, with sublinear bandwidth and with at least $C \max\{p^{-2},p^{-1}\log n\}$ vertices not in triangles. Neither the restriction on the bandwidth, nor the condition that not all vertices are allowed to be in triangles can be removed. The proof uses a sparse version of the Blow-Up Lemma. Joint work with Peter Allen, Julia Ehrenmüller, Anusch Taraz.

Suppose that we have a tile $T$ in say $\mathbb{Z}^2$, meaning a finite subset of $\mathbb{Z}^2$. It may or may not be the case that $T$ tiles $\mathbb{Z}^2$, in the sense that $\mathbb{Z}^2$ can be partitioned into copies of $T$. But is there always some higher dimension $\mathbb{Z}^d$ that can be tiled with copies of $T$? We prove that this is the case: for any tile in $\mathbb{Z}^2$ (or in $\mathbb{Z}^n$, any $n$) there is a $d$ such that $\mathbb{Z}^d$ can be tiled with copies of it. This proves a conjecture of Chalcraft.

Suppose we have a finite graph. We can view this as a resistor network where each edge has unit resistance. We can then calculate the resistance between any two vertices and ask questions like `which graph with $n$ vertices and $m$ edges minimises the average resistance between pairs of vertices?' There is a `obvious' solution; we show that this answer is not correct.

This problem was motivated by some questions about the design of statistical experiments (and has some surprising applications in chemistry) but this talk will not assume any statistical knowledge.

This is joint work with Robert Johnson.