Past Events

 

 

Past Combinatorics Seminars

 

2017/18

Conjectures in spectral graph theory

I will discuss six of my conjectures in spectral graph theory, two of which have been proved (by others) to date. All of the conjectures involve eigenvalues of the adjacency matrix of a graph, and several are bounds for the clique or chromatic number. This is joint work, principally with Pawel Wocjan.

Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of n-leaf Galton-Watson trees

In this paper we study the vertex cut-trees of Galton-Watson trees conditioned to have n leaves. This notion is a slight variation of Dieuleveut’s vertex cut-tree of Galton-Watson trees conditioned to have n vertices. Our main result is a joint Gromov-Hausdorff-Prokhorov convergence in the finite variance case of the Galton-Watson tree and its vertex cut-tree to Bertoin and Miermont’s joint distribution of the Brownian CRT and its cut-tree. The methods also apply to the infinite variance case, but the problem to strengthen Dieuleveut’s and Bertoin and Miermont’s Gromov-Prokhorov convergence to Gromov-Hausdorff-Prokhorov remains open for their models conditioned to have n vertices.

This is joint work with Hui He, Beijing Normal University.

On the List Coloring Version of Reed's Conjecture

Reed conjectured in 1998 that the chromatic number of a graph should be at most the average of the clique number (a trivial lower bound) and maximum degree plus one (a trivial upper bound); in support of this conjecture, Reed proved that the chromatic number is at most some nontrivial convex combination of these two quantities. King and Reed later showed that a fraction of roughly 1/130000 away from the upper bound holds. Motivated by a paper by Bruhn and Joos, last year Bonamy, Perrett, and Postle proved for large enough maximum degree, a fraction of 1/26 away from the upper bound holds, a signfi cant step towards the conjectured value of 1/2. Using new techniques, we show that the list-coloring version holds; for large enough maximum degree, a fraction of 1/13 suffices for list chromatic number. This result implies that 1/13 suffices for ordinary chromatic number as well. This is joint work with Luke Postle.

Exceptional times of the critical ErdƑs-RĂ©nyi graph

It is well known that the largest components in the critical ErdƑs-RĂ©nyi graph have size of order n2/3. We introduce a dynamic ErdƑs-RĂ©nyi graph by rerandomising each edge at rate 1, and ask whether there exist times in [0,1] at which the largest component is significantly larger than n2/3.

Contagious sets in a degree-proportional bootstrap percolation process

We study the following bootstrap percolation process: given a connected graph G, we infect an initial set of vertices A, and in each step a vertex v becomes infected if at least a \rho-proportion of its neighbours are infected (where \rho is a fixed constant). Once infected, a vertex remains infected forever. A set A which infects the whole graph is called a contagious set. It is natural to ask for the minimal size of a contagious set.

Our main result states that for every \rho between 0 and 1, every connected graph G on n vertices has a contagious set of size less than 2\rho n or a contagious set of size 1 (note that allowing the latter possibility is necessary since every contagious set has size at least one). This improves previous results of Chang and of Chang and Lyuu, who established the analogous bounds with 5.83 \rho n and 4.92 \rho n respectively in place of 2 \rho n, and also improves a recent result of Gentner and Rautenbach, who proved the analogous result with (2+\eps)\rho n in place of 2 \rho n for the special case when G has girth at least five and \rho is sufficiently small compared to \eps. Moreover, a simple construction shows that our theorem is best-possible in the sense that the bound 2\rho n cannot be replaced by C \rho n for any C < 2.

This is joint work with Andrew McDowell and Richard Mycroft.

On some recent applications of the polynomial method

In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z_4n and F_qn are exponentially small (compared to the size of the group). Since then many interesting applications of this method were shown, for instance, the solution of the ErdƑs-SzemerĂ©di sunflower conjecture, tight bound for Green’s arithmetic triangle removal lemma and growth rate of tri-colored sumfree sets. Finally, I will also mention some open problems.

Extremal Cuts and Isoperimetry in Random Cubic Graphs

Random 3-regular graphs are a particularly simple random structure, the bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms, and it seems likely that random cubic graphs are extremal. It is known that a random cubic graph has a (minimum) bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs), and we reduce this to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection (from 1/9.9 to 0.10133) using the Hamilton cycle model of a random cubic graph. We use the same Hamilton cycle approach to decrease the upper bound on maximum cut (from 1.4026 to 1.40031). We will discuss some related conjectures.

Correspondence Coloring and its Applications

Correspondence coloring, introduced by Dvorak and I in 2015, is a generalization of list coloring wherein vertices are given lists of colors and each edge is given a matching between the lists of its endpoints. So unlike in list or even ordinary coloring where adjacent vertices are not allowed to be colored the same, here we require that the colors of adjacent vertices are not matched along the edge. In this manner, correspondence coloring is list coloring where the ‘meaning’ of color is a local rather than global notion. Although results for correspondence coloring are interesting in their own right, in this talk we will focus on applying correspondence coloring to difficult problems from coloring and list-coloring to obtain new results; for example, for 3-list-coloring planar graphs without 4 to 8 cycles (joint work with Dvorak), on Reed’s conjecture (joint work with Bonamy and Perrett) and on the list coloring version of Reed’s conjecture (joint work with Delcourt).

Exploiting structure in sets of frequencies

Many problems in additive combinatorics and theoretical computer science are amenable to techniques of Fourier analysis, which is a powerful way of quantifying the well-known dichotomy between structure and randomness. In particular, if a set of integers does not behave pseudorandomly then it has many large Fourier coefficients. In the past few years there have been many developments achieved by treating this set of large Fourier coefficients as a subset of an abelian group and applying physical combinatorial arguments to extract more useful information. I will discuss these ideas and their applications to several problems in additive combinatorics.

Measure-valued PĂłlya processes

A P Ăłlya urn is a stochastic process that describes the composition of an urn that contains balls of different colours. The set of colours is usually a finite set {1, ... , d}. At each discrete-time step, one draws a ball uniformly at random in the urn (let c be its colour), and replace it in the urn together with R(c,i) balls of colour i, for all i = 1, ... , d. In this talk, I will present a generalisation of this model to an infinite, and potentially uncountable set of colours. In this new framework, the composition of the urn is a measure (possibly non-atomic) on a Polish space.

Two problems in extremal graph theory

In this talk, we prove a conjecture of Gyori and Tuza which states that the edges of every n-vertex graph G can be decomposed into edges and triangles C_1, . . . , C_k such that |C_1| . . . |C_k| ≀ (1/2 + o(1))n2 and we generalize a result of Sudakov concerning the number of edges needed to be removed from a K_4-free graph to make it bipartite. We show that if H is 6-colourable, then any H-free n-vertex graph can be made bipartite by deleting at most 4n2/25 edges. Both results are obtained using the flag algebra method. During the talk, we introduce the method and show how it can be applied to obtain the two results.

Joint work with P. Hu, D. Kral, B. Lidicky, S. Norin, Y. Pehova and J. Volec.

Intersecting families

In the talk we will discuss some classical and new results on intersecting families of k-element subsets of an n-element set. We will present a new proof of the Erdos-Ko-Rado and Hilton-Milner theorems using regular bipartite graphs. Then we will show how this method may be used to prove some general structural results on intersecting families.

The trophic structure of directed graphs

Directed graphs can be characterised by their ‘trophic structure’—that is, the patterns observed when vertices are assigned ‘trophic levels’ (as ecologists do with species in food webs) [1]. It has recently been shown using random graph ensembles that this structure, and in particular a quantity called ‘trophic coherence’, can be related to the distributions of directed cycles and adjacency matrix eigenvalues [2]. This, in turn, has important effects on other properties of systems of interacting elements, such as percolation in certain processes or the stability of dynamical systems [3]. I will summarise this work and consider some open questions.

[1] S. Johnson, V. Domínguez-García, L. Donetti, and M.A. Muñoz, Trophic coherence determines food-web stability, PNAS 111 , 17923 (2014) arXiv:1404.7728

[2] S. Johnson and N.S. Jones, Looplessness in networks is linked to trophic coherence, PNAS 114 , 5618 (2017) arXiv:1505.07332

[3] J. Klaise and S. Johnson, From neurons to epidemics: How trophic coherence affects spreading processes, Chaos 26, 065310 (2016) arXiv:1603.00670

Self-avoiding walk in ∞ + 1 dimensions

A self-avoiding walk in a graph is a path that visits each vertex at most once. Given an infinite, vertex-transitive graph, we are interested in the following questions:

1. How does the number of length-n self-avoiding walks started at the origin grow as a function of n?

2. What does a typical length-n self-avoiding walk look like?

In this talk, I will show how these questions can be addressed for certain nonamenable graphs, with emphasis on the product T x Z of a 3-regular tree T with the integers Z.

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP , a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and Jakub Tarnawski.

Bounding the cop-number of a graph in terms of its genus

The cop-and-robber game is a game on a graph played between two players, a set of cops, and a single robber. The rules of the game are as follows: In the first round both the cops and the robber choose starting vertices, in each consecutive even round each cop can move to a neighbouring vertex, in odd rounds, the robber can move to a neighbouring vertex. The game has perfect information, meaning that each player knows the positions of both the cops and the robber at any point in time. The cops win, if after some finite number of steps one of them occupies the same vertex as the robber, otherwise the robber wins.

A graph $G$ is called $k$-cop win, if for a set of $k$ cops there is a strategy to win the game no matter how the robber plays. The cop number $c(G)$ is the least number $k$ such that $G$ is $k$-cop win. This notion was first introduced in 1984 by Aigner and Fromme, who showed that the cop number of a planar graph is at most $3$. Using similar techniques, Quilliot showed that if $G$ can be embedded on an orientable surface of genus $g$, then $c(G) \leq 2g+3$. Schroeder subsequently improved this bound to $\frac 32g+3$ and conjectured an upper bound of $g+3$.

Using a reduction to a topological game played on an orientable surface, we are able to further improve the bound to $\frac 43 g + 3$ which to our knowledge is the first improvement since Schroeder first formulated his conjecture in 2001. (joint work with N. Bowler, J. Erde, and M. Pitz)

Rainbow spanning subgraphs of graphs with large minimum degree

If G is an edge coloured graph of order n, we say a subgraph H is rainbow if each edge of H has a different colour. Allowing the colouring of G to be arbitrary makes it easy to avoid all non-trivial rainbow spanning subgraphs. Suppose instead that the colouring is k-bounded, we ask how large k can be for certain pairings of graphs G with a spanning subgraph H. The case in which G is complete was solved by Böttcher, Kohayakawa and Procacci. We will exhibit some graphs H where taking the minimum degree of G to be slightly above H’s containment threshold allows us to find a rainbow copy of H in G for any ÎŒn-bounded colouring of G.

Joint work with Peter Keevash, Guillem Perarnau and Liana Yepremyan.

Scaling limits of critical inhomogeneous random graphs

Branching processes are known to be useful tools in studying random graphs, for instance in understanding the phase transition phenomenon in the asymptotics sizes of their connected components. In this talk, I’d like to discuss some applications of Galton—Watson trees (genealogy of branching process) in studying the geometrical aspects of random graphs. In particular, we will look at the so-called Poisson random graph, a random graph model which generalises the Erdos-Renyi graph G(n, p) and which has been previously studied by Aldous and Limic for its close connection with the multiplicative coalescents. Relying upon an embedding of the graph into a Galton-Watson forest, we can identify the scaling limits of these graphs inside the critical window.

Based on a joint work with Nicolas Broutin and Thomas Duquesne.

The minimum number of triangles in a graph of given order and size

A famous theorem of Mantel from 1907 states that every n-vertex graph with more than n^2/4 edges contains at least one triangle. In the 50s, ErdƑs asked for a quantitative version of this statement: for every n and e, how many triangles must an n-vertex e-edge graph contain? This question has received a great deal of attention, and a long series of partial results culminated in an asymptotic solution by Razborov, extended to larger cliques by Nikiforov and Reiher. Until recently, an exact solution was only known for a small range of edge densities, due to Lovász and Simonovits. In this talk, I will discuss the history of the problem and some new work which gives an exact solution for almost the entire range of edge densities. This is joint work with Hong Liu and Oleg Pikhurko.

A bandwidth theorem for approximate decompositions

We provide a degree condition on a regular $n$-vertex graph $G$ which ensures the existence of a near optimal packing of any family $H$ of bounded degree $n$-vertex $k$-chromatic separable graphs into $G$. In general, this degree condition is best possible.

Here a graph is separable if it has a sublinear separator whose removal results in a set of components of sublinear size. Equivalently, the separability condition can be replaced by that of having small bandwidth. Thus our result can be viewed as a version of the bandwidth theorem of B\”ottcher, Schacht and Taraz in the setting of approximate decompositions.

In particular, this yields an approximate version of the tree packing conjecture in the setting of regular host graphs $G$ of high degree. Similarly, our result implies approximate versions of the Oberwolfach problem, the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree. This is joint work with Jaehoon Kim, Daniela K\”uhn and Deryk Osthus.

The size of the giant component in random hypergraphs: a short proof

We consider connected components in k-uniform hypergraphs for the following notion of connectedness: given integers k> 1 and 0< j < k, two j-sets (j-tuples of distinct vertices) lie in the same j-component if there is a sequence of edges from one to the other such that consecutive edges intersect in at least j vertices.

We prove that certain collections of j-sets constructed during a breadth-first search process on j-components in a random k-uniform hypergraph are reasonably regularly distributed with high probability. As an application we provide a short proof of the asymptotic size of the giant j-component shortly after it appears.

This is joint work with Oliver Cooley and Mihyun Kang.

Shotgun Assembly of the Hypercube

In recent work, Mossel and Ross, and others have considered the shotgun assembly problem in various settings. We consider shotgun assembly of the hypercube – given the r-balls of a random q colouring of the vertices, can we reconstruct the colouring up to an automorphism with high probability? We show that for 2-balls, q=2 is sufficient, and that for 1-balls q ≄ n { 2 + Ω( log(n){1/2} )} is sufficient.

Joint work with Alexander Roberts and Alex Scott.

Edge correlations in random regular hypergraphs

The study of random regular $r$-graphs is made more challenging than the study of other classical models by the correlations existing between different edges of the $r$-graph. In this talk we show how an edge switching technique can be used to prove that, under mild conditions, these correlations are in fact very small and do not affect the distribution too much. We use this to derive some counting results in random regular $r$-graphs, including small subgraph counts and some spanning subgraph counts. In particular, we prove a conjecture about the threshold for the appearance of Hamilton cycles. We also show an application for testing subgraph freeness.

The edge-Erdös-Posa property

A class F of graphs has the vertex/edge-Erdös-Posa property if there is a function f:N->N such that for every natural number k and every graph G either G contains k vertex/edge-disjoint subgraphs isomorphic to a member of F or a set X of at most f(k) vertices/edges such that G-X contains no member of F as subgraph. Erdös and Posa proved in 1965 that cycles have this property and in the past 50 years many other classes were shown to have the vertex-Erdös-Posa property. However, only few classes were investigated regarding the edge-version of the property and it has been an open problem whether the vertex property implies the edge property or vice versa. I will present some recent developments in this area. Some parts of my work is joint with Felix Joos and Henning Bruhn.

Colourings without monochromatic chains

In 1974, ErdƑs and Rothschild introduced a new kind of extremal problem, asking which n-vertex graph has the maximum number of monochromatic-triangle-free red/blue edge-colourings. While this original problem strengthens Mantel’s theorem, recent years have witnessed the study of the ErdƑs-Rothschild extension of several classic combinatorial theorems. In this talk, we seek the ErdƑs-Rothschild extension of Sperner’s Theorem. More precisely, we search for the set families in 2^{[n]} with the most monochromatic-k-chain-free r-colourings. Time and interest permitting, we shall present some results, sketch some proofs, and offer open problems.

This is joint work with Roman Glebov, Benny Sudakov and Tuan Tran.

The Junta Method for Hypergraphs

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an ‘enlarged’ copy H^+ of a fixed hypergraph H. These include well-known problems such as the ErdƑs-SĂłs ‘forbidding one intersection’ problem and the Frankl-FĂŒredi ‘special simplex’ problem.

In this talk we present a general approach to such problems, using a ‘junta approximation method’ that originates from analysis of Boolean functions. We prove that any (H^+)-free hypergraph is essentially contained in a ‘junta’ — a hypergraph determined by a small number of vertices — that is also (H^+)–free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C < k < n/C, a complete solution of the extremal problem for a large class of H’s, which includes the aforementioned problems, and solves them for a large new set of parameters.

Based on joint works with David Ellis and Nathan Keller.

Colouring triangle-free graphs with few colours

A classical theorem of Johansson from 1996 asserts that $\chi(G) = O(\Delta/\ln\Delta)$ for triangle-free graphs $G$ of maximum degree $\Delta$. Johansson’s original proof of this result was quite intricate and involved iterated applications of the Lov\’{a}sz Local Lemma. Recently, Molloy has sharpened Johansson’s bound to $\chi(G) \leq (1+o(1))\Delta/\ln\Delta$ using the so-called entropy compression method—-an algorithmic alternative to the Lov\’{a}sz Local Lemma developed by Moser and Tardos. In this talk, I will sketch a simple proof of the Johansson—Molloy theorem that avoids the technicalities of the entropy compression method and only uses the standard Local Lemma (albeit in a somewhat unusual way). I will also mention some extensions of this result to more general notions of colouring, such as list and correspondence colouring.

Online graph coloring with bichromatic exchanges

Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires $\Omega(\log n)$ colors in the worst case. We consider a variation of the First-Fit algorithm in which the algorithm is allowed to make modifications to previously colored vertices by performing local bichromatic exchanges. We show that such algorithms can be used to find an optimal coloring in the case of bipartite graphs, chordal graphs and outerplanar graphs. We also show that it can find coloring of general planar graphs with $O(\log \Delta)$ colors, where$\Delta$ is the maximum degree of the graph. The question of whether planar graphs can be colored by an online algorithm with bichromatic exchanges using only a constant number of colors is still open. This is a joint work with Sylvain Gravier.

Previous seminars: Autumn 2006, Spring 2007, Autumn 2007, Spring 2008, Autumn 2008, Spring 2009, Autumn 2009, Spring 2010, 2010-2016, 2016/17, 2017/18, 2018/19, 2019/20, 2020/21, 2021/22, 2022/23