Source author record

Alex Scott

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Distributed, Parallel, and Cluster Computing math.PR Computer Science and Game Theory Data Structures and Algorithms econ.TH math.OC

Catalog footprint

Research overview

49works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Game connectivity and adaptive dynamics in many-action games

We study the typical structure of games in terms of their connectivity properties. A game is said to be `connected' if it has a pure Nash equilibrium and the property that there is a best-response path from every action profile which is not a pure Nash equilibrium to every pure Nash equilibrium, and it is generic if it has no indifferences. In previous work we showed that, among all $n$ -player $k$ -action generic games that admit a pure Nash equilibrium, the fraction that are connected tends to $1$ as $n$ gets sufficiently large relative to $k$ . The present paper considers the large- $k$ regime, which behaves differently: we show that the connected fraction tends to $1-ζ_n$ as $k$ gets large, where $ζ_n>0$ . In other words, a constant fraction of many-action games are not connected. However, $ζ_n$ is small and tends to $0$ rapidly with $n$ , so as $n$ increases all but a vanishingly small fraction of many-player-many-action games are connected. Since connectedness is conducive to equilibrium convergence we obtain, by implication, that there is a simple adaptive dynamic that is guaranteed to lead to a pure Nash equilibrium in all but a vanishingly small fraction of generic games that have one. Our results are based on new probabilistic and combinatorial arguments which allow us to address the large- $k$ regime that the approach used in our previous work could not tackle. We thus complement our previous work to provide a more complete picture of game connectivity across different regimes.

preprint2023arXiv

Induced paths in graphs without anticomplete cycles

Let us say a graph is $s\mathcal{O}$ -free, where $s\ge 1$ is an integer, if there do not exist $s$ cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when $s=2$ , is not well understood. For instance, until now we did not know how to test whether a graph is $2\mathcal{O}$ -free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that $2\mathcal{O}$ -free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all $s\ge 1$ , there exists $c>0$ such that every $s\mathcal{O}$ -free graph $G$ has at most $|G|^c$ induced paths. This provides a poly-time algorithm to test if a graph is $s\mathcal{O}$ -free, for all fixed $s$ . The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek, that in every $s\mathcal{O}$ -free graph $G$ with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in $|G|$ . And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper.

preprint2023arXiv

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

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 number. (A graph is $H$ -free if it does not contain an induced copy of $H$ .) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest $H$ , if $G$ is $H$ -free and does not contain $K_{t,t}$ as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest $H$ , the bound on chromatic number can be taken to be polynomial in $t$ . In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree $H$ of radius two and every integer $d\ge 2$ , if $G$ is $H$ -free and does not contain as a subgraph the complete $d$ -partite graph with parts of cardinality $t$ , then its chromatic number is at most polynomial in $t$ .

preprint2022arXiv

A note on infinite antichain density

Let $\mathcal{F}$ be an antichain of finite subsets of $\mathbb{N}$ . How quickly can the quantities $|\mathcal{F}\cap 2^{[n]}|$ grow as $n\to\infty$ ? We show that for any sequence $(f_n)_{n\ge n_0}$ of positive integers satisfying $\sum_{n=n_0}^\infty f_n/2^n \le 1/4$ , $f_{n_0}=1$ and $f_n\le f_{n+1}\le 2f_n$ , there exists an infinite antichain $\mathcal{F}$ of finite subsets of $\mathbb{N}$ such that $|\mathcal{F}\cap 2^{[n]}| \geq f_n$ for all $n\ge n_0$ . It follows that for any $\varepsilon>0$ there exists an antichain $\mathcal{F}\subseteq 2^\mathbb{N}$ such that $\liminf_{n \to \infty} |\mathcal{F}\cap 2^{[n]}| \cdot \left(\frac{2^n}{n\log^{1+\varepsilon} n}\right)^{-1} > 0.$ This resolves a problem of Sudakov, Tomon and Wagner in a strong form, and is essentially tight.

preprint2022arXiv

Bipartite graphs with no $K_6$ minor

A theorem of Mader shows that every graph with average degree at least eight has a $K_6$ minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have $K_6$ minors, but minimum degree six is certainly not enough. For every $c>0$ there are arbitrarily large graphs with average degree at least $8-c$ and minimum degree at least six, with no $K_6$ minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every $c>0$ there are arbitrarily large bipartite graphs with average degree at least $8-c$ and no $K_6$ minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a $K_6$ minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

preprint2022arXiv

Clustered colouring of graph classes with bounded treedepth or pathwidth

The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$ -colourable with monochromatic components of size at most $c$ . We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class.

preprint2022arXiv

Defective Colouring of Hypergraphs

We prove that the vertices of every $(r + 1)$ -uniform hypergraph with maximum degree $Δ$ may be coloured with $c(\fracΔ{d + 1})^{1/r}$ colours such that each vertex is in at most $d$ monochromatic edges. This result, which is best possible up to the value of the constant $c$ , generalises the classical result of Erdős and Lovász who proved the $d = 0$ case.

preprint2022arXiv

Perfect shuffling with fewer lazy transpositions

A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)\in S_n$ with probability $p$ . How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length $\binom{n}2$ , but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length $\frac23 \binom{n}2+O(n\log n)$ , and consider some related questions.

preprint2022arXiv

Polynomial bounds for chromatic number VII. Disjoint holes

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 not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any $k$ , if $G$ does not contain a $k$ -multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially $χ$ -bounded.

preprint2022arXiv

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

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\geq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.

preprint2022arXiv

Strengthening Rodl's theorem

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 dense or very sparse. More precisely, let us say that a graph F on n vertices is c-restricted if either F or its complement has maximum degree at most cn. Rodl proved that for every graph H, and every c>0, every H-free graph G has a linear-sized set of vertices inducing a c-restricted graph. We strengthen Rodl's result as follows: for every graph H, and all c>0, every H-free graph can be partitioned into a bounded number of subsets inducing c-restricted graphs.

preprint2021arXiv

Erdos-Hajnal for graphs with no 5-hole

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 at least |G|^c. We prove that this is true when H is a cycle of length five. We also prove several further results: for instance, that if C is a cycle and H is the complement of a forest, there exists c>0 such that every graph G containing neither of C,H as an induced subgraph has a clique or stable set of cardinality at least |G|^c.

preprint2021arXiv

Powers of paths in tournaments

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when $k=2$ , showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$ , which is best possible.

preprint2021arXiv

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

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(\log n)$ . But let us fix a matrix $H$ , and define $f_H(n)$ to be the same, minimized over over all $n\times n$ $0/1$ -matrices $M$ such that neither $M$ nor its complement (that is, change all $0$ 's to $1$ 's and vice versa) contains $H$ as a submatrix. It is known that $f_H(n)\ge εn^c$ , where $c, ε>0$ are constants depending on $H$ . When can we take $c=1$ ? If so, then one of $H$ and its complement must be an acyclic matrix (that is, the corresponding bipartite graph is a forest). Korandi, Pach, and Tomon conjectured the converse, that $f_H(n)$ is linear in $n$ for every acyclic matrix $H$ ; and they proved it for certain matrices $H$ with only two rows. Their conjecture remains open, but we show $f_H(n)=n^{1-o(1)}$ for every acyclic matrix $H$ ; and indeed there is a $0/1$ -submatrix that is either $Ω(n)\times n^{1-o(1)}$ or $n^{1-o(1)}\times Ω(n)$ .

preprint2021arXiv

The component structure of dense random subgraphs of the hypercube

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 that, as $d \rightarrow \infty$ , if $p>\frac12$ then with high probability $Q_p$ is connected; and if $p<\frac12$ then with high probability $Q_p$ consists of one giant component together with many smaller components which form the `fragment'. Here we fix $p \in (0,\frac12)$ , and investigate the fragment, and how it sits inside the hypercube. In particular we give asymptotic estimates for the mean numbers of components in the fragment of each size, and describe their asymptotic distributions and indeed their joint distribution, much extending earlier work of Weber.

preprint2020arXiv

A survey of $χ$ -boundedness

If a graph has bounded clique number, and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980's, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

preprint2020arXiv

A universal exponent for homeomorphs

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}$ facets contains a homeomorphic copy of $S$ , where $C_S > 0$ is an absolute constant depending on $S$ alone. This result, a two-dimensional analogue of a classical result of Mader for one-dimensional complexes, sheds some light on an old problem of Linial from 2006.

preprint2020arXiv

Detecting a long odd hole

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

preprint2020arXiv

Finding a shortest odd hole

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 algorithm to test if a graph has an odd hole. We subsequently showed that, for every t, there is a polynomial time algorithm to test whether a graph contains an odd hole of length at least t. In this paper, we give an algorithm that finds a shortest odd hole, if one exists.

preprint2020arXiv

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Fix $k \ge 2$ and let $H$ be a graph with $χ(H) = k+1$ containing a critical edge. We show that for sufficiently large $n$ , the unique $n$ -vertex $H$ -free graph containing the maximum number of cycles is $T_k(n)$ . This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian.

preprint2020arXiv

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

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)$ . Our approach is based on applying Freedman's inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.

preprint2020arXiv

Monochromatic Components in Edge-Coloured Graphs with Large Minimum Degree

For every $n\in\mathbb{N}$ and $k\geq2$ , it is known that every $k$ -edge-colouring of the complete graph on $n$ vertices contains a monochromatic connected component of order at least $\frac{n}{k-1}$ . For $k\geq3$ , it is known that the complete graph can be replaced by a graph $G$ with $δ(G)\geq(1-\varepsilon_k)n$ for some constant $\varepsilon_k$ . In this paper, we show that the maximum possible value of $\varepsilon_3$ is $\frac16$ . This disproves a conjecture of Gyárfas and Sárközy.

preprint2020arXiv

Partitioning the vertices of a torus into isomorphic subgraphs

Let $H$ be an induced subgraph of the torus $C_k^m$ . We show that when $k \ge 3$ is even and $|V(H)|$ divides some power of $k$ , then for sufficiently large $n$ the torus $C_k^n$ has a perfect vertex-packing with induced copies of $H$ . On the other hand, disproving a conjecture of Gruslys, we show that when $k$ is odd and not a prime power, then there exists $H$ such that $|V(H)|$ divides some power of $k$ , but there is no $n$ such that $C_k^n$ has a perfect vertex-packing with copies of $H$ . We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph $H$ of the $k$ -dimensional hypercube $Q_k$ , such that there is no $n$ for which $Q_n$ has a perfect edge-packing with copies of $H$ .

preprint2020arXiv

Pure pairs. I. Trees and linear anticomplete pairs

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 set of cardinality at least |G|^c. In this paper, we prove a conjecture of Liebenau and Pilipczuk, that for every forest H there exists c > 0, such that every graph G contains either an induced copy of H, or a vertex of degree at least c|G|, or two disjoint sets of at least c|G| vertices with no edges between them. It follows that for every forest H there is c > 0 so that if G contains neither H nor its complement as an induced subgraph then there is a clique or stable set of cardinality at least |G|^c.

preprint2020arXiv

Pure pairs. II. Excluding all subdivisions of a graph

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 has at least a|G| neighbours, or there are two disjoint sets A,B of at least a|G| vertices such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|^c. This is related to the Erdos-Hajnal conjecture.

preprint2020arXiv

Size reconstructibility of graphs

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 showed that, for $n\geq29$ , the number of edges of a graph $G$ can be computed from any deck missing 2 cards. We show that, for sufficiently large $n$ , the number of edges can be computed from any deck missing at most $\frac1{20}\sqrt{n}$ cards.

preprint2019arXiv

Better bounds for poset dimension and boxicity

We prove that the dimension of every poset whose comparability graph has maximum degree $Δ$ is at most $Δ\log^{1+o(1)} Δ$ . This result improves on a 30-year old bound of Füredi and Kahn, and is within a $\log^{o(1)}Δ$ factor of optimal. We prove this result via the notion of boxicity. The "boxicity" of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$ -dimensional axis-aligned boxes. We prove that every graph with maximum degree $Δ$ has boxicity at most $Δ\log^{1+o(1)} Δ$ , which is also within a $\log^{o(1)}Δ$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $Θ(\sqrt{g \log g})$ , which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor.

preprint2018arXiv

Clustered Colouring in Minor-Closed Classes

The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$ -colourable with monochromatic components of size at most $c$ . We prove that for every graph $H$ , the clustered chromatic number of the class of $H$ -minor-free graphs is tied to the tree-depth of $H$ . In particular, if $H$ is connected with tree-depth $t$ then every $H$ -minor-free graph is $(2^{t+1}-4)$ -colourable with monochromatic components of size at most $c(H)$ . This provides the first evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about defective colouring of $H$ -minor-free graphs. If $t=3$ then we prove that 4 colours suffice, which is best possible. We also determine those minor-closed graph classes with clustered chromatic number 2. Finally, we develop a conjecture for the clustered chromatic number of an arbitrary minor-closed class.

preprint2016arXiv

Disjoint induced subgraphs of the same order and size

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 edges. We prove that $f(G) \ge n/2 - o(n)$ for every graph $G$ on $n$ vertices. This answers a question of Caro and Yuster.

preprint2016arXiv

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

We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorithm for maximal independent set selection operates on a network of identical anonymous processors. The processor at each node has no prior information about the network. At each time step, each node can only broadcast a single bit to all its neighbours, or remain silent. Each node can detect whether one or more neighbours have broadcast, but cannot tell how many of its neighbours have broadcast, or which ones. We build on recent work of Afek et al. which was inspired by studying the development of a network of cells in the fruit fly~\cite{Afek2011a}. However we incorporate for the first time another important feature of the biological system: varying the probability value used at each node based on local feedback from neighbouring nodes. Given any $n$ -node network, our algorithm achieves the optimal expected time complexity of $O(\log n)$ rounds and the optimal expected message complexity of $O(1)$ single-bit messages broadcast by each node.We also show that the previous approach, without feedback, cannot achieve better than $Ω(\log^2 n)$ expected time complexity, whatever global scheme is used to choose the probabilities. Our algorithm for distributed greedy colouring works under similar harsh conditions: each identical node has no prior information about the network, can only broadcast a single message to all neighbours at each time step representing a desired colour, and can only detect whether at least one neighbour has broadcast each colour value. We show that our algorithm has an expected time complexity of $O(Δ+\log n)$ , where $Δ$ is the maximum degree of the network, and expected message complexity of $O(1)$ messages broadcast by each node.

preprint2016arXiv

Induced subgraphs of graphs with large chromatic number. III. Long holes

We prove a 1985 conjecture of Gyárfás that for all $k,\ell$ , every graph with sufficiently large chromatic number contains either a complete subgraph with $k$ vertices or an induced cycle of length at least $\ell$ .

preprint2016arXiv

On a problem of Erdos and Moser

A set $A$ of vertices in an $r$ -uniform hypergraph $\mathcal H$ is covered in $\mathcal H$ if there is some vertex $u\not\in A$ such that, for every $(r-1)$ -set $B\subset A$ , the set $\{u\}\cup B$ is in $\mathcal H$ . Erdos and Moser (1970) determined the minimum number of edges in a graph on $n$ vertices such that every $k$ -set is covered. We extend this result to $r$ -uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs.

preprint2016arXiv

On lower bounds for the matching number of subcubic graphs

We give a complete description of the set of triples (a,b,c) of real numbers with the following property. There exists a constant K such that a n_3 + b n_2 + c n_1 - K is a lower bound for the matching number of every connected subcubic graph G, where n_i denotes the number of vertices of degree i for each i.

preprint2016arXiv

Packing random graphs and hypergraphs

We determine to within a constant factor the threshold for the property that two random k-uniform hypergraphs with edge probability p have an edge-disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger result, on packing a random graph with a fixed graph.

preprint2016arXiv

Random graphs from a block-stable class

A class of graphs is called block-stable when a graph is in the class if and only if each of its blocks is. We show that, as for trees, for most $n$ -vertex graphs in such a class, each vertex is in at most $(1+o(1)) \log n / \log\log n$ blocks, and each path passes through at most $5 (n \log n)^{1/2}$ blocks. These results extend to `weakly block-stable' classes of graphs.

preprint2016arXiv

Uniform multicommodity flow in the hypercube with random edge capacities

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, with high probability as $d \rightarrow \infty$ , the network can support simultaneous multicommodity flows of volume close to $E[C]$ between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to $2^{1-d} E[C]$ between all vertex pairs. Both results are best possible.

preprint2015arXiv

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

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 graph with no K_t subgraph and no odd hole is n-colourable. We prove this conjecture.

preprint2015arXiv

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

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 function of $k$ and $l$ . We prove three weaker statements: (1) Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five; (2) For all $l$ , every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than $l$ ; (3) For all $k$ , $l$ , every graph with no clique of size more than $k$ and sufficiently large chromatic number contains either a 5-hole or a hole of length more than $l$ .

preprint2015arXiv

Saturation in the Hypercube and Bootstrap Percolation

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 but adding any edge of $E(Q_d)\setminus E(G)$ creates a copy of $Q_m$ in $G$ . Answering a question of Johnson and Pinto, we show that for every fixed $m\geq2$ the minimum number of edges in a $(Q_d,Q_m)$ -saturated graph is $Θ(2^d)$ . We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of $Q_d$ is said to be weakly $(Q_d,Q_m)$ -saturated if the edges of $E(Q_d)\setminus E(G)$ can be added to $G$ one at a time so that each added edge creates a new copy of $Q_m$ . Answering another question of Johnson and Pinto, we determine the minimum number of edges in a weakly $(Q_d,Q_m)$ -saturated graph for all $d\geq m\geq1$ . More generally, we determine the minimum number of edges in a subgraph of the $d$ -dimensional grid $P_k^d$ which is weakly saturated with respect to `axis aligned' copies of a smaller grid $P_r^m$ . We also study weak saturation of cycles in the grid.

preprint2014arXiv

Disjoint dijoins

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 there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths. We conjecture that when k = 2, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S is a subset of the edges of G that forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins. We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.

preprint2014arXiv

Disjoint paths in tournaments

Given $k$ pairs of vertices $(s_i,t_i)$ , $1\le i\le k$ , of a digraph $G$ , how can we test whether there exist $k$ vertex-disjoint directed paths from $s_i$ to $t_i$ for $1\le i\le k$ ? This is NP-complete in general digraphs, even for $k = 2$ , but for $k=2$ there is a polynomial-time algorithm when $G$ is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen. Here we prove that for all fixed $k$ there is a polynomial-time algorithm to solve the problem when $G$ is semicomplete.

preprint2014arXiv

Intersections of hypergraphs

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 concentrated is the distribution of the intersection? The aim of this paper is to investigate these questions.

preprint2014arXiv

On Saturated $k$ -Sperner Systems

Given a set $X$ , a collection $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be $k$ -Sperner if it does not contain a chain of length $k+1$ under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. conjectured that, if $|X|$ is sufficiently large with respect to $k$ , then the minimum size of a saturated $k$ -Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ is $2^{k-1}$ . We disprove this conjecture by showing that there exists $\varepsilon>0$ such that for every $k$ and $|X| \geq n_0(k)$ there exists a saturated $k$ -Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ with cardinality at most $2^{(1-\varepsilon)k}$ . A collection $\mathcal{F}\subseteq \mathcal{P}(X)$ is said to be an oversaturated $k$ -Sperner system if, for every $S\in\mathcal{P}(X)\setminus\mathcal{F}$ , $\mathcal{F}\cup\{S\}$ contains more chains of length $k+1$ than $\mathcal{F}$ . Gerbner et al. proved that, if $|X|\geq k$ , then the smallest such collection contains between $2^{k/2-1}$ and $O\left(\frac{\log{k}}{k}2^k\right)$ elements. We show that if $|X|\geq k^2+k$ , then the lower bound is best possible, up to a polynomial factor.

preprint2013arXiv

Excluding Pairs of Graphs

For a graph $G$ and a set of graphs $\mathcal{H}$ , we say that $G$ is {\em $\mathcal{H}$ -free} if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$ . Given an integer $P>0$ , a graph $G$ , and a set of graphs $\mathcal{F}$ , we say that $G$ {\em admits an $(\mathcal{F},P)$ -partition} if the vertex set of $G$ can be partitioned into $P$ subsets $X_1,..., X_P$ , so that for every $i \in \{1,..., P\}$ , either $|X_i|=1$ , or the subgraph of $G$ induced by $X_i$ is $\{F\}$ -free for some $F \in \mathcal{F}$ . Our first result is the following. For every pair $(H,J)$ of graphs such that $H$ is the disjoint union of two graphs $H_1$ and $H_2$ , and the complement $J^c$ of $J$ is the disjoint union of two graphs $J_1^c$ and $J_2^c$ , there exists an integer $P>0$ such that every $\{H,J\}$ -free graph has an $(\{H_1,H_2,J_1,J_2\},P)$ -partition. Using a similar idea we also give a short proof of one of the results of \cite{heroes}. Our final result is a construction showing that if $\{H,J\}$ are graphs each with at least one edge, then for every pair of integers $r,k$ there exists a graph $G$ such that every $r$ -vertex induced subgraph of $G$ is $\{H,J\}$ -split, but $G$ does not admits an $(\{H,J\},k)$ -partition.

preprint2013arXiv

Substitution and $χ$ -Boundedness

A class $\mathcal{G}$ of graphs is said to be {\em $χ$ -bounded} if there is a function $f:\mathbb{N} \rightarrow \mathbb{R}$ such that for all $G \in \mathcal{G}$ and all induced subgraphs $H$ of $G$ , $χ(H) \leq f(ω(H))$ . In this paper, we show that if $\mathcal{G}$ is a $χ$ -bounded class, then so is the closure of $\mathcal{G}$ under any one of the following three operations: substitution, gluing along a clique, and gluing along a bounded number of vertices. Furthermore, if $\mathcal{G}$ is $χ$ -bounded by a polynomial (respectively: exponential) function, then the closure of $\mathcal{G}$ under substitution is also $χ$ -bounded by some polynomial (respectively: exponential) function. In addition, we show that if $\mathcal{G}$ is a $χ$ -bounded class, then the closure of $\mathcal{G}$ under the operations of gluing along a clique and gluing along a bounded number of vertices together is also $χ$ -bounded, as is the closure of $\mathcal{G}$ under the operations of substitution and gluing along a clique together.

preprint2012arXiv

Cover-Decomposition and Polychromatic Numbers

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 such a colouring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded VC-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.

preprint2012arXiv

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

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, inspired by the study of the way that developing cells in the fly become specialised. The algorithm they propose is simple and robust, but not as efficient as previous approaches: the expected time complexity is O(log^2 n). Here we first show that the approach of Afek et al cannot achieve better efficiency than this across all networks, no matter how the probability values are chosen. However, we then propose a new algorithm that incorporates another important feature of the biological system: adapting the probabilities used at each node based on local feedback from neighbouring nodes. Our new algorithm retains all the advantages of simplicity and robustness, but also achieves the optimal efficiency of O(log n) expected time.

preprint2011arXiv

Monochromatic cycles and the monochromatic circumference in 2-coloured graphs

Li, Nikiforov and Schelp conjectured that a 2-edge coloured graph G with order n and minimal degree strictly greater than 3n/4 contains a monochromatic cycle of length l, for all l at least four and at most n/2. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with minimal degree equal to 3n/4 that do not contain all such cycles. Finally we show that, for all positive constants d and sufficiently large n, a 2-edge coloured graph G of order n with minimal degree at least 3n/4 either contains a monochromatic cycle of length at least (2/3+d/2)n, or, in one of the two colours, contains a cycle of all lengths between three and (2/3-d)n.

preprint2010arXiv

A new bound for the cops and robbers problem

In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph $G$ . Cops and a robber are allowed to move along the edges of $G$ and the goal of cops is to capture the robber. The cop number $c(G)$ of $G$ is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that $O(\sqrt{n})$ cops are enough for any connected $G$ on $n$ vertices. Improving several previous results, we prove that the cop number of $n$ -vertex graph is at most $n 2^{-(1+o(1))\sqrt{\log n}}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Alex Scott

Research overview

Is this your work?

49 publications

Game connectivity and adaptive dynamics in many-action games

Induced paths in graphs without anticomplete cycles

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

A note on infinite antichain density

Bipartite graphs with no K6K_6K6​ minor

Clustered colouring of graph classes with bounded treedepth or pathwidth

Defective Colouring of Hypergraphs

Perfect shuffling with fewer lazy transpositions

Polynomial bounds for chromatic number VII. Disjoint holes

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

Strengthening Rodl's theorem

Erdos-Hajnal for graphs with no 5-hole

Powers of paths in tournaments

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

The component structure of dense random subgraphs of the hypercube

A survey of χχχ-boundedness

A universal exponent for homeomorphs

Detecting a long odd hole

Finding a shortest odd hole

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m)G(n,m)G(n,m) and G(n,p)G(n,p)G(n,p)

Monochromatic Components in Edge-Coloured Graphs with Large Minimum Degree

Partitioning the vertices of a torus into isomorphic subgraphs

Pure pairs. I. Trees and linear anticomplete pairs

Pure pairs. II. Excluding all subdivisions of a graph

Size reconstructibility of graphs

Better bounds for poset dimension and boxicity

Clustered Colouring in Minor-Closed Classes

Disjoint induced subgraphs of the same order and size

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

Induced subgraphs of graphs with large chromatic number. III. Long holes

On a problem of Erdos and Moser

On lower bounds for the matching number of subcubic graphs

Packing random graphs and hypergraphs

Random graphs from a block-stable class

Uniform multicommodity flow in the hypercube with random edge capacities

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

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

Saturation in the Hypercube and Bootstrap Percolation

Disjoint dijoins

Disjoint paths in tournaments

Intersections of hypergraphs

On Saturated kkk-Sperner Systems

Excluding Pairs of Graphs

Substitution and χχχ-Boundedness

Cover-Decomposition and Polychromatic Numbers

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

Monochromatic cycles and the monochromatic circumference in 2-coloured graphs

A new bound for the cops and robbers problem

See the researcher in context

Building this map preview

Bipartite graphs with no $K_6$ minor

A survey of $χ$ -boundedness

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

On Saturated $k$ -Sperner Systems

Substitution and $χ$ -Boundedness