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.
- Part of Combinatorics and Probability seminar
- Speaker: Clive Elphick (University of Birmingham)
- Tuesday 26 September 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Matthias Winkel (University of Oxford)
- Tuesday 03 October 2017, 15:00-16:00
- Watson LTA.
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 signficant 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.
- Part of Combinatorics and Probability seminar
- Speaker: Michelle Delcourt (University of Birmingham)
- Tuesday 10 October 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Matt Roberts (University of Bath)
- Tuesday 17 October 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Fred Garbe (University of Birmingham)
- Tuesday 24 October 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Peter Pach (University of Warwick)
- Tuesday 31 October 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Gregory Sorkin (London School of Economics)
- Tuesday 07 November 2017, 15:00-16:00
- Watson LTA.
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).
- Part of Combinatorics and Probability seminar
- Speaker: Luke Postle (University of Waterloo)
- Friday 10 November 2017, 14:00-15:00
- Watson LTC.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Thomas Bloom (University of Bristol)
- Tuesday 14 November 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: CĂ©cile Mailler (University of Bath)
- Tuesday 21 November 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Taisa Martins (University of Warwick)
- Tuesday 28 November 2017, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Andrey Kupavskii (University of Birmingham)
- Tuesday 05 December 2017, 15:00-16:00
- Watson LTA.
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
- Part of Combinatorics and Probability seminar
- Speaker: Samuel Johnson (University of Birmingham)
- Tuesday 09 January 2018, 15:00-16:00
- Physics West 106.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Tom Hutchcroft (University of Cambridge)
- Tuesday 16 January 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Lazlo Vegh (LSE)
- Tuesday 23 January 2018, 15:00-16:00
- Physics West 106.
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)
- Part of Combinatorics and Probability seminar
- Speaker: Florian Lehner (University of Warwick)
- Tuesday 30 January 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Matthew Coulson (University of Birmingham)
- Tuesday 06 February 2018, 15:00-16:00
- Physics West 106.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Minmin Wang (University of Bath)
- Tuesday 13 February 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Katherine Staden (University of Oxford)
- Tuesday 20 February 2018, 15:00-16:00
- Physics West 106.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Padraig Condon (University of Birmingham)
- Tuesday 27 February 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Christoph Koch (University of Oxford)
- Tuesday 13 March 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Michal Przykucki (University of Oxford)
- Tuesday 20 March 2018, 15:00-16:00
- Physics West 106.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Alberto Espuny (University of Birmingham)
- Wednesday 02 May 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Matthias Heinlein (UniversitÀt Ulm)
- Tuesday 08 May 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Shagnik Das
- Tuesday 15 May 2018, 15:00-16:00
- Watson LTC.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Noam Lifshitz (Bar Ilan University)
- Thursday 17 May 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Anton Bernshteyn (University of Illinois at Urbana-Champaign)
- Wednesday 30 May 2018, 15:00-16:00
- Watson LTA.
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.
- Part of Combinatorics and Probability seminar
- Speaker: Marc Heinrich (Université Lyon 1)
- Wednesday 13 June 2018, 15:00-16:00
- Watson LTA.
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