The single-source unsplittable flow problem asks to send flow in a digraph with capacities from a common source to different terminals with unrelated demands, each terminal being served through a single path. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. Moreover, Morell and Skutella conjecture a version with lower and upper bounds on the flow along every arc. In this talk we will see that the conjecture by Morell and Skutella as well as a slightly weaker version of the Goemans’ conjecture hold on planar graphs. Moreover, we will observe that our approach can be extended to general (non-planar) graphs with a capacity violation that depends on the genus. Based on joint work with Vera Traub and Rico Zenklusen.

Determining the chromatic number of a graph is an important but difficult problem. A natural variety of this problem is to find meaningful upper bounds for the chromatic number of certain families of graphs. One type of graph family that received considerable attention is that the family of graphs G which do not contain a given graph H as subgraph (H-free graphs). Erdős showed that the chromatic number of H-free graphs G can be arbitrarily large (when H is not a forest). In 1973 Erdős and Simonovits asked what happens if we additionally impose a minimum degree condition for G. This initiated the study of the so-called chromatic threshold of a graph H and opened several important directions of research.

In the talk I will provide all necessary background and discuss the relations between the chromatic threshold and other important concepts such as the chromatic profile and the homomorphism threshold. I will also talk about recent work with Liu, Shangguan and Xu in which we establish a novel connection between the chromatic threshold problem in extremal combinatorics and the celebrated (p,q)-theorem in discrete geometry.

Let $\mathcal P$ be a finite poset. We say that a family of subsets of $[n]$ is $\mathcal P$-saturated if the family does not contain an induced copy of $\mathcal P$, but adding any other new set to the family creates such a copy. How small can such a family be? This is called the saturation number for P, denoted by $\text{sat}^*(n, \mathcal P)$. It turns out that this is a misleadingly easy looking question, as so far, this question has been answered exactly for just a few precious posets. Even more intriguing is the fact that for some posets the saturation number is bounded whilst for others it is not, and there is no structural classification that tells us the behaviour of the saturation number. Furthermore, the saturation number displays a dichotomy: it is either bounded or it grows at least as fast as $\sqrt n$. It is believed that in fact, for all posets, the saturation number is either bounded or linear. In this talk we will discuss a certain operation which allows us to create a very general infinite class of posets with unbounded saturation number. In particular, we show that any poset can be an induced subposet of one with unbounded saturation number. This superposet can even be chosen to be a certain combination of just the original poset and any antichain of any size. We will also look at the weak version of the problem, the poset analogue of weak saturation for graphs, called the poset percolating number, and show how differently, once again, these notions are from the classical graph saturation ones.

Joint work with Sean Jaffe

In 1976, Burr, Erdős and Lovász initiated a systematic study of various properties of Ramsey graphs. A graph $G$ is said to be $r$-Ramsey if every $r$-colouring of the edges of $G$ contains a monochromatic copy of $K_k$. Moreover, it is called minimal when no proper subgraph of $G$ has this property. While historically a lot of attention has been devoted to the smallest possible order of a $2$-Ramsey graph, one could also consider for example the smallest chromatic number, maximum, or minimum degree of a minimal $r$-Ramsey graph.

While Burr, Erdős and Lovász already determined the smallest possible minimum degree of minimal $2$-Ramsey graphs, the behavior of this quantity is much less understood for more colours. In particular, it is not clear what the correct asymptotic behaviour (in both $k$ and $r$) is. We will present some progress towards this problem, based on joint work Jacques Verstraete.

The classical result of Vizing states that a graph $G$ be properly edge coloured using $\Delta(G) +1$ colours. We study a generalisation, where the goal is to simultaneously colour the edges of graphs $G_1, \dots, G_k$ with few colours. That is, we seek an edge-colouring on $G_1 \cup \dots \cup G_k$ that is proper for each individual $G_i$. When $k = 2$, we should that $( 1+o(1) ) \Delta$ colours suffice, where $\Delta(G_1), \Delta(G_2) \le \Delta$. This confirms asymptotically a conjecture of Agdur, Cambie, Heckel, Perarnau and Volec. For general $k$, we show that the asymptotical values is closely related to a conjecture of Füredi, Kahn, and Seymour from the 1990s and an old problem about fractional matchings.

This is joint work with Simona Boyadzhiyska, Richard Lang and Michael Molloy.

We call a convex body lattice reduced if it does not strictly contain any other convex body of the same lattice width—a parameter studying “how flat” a convex body is with respect to the lattice of integer points. We show structural properties of lattice reduced convex bodies: that they are polytopes, with not too many vertices; and then investigate the connection to the flatness problem: determining, for each dimension, the maximum lattice width of convex bodies without interior integer points. We will then delve into further directions of study and open questions.

What conditions on an edge colouring of the complete graph with n vertices imply that it must contain an n-vertex cycle in which no two touching edges have the same colour (i.e., a properly-coloured Hamilton cycle)? In 1976, Bollobás and Erdős conjectured that if every vertex is adjacent to fewer than $\lfloor n/2\rfloor$ edges of the same colour, then there is always a properly-colored Hamilton cycle. Bollobás and Erdős gave an extremal example showing that the bound $\lfloor n/2\rfloor$ would be tight, and further extremal examples were later found by Fujita and Magnant, and by Lo who also proved the conjecture asymptotically in 2016.

I will discuss further extremal examples and a proof that this conjecture is true for large n. This is joint work with Aleksa Milojević, Alexey Pokrovskiy, and Benny Sudakov.

Modularity, despite known flaws, is a quality function on clusterings of networks which is commonly used in clustering algorithms. For a given graph G, each clustering of the vertices has a modularity score, with higher values taken to indicate that the clustering better captures community structure in G. The modularity of G is the maximum over all clusterings and lies in [0,1].

Modularity redemption?: Guimerà, Sales-Pardo and Amaral discovered high modularity of the Erdős-Rényi (ER) random graph with constant average degree and suggested it stems from the random fluctuations in its edge distribution. With minor assumptions on the degree sequence we show that any graph with average degree d, has modularity at least order 1/sqrt(d) matching that in ER up to order of magnitude. These lower bounds offer a certain level of validation to modularity as a measure for community structure. Since, by these results, random graphs do, up to order of magnitude, have the minimum achievable modularity for a given density.

We relate two important notions in graph theory: expander and modularity. More precisely, we show that a graph having modularity bounded below 1 is equivalent to it having a large subgraph which is an expander. The resolution limit says that in an m-edge graph any component of size less than sqrt(2m) will not be split in any modularity optimal component (Fortunato-Barthélemy). We generalise this and show that whether or not a component is split is a function only a conductance measure on the component and the relative size of the component.

I will end with some open questions. Joint work with Vilhelm Agdur, Nina Kamčev, Baptiste Louf, Colin McDiarmid.

A $d$-dimensional framework is a pair $(G,p)$ where $G=(V,E)$ is a graph and $p:V\to {\mathbb R}^d$. The length of each edge of $(G,p)$ is the Euclidean distance between its endpoints. The framework is rigid if every continuous motion of the vertices of $(G,p)$ which preserves the edge lengths, preserves the distances between all pairs of vertices. It is globally rigid if every realisation of $G$ in ${\mathbb R}^d$ which has the same edge lengths as $(G,p)$, has the same distances between all pairs of vertices. A graph $G$ is rigid, respectively globally rigid, in ${\mathbb R}^d$ if every, or equivalently some, generic realisation of $G$ in ${\mathbb R}^d$ is rigid, respectively globally rigid. Both properties have been characterised for graphs when $d=1,2$. Extending these characterizations to ${\mathbb R}^d$ for $d\geq 3$ is an important open problem in discrete geometry.

Simplicial $(d-1)$-manifolds, i.e simplicial $(d-1)$-complexes whose underlying topological space is a manifold, provide a large family of graphs for which we can determine both rigidity and global rigidity in ${\mathbb R}^d$. Indeed, the first theorem on the rigidity of frameworks is a celebrated result of Cauchy which implies that the 1-skeleton of every convex simplicial polyhedron is rigid in ${\mathbb R}^3$. This result was extended to convex $d$-polytopes in ${\mathbb R}^d$ for all $d\geq 3$ by Whiteley. Kallai used Whiteley’s theorem to deduce that 1-skeleta of simplicial $(d-1)$-manifolds are generically rigid in ${\mathbb R}^{d}$ when $d\geq 4$. Fogelsanger introduced an ingenious new proof technique in his PhD thesis in 1988 to show that the same result holds for all $d\geq 3$.

I will give a brief introduction to combinatorial rigidity theory, emphasising results on triangulations of surfaces. I will then describe recent joint work on simplicial $(d-1)$-manifolds with James Cruickshank and Shin-ichi Tanigawa in which we characterise when their 1-skeleta are globally rigidity in ${\mathbb R}^d$, and also show that simplicial $(d-1)$-manifolds remain rigid if, instead of fixing the lengths of their edges, we fix the volume of their faces of dimension $k$ for any fixed $1\leq k\leq d-3$.

Dirac’s Theorem says that every n-vertex graph with minimum degree at least $n/2$ contains a Hamilton cycle. Lee and Sudakov extended Dirac’s theorem to the setting of random graphs, showing that a random graph (above the threshold to contain a Hamilton cycle) typically has the property that every spanning subgraph with minimum degree at least $(1/2 +o(1))np$ contains a Hamilton cycle.

In a different direction, we can ask for a discrepancy version of Dirac’s theorem. In this setting, the edges of the graph G are coloured with r colours and we want to know whether there necessarily exists a colour-biased Hamilton cycle where some colour is used (a lot) more than $n/r$ times. Heuristically, this implies there must be many intersecting Hamilton cycles. If G has minimum degree at least $(1/2 + 1/2r + o(1))n$ then such a result holds.

This talk concerns a combination of the above lines of research to give a discrepancy Dirac-type result in the random graph. I will finish with a brief discussion of some potential generalisations and related problems.

This is joint work with Debsoumya Chakraborti and Jared Leon.

In this talk I will present some recent work, joint with various collaborators, on longest paths and cycles in graphs. First, I will discuss three conjectures due to Lovasz (1969), Thomassen (1978) and Smith (1984), respectively, regarding the length and intersections of longest paths and cycles in (vertex-transitive) graphs, and present improved bounds towards these conjectures. If time permits, I will also present some recent new results on the corresponding problem for directed graphs.

Motivated by and related to these conjectures I will then present an improved upper bound for another well-known problem, going back to an old question of Gallai from 1966, namely: How many vertices are needed to hit all longest paths (cycles) in a connected (2-connected) graph?

In the early days of modern era democracy, Condorcet made several important mathematical discoveries regarding elections and the majority rule.
Condorcet’s jury theorem asserts that when the number of voters is large,even a small signal favoring a preferable choice leads, with high probability, to a socially optimal outcome. This result, derived from the weak law of large numbers, reflects the idea that the collective opinion of a diverse and independent group tends to yield good judgments. Condorcet’s paradox states that when there are three or more candidates, the majority rule can lead to cyclic social preferences. Arrow later demonstrated that under very general conditions, Condorcet’s paradox applies to every non-dictatorial voting rule.

We will explore combinatorial and probabilistic aspects of voting rules. Specifically, for general monotone two-candidate voting rules, we will present a sharp connection between Condorcet’s jury theorem and the maximal Shapley-Shubik power index of voters (joint work with Noam Lifshitz). Additionally, we will discuss research by Eric Maskin and Gabriel Gendler on a relaxation of Arrow’s Independence of Irrelevant Alternatives (IIA) condition. If time permits, we will also touch on indeterminacy and noise sensitivity.