Source author record

Colin McDiarmid

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

ResearcherUnclaimed source record

math.CO math.PR Data Structures and Algorithms Computational Geometry math.MG math.OC Social and Information Networks

Catalog footprint

Research overview

22works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Note on edge expansion and modularity in preferential attachment graphs

Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and is an important notion in theoretical computer science. Modularity is a measure of how well a graph can be partitioned into communities and is widely used in clustering applications. We study these two parameters in two commonly considered models of random preferential attachment graphs, with $h \geq 2$ edges added per step. We establish new bounds for the likely edge expansion for both random models. Using bounds for edge expansion of small subsets of vertices, we derive new upper bounds also for the modularity values for small $h$ .

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

Connectivity for an unlabelled bridge-addable graph class

Let the class A of graphs be bridge-addable; that is, whenever a graph G in A has vertices u and v in different components then the graph G+uv is in A. For a random graph sampled uniformly from the graphs in A on vertex set {1,..,n}, there are known lower bounds on the probability of being connected (for example, the probability is always at least 1/e). We ask here about similar results when the random graph is sampled uniformly from the unlabelled n-vertex graphs in A.

preprint2016arXiv

Clique colouring of binomial random graphs

A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(n,p) for a wide range of edge-probabilities p=p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.

preprint2016arXiv

Connectivity for bridge-alterable graph classes

A collection of graphs is called bridge-alterable if, for each graph G with a bridge e, G is in the class if and only if G-e is. For example the class of forests is bridge-alterable. For a random forest $F_n$ sampled uniformly from the set of forests on vertex set {1,..,n}, a classical result of Renyi (1959) shows that the probability that $F_n$ is connected is $e^{-1/2 +o(1)}$ . Recently Addario-Berry, McDiarmid and Reed (2012) and Kang and Panagiotou (2013) independently proved that, given a bridge-alterable class, for a random graph $R_n$ sampled uniformly from the graphs in the class on {1,..,n}, the probability that $R_n$ is connected is at least $e^{-1/2 +o(1)}$ . Here we give a more straightforward proof, and obtain a stronger non-asymptotic form of this result, which compares the probability to that for a random forest. We see that the probability that $R_n$ is connected is at least the minimum over $\frac25 n < t \leq n$ of the probability that $F_t$ is connected.

preprint2016arXiv

Hamilton cycles, minimum degree and bipartite holes

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large ``bipartite hole`` (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erdős. In detail, an $(s, t)$ -bipartite-hole in a graph $G$ consists of two disjoint sets of vertices $S$ and $T$ with $|S|= s$ and $|T|=t$ such that there are no edges between $S$ and $T$ ; and $\widetildeα(G)$ is the maximum integer $r$ such that $G$ contains an $(s, t)$ -bipartite-hole for every pair of non-negative integers $s$ and $t$ with $s + t = r$ . Our central theorem is that a graph $G$ with at least $3$ vertices is Hamiltonian if its minimum degree is at least $\widetildeα(G)$ . From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of $k$ edge-disjoint Hamilton cycles. We see that for dense random graphs $G(n,p)$ , the probability of failing to contain many edge-disjoint Hamilton cycles is $(1 - p)^{(1 + o(1))n}$ . Finally, we discuss the complexity of calculating and approximating $\widetildeα(G)$ .

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

Recognition of unipolar and generalised split graphs

A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present the first $O(n^2)$ time algorithm for recognition of $n$ -vertex unipolar and generalised split graphs, improving on previous $O(n^3)$ time algorithms.

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

Balanced routing of random calls

We consider an online network routing problem in continuous time, where calls have Poisson arrivals and exponential durations. The first-fit dynamic alternative routing algorithm sequentially selects up to $d$ random two-link routes between the two endpoints of a call, via an intermediate node, and assigns the call to the first route with spare capacity on each link, if there is such a route. The balanced dynamic alternative routing algorithm simultaneously selects $d$ random two-link routes, and the call is accepted on a route minimising the maximum of the loads on its two links, provided neither of these two links is saturated. We determine the capacities needed for these algorithms to route calls successfully and find that the balanced algorithm requires a much smaller capacity. In order to handle such interacting random processes on networks, we develop appropriate tools such as lemmas on biased random walks.

preprint2015arXiv

Extremal Distances for Subtree Transfer Operations in Binary Trees

Three standard subtree transfer operations for binary trees, used in particular for phylogenetic trees, are: tree bisection and reconnection ( $TBR$ ), subtree prune and regraft ( $SPR$ ) and rooted subtree prune and regraft ( $rSPR$ ). For a pair of leaf-labelled binary trees with $n$ leaves, the maximum number of such moves required to transform one into the other is $n-Θ(\sqrt{n})$ , extending a result of Ding, Grunewald and Humphries. We show that if the pair is chosen uniformly at random, then the expected number of moves required to transfer one into the other is $n-Θ(n^{2/3})$ . These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees.

preprint2012arXiv

Connectivity for random graphs from a weighted bridge-addable class

There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable structured class, such as the class of all planar graphs. Here we consider a general 'bridge-addable' class of graphs - if a graph is in the class and u and v are vertices in different components then the graph obtained by adding an edge (bridge) between u and v must also be in the class. Various bounds are known concerning the probability of a random graph from such a class being connected or having many components, sometimes under the additional assumption that bridges can be deleted as well as added. Here we improve or amplify or generalise these bounds. For example, we see that the expected number of vertices left when we remove a largest component is less than 2. The generalisation is to consider 'weighted' random graphs, sampled from a suitable more general distribution, where the focus is on the bridges.

preprint2012arXiv

Independent sets in graphs with given minimum degree

We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$ , when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.

preprint2012arXiv

Largest sparse subgraphs of random graphs

For the Erdős-Rényi random graph G(n,p), we give a precise asymptotic formula for the size of a largest vertex subset in G(n,p) that induces a subgraph with average degree at most t, provided that p = p(n) is not too small and t = t(n) is not too large. In the case of fixed t and p, we find that this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.

preprint2012arXiv

On the spread of random graphs

The spread of a connected graph G was introduced by Alon, Boppana and Spencer (1998) and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph; in particular for random regular graphs G(n,d), for Erdős-Rényi random graphs G_{n,p} in the supercritical range p>1/n, and for a 'small world' model. For supercritical G_{n,p}, we show that if p=c/n with c>1 fixed then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge-lengths. We also give lower bounds on the spread for the barely supercritical case when p=(1+o(1))/n. Further, we show that for d large, with high probability the spread of G(n,d) becomes arbitrarily close to that of the complete graph K_n.

preprint2012arXiv

Random graphs from a weighted minor-closed class

There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable minor-closed class, such as the class of all planar graphs. Here we use combinatorial and probabilistic methods to investigate a more general model. We consider random graphs from a `well-behaved' class of graphs: examples of such classes include all minor-closed classes of graphs with 2-connected excluded minors (such as forests, series-parallel graphs and planar graphs), the class of graphs embeddable on any given surface, and the class of graphs with at most k vertex-disjoint cycles. Also, we give weights to edges and components to specify probabilities, so that our random graphs correspond to the random cluster model, appropriately conditioned. We find that earlier results extend naturally in both directions, to general well-behaved classes of graphs, and to the weighted framework, for example results concerning the probability of a random graph being connected; and we also give results on the 2-core which are new even for the uniform (unweighted) case.

preprint2011arXiv

Connectivity for bridge-addable monotone graph classes

A class A of labelled graphs is bridge-addable if for all graphs G in A and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and u is also in A; the class A is monotone if for all G in A and all subgraphs H of G, H is also in A. We show that for any bridge-addable, monotone class A whose elements have vertex set 1,...,n, the probability that a uniformly random element of A is connected is at least (1-o_n(1)) e^{-1/2}, where o_n(1) tends to zero as n tends to infinity. This establishes the special case of a conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotiou (2011).

preprint2011arXiv

Integer realizations of disk and segment graphs

A disk graph is the intersection graph of disks in the plane, a unit disk graph is the intersection graph of same radius disks in the plane, and a segment graph is an intersection graph of line segments in the plane. It can be seen that every disk graph can be realized by disks with centers on the integer grid and with integer radii; and similarly every unit disk graph can be realized by disks with centers on the integer grid and equal (integer) radius; and every segment graph can be realized by segments whose endpoints lie on the integer grid. Here we show that there exist disk graphs on $n$ vertices such that in every realization by integer disks at least one coordinate or radius is $2^{2^{Ω(n)}}$ and on the other hand every disk graph can be realized by disks with integer coordinates and radii that are at most $2^{2^{O(n)}}$ ; and we show the analogous results for unit disk graphs and segment graphs. For (unit) disk graphs this answers a question of Spinrad, and for segment graphs this improves over a previous result by Kratochv\'ıl and Matou{š}ek.

preprint2011arXiv

On the chromatic number of random geometric graphs

Given independent random points $X_1,...,X_n\in\eR^d$ with common probability distribution $ν$ , and a positive distance $r=r(n)>0$ , we construct a random geometric graph $G_n$ with vertex set $\{1,...,n\}$ where distinct $i$ and $j$ are adjacent when $\norm{X_i-X_j}\leq r$. Here $\norm{.}$ may be any norm on $\eR^d$, and $ν$ may be any probability distribution on $\eR^d$ with a bounded density function. We consider the chromatic number $χ(G_n)$ of $G_n$ and its relation to the clique number $ω(G_n)$ as $n \to \infty$ . Both McDiarmid and Penrose considered the range of $r$ when $r \ll (\frac{\ln n}{n})^{1/d}$ and the range when $r \gg (\frac{\ln n}{n})^{1/d}$ , and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the `phase change' range when $r \sim (\frac{t\ln n}{n})^{1/d}$ with $t>0$ a fixed constant. Both McDiarmid and Penrose asked for the behaviour of the chromatic number in this range. We determine constants $c(t)$ such that $\frac{χ(G_n)}{nr^d}\to c(t)$ almost surely. Further, we find a "sharp threshold" (except for less interesting choices of the norm when the unit ball tiles $d$ -space): there is a constant $t_0>0$ such that if $t \leq t_0$ then $\frac{χ(G_n)}{ω(G_n)}$ tends to 1 almost surely, but if $t > t_0$ then $\frac{χ(G_n)}{ω(G_n)}$ tends to a limit $>1$ almost surely.

preprint2010arXiv

Random graphs with few disjoint cycles

The classical Erdős-Pósa theorem states that for each positive integer k there is an f(k) such that, in each graph G which does not have k+1 disjoint cycles, there is a blocker of size at most f(k); that is, a set B of at most f(k) vertices such that G-B has no cycles. We show that, amongst all such graphs on vertex set {1,..,n}, all but an exponentially small proportion have a blocker of size k. We also give further properties of a random graph sampled uniformly from this class; concerning uniqueness of the blocker, connectivity, chromatic number and clique number. A key step in the proof of the main theorem is to show that there must be a blocker as in the Erdős-Pósa theorem with the extra `redundancy' property that B-v is still a blocker for all but at most k vertices v in B.

preprint2010arXiv

The t-stability number of a random graph

Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the maximum order of a t-stable set in G. We investigate the typical values that this parameter takes on a random graph on n vertices and edge probability equal to p. For any fixed 0 < p < 1 and fixed non-negative integer t, we show that, with probability tending to 1 as n grows, the t-stability number takes on at most two values which we identify as functions of t, p and n. The main tool we use is an asymptotic expression for the expected number of t-stable sets of order k. We derive this expression by performing a precise count of the number of graphs on k vertices that have maximum degree at most k. Using the above results, we also obtain asymptotic bounds on the t-improper chromatic number of a random graph (this is the generalisation of the chromatic number, where we partition of the vertex set of the graph into t-stable sets).

preprint2009arXiv

The t-improper chromatic number of random graphs

We consider the $t$ -improper chromatic number of the Erd{\H o}s-R{é}nyi random graph $G(n,p)$ . The t-improper chromatic number $χ^t(G)$ of $G$ is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most $t$ . If $t = 0$ , then this is the usual notion of proper colouring. When the edge probability $p$ is constant, we provide a detailed description of the asymptotic behaviour of $χ^t(G(n,p))$ over the range of choices for the growth of $t = t(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.

Colin McDiarmid

Research overview

Is this your work?

22 publications

Note on edge expansion and modularity in preferential attachment graphs

The component structure of dense random subgraphs of the hypercube

Connectivity for an unlabelled bridge-addable graph class

Clique colouring of binomial random graphs

Connectivity for bridge-alterable graph classes

Hamilton cycles, minimum degree and bipartite holes

Random graphs from a block-stable class

Recognition of unipolar and generalised split graphs

Uniform multicommodity flow in the hypercube with random edge capacities

Balanced routing of random calls

Extremal Distances for Subtree Transfer Operations in Binary Trees

Connectivity for random graphs from a weighted bridge-addable class

Independent sets in graphs with given minimum degree

Largest sparse subgraphs of random graphs

On the spread of random graphs

Random graphs from a weighted minor-closed class

Connectivity for bridge-addable monotone graph classes

Integer realizations of disk and segment graphs

On the chromatic number of random geometric graphs

Random graphs with few disjoint cycles

The t-stability number of a random graph

The t-improper chromatic number of random graphs

See the researcher in context

Building this map preview