Past Events

 

 

Past Combinatorics Seminars

 

2021/22

Open Problem Workshop

Please come around and discuss some open problems.

Open Problem Workshop, part 2

Please come around and discuss some open problems.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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