Open Problem Workshop
Please come around and discuss some open problems.
- Part of Combinatorics and Probability seminar
- Speaker: Various Speakers
- Thursday 30 September 2021, 15:00-17:00
- LTA.
Open Problem Workshop, part 2
Please come around and discuss some open problems.
- Part of Combinatorics and Probability seminar
- Speaker: Various Speakers
- Thursday 07 October 2021, 15:00-17:00
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\geq 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree ${O(t (log t)0.5)}$ $$ and hence is $O(t (log t)0.5)$ $$-colorable. In a recent breakthrough, Norin, Song, and Postle proved that every graph with no $K_t$ minor is $O(t log t)c)$ $$-colorable for every $c > 0.25$, Subsequently Postle showed that every graph with no $K_t$ minor is $O(t (log log t)6)$ $ $ -colorable. We improve upon this further by showing that every graph with no $K_t$ minor is $O(t log log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwigerâs Conjecture is the so-called Linear Hadwigerâs Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwigerâs Conjecture reduces to small graphs. In 2003, KĂŒhn and Osthus proved that Hadwigerâs Conjecture holds for graphs of girth at least five (provided that $t$ is sufficiently large). In 2005, KĂŒhn and Osthus extended this result to the class of $K_{s,s}$-free graphs for any fixed positive integer $s\geq 2$. Along this line, we show that Linear Hadwigerâs Conjecture holds for the class of $K_r$-free graphs for every fixed $r$. This is joint work with Luke Postle.
- Part of Combinatorics and Probability seminar
- Speaker: Michelle Delcourt, Toronto
- Thursday 14 October 2021, 15:00-16:00
- https://bham-ac-uk.zoom.us/j/87124623071.
Progress on the Kohayakawa-Kreuter conjecture
Let H_1, ..., H_r be graphs. We write G(n,p) â (H_1, ..., H_r) to denote the property that whenever we colour the edges of G(n,p) with colours from the set {1, ..., r} there exists some 1 †i †r and a copy of H_i in G(n,p) monochromatic in colour i.
There has been much interest in determining the asymptotic threshold function for this property. Rödl and RuciĆski (1995) determined the threshold function for the general symmetric case; that is, when H_1 = ... = H_r. A conjecture of Kohayakawa and Kreuter (1997), if true, would fully resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij (2021+). The 0-statement however has only been proved for pairs of cycles, pairs of cliques and pairs of a clique and a cycle.
- Part of Combinatorics and Probability seminar
- Speaker: Joseph Hyde, Warwick
- Thursday 21 October 2021, 15:00-16:00
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
Counting cliques in 1-planar graphs
The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of 1-planar graphs, i.e. graphs that can be drawn in the plane in such a way that each edge crosses at most 1 other edge, where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems. This is joint work with Kevin Hendrey, Abhishek Methuku, Casey Tompkins and Xin Zhang.
- Part of Combinatorics and Probability seminar
- Speaker: Pascal Gollin, IBS Korea
- Thursday 28 October 2021, 15:00-16:00
- https://bham-ac-uk.zoom.us/j/87124623071.
Average degree and bicliques
When is the maximum average degree of a graph tied to the size of its largest balanced biclique? It turns out that we just need to forbid induced 4-cycle-free subgraphs of large average degree. But can we use this approach to find an efficient relationship? This talk will be informal and focused on open problems.
- Part of Combinatorics and Probability seminar
- Speaker: Rose McCarty, Waterloo
- Thursday 04 November 2021, 15:00-16:00
- https://bham-ac-uk.zoom.us/j/87124623071.
Degree conditions for spanning hypergraphs
A central problem in extremal graph theory is the study of degree conditions that force a graph G to contain a copy of some large or even spanning subgraph. Famous examples in this area include Diracâs theorem on Hamilton cycles, the BollobĂĄs conjecture on spanning trees, the PĂłsa-Seymour conjecture on powers of Hamilton cycles, and the Bandwidth conjecture of BollobĂĄs and KomlĂłs.
In this talk, we will describe some recent results trying to generalise this problem to the setting of k-uniform hypergraphs. In particular, we will show a hypergraph version of BollobĂĄsâs conjecture and progress to a hypergraph version of the PĂłsa-Seymour conjecture.
- Part of Combinatorics and Probability seminar
- Speaker: Matias Pavez-Signe, Birmingham
- Thursday 18 November 2021, 15:00-16:00
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
The ErdĆs-Rothschild problem
Consider an $n$-vertex graph $G$ whose edges are coloured with $s$ colours so that there is no monochromatic clique of size $k$, and call such a colouring of $G$ valid. The ErdĆs-Rothschild problem from 1974 is to determine the maximum number of valid colourings over all $n$-vertex graphs $G$. This problem is in general wide open and an exact (or even asymptotic) answer is only known for a few pairs $(k,s)$. In this talk I will discuss a method for obtaining new exact results. Joint work with Oleg Pikhurko
- Part of Combinatorics and Probability seminar
- Speaker: Katherine Staden, Oxford
- Thursday 25 November 2021, 15:00-16:00
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
The n-queens problem
How many ways are there to place n queens on an n by n chessboard so that no two can attack one another? What if the chessboard is embedded on the torus? Let Q(n) be the number of ways on the standard chessboard and T(n) the number on the toroidal board. The toroidal problem was first studied in 1918 by PĂłlya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne)n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne)n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n).
In this talk weâll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almostâ configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.
This is joint work with Peter Keevash.
- Part of Combinatorics and Probability seminar
- Speaker: Candida Bowtell, Birmingham
- Thursday 09 December 2021, 15:30-16:30
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071 (NOTE: UNUSUAL TIME).
Tight Ramsey bounds for multiple copies of a graph
The Ramsey number r(G) of a graph G is the smallest integer n such that any 2-colouring of the edges of a clique on n vertices contains a monochromatic copy of G. Determining the Ramsey number of G is a central problem of Ramsey theory with a long history. Despite this there are very few classes of graphs G for which the value of r(G) is known exactly. One such family consists of large vertex disjoint unions of a fixed graph H, we denote such a graph, consisting of n copies of H by nH. This classical result was proved by Burr, ErdĆs and Spencer in 1975, who showed r(nH)=(2|H|âα(H))n+c, for some c=c(H), provided n is large enough. Since it did not follow from their arguments, Burr, ErdĆs and Spencer further asked to determine the number of copies we need to take in order to see this long term behaviour and the value of c. More than 30 years ago Burr gave a way of determining c(H), which only applies when the number of copies n is triple exponential in |H|. We obtain an essentially tight answer to this very old problem of Burr, ErdĆs and Spencer by showing that the long term behaviour occurs already when the number of copies is single exponential.
Joint work with B. Sudakov.
- Part of Combinatorics and Probability seminar
- Speaker: Matija Bucic, Princeton
- Thursday 13 January 2022, 15:00-16:00
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
Graph Decompositions
Chokepoints raise challenges in numerous fields, from everyday traffic and logistics to ancient and digital military strategies. In graph theory, the global chokepoints of any graph allow us to decompose it in a tree-like way into smaller graphs by cutting at the global chokepoints. The basic instance of this idea is the block-cutvertex tree. In practice, however, chokepoints usually are not global in nature, and many graphs are not tree-like. We introduce a new method which allows us to decompose any graph into smaller graphs in an H-like way, where H is a graph simpler than G which represents the global shape of G, by cutting at the local chokepoints of G. Joint work with Carmesin, Diestel, Jacobs and Knappe.
- Part of Combinatorics and Probability seminar
- Speaker: Jan Kurkofka, Birmingham
- Thursday 20 January 2022, 15:00-16:00
- LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
Towards a 1-dependent version of the Harris--Kesten theorem
Consider a random subgraph of the square integer lattice Z2 obtained by including each edge independently at random with probability p, and leaving it out otherwise. The HarrisâKesten theorem states that if p is at most 1/2, then almost surely all connected components in this random subgraph are finite, while if p>1/2 then almost surely there exists a unique infinite connected component.
But now what if we introduced some local dependencies between the edges? More precisely, suppose each edge still has a probability p of being included in our random subgraph, but its state (present/absent) may depend on the states of edges it shares a vertex with. To what extent can we exploit such local dependencies to delay the appearance of an infinite component?
In this talk I will discuss this question, which first arose in work of Balister, BollobĂĄs and Walters in 2005, and discuss some recent progress on it made in joint work with Nicholas Day, Robert Hancock and Vincent Pfenninger.
- Part of Combinatorics and Probability seminar
- Speaker: Victor Falgas Ravry, Umea
- Thursday 27 January 2022, 13:00-14:00
- Attention: unusual time, zoom link: https://bham-ac-uk.zoom.us/j/87124623071.
Sufficient Conditions for Perfect Mixed Tilings
We develop a method to study sufficient conditions for perfect mixed tilings. Our framework allows the embedding of bounded degree graphs H with components of sublinear order. As a corollary, we recover and extend the work of KĂŒhn and Osthus regarding sufficient minimum degree conditions for perfect F-tilings (for an arbitrary fixed graph F) by replacing the F-tiling with the aforementioned graphs H. Moreover, we obtain analogous results for degree sequences and in the setting of uniformly dense graphs. Finally, we asymptotically resolve a conjecture of KomlĂłs in a strong sense.
- Part of Combinatorics and Probability seminar
- Speaker: Eoin Hurley, Heidelberg
- Thursday 10 February 2022, 16:00-17:00
- Poynting Large Lecture Theatre, additional zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
High-girth Steiner triple systems
In this talk Iâll discuss our recent resolution of a conjecture due to ErdĆs on the existence of Steiner triple systems with arbitrarily high girth. Iâll start by giving a brief overview of random greedy processes and the method of iterative absorption, and discussing the relevant challenges in the high-girth setting. Then, Iâll outline some ideas that help overcome these challenges, related to sparsification, efficient absorption, and âretrospectiveâ analysis of random processes. This is joint work with Ashwin Sah, Mehtaab Sawhney, and Michael Simkin.
- Part of Combinatorics and Probability seminar
- Speaker: Matthew Kwan, IST Austria
- Thursday 24 February 2022, 15:00-16:00
- Via Zoom, but Poynting Large Lecture Theatre is also booked. Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Dirac-type results for tilings and coverings in ordered graphs
A (vertex) ordered graph H on h vertices is a graph whose vertices have been labelled with {1, . . . , h}. Balogh, Li and Treglown recently initiated the study of Dirac-type problems for ordered graphs. In particular, they focused on the problem of determining the minimum degree threshold for forcing a perfect H-tiling in an ordered graph for any fixed ordered graph H (recall that a perfect H-tiling in a graph G is a collection of vertex-disjoint copies of H covering all the vertices in G). In this talk we present a result which builds up on their ideas and fully resolve such problem. We also determine the asymptotic minimum degree threshold for forcing an H-cover in an ordered graph. This is joint work with Andrew Treglown.
- Part of Combinatorics and Probability seminar
- Speaker: Andrea Freschi, University of Birmingham
- Thursday 03 March 2022, 15:00-16:00
- Poynting Large Lecture Theatre. Also via Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
How to build a pillar: a proof of Thomassen's conjecture
Carsten Thomassen in 1989 conjectured that if a graph has minimum degree more than the number of atoms in the universe (delta(G) > 10{10{10}}), then it contains a pillar, which is a graph that consists of two vertex-disjoint cycles of the same length, s say, along with s vertex-disjoint paths of the same length which connect matching vertices in order around the cycles. Despite the simplicity of the structure of pillars and various developments of powerful embedding methods for paths and cycles in the past three decades, this innocent looking conjecture has seen no progress to date. In this talk, we will try to give an idea of the tools used in the proof of this conjecture, which consists of building a pillar (algorithmically) in sublinear expanders. This is joint work with Hong Liu.
- Part of Combinatorics and Probability seminar
- Speaker: Irene Gil FernĂĄndez, University of Warwick
- Thursday 10 March 2022, 15:00-16:00
- Poynting Large Lecture Theatre, additional zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Distinct degrees and homogeneous sets
In this talk I will discuss some recent work examining the extremal relationship between two well-studied graph parameters: the order of the largest homogeneous set in a graph G and the maximal number of distinct degrees appearing in an induced subgraph of G, denoted respectively by hom (G) and f(G).
Our main theorem improves estimates due to Bukh and Sudakov and to Narayanan and Tomon and shows that if G is an n-vertex graph with hom (G) at least n1/2 then f(G) > ( n / hom (G) )1 â o(1). The bound here is sharp up to the o(1)-term, and asymptotically solves a conjecture of Narayanan and Tomon. In particular, this implies that max { hom (G), f(G) } > n1/2 -o(1) for any n-vertex graph G, which is also sharp.
The relationship between these parameters changes when hom (G) < n1/2. I hope to discuss the suspected relationship in this other region, along with supporting results. Joint work with Eoin Long.
- Part of Combinatorics and Probability seminar
- Speaker: Laurentiu Ploscaru, University of Birmingham
- Thursday 17 March 2022, 15:00-16:00
- Poynting Large Lecture Theatre, additional zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
I will present a counterexample to the following well-known conjecture: for every k, r, every graph G with clique number at most k and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least r. Then I will discuss a related counterexample, due to Brianski, Davies, and Walczak, for another conjecture about graphs of large chromatic number. Joint work with Alvaro Carbonero, Patrick Hompe, and Benjamin Moore.
- Part of Combinatorics and Probability seminar
- Speaker: Sophie Spirkl, University of Waterloo
- Thursday 31 March 2022, 15:00-16:00
- Via Zoom, but Poynting Large Lecture Theatre is also booked. Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Rödl's theorem with restrictions
It is well known that every uniform d-regular hypergraph with small codegrees contains an almost perfect matching (provided d is large). This result and the proof method have influenced combinatorics substantially. We provide an extension of this theorem where one additional can forbid certain tuples of edges not to appear in the almost perfect matching. This is often very helpful for applications and in particular includes approximate high girth Steiner triple systems. This is joint work with Stefan Glock, Jaehoon Kim, Marcus KĂŒhn and Lyuben Lichev.
- Part of Combinatorics and Probability seminar
- Speaker: Felix Joos, Heidelberg University
- Thursday 07 April 2022, 15:00-16:00
- Poynting Large Lecture Theatre. Also via Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Subgraphs in Semi-random Graphs (and Hypergraphs)
The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible. We will consider the property of constructing a fixed graph G as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct G given n^{1 â 1/d}w rounds, where w is any function tending to infinity with n and d is the degeneracy of the graph G. We have proved a matching lower bound. I will talk about this result, and also discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.
This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.
- Part of Combinatorics and Probability seminar
- Speaker: Natalie Behague, University of Victoria
- Thursday 28 April 2022, 16:00-17:00
- Via Zoom, but Poynting Large Lecture Theatre is also booked. Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Constructible graphs and the game of cops and robbers
The game of cops and robbers is played on a fixed graph G. The cop picks a vertex to start at, and the robber then does the same. Then they move alternately, with the cop moving first: at each turn the player moves to an adjacent vertex or does not move. The game is won by the cop if he lands on the robber. The graph G is called cop-win if the cop has a winning strategy, and weak cop-win if the cop has a strategy that ensures that the robber is either caught or visits each vertex only finitely many times.
A graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood.
In this talk we focus on infinite graphs and the relation between constructible graphs and cop-win or weak cop-win graphs.
We also investigate how these notions relate to the (weaker and more natural) notion of âlocally constructibleâ (every finite subgraph is contained in a finite constructible subgraph).
Joint work with Imre Leader and Mark Walters.
- Part of Combinatorics and Probability seminar
- Speaker: Maria-Romina Ivan, University of Cambridge
- Thursday 05 May 2022, 15:00-16:00
- Poynting Small Lecture Theatre, additional zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Almost every matroid has a rank-3 wheel or rank-3 whirl as minor
Many conjectures â but few results â exist for the statistical properties of large ârandomâ matroids. For example, the question which matroids appear as a minor of almost every matroid has been settled for only a few matroids. I will present recent progress in this direction: almost every matroid has at least one of two particular matroids, the rank-3 wheel M(K_4) or the rank-3 whirl W^3, as a minor.
At the heart of the argument lies a counting version of the RuzsaâSzemerĂ©di (6,3)-theorem on 3-uniform hypergraphs, which is then generalised in several ways to obtain the main result.
This talk focuses on the hypergraph side of things; in particular, no prior knowledge about matroids is assumed.
- Part of Combinatorics and Probability seminar
- Speaker: Jorn van der Pol, University of Waterloo
- Thursday 19 May 2022, 15:00-16:00
- Via Zoom, but Poynting Large Lecture Theatre is also booked. Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
TurĂĄn densities for hypergraph with quasirandom links
Reiher, Rödl, and Schacht proved that 3-uniform hypergraphs with the property that all vertices have a quasirandom link graph with density bigger than $(r-2)/(r-3)$ contain a clique on $2^r$ vertices. This result turned out to be asymptotically best possible for several cliques up to size 16. Their proof is based on an application of the regularity method for hypergraphs. Here we find a substantially simpler proof of this result based mainly on supersaturation arguments. In fact this new approach allows us to obtain slightly more general results.
Additionally, for the appropriately defined Turån density for this context, we establish a general bound for the Turån density of $K_{2r}$ with respect to the Turån density of $K_r$. This is a joint work with Berger, Reiher, Rödl, and Schacht.
- Part of Combinatorics and Probability seminar
- Speaker: SimĂłn Piga, University of Birmingham
- Thursday 26 May 2022, 15:00-16:00
- Poynting Large Lecture Theatre. Also via Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
Discrete group actions on 3-manifolds and embeddable Cayley complexes
A classic theorem of Tucker asserts that a finite group Î acts on an oriented surface S if and only if Î has a Cayley graph G that embeds in S equivariantly, i.e. the canonical action of Î on G can be extended to an action of Î on all of S. Following the trend for extending graph-theoretic results to higher-dimensional complexes, we prove the following 3-dimensional analogue of Tuckerâs Theorem: a finitely generated group Î acts âdiscretely on a simply connected 3-manifold M if and only if Î has a âgeneralised Cayley complexâ that embeds equivariantly in one of the following four 3-manifolds: (i) S3 , (ii) R3 , (iii) S2 x R, and (iv) the complement of a tame Cantor set in S3. In the process, we will see some recent theorems and lemmata concerning 2-complex embeddings and group actions over 2-complexes, and we will derive a combinatorial characterization of finitely generated groups acting âdiscretely on simply connected 3-manifolds.
- Part of Combinatorics and Probability seminar
- Speaker: George Kontogeorgiou, University of Warwick
- Thursday 09 June 2022, 15:00-16:00
- Poynting Large Lecture Theatre. Also via Zoom link: https://bham-ac-uk.zoom.us/j/88168768618.
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