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.

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 wheelchair accessable, and 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. 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 (Amsterdam)

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

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.

Jakub Opršal - Homotopy theory of complexity of constraints

TBC

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.

Organisers

John Sylvester

Linglong Yuan

Viktor Zamaraev

Supported by