Past Events

 

 

Past Combinatorics Seminars

 

2022/23

Open Problem Session

Open problems will be presented by various speakers.

Mini-workshops

As a follow-up of the Open Problems Workshop, we will be meeting in small groups each focussing on a single problem.

Open Problem Session

Open problems will be presented by various speakers.

Rigidity of graphs

A (bar-joint) framework is the combination of a graph G and a map p assigning positions in Euclidean d-space to the vertices of G. The vertices are modelled as universal joints and the edges as stiff bars. The framework is rigid if the only edge-length-preserving continuous deformation of the vertices arises from an isometry of the space. While it is computationally difficult to determine if a given framework is rigid, the generic behaviour depends only on the graph. Indeed, when d=1, G is rigid if and only if it is connected, and when d=2, a precise combinatorial description was obtained by Polaczek-Geiringer in the 1920s. However, giving a combinatorial description in all higher dimensions remains open 100 years later. The talk will survey graph rigidity and then report on recent joint work on a particular special case as well as an application to maximum likelihood estimation.

Percolation in High-Dimensional Product Graphs

A classic result of ErdƑs and RĂ©nyi describes the phase transition that the component structure of the binomial random graph G(n,p) undergoes when p is around 1/n. Below this point, the graph typically contains only small components, of logarithmic order, whereas above this point many of these component coalesce to a unique `giant’ component of linear order, and all other components are of logarithmic order. It has been observed that quantitatively similar phase transitions occur in many other percolation models, and, in particular, work of Ajtai, KomlĂłs and SzemerĂ©di and of BollobĂĄs, Kohayakawa and Ɓuczak shows that such a phenomena occurs in the percolated hypercube. We consider this phase transition in percolation on graphs arising from the cartesian product of many graphs and show that, under some mild conditions on the factor graphs, this phenomena is universal.

Joint with Sahar Diskin, Mihyun Kang and Michael Krivelevich

Transversal cycle factors in multipartite graphs

A transversal Ck-factor in a k-partite graph G is a collection of vertex-disjoint copies of Ck in G such that each copy of Ck contains exactly one vertex from each vertex class, and such that every vertex of G belongs to some copy of Ck.

Let G be a k-partite graph with vertex classes V1 , 
, Vk each of size n. Suppose ÎŽ(G[Vi , Vi+1]) ≄ (1/2 \add 1/2k)n for each i in [k-1] and ÎŽ(G[V1 , Vk]) ≄ (1/2 \add 1/2k)n. We show that when k is even and n is sufficiently large, G contains a transversal Ck-factor. This resolves independent conjectures of Häggkvist and Fischer in the case when k is even. Furthermore, we show that when k is odd and n is sufficiently large, either G contains a transversal Ck-factor, or G is ‘close to’ being extremal.

This is joint work with Richard Mycroft.

Odd distances in colourings of the plane

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integral distance from each other.

Counting vertices of integral polytopes defined by facets

I’ll address the computational complexity of counting vertices of an integral polytope defined by a system of linear inequalities. The focus will be on polytopes with small integer vertices, particularly 0/1 and half-integral polytopes. The geometric approach to combinatorial optimisation, as explored in Schrijver’s 3-volume monograph, provides plentiful examples of these. The complexity of exact counting is pretty well understood, so I’ll concentrate on approximate counting with guaranteed error bounds. The complexity landscape is only partially understood, but there appear to be natural examples that are neither in P nor NP-hard. No knowledge of complexity theory beyond P and NP will be assumed.

This is joint work with Heng Guo (Edinburgh)

Matroid valuations and where to see them

Valuativity is a set of equations that a function on matroids may satisfy, of similar flavour to (in fact more general than) having a deletion-contraction recurrence. The condition arises from the polyhedral perspective on matroids introduced by Edmonds, but turns up in several other algebraic and geometric perspectives on matroid theory, such as combinatorial Hopf algebras, and the matroid Chow rings central to June Huh’s Fields medal work. I’ll give a survey of these connections and some of my work in the area.

No seminar

Abstract not available

Tight Lower Bounds for Parameterized Algorithms under ETH

Parameterized (time) complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we analyze the running time with respect to additional parameters. This approach has proven to be highly successful in delineating our understanding of NP-hard problems.

Recently, the Exponential Time Hypothesis (ETH) has proven to be quite useful in showing (almost) tight lower bounds on the running time of parameterized algorithms for several problems. In this talk, I will give a survey of these lower bounds (including a few of my results) and conclude with an open problem.

Structured Decompositions: recursive data and recursive algorithms

What is recursive structure? And how can we exploit it algorithmically?  In this talk I will give as general an answer as I can to these questions by calling upon the new notion of structured decompositions. This is a category-theoretic formalism that Jade Master, Zoltan Kocsis and I recently introduced which yields a vast generalisation of tree-width to arbitrary categories. I will explain — assuming no prior knowledge at all of category theory — how to make use of structured decompositions for three purposes: (1) defining new tree-width-like invariants, (2) relating these decompositions to each-other via functors and (3) how one might go about proving algorithmic meta-theorems using the language of category theory.  This is ongoing, multidisciplinary work. As such it requires lots people with different types of expertise, so you should consider this talk is an invitation to get involved! 

Uncommon systems of equations

A system of linear equations $L$ over $\mathbb{F}_q$ is \emph{common} if the number of monochromatic solutions to $L$ in any two-colouring of $\mathbb{F}_qn$ is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of $\mathbb{F}_qn$. Motivated by existing results for specific systems (such as Schur triples and arithmetic progressions), as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Building on earlier work of of Cameron, Cilleruelo and Serra, as well as Saad and Wolf, common linear equations have been fully characterised by Fox, Pham and Zhao.

In this talk I will discuss some recent progress towards a characterisation of common systems of two or more equations. In particular we prove that any system containing an arithmetic progression of length four is uncommon, confirming a conjecture of Saad and Wolf. This follows from a more general result which allows us to deduce the uncommonness of a general system from certain properties of one- or two-equation subsystems.

Heawood's theorem in 3D

We prove an analogue of Heawood’s theorem in 3D and conjectures about how this might extend to higher dimensions are proposed.

Antidirected subgraphs of oriented graphs

For simple connected graphs, minimum degree at least k/2 guarantees having the k-path as a subgraph, if the graph has at least k+1 vertices. For oriented graphs, Stein conjectured that minimum semidegree greater than k/2 should be enough to have every oriented path of length k. We prove that this is asymptotically true for large antidirected paths in large graphs. Even more, the result is true for large antidirected trees that are balanced and of bounded maximum degree under the same condition on the minimum semidegree. We also prove a similar result for antisubdivisions of a sufficiently small complete graph, which implies having the k-edge antidirected cycle.

Lastly, we address a conjecture by Addario-Berry, Havet, Linhares Sales, Reed and Thomassé about edge density on digraphs and antidirected trees. We show that this conjecture is asymptotically true for oriented graphs with n vertices and all balanced antidirected trees of bounded maximum degree and of size linear in n.

Monochromatic Sums and Products over the Rationals

Hindman’s Theorem states that whenever the natural numbers are finitely coloured there exists an infinite sequence all of those finite sums are the same colour. By considering just powers of 2, this immediately implies the corresponding result for products: whenever the naturals are finitely coloured there exists a sequence all of whose products are the same colour.

But what happens if we ask for both the sums and the products to all have the same colour? It turns out that this is not true: it has been known since the 1970s that there is a finite colouring of the naturals for which no infinite sequence has the set of all of its sums and products monochromatic.

In this talk we will investigate what happens to this question if we move from the naturals to a larger space such as the dyadic rationals, the rationals, or even the reals.

Joint work with Neil Hindman and Imre Leader.

Perfect matchings in random sparsifications of Dirac hypergraphs

We show that, for k >= 3 and n divisible by k, if a k-uniform hypergraph H on n vertices has large enough minimum (k-1)-degree to guarantee a perfect matching, then asymptotically almost surely a p-random subhypergraph of H also contains a perfect matching, provided that p > C log n / n^{k-1}. Our result strengthens Johansson, Kahn, and Vu’s seminal solution to Shamir’s problem and can be viewed as a ‘robust’ version of a hypergraph Dirac-type result by Rödl, RuciƄski, and SzemerĂ©di.

Lower Bounds for Exact and Approximate k-Disjoint-Shortest-Paths

Given a graph G and a set T = {(s_i, t_i) : 1 ≀ i ≀ k} of k pairs, the k-Vertex-Disjoint-Paths (resp. k-Edge-Disjoint-Paths) problem asks to determine whether there exist pairwise vertex-disjoint (resp. edge-disjoint) paths P_1, P_2, ... , P_k in G such that, for each 1 ≀ i ≀ k, P_i connects s_i to t_i. Both the edge-disjoint and vertex-disjoint versions in undirected graphs are famously known to be FPT (parameterized by k) due to the Graph Minor Theory of Robertson and Seymour.

Eilam-Tzoreff [DAM ’98] introduced a variant, known as the k-Disjoint-Shortest-Paths problem, where the individual paths are further required to be shortest paths connecting each pair. They showed that the k-Disjoint-Shortest-Paths problem is NP-complete on both directed and undirected graphs, even when they are planar and have unit edge lengths.

There are four versions of the k-Disjoint-Shortest-Paths problem, depending on whether we require edge-disjointness or vertex-disjointness and if the input graph is directed or undirected. Building on the reduction of Chitnis [CIAC ’21] for k-Edge-Disjoint-Paths on planar DAGs, we obtain the following two types of lower bounds for each of the aforementioned four versions of k-Disjoint-Shortest-Paths on graphs with n vertices:

‱ Exact lower bound: Under the Exponential Time Hypothesis (ETH), there is no computable function f such that there is an exact algorithm running in f(k) n) time.

‱ Approximation lower bound: Under the gap version of the Exact Exponential Hypothesis (Gap-ETH), there exist constants Ï”, ÎŽ > 0 such that for any computable function f there is no (1/2+Ï”)-approximation in f(k) n(ÎŽk) time.

For each of the four versions of k-Disjoint-Shortest-Paths, we are able to further strengthen our results by restricting the structure of the input graphs in the lower bound constructions as follows:

‱ Directed edge-disjoint: The two lower bounds hold even if the input graph is a planar DAG with max in-degree and max out-degree at most 2.

‱ Directed vertex-disjoint: The two lower bounds hold even if the input graph is a 1-planar DAG with max in-degree and max out-degree at most 2.

‱ Undirected edge-disjoint: The two lower bounds hold even if the input graph is planar and has max degree 4.

‱ Undirected vertex-disjoint: The two lower bounds hold even if the input graph is 1-planar and has max degree 4.

We understand these are the first FPT (in)approximability results for any variant of the k-Disjoint-Paths problem, on directed or undirected graphs. Our exact lower bounds show that the n^(O(k))-time algorithms of Berczi and Kobayashi [ESA ’17] for the vertex-disjoint version on planar directed graphs and edge-disjoint version on undirected planar graphs are asymptotically optimal. The inapproximability results are tight for our specific reductions because in all our instances of Disjoint-Shortest-Paths it is trivially possible to satisfy half the pairs.

Maximum Coverage in Sublinear Space, Faster

Given a collection of m sets from a universe U, the Maximum Set Coverage problem consists of finding k sets whose union has largest cardinality. This problem is NP-Hard, but the solution can be approximated by a polynomial time algorithm up to a factor 1−1/e. However, this algorithm does not scale well with the input size. In a streaming context, practical high-quality solutions are found, but with space complexity that scales linearly with respect to the size of the universe |U|. However, one randomized streaming algorithm has been shown to produce a 1−1/e−Δ approximation of the optimal solution with a space complexity that scales only poly-logarithmically with respect to m and |U|. In order to achieve such a low space complexity, the authors used a technique called subsampling, based on independent-wise hash functions. This article focuses on this sublinear-space algorithm and introduces methods to reduce the time cost of subsampling. We first show how to accelerate by several orders of magnitude without altering the space complexity, number of passes and approximation quality of the original algorithm. Secondly, we derive a new lower bound for the probability of producing a 1−1/e−Δ approximation using only pairwise independence: 1 − 4/(ck log m) compared to the original 1−2e/m^(ck/6). Although the theoretical approximation guarantees are weaker, for large streams, our algorithm performs well in practice and present the best time-space-performance trade-off for maximum coverage in streams.

Reconstructing 3D cube complexes from boundary distances

Given a quadrangulation of a disc, suppose we know all the pairwise distances (measured by the graph metric) between vertices on the boundary of the disc. Somewhat surprisingly, a result of Haslegrave states that this is enough information to recover the whole interior structure of the quadrangulation provided all internal vertex degrees are at least 4. In this talk, we look at a generalisation of this result to 3 dimensions. We show that it is possible to reconstruct cube complexes that are homeomorphic to a ball from the pairwise distances between all points on the boundary sphere as long as a certain curvature condition holds. We’ll also discuss some plausible variants that turn out to be false, and generalisations that should be true. This is joint work with Haslegrave, Scott and Tamitegama.

Covering real grids with multiplicity

Given a field $\mathbb{F}$, finite subsets $S_1,\dots,S_d\subseteq \mathbb{F}$, and a point $\vec{p}\in S_1\times \dots\times S_d$, what is the smallest number of hyperplanes needed to cover all points of $S_1\times\dots\times S_d\setminus\{\vec{p}\}\subseteq \mathbb{F}d$ while omitting $\vec{p}$? This question was answered precisely in a celebrated paper of Alon and F\”uredi.

We will discuss a variant of this problem in which every point in $S_1\times\dots\times S_d\setminus\{\vec{p}\}$ must be covered \emph{at least $k\geq 1$ times}, while the remaining point $\vec{p}$ is again left uncovered. In contrast to the case $k=1$, this problem is generally not well understood for larger $k$. Recently Clifton and Huang and Sauermann and Wigderson investigated the special case where $\mathbb{F} = \mathbb{R}$ and the grid is $\{0,1\}d$. A natural next step is to consider larger grids over the reals. In this talk, we will focus on the two-dimensional setting and determine the answer for several different types of grids.

This is joint work with Anurag Bishnoi, Shagnik Das, and Yvonne den Bakker.

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