Source author record

Graham Brightwell

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

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Long-term concentration of measure and cut-off

We present new concentration of measure inequalities for Markov chains, generalising results for chains that are contracting in Wasserstein distance. These are particularly suited to establishing the cut-off phenomenon for suitable chains. We apply our discrete-time inequality to the well-studied Bernoulli-Laplace model of diffusion, and give a probabilistic proof of cut-off, recovering and improving the bounds of Diaconis and Shahshahani. We also extend the notion of cut-off to chains with an infinite state space, and illustrate this in a second example, of a two-host model of disease in continuous time. We give a third example, giving concentration results for the supermarket model, illustrating the full generality and power of our results.

preprint2015arXiv

The greedy independent set in a random graph with given degrees

We analyse the size of an independent set in a random graph on $n$ vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as $n \to \infty$ , expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges to the jamming constant as $n \to \infty$ . The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model.

preprint2015arXiv

The mathematics of causal sets

The causal set approach to quantum gravity is based on the hypothesis that the underlying structure of spacetime is that of a random partial order. We survey some of the interesting mathematics that has arisen in connection with the causal set hypothesis, and describe how the mathematical theory can be translated to the application area. We highlight a number of open problems of interest to those working in causal set theory.

preprint2013arXiv

A fixed-point approximation for a routing model in equilibrium

We use a method of Luczak (arXiv:1212.3231) to investigate the equilibrium distribution of a dynamic routing model on a network. In this model, there are $n$ nodes, each pair joined by a link of capacity $C$ . For each pair of nodes, calls arrive for this pair of endpoints as a Poisson process with rate $λ$ . A call for endpoints $\{u,v\}$ is routed directly onto the link between the two nodes if there is spare capacity; otherwise $d$ two-link paths between $u$ and $v$ are considered, and the call is routed along a path with lowest maximum load, if possible. The duration of each call is an exponential random variable with unit mean. In the case $d=1$ , it was suggested by Gibbens, Hunt and Kelly in 1990 that the equilibrium of this process is related to the fixed points of a certain equation. We show that this is indeed the case, for every $d \ge 1$ , provided the arrival rate $λ$ is either sufficiently small or sufficiently large. In either regime, we show that the equation has a unique fixed point, and that, in equilibrium, for each $j$ , the proportion of links at each node with load $j$ is strongly concentrated around the $j$ th coordinate of the fixed point.

preprint2013arXiv

The Reversal Ratio of a Poset

Felsner and Reuter introduced the linear extension diameter of a partially ordered set $\mathbf{P}$ , denoted $\mbox{led}(\mathbf{P})$, as the maximum distance between two linear extensions of $\mathbf{P}$ , where distance is defined to be the number of incomparable pairs appearing in opposite orders (reversed) in the linear extensions. In this paper, we introduce the reversal ratio $RR(\mathbf{P})$ of $\mathbf{P}$ as the ratio of the linear extension diameter to the number of (unordered) incomparable pairs. We use probabilistic techniques to provide a family of posets $\mathbf{P}_k$ on at most $k\log k$ elements for which the reversal ratio $RR(\mathbf{P}_k)\leq C/\log k$ , where $C$ is a constant. We also examine the questions of bounding the reversal ratio in terms of order dimension and width.

preprint2012arXiv

Order-invariant measures on fixed causal sets

A causal set is a countably infinite poset in which every element is above finitely many others; causal sets are exactly the posets that have a linear extension with the order-type of the natural numbers -- we call such a linear extension a {\em natural extension}. We study probability measures on the set of natural extensions of a causal set, especially those measures having the property of {\em order-invariance}: if we condition on the set of the bottom $k$ elements of the natural extension, each possible ordering among these $k$ elements is equally likely. We give sufficient conditions for the existence and uniqueness of an order-invariant measure on the set of natural extensions of a causal set.

preprint2012arXiv

The supermarket model with arrival rate tending to one

In the supermarket model, there are $n$ queues, each with a single server. Customers arrive in a Poisson process with arrival rate $λn$ , where $λ= λ(n) \in (0,1)$ . Upon arrival, a customer selects $d=d(n)$ servers uniformly at random, and joins the queue of a least-loaded server amongst those chosen. Service times are independent exponentially distributed random variables with mean~1. In this paper, we analyse the behaviour of the supermarket model in a regime where $λ(n)$ tends to~1, and $d(n)$ tends to infinity, as $n \to \infty$ . For suitable triples $(n,d,λ)$ , we identify a subset ${\cal N}$ of the state space where the process remains for a long time in equilibrium. We further show that the process is rapidly mixing when started in ${\cal N}$ , and give bounds on the speed of mixing for more general initial conditions.

preprint2012arXiv

Vertices of high degree in the preferential attachment tree

We study the basic preferential attachment process, which generates a sequence of random trees, each obtained from the previous one by introducing a new vertex and joining it to one existing vertex, chosen with probability proportional to its degree. We investigate the number $D_t(\ell)$ of vertices of each degree $\ell$ at each time $t$ , focussing particularly on the case where $\ell$ is a growing function of $t$ . We show that $D_t(\ell)$ is concentrated around its mean, which is approximately $4t/\ell^3$ , for all $\ell \le (t/\log t)^{-1/3}$ ; this is best possible up to a logarithmic factor.

preprint2011arXiv

Asymptotic Enumeration of Labelled Interval Orders

Building on work by Zagier, Bousquet-Mélou et al., and Khamis, we give an asymptotic formula for the number of labelled interval orders on an $n$ -element set.

preprint2011arXiv

Order-invariant measures on causal sets

A causal set is a partially ordered set on a countably infinite ground-set such that each element is above finitely many others. A natural extension of a causal set is an enumeration of its elements which respects the order. We bring together two different classes of random processes. In one class, we are given a fixed causal set, and we consider random natural extensions of this causal set: we think of the random enumeration as being generated one point at a time. In the other class of processes, we generate a random causal set, working from the bottom up, adding one new maximal element at each stage. Processes of both types can exhibit a property called order-invariance: if we stop the process after some fixed number of steps, then, conditioned on the structure of the causal set, every possible order of generation of its elements is equally likely. We develop a framework for the study of order-invariance which includes both types of example: order-invariance is then a property of probability measures on a certain space. Our main result is a description of the extremal order-invariant measures.

preprint2011arXiv

Shadows of ordered graphs

Isoperimetric inequalities have been studied since antiquity, and in recent decades they have been studied extensively on discrete objects, such as the hypercube. An important special case of this problem involves bounding the size of the shadow of a set system, and the basic question was solved by Kruskal (in 1963) and Katona (in 1968). In this paper we introduce the concept of the shadow \d\G of a collection \G of ordered graphs, and prove the following, simple-sounding statement: if n \in \N is sufficiently large, |V(G)| = n for each G \in \G, and |\G| < n, then |\d \G| \ge |\G|. As a consequence, we substantially strengthen a result of Balogh, Bollobás and Morris on hereditary properties of ordered graphs: we show that if ¶is such a property, and |¶_k| < k for some sufficiently large k \in \N, then |¶_n| is decreasing for k \le n < \infty.

preprint2010arXiv

Ramsey-goodness -- and otherwise

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number $Δ$ , there is a constant $r_Δ$ such that, for any connected $n$ -vertex graph $G$ with maximum degree $Δ$ , the Ramsey number $R(G,G)$ is at most $r_Δn$ , provided $n$ is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take $r_Δ= Δ$ . However, Graham, Rödl and Ruciński showed, by taking $G$ to be a suitable expander graph, that necessarily $r_Δ> 2^{cΔ}$ for some constant $c>0$ . We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of $G$ be at most some function $β(n) = o(n)$ , then $R(G,G) \le (2χ(G)+4)n\leq (2Δ+6)n$ , i.e., $r_Δ= 2Δ+6$ suffices. On the other hand, we show that Burr's conjecture itself fails even for $P_n^k$ , the $k$ th power of a path $P_n$ . Brandt showed that for any $c$ , if $Δ$ is sufficiently large, there are connected $n$ -vertex graphs $G$ with $Δ(G)\leqΔ$ but $R(G,K_3)>cn$ . We show that, given $Δ$ and $H$ , there are $β>0$ and $n_0$ such that, if $G$ is a connected graph on $n\ge n_0$ vertices with maximum degree at most $Δ$ and bandwidth at most $βn$ , then we have $R(G,H)=(χ(H)-1)(n-1)+σ(H)$ , where $σ(H)$ is the smallest size of any part in any $χ(H)$ -partition of $H$ . We also show that the same conclusion holds without any restriction on the maximum degree of $G$ if the bandwidth of $G$ is at most $ε(H) \log n/\log\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.

Graham Brightwell

Research overview

Is this your work?

12 publications

Long-term concentration of measure and cut-off

The greedy independent set in a random graph with given degrees

The mathematics of causal sets

A fixed-point approximation for a routing model in equilibrium

The Reversal Ratio of a Poset

Order-invariant measures on fixed causal sets

The supermarket model with arrival rate tending to one

Vertices of high degree in the preferential attachment tree

Asymptotic Enumeration of Labelled Interval Orders

Order-invariant measures on causal sets

Shadows of ordered graphs

Ramsey-goodness -- and otherwise

See the researcher in context

Building this map preview