Alex Scott

Induced subgraphs of induced subgraphs of large chromatic number

AntÃ³nio GirÃ£o, Freddie Illingworth, Emil Powierski +4

We prove that, for every graph $F$ with at least one edge, there is a constant $c_{F}$ such that there are graphs of arbitrarily large chromatic number and the same clique number as…

A note on simplicial cliques

Maria Chudnovsky, Alex Scott, Paul Seymour +1

Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is…

Pure pairs. IV. Trees in bipartite graphs

Alex Scott, Paul Seymour, Sophie Spirkl

In this paper we investigate the bipartite analogue of the strong Erdos-Hajnal property. We prove that for every forest $H$ and every $I ¨ > 0$ there exists $I^µ > 0$ , such that if $G$ h…

Pure pairs. V. Excluding some long subdivision

Alex Scott, Paul Seymour, Sophie Spirkl

A pure pair in a graph $G$ is a pair $A, B$ of disjoint subsets of $V (G)$ such that $A$ is complete or anticomplete to $B$ . Jacob Fox showed that for all $I^µ > 0$ , there is a comparab…

Reconstruction from smaller cards

Carla Groenland, Tom Johnston, Alex Scott +1

The $ℓ$ -deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $ℓ$ vertices. We say that a graph is reconstructible from its $ℓ$ -deck if no other graph has…

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes

Alex Scott, Paul Seymour

A hole in a graph is an induced subgraph which is a cycle of length at least four. We prove that for every positive integer k, every triangle-free graph with sufficiently large chr…

Colour-balanced subgraphs

Emma Hogan, Alex Scott, Dmitry Tsarev

A $k$ -edge-coloured graph is colour-balanced if each colour appears equally often. Resolving a conjecture of Pardey and Rautenbach, we show that any colour-balanced $k$ -edge-colour…

Induced subgraphs of graphs with large chromatic number. XIII. New brooms

Alex Scott, Paul Seymour

GyÃ¡rfÃ¡s and Sumner independently conjectured that for every tree $T$ , the class of graphs not containing $T$ as an induced subgraph is $I ¨ $ -bounded, that is, the chromatic number…

#erdos-posa property#long cycles#distance constraints#graph separators

Far-apart ErdÅs--PÃ³sa property of long cycles

Maria Chudnovsky, Vida DujmoviÄ, GwenaÃ«l Joret +4

The authors prove that for any graph, either it contains many cycles of length at least ℓ that are pairwise far apart, or a small vertex set can be removed to eliminate all such lo…

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…

Product structure of graphs with an excluded minor

Freddie Illingworth, Alex Scott, David R. Wood

This paper shows that $K_{t}$ -minor-free (and $K_{s, t}$ -minor-free) graphs $G$ are subgraphs of products of a tree-like graph $H$ (of bounded treewidth) and a complete graph $K_{m}$ .…

Induced subgraphs of graphs with large chromatic number. XI. Orientations

Maria Chudnovsky, Alex Scott, Paul Seymour

Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomor…

Induced $C_{4}$ -free subgraphs with large average degree

Xiying Du, AntÃ³nio GirÃ£o, Zach Hunter +2

We prove that there exists a constant $C$ so that, for all $s, k \in N$ , if $G$ has average degree at least $k^{C s^{3}}$ and does not contain $K_{s, s}$ as a subgraph then it…

Induced subgraph density. IV. New graphs with the ErdÅs-Hajnal property

Tung Nguyen, Alex Scott, Paul Seymour

ErdÅs and Hajnal conjectured that for every graph $H$ , there exists $c > 0$ such that every $H$ -free graph $G$ has a clique or a stable set of size at least $∣ G ∣^{c}$ (a graph is $H$ -…

Combinatorics in the exterior algebra and the BollobÃ¡s Two Families Theorem

Alex Scott, Elizabeth Wilmer

We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hy…

The component structure of dense random subgraphs of the hypercube

Colin McDiarmid, Alex Scott, Paul Withers

Given $p \in (0, 1)$ , we let $Q_{p} = Q_{p}^{d}$ be the random subgraph of the $d$ -dimensional hypercube $Q^{d}$ where edges are present independently with probability $p$ . It is well known…

Towards Erdos-Hajnal for graphs with no 5-hole

Maria Chudnovsky, Jacob Fox, Alex Scott +2

The Erdos-Hajnal conjecture says that for every graph $H$ there exists $c > 0$ such that $max (I^\pm (G), I ¨ (G)) \geq n^{c}$ for every $H$ -free graph $G$ with $n$ vertices, and this is still…

Graphs without a 3-connected subgraph are 4-colorable

Ãdouard Bonnet, Carl Feghali, Tung Nguyen +4

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…

Balancing connected colourings of graphs

Freddie Illingworth, Emil Powierski, Alex Scott +1

We show that the edges of any graph $G$ containing two edge-disjoint spanning trees can be blue/red coloured so that the blue and red graphs are connected and the blue and red degr…

cs.DC2016

Feedback from Nature: Simple Randomised Distributed Algorithms for Maximal Independent Set Selection and Greedy Colouring

Peter Jeavons, Alex Scott, Lei Xu

We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance i…

Induced paths in graphs without anticomplete cycles

Tung Nguyen, Alex Scott, Paul Seymour

Let us say a graph is $s O$ -free, where $s \geq 1$ is an integer, if there do not exist $s$ cycles of the graph that are pairwise vertex-disjoint and have no edges joining t…

Polynomial bounds for chromatic number VII. Disjoint holes

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A hole in a graph $G$ is an induced cycle of length at least four, and a $k$ -multihole in $G$ is a set of pairwise disjoint and nonadjacent holes. It is well known that if $G$ does…

math.CO2015

Induced subgraphs of graphs with large chromatic number. I. Odd holes

Alex Scott, Paul Seymour

An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyarfas made the conjecture that for all t there exists n such that every gr…

Anticoncentration of random spanning trees in graphs with large minimum degree

Veronica Bitonti, Lukas Michel, Alex Scott

A classical result by Otter shows that the complete graph has an exponential number of non-isomorphic spanning trees. This was recently extended by Lee to every almost regular grap…

math.CO2014

Intersections of hypergraphs

BÃ©la BollobÃ¡s, Alex Scott

Given two weighted k-uniform hypergraphs G, H of order n, how much (or little) can we make them overlap by placing them on the same vertex set? If we place them at random, how conc…

math.CO2013

Hypergraphs of bounded disjointness

Alex Scott, Elizabeth Wilmer

A $k$ -uniform hypergraph is $s$ -almost intersecting if every edge is disjoint from exactly $s$ other edges. Gerbner, Lemons, Palmer, PatkÃ³s and SzÃ©csi conjectured that for every…

math.CO2017

Maximising the number of induced cycles in a graph

Natasha Morrison, Alex Scott

We determine the maximum number of induced cycles that can be contained in a graph on $n \geq n_{0}$ vertices, and show that there is a unique graph that achieves this maximum. This an…

Pure pairs. I. Trees and linear anticomplete pairs

Maria Chudnovsky, Alex Scott, Paul Seymour +1

The Erdos-Hajnal Conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable s…

Pure pairs. II. Excluding all subdivisions of a graph

Maria Chudnovsky, Alex Scott, Paul Seymour +1

We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G…

Induced subgraph density. VII. The five-vertex path

Tung Nguyen, Alex Scott, Paul Seymour

We prove the ErdÅs-Hajnal conjecture for the five-vertex path $P_{5}$ ; that is, there exists $c > 0$ such that every $n$ -vertex graph with no induced $P_{5}$ has a clique or stable set…

Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces

Marthe Bonamy, Nicolas Bousquet, Louis Esperet +4

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric…

Sparse graphs with no polynomial-sized anticomplete pairs

Maria Chudnovsky, Jacob Fox, Alex Scott +2

A graph is " $H$ -free" if it has no induced subgraph isomorphic to $H$ . A conjecture of Conlon, Fox and Sudakov states that for every graph $H$ , there exists $s > 0$ such that in ever…

Induced subgraphs of graphs with large chromatic number. VI. Banana trees

Alex Scott, Paul Seymour

We investigate which graphs H have the property that in every graph with bounded clique number and sufficiently large chromatic number, some induced subgraph is isomorphic to a sub…

Disjoint paths in unions of tournaments

Maria Chudnovsky, Alex Scott, Paul Seymour

Given $k$ pairs of vertices $(s_{i}, t_{i}) (1 \leq i \leq k)$ of a digraph $G$ , how can we test whether there exist vertex-disjoint directed paths from $s_{i}$ to $t_{i}$ for $1 \leq i \leq k$ ? T…

Defective Colouring of Hypergraphs

AntÃ³nio GirÃ£o, Freddie Illingworth, Alex Scott +1

We prove that the vertices of every $(r + 1)$ -uniform hypergraph with maximum degree $I^$ may be coloured with $c (\frac{I ^}{} d + 1)^{1/ r}$ colours such that each vertex is in at most…

Polynomial bounds for chromatic number. II. Excluding a star-forest

Alex Scott, Paul Seymour, Sophie Spirkl

The Gyarfas-Sumner conjecture says that for every forest $H$ , there is a function $f$ such that if $G$ is $H$ -free then $I ¨ (G) \leq f (I ¨ (G))$ (where $I ¨ , I ¨ $ are the chromatic number…

Proof of the Kalai-Meshulam conjecture

Maria Chudnovsky, Alex Scott, Paul Seymour +1

Let $G$ be a graph, and let $f_{G}$ be the sum of $(- 1)^{∣ A ∣}$ , over all stable sets $A$ . If $G$ is a cycle with length divisible by three, then $f_{G} = \pm 2$ . Motivated by topologica…

Strengthening Rodl's theorem

Maria Chudnovsky, Alex Scott, Paul Seymour +1

What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very d…

math.CO2012

Cover-Decomposition and Polychromatic Numbers

BÃ©la BollobÃ¡s, David Pritchard, Thomas RothvoÃ +1

A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in…

Monochromatic Components in Edge-Coloured Graphs with Large Minimum Degree

Hannah Guggiari, Alex Scott

For every $n \in N$ and $k \geq 2$ , it is known that every $k$ -edge-colouring of the complete graph on $n$ vertices contains a monochromatic connected component of order at le…

math.OC2016

Uniform multicommodity flow in the hypercube with random edge capacities

Colin McDiarmid, Alex Scott, Paul Withers

We give two results for multicommodity flows in the $d$ -dimensional hypercube $Q^{d}$ with independent random edge capacities distributed like $C$ where $Pr [C > 0] > 1/2$ . Firstly, wi…

Detecting a long odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour

For each integer $t \geq 5$ , we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $t$ and odd.

math.CO2015

Saturation in the Hypercube and Bootstrap Percolation

Natasha Morrison, Jonathan A. Noel, Alex Scott

Let $Q_{d}$ denote the hypercube of dimension $d$ . Given $d \geq m$ , a spanning subgraph $G$ of $Q_{d}$ is said to be $(Q_{d}, Q_{m})$ -saturated if it does not contain $Q_{m}$ as a subgraph bu…

econ.TH2026

Game Connectivity and Adaptive Dynamics

Tom Johnston, Michael Savery, Alex Scott +1

We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that, among games that are `generic' (with…

Exact stability for TurÃ¡n's Theorem

DÃ¡niel KorÃ¡ndi, Alexander Roberts, Alex Scott

TurÃ¡n's Theorem says that an extremal $K_{r + 1}$ -free graph is $r$ -partite. The Stability Theorem of ErdÅs and Simonovits shows that if a $K_{r + 1}$ -free graph with $n$ vertices ha…

Separation Dimension and Degree

Alex Scott, David R. Wood

The "separation dimension" of a graph $G$ is the minimum positive integer $d$ for which there is an embedding of $G$ into $R^{d}$ , such that every pair of disjoint edges are…

math.CO2013

Excluding Pairs of Graphs

Maria Chudnovsky, Alex Scott, Paul Seymour

For a graph $G$ and a set of graphs $H$ , we say that $G$ is {\em $H$ -free} if no induced subgraph of $G$ is isomorphic to a member of $H$ . Given an in…

Pure pairs. IX. Transversal trees

Alex Scott, Paul Seymour, Sophie Spirkl

Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this part…

Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree

Alex Scott, Paul Seymour, Sophie Spirkl

Let H be a tree. It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph $K_{t, t}$ as a subgraph, have bound…

cs.DS2021

Active clustering for labeling training data

Quentin Lutz, Ãlie de Panafieu, Alex Scott +1

Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality of the training data has a…

Pure pairs. VI. Excluding an ordered tree

Alex Scott, Paul Seymour, Sophie Spirkl

A pure pair in a graph $G$ is a pair $(Z_{1}, Z_{2})$ of disjoint sets of vertices such that either every vertex in $Z_{1}$ is adjacent to every vertex in $Z_{2}$ , or there are no edges bet…

How unproportional must a graph be?

Humberto Naves, Oleg Pikhurko, Alex Scott

Let $u_{k} (G, p)$ be the maximum over all $k$ -vertex graphs $F$ of by how much the number of induced copies of $F$ in $G$ differs from its expectation in the binomial random graph wit…

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

Alex Scott, Paul Seymour, Sophie Spirkl

For integer $n > 0$ , let $f (n)$ be the number of rows of the largest all-0 or all-1 square submatrix of $M$ , minimized over all $n \times n$ $0/1$ -matrices $M$ . Thus $f (n) = O (lo g n)$ …

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…

A universal exponent for homeomorphs

Peter Keevash, Jason Long, Bhargav Narayanan +1

We prove a uniform bound on the topological TurÃ¡n number of an arbitrary two-dimensional simplicial complex $S$ : any $n$ -vertex two-dimensional complex with at least $C_S n^{3-1/5…

math.CO2014

Disjoint dijoins

Maria Chudnovsky, Katherine Edwards, Ringi Kim +2

A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then…

Trees and near-linear stable sets

Tung Nguyen, Alex Scott, Paul Seymour

When $H$ is a forest, the GyÃ¡rfÃ¡s-Sumner conjecture implies that every graph $G$ with no induced subgraph isomorphic to $H$ and with bounded clique number has a stable set of lin…

math.CO2016

Disjoint induced subgraphs of the same order and size

BÃ©la BollobÃ¡s, Teeradej Kittipassorn, Bhargav Narayanan +1

For a graph $G$ , let $f (G)$ be the largest integer $k$ for which there exist two vertex-disjoint induced subgraphs of $G$ each on $k$ vertices, both inducing the same number of edg…

math.PR2018

Balancing sums of random vectors

Juhan Aru, Bhargav Narayanan, Alex Scott +1

We study a higher-dimensional 'balls-into-bins' problem. An infinite sequence of i.i.d. random vectors is revealed to us one vector at a time, and we are required to partition thes…

cs.DC2012

Feedback from nature: an optimal distributed algorithm for maximal independent set selection

Alex Scott, Peter Jeavons, Lei Xu

Maximal Independent Set selection is a fundamental problem in distributed computing. A novel probabilistic algorithm for this problem has recently been proposed by Afek et al, insp…

Shotgun assembly of random graphs

Tom Johnston, Gal Kronenberg, Alexander Roberts +1

In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the E…

Moderate deviations of subgraph counts in the ErdÅs-RÃ©nyi random graphs $G (n, m)$ and $G (n, p)$

Christina Goldschmidt, Simon Griffiths, Alex Scott

The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the ErdÅs-RÃ©nyi random graph $G (n, m)$ . Ou…

Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue

Alex Scott, Paul Seymour

A large body of research in graph theory concerns the induced subgraphs of graphs with large chromatic number, and especially which induced cycles must occur. In this paper, we uni…

Induced subgraph density. I. A loglog step towards Erdos-Hajnal

Matija BuciÄ, Tung Nguyen, Alex Scott +1

In 1977, ErdÅs and Hajnal made the conjecture that, for every graph $H$ , there exists $c > 0$ such that every $H$ -free graph $G$ has a clique or stable set of size at least $∣ G ∣^{c}$ ;…

Stability results for graphs with a critical edge

Alexander Roberts, Alex Scott

The classical stability theorem of ErdÅs and Simonovits states that, for any fixed graph with chromatic number $k + 1 \geq 3$ , the following holds: every $n$ -vertex graph that is $H$ …

Some results and problems on tournament structure

Tung Nguyen, Alex Scott, Paul Seymour

This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vert…

Finding a shortest odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour

An odd hole in a graph is a induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time a…

math.PR2021

Parking on the integers

MichaÅ Przykucki, Alexander Roberts, Alex Scott

Models of parking in which cars are placed randomly and then move according to a deterministic rule have been studied since the work of Konheim and Weiss in the 1960s. Recently, Da…

Concatenating bipartite graphs

Maria Chudnovsky, Patrick Hompe, Alex Scott +2

Let $x, y \in (0, 1]$ and let $A, B, C$ be disjoint nonempty subsets of a graph $G$ , where every vertex in $A$ has at least $x ∣ B ∣$ neighbours in $B$ , and every vertex in $B$ has at least…

Decomposing random permutations into order-isomorphic subpermutations

Carla Groenland, Tom Johnston, DÃ¡niel KorÃ¡ndi +3

Two permutations $s$ and $t$ are $k$ -similar if they can be decomposed into subpermutations $s^{1}, \dots, s^{k}$ and $t^{1}, \dots, t^{k}$ such that $s^{i}$ is order-isomorphic to $t^{i}$ f…

Better bounds for poset dimension and boxicity

Alex Scott, David R. Wood

We prove that the dimension of every poset whose comparability graph has maximum degree $I^$ is at most $I^ lo g^{1 + o (1)} I^$ . This result improves on a 30-year old bound of FÃ¼redi…

A multidimensional Ramsey Theorem

AntÃ³nio GirÃ£o, Gal Kronenberg, Alex Scott

Ramsey theory is a central and active branch of combinatorics. Although Ramsey numbers for graphs have been extensively investigated since Ramsey's work in the 1930s, there is stil…

Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph

Alex Scott, Paul Seymour

The GyÃ¡rfÃ¡s-Sumner conjecture says that for every forest $H$ and every integer $k$ , if $G$ is $H$ -free and does not contain a clique on $k$ vertices then it has bounded chromatic…

math.CO2016

On a problem of Erdos and Moser

Bela Bollobas, Alex Scott

A set $A$ of vertices in an $r$ -uniform hypergraph $H$ is covered in $H$ if there is some vertex $u \neq \in A$ such that, for every $(r - 1)$ -set $B \subset A$ , the s…

math.CO2017

Supersaturation in Posets and Applications Involving the Container Method

Jonathan A. Noel, Alex Scott, Benny Sudakov

We consider 'supersaturation' problems in partially ordered sets (posets) of the following form. Given a finite poset $P$ and an integer $m$ greater than the cardinality of the lar…

Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture

Tung Nguyen, Alex Scott, Paul Seymour

Coarse graph theory concerns finding 'coarse' analogues of graph theory theorems, replacing disjointness with being far apart. One of the most interesting open questions is to find…

Infinite induced-saturated graphs

Marthe Bonamy, Carla Groenland, Tom Johnston +2

A graph $G$ is $H$ -induced-saturated if $G$ is $H$ -free but deleting any edge or adding any edge creates an induced copy of $H$ . There are non-trivial graphs $H$ , such as $P_{4}$ , fo…

Induced subgraph density. V. All paths approach Erdos-Hajnal

Tung Nguyen, Alex Scott, Paul Seymour

The ErdÅs-Hajnal conjecture says that, for every graph $H$ , there exists $c > 0$ such that every $H$ -free graph on $n$ vertices has a clique or stable set of size at least $n^{c}$ . In…

Clique covers of H-free graphs

Tung Nguyen, Alex Scott, Paul Seymour +1

It takes $n^{2} /4$ cliques to cover all the edges of a complete bipartite graph $K_{n /2, n /2}$ , but how many cliques does it take to cover all the edges of a graph $G$ if $G$ has no $…

Reconstructing the degree sequence of a sparse graph from a partial deck

Carla Groenland, Tom Johnston, Andrey Kupavskii +3

The deck of a graph $G$ is the multiset of cards ${G - v : v \in V (G)}$ . Myrvold (1992) showed that the degree sequence of a graph on $n \geq 7$ vertices can be reconstructed from any d…

Detecting an odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A hole in a graph G is an induced cycle of length at least four; an antihole is a hole in the complement of G. In 2005, Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic showed tha…

Pure pairs. X. Tournaments and the strong Erdos-Hajnal property

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A pure pair in a tournament $G$ is an ordered pair $(A, B)$ of disjoint subsets of $V (G)$ such that every vertex in $B$ is adjacent from every vertex in $A$ . Which tournaments $H$ h…

Shotgun reconstruction in the hypercube

MichaÅ Przykucki, Alexander Roberts, Alex Scott

Mossel and Ross raised the question of when a random colouring of a graph can be reconstructed from local information, namely the colourings (with multiplicity) of balls of given r…

Erdos-Hajnal for graphs with no 5-hole

Maria Chudnovsky, Alex Scott, Paul Seymour +1

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality a…

Infinite Schnyder Woods

Louigi Addario-Berry, Emma Hogan, Lukas Michel +1

It is well-known that any finite triangulation possesses a unique maximal Schnyder wood. We introduce Schnyder woods of infinite triangulations, and prove there exists a unique max…

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,…

Graphs with arbitrary Ramsey number and connectivity

Isabel Ahme, Alex Scott

The Ramsey number $r (G)$ of a graph $G$ is the minimum number $N$ such that any red-blue colouring of the edges of $K_{N}$ contains a monochromatic copy of $G$ . Pavez-SignÃ©, Piga an…

Subdivisions and near-linear stable sets

Tung Nguyen, Alex Scott, Paul Seymour

We prove that for every complete graph $K_{t}$ , all graphs $G$ with no induced subgraph isomorphic to a subdivision of $K_{t}$ have a stable subset of size at least $|G|/{\rm polylog}|…

A counterexample to the coarse Menger conjecture

Tung Nguyen, Alex Scott, Paul Seymour

Menger's well-known theorem from 1927 characterizes when it is possible to find $k$ vertex-disjoint paths between two sets of vertices in a graph $G$ . Recently, Georgakopoulos and…

Asymptotic structure. V. The coarse Menger conjecture in bounded path-width

Alex Divoux, Tung Nguyen, Alex Scott +1

Menger's theorem tells us that if $S, T$ are sets of vertices in a graph $G$ , then (for $k \geq 0$ ) either there are $k + 1$ vertex-disjoint paths between $S$ and $T$ , or there is a set…

cs.DS2024

Lower bounds for graph reconstruction with maximal independent set queries

Lukas Michel, Alex Scott

We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least $Î©(Î^2…

Size reconstructibility of graphs

Carla Groenland, Hannah Guggiari, Alex Scott

The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs ${G - v : v \in V (G)}$ . The subgraphs $G - v$ are referred to as the cards of $G$ . Brown and Fenner recently s…

Asymptotic structure. II. Path-width and additive quasi-isometry

Tung Nguyen, Alex Scott, Paul Seymour

We show that if a graph $G$ admits a quasi-isometry $I ¨ $ to a graph $H$ of bounded path-width, then we can assign a non-negative integer length to each edge of $H$ , such that the s…

Bad News for Chordal Partitions

Alex Scott, Paul Seymour, David R. Wood

Reed and Seymour [1998] asked whether every graph has a partition into induced connected non-empty bipartite subgraphs such that the quotient graph is chordal. If true, this would…

math.PR2025

Improved bounds for 1-independent percolation on $Z^{n}$

Paul Balister, Tom Johnston, Michael Savery +1

A 1-independent bond percolation model on a graph $G$ is a probability distribution on the spanning subgraphs of $G$ in which, for all vertex-disjoint sets of edges $S_{1}$ and $S_{2}$ …

Boundary rigidity of 3D CAT(0) cube complexes

John Haslegrave, Alex Scott, Youri Tamitegama +1

The boundary rigidity problem is a classical question from Riemannian geometry: if $(M, g)$ is a Riemannian manifold with smooth boundary, is the geometry of $M$ determined up to i…

math.CO2017

A note on intersecting hypergraphs with large cover number

Penny Haxell, Alex Scott

We give a construction of r-partite r-uniform intersecting hypergraphs with cover number at least r-4 for all but finitely many r. This answers a question of Abu-Khazneh, Barat, Po…

math.CO2015

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures

Maria Chudnovsky, Paul Seymour, Alex Scott

Gyarfas conjectured in 1985 that for all $k$ , $l$ , every graph with no clique of size more than $k$ and no odd hole of length more than $l$ has chromatic number bounded by a functi…

A note on the GyÃ¡rfÃ¡s-Sumner conjecture

Tung Nguyen, Alex Scott, Paul Seymour

The GyÃ¡rfÃ¡s-Sumner conjecture says that for every tree $T$ and every integer $t \geq 1$ , if $G$ is a graph with no clique of size $t$ and with sufficiently large chromatic number,…