This project is funded by a New Investigotor Award from the Engineering and Physical Sciences Research Council, part of UK Research and Innovation, grant ref. EP/X030989/1.
Duration: October 2023 - September 2026
Hosted by: Department of Mathematics, London School of Economics and Political Science
Principal Investigator: Ahmad Abdi
The aims of the project are to tackle two important and intimately linked unsolved problems in Combinatorial Optimisation, each conjecturing a min-max relation.
The first of these is known as Woodall's Conjecture (Woodall 1978). One can think of a digraph as a network of one-way roads in a city; it is strongly connected if one can drive from any location to any other one. To guarantee this requirement, the council may enable two-way traffic in certain roads, but would like to do so on the fewest possible roads. After this optimisation problem was addressed in an influential min-max theorem by Lucchesi and Younger (1978), Woodall proposed the natural "dual" variant. It conjectures that in any digraph, the minimum size of a dijoin is equal to the maximum number of disjoint dicuts. The conjecture remains unresolved despite significant interest, and efforts to tackle it have led to some crucial developments in the broader area.
The second unsolved problem is the Generalised Berge-Fulkerson Conjecture (GBFC), posed by Seymour in 1979. The origins of the conjecture come from the famous Four-Colour Problem: Given a map of regions, known formally as a planar graph, are four colours sufficient to colour the regions such that any two regions sharing a border are assigned different colours? After this question was answered affirmatively (Appel and Haken 1977), GBFC arose as a natural extension to all graphs. Vaguely speaking, the conjecture states that in an r-graph, twice the minimum degree is equal to the maximum number of perfect matchings such that every edge is used exactly twice. The study of this conjecture has shaped the topic of Matching Theory (see Lovasz 1987), important in the subject area of Graph Theory. The conjecture is also intimately linked to the Chinese Postman Problem and the famous Travelling Salesman Problem.
The following recent papers serve as starting points: