Freddie Illingworth

Asymptotic dimension of graphs excluding an induced or fat minor

Robert Hickingbotham, Freddie Illingworth, Piotr Micek +1

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed gra…

Hypergraphs with the smallest Hall ratio are still hard to colour

Veronica Bitonti, Freddie Illingworth, Pedram Noohi +1

For $H$ a hypergraph, the Hall ratio $ρ (H) = max_{X \subseteq V (H)} \frac{∣ X ∣}{α ( H [ X ])}$ is a natural lower bound for its chromatic number, and among non-empty $k$ -u…

Disproof of the dominating Hadwiger conjecture

Freddie Illingworth, Raphael Steiner

Hadwiger's conjecture (1943) states that every graph $G$ with chromatic number at least $t$ contains a $K_{t}$ -model: a collection of $t$ vertex-disjoint connected subgraphs $T_1,\do…

Countable Graphs with Finite Path-width: Characterisation and Universality

Tony Huynh, Freddie Illingworth, Nikolai Karol +4

We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs t…

Disproof of the tree product conjecture via the Heisenberg group

Freddie Illingworth, Sergey Norin, Raphael Steiner

Product structure theory aims to understand complex graphs by embedding them into products of simpler graphs. In this direction, Campbell, Distel, Gollin, Harvey, Hendrey, Hickingb…

The Dominating 4-Colour Theorem

António Girão, Freddie Illingworth, Bojan Mohar +6

A "dominating $K_{t}$ -model" in a graph $G$ is a sequence $(T_{1}, \dots, T_{t})$ of pairwise vertex-disjoint connected subgraphs of $G$ , such that whenever $1 \leq i < j \leq t$ every vertex…

math.CO2025

Relative Turán densities for ordered graphs: all and nothing

Freddie Illingworth, Arjun Ranganathan, Leo Versteegen +1

Reiher, Rödl, Sales, and Schacht initiated the study of relative Turán densities of ordered graphs and showed that it is more subtle and interesting than the unordered case. For an…

math.CO2025

Treedepth and 2-treedepth in graphs with no long induced paths

Jędrzej Hodor, Freddie Illingworth, Tomasz Mazur

Huynh, Joret, Micek, Seweryn, and Wollan (Combinatorica, 2022) introduced a graph parameter, later referred to as 2-treedepth and denoted $td_{2} (\cdot)$ . The parameter is t…

The Zarankiewicz problem on tripartite graphs

Francesco Di Braccio, Freddie Illingworth

In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest $τ$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + τ$ must contain $K_{t, t, t}$ , conje…

Exponential odd-distance sets under the Manhattan metric

Alberto Espuny Díaz, Emma Hogan, Freddie Illingworth +3

We construct a set of $2^{n}$ points in $R^{n}$ such that all pairwise Manhattan distances are odd integers, which improves the recent linear lower bound of Golovanov, Kupavsk…

Spanning spheres in Dirac hypergraphs

Freddie Illingworth, Richard Lang, Alp Müyesser +2

We show that a $k$ -uniform hypergraph on $n$ vertices has a spanning subgraph homeomorphic to the $(k - 1)$ -dimensional sphere provided that $H$ has no isolated vertices and each s…

When $t$ -intersecting hypergraphs admit bounded $c$ -strong colourings

Kevin Hendrey, Freddie Illingworth, Nina Kamčev +1

The $c$ -strong chromatic number of a hypergraph is the smallest number of colours needed to colour its vertices so that every edge sees at least $c$ colours or is rainbow. We show…

Dominating $K_{t}$ -Models

Freddie Illingworth, David R. Wood

A $\textit{dominating $K_t$-model}$ in a graph $G$ is a sequence $(T_{1}, \dots, T_{t})$ of pairwise disjoint non-empty connected subgraphs of $G$ , such that for $1 \leqslant i<j \leqsla…

Fat minors cannot be thinned (by quasi-isometries)

James Davies, Robert Hickingbotham, Freddie Illingworth +1

We disprove the conjecture of Georgakopoulos and Papasoglu that a length space (or graph) with no $K$ -fat $H$ minor is quasi-isometric to a graph with no $H$ minor. Our counterexam…

Non-Homotopic Drawings of Multigraphs

António Girão, Freddie Illingworth, Alex Scott +1

A multigraph drawn in the plane is non-homotopic if no two edges connecting the same pair of vertices can be continuously deformed into each other without passing through a vertex,…

Abundance: Asymmetric Graph Removal Lemmas and Integer Solutions to Linear Equations

António Girão, Eoin Hurley, Freddie Illingworth +1

We prove that a large family of pairs of graphs satisfy a polynomial dependence in asymmetric graph removal lemmas. In particular, we give an unexpected answer to a question of Gis…

Flashes and rainbows in tournaments

António Girão, Freddie Illingworth, Lukas Michel +2

Colour the edges of the complete graph with vertex set ${1, 2, \dots, n}$ with an arbitrary number of colours. What is the smallest integer $f (l, k)$ such that if $n > f (l, k)$ th…

Chromatic number is not tournament-local

António Girão, Kevin Hendrey, Freddie Illingworth +4

Scott and Seymour conjectured the existence of a function $f : N \to N$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $χ(G) \geqs…

The structure and density of $k$ -product-free sets in the free semigroup

Freddie Illingworth, Lukas Michel, Alex Scott

The free semigroup $F$ over a finite alphabet $A$ is the set of all finite words with letters from $A$ equipped with the operation of concatenation. A…

On tree decompositions whose trees are minors

Pablo Blanco, Linda Cook, Meike Hatzel +3

In 2019, Dvořák asked whether every connected graph $G$ has a tree decomposition $(T, B)$ so that $T$ is a subgraph of $G$ and the width of $(T, B)$ is bounded…