Past Combinatorial Theory Seminar

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.

Erdős asked the following question: given a positive integer $n$, what is the largest integer $k$ such that any set of $n$ points in a plane, with no $4$ on a line, contains $k$ points no $3$ of which are collinear? Füredi proved that $k = o(n)$. Cardinal, Toth and Wood extended this result to $\mathbb{R}^3$, finding sets of $n$ points with no $5$ on a plane whose subsets with no $4$ points on a plane have size $o(n)$, and asked the question for the higher dimensions. For given $n$, let $k$ be largest integer such that any set of $n$ points in $\mathbb{R}^d$ with no more than $d + 1$ cohyperplanar points, has $k$ points with no $d + 1$ on a hyperplane. Is $k = o(n)$? We prove that $k = o(n)$ for any fixed $d \geq 3$.

The Number Field Sieve is the current practical and theoretical state of the art algorithm for factoring. Unfortunately, there has been no rigorous analysis of this type of algorithm. We randomise key aspects of the number theory, and prove that in this variant congruences of squares are formed in expected time $L(1/3, 2.88)$. These results are tightly coupled to recent progress on the distribution of smooth numbers, and we provide additional tools to turn progress on these problems into improved bounds.

Given two probability distributions $P_R$ and $P_B$ on the positive reals with finite means, colour the real line alternately with red and blue intervals so that the lengths of the red intervals have distribution $P_R$, the lengths of the blue intervals have distribution $P_B$, and distinct intervals have independent lengths. Now iteratively update this colouring of the line by coalescing intervals: change the colour of any interval that is surrounded by longer intervals so that these three consecutive intervals subsequently form a single monochromatic interval. Say that a colour (either red or blue) `wins' if every point of the line is eventually of that colour. I will attempt to answer the following question: under what natural conditions on the distributions is one of the colours almost surely guaranteed to win?

Gyárfás conjectured in 1985 that if $G$ is a graph with no induced cycle of odd length at least 5, then the chromatic number of $G$ is bounded by a function of its clique number.  We prove this conjecture.  Joint work with Paul Seymour.

More than twenty years ago Erdős conjectured that a triangle-free graph $G$ of chromatic number $k$ contains cycles of at least $k^{2−o(1)}$ different lengths. In this talk we prove this conjecture in a stronger form, showing that every such $G$ contains cycles of $ck^2\log k$ consecutive lengths, which is tight. Our approach can be also used to give new bounds on the number of different cycle lengths for other monotone classes of $k$-chromatic graphs, i.e.,  clique-free graphs and graphs without odd cycles.

Joint work with A. Kostochka and J. Verstraete.