Liverpool Discrete Mathematics Colloquium

About

This two day Colloquium aims to bring together researchers in discrete mathematics, from areas such as structural and algorithmic graph theory, extremal combinatorics, logic and foundations of Computer Science.

There is a four-hour tutorial on Constraint Satisfaction Problems given by Andrei Krokhin (Durham), nine invited talks, and a session with contributed one slide pitches by junior researchers.

Conference Photo (from day 2)

Venue

All talks will be held in the Ashton Lecture Room which is on the First floor of the Ashton Building, The University of Liverpool, Brownlow Street, Liverpool, L3 3GJ

The venue is a 15 minute walk from Liverpool Lime street (main train station).

Catering

There are tea/coffee breaks provided. Lunches are not provided, however there is the University of Liverpool refectory and plenty of local cafes and restaurants nearby.

There will be a conference dinner on the evening of the first day at Bistro Franc at 7pm. All participants are welcome to attend, however non-speaking participants will have to cover the cost of their own meal.

Funding for Students

We urge all students to keep receipts for expenses as we may be able to refund some expenses after the conference.

Registration

Attendance at the Liverpool Discrete Mathematics Colloquium is free of charge. However, registration is required (deadline 25th August 2025) to help us with logisics, and to ensure adequate arrangements for the coffee/tea breaks.

Click here for Registration Form

Speakers

Candida Bowtell (Birmingham)

Linda Cook (Utrecht)

Jan Dreier (TU Wien)

Maximilien Gadouleau (Durham)

Jakub Opršal (Birmingham)

Karolina Okrasa (Oxford)

Sebastian Ordyniak (Leeds)

Katherine Staden (Open)

Standa Živný (Oxford)

Tutorial Speaker

Andrei Krokhin (Durham)

Schedule (TBC)

Talk Abstracts

Candida Bowtell - Decomposing Latin squares into transversals

A Latin square of order $n$ is an $n \times n$ grid filled with $n$ symbols such that each symbol appears exactly once in each row and column. A transversal in a Latin square of order $n$ is a collection of $n$ cells such that each row, column and symbol appears exactly once in the collection.

Latin squares were introduced by Euler in the 1700s and he was interested in the question of when a Latin square decomposes fully into transversals. In this talk we'll discuss some of the history of this question, including some recent joint work with Richard Montgomery.

Linda Cook -200,000 colors suffice for t-perfect graphs

Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities. In 1975, V. Chvátal defined an analogous class called t-perfect graphs, which are the graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. We show that t-perfect graphs are 200,000-colourable. This is the first finite bound on the chromatic number of t-perfect graphs, and answers a question of B. Shepherd from 1995.

This bound is probably not tight; M. Laurent and P. Seymour gave an example of a t-perfect graph requiring four colors in the 1990's and it is open whether all t-perfect graphs are 4-colorable. Our proof is mainly graph theoretic and uses techniques developed in the context of ``$\chi$-boundedness''. In this talk we discuss this result and related open problems.

This is joint work with Maria Chudnovsky, James Davies, Sang-il Oum, and Jane Tan.

Jan Dreier - The algorithmic and combinatorial nature of monadic dependence and merge-width

An active line of research tries to exactly characterize what kinds of graphs admit near-linear time algorithms for finding constant-size independent sets, dominating sets, cliques, subgraphs, etc. -- or, more precisely, which graph classes admit fpt first-order model checking. To understand these algorithmic dividing lines, we must first study combinatorial dividing lines: Duality theorems that characterize certain kinds of graphs both constructively (via decompositions) and restrictively (via forbidden subgraphs). This talk reviews recent developments, and introduces key concepts such as monadic dependence (NIP), monadic stability, and the very recent notion of merge-width.

Maximilien Gadouleau - Maximal Independent Sets and Boolean Networks

A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neighbours are already in the set. In this talk, we consider (the complexity of decision problems related to) the generalisation of this MIS algorithm wherein any starting set is allowed. Two main approaches are leveraged. Firstly, we view the MIS algorithm as a sequential update of a Boolean network according to a permutation of the vertex set. Secondly, we introduce the concept of a constituency of a graph: a set of vertices that is dominated by an independent set. Recognizing a constituency is NP-complete, a fact we leverage repeatedly in our investigation. We will show that fixing words (which reach a MIS from any starting configuration) and fixing permutations (briefly, permises) are coNP-complete to recognize; and that permissible graphs (graphs with a permis) are coNP-hard to recognize. If time permits, we shall give an overview of related results in that area, and close with some open problems.

Andrei Krokhin - Introduction to the theory of constraint satisfaction

I will explain what constraint satisfaction problems (CSPs) are and why they are studied so much in Theoretical Computer Science. I will also present the basics of the mathematical theory of CSPs that has been very successful in classifying the computational complexity of CSPs.

Karolina Okrasa - Dissimilar CSP: when having one solution is just not enough

Consider a variant of the constraint satisfaction problem in which we ask whether there exist two solutions that are equal on at most $p$ variables. While for some of the classic CSPs, like $k$-Colouring, this variant is trivially equivalent to the original problem, in general it turns out to be a surprisingly rich framework, covering e.g., Odd Cycle Transversal and a variety of MinCut problems.

During the talk, I will show what we know about the parameterized complexity of Dissimilar CSP in the two most natural cases, one being CSPs on Boolean domain and the other one being the graph homomorphism problem.

This is based on a joint work with Tamio-Vesa Nakajima, George Osipov and Standa Živný.

Jakub Opršal - A topological proof of the $H$-colouring dichotomy

A colouring of a graph with $k$ colours is an assignment of colours to vertices so that no edge is monochromatic. As it is well-known colouring with 2 colours is in P while colouring with $k > 2$ colours is NP-complete. This dichotomy was extended to the *graph homomorphism problem*, also called $H$-colouring, by Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990]. More precisely, they proved that deciding whether there is a graph homomorphism from a given graph to a fixed graph $H$ is in P if $H$ is bipartite (or contains a self-loop), and is NP-complete otherwise. This dichotomy served as an important test-case for the Feder–Vardi dichotomy conjecture, and Bulatov–Zhuk dichotomy of complexity of finite-template CSPs.

In the talk, I will present a new proof of this theorem using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319-324, 1978] and Brower’s fixed-point theorem. This is joint work with Sebastian Meyer (TU Dresden).

Sebastian Ordyniak - Almost Consistent Systems of Linear Equations

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains---a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests.

Katherine Staden - The semi-inducibility problem

Let $H$ be a $k$-edge-coloured graph and let $n$ be a positive integer. What is the maximum number of copies of $H$ in a $k$-edge-coloured complete graph on $n$ vertices? I will discuss the case $k=2$, which we call the semi-inducibility problem. This problem is a generalisation of the inducibility problem of Pippenger and Golumbic which is solved only for some small graphs and limited families of graphs.

I will introduce some new results in joint work with Abdul Basit, Bertille Granet, Daniel Horsley and André Kündgen.

Standa Živný - On Approximating Colourings

I will present a recent result on approximating linearly-ordered colourings of 3-uniform hypergraphs. Along the way, I shall introduce a new notion of sparsification that may be of independent interest, and show that 1-in-3-SAT admits a non-trivial sparsification.

Based on joint work with B. Bedert, T.-V. Nakajima, and K. Okrasa, to appear in FOCS'25.

Organisers

John Sylvester

Linglong Yuan

Viktor Zamaraev

Supported by