John Haslegrave
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
John Haslegrave has a total of 53 co-authors. Here are the top co-authors by number of shared publications:
Sebastian Koch
5 shared publicationsAgelos Georgakopoulos
University of Warwick
3 shared publications- Hong Liu
Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea
3 shared publications - Jaehoon Kim
Department of Mathematical Sciences, KAIST, Daejeon, South Korea
3 shared publications Richard A.B. Johnson
3 shared publications- Stijn Cambie
Department of Computer Science KU Leuven Campus Kulak‐Kortrijk Kortrijk Belgium
3 shared publications
Latest Publications
- 1 January 2026
- Published by Institute of Mathematical Statistics in Electronic Communications in Probability
- Vol. 31 (none) , 1-11
Balanced two-type annihilation: Mean-field asymptotics
We consider an interacting particle system where equal-sized populations of two types of particles move by random walk steps on a graph, the two types may have different speeds, and meetings of opposite-type particles result in annihilation. The key quantity of interest is the expected extinction time. Even for the mean-field setting of complete graphs, the correct order of magnitude was not previously known. Under essentially optimal assumptions on the starting configuration, we determine not only the order of magnitude but also the asymptotics: the expected extinction time on K2n is (2+o(1))nlogn, independently of the relative speeds of the two types.
- 1 January 2026
- Published by Institute of Mathematical Statistics in Electronic Communications in Probability
- Vol. 31 (none) , 1-11
Balanced two-type annihilation: Mean-field asymptotics
We consider an interacting particle system where equal-sized populations of two types of particles move by random walk steps on a graph, the two types may have different speeds, and meetings of opposite-type particles result in annihilation. The key quantity of interest is the expected extinction time. Even for the mean-field setting of complete graphs, the correct order of magnitude was not previously known. Under essentially optimal assumptions on the starting configuration, we determine not only the order of magnitude but also the asymptotics: the expected extinction time on K2n is (2+o(1))nlogn, independently of the relative speeds of the two types.
- Open Access
Sharp thresholds for NAC-colourings and stable cuts in random graphs
NAC-colourings of graphs correspond to flexible quasi-injective realisations in $\mathbb {R} ^2$. A special class of NAC-colourings are those that arise from stable cuts. We give sharp thresholds for the random graph to have no stable cut and to have no NAC-colouring via exact hitting-time results: with high probability, the random graph process gains both properties at the precise time that every vertex is in a triangle. Our thresholds complement recent results on the thresholds for the random graph to be generically or globally rigid in $\mathbb {R} ^d$, and for all injective realisations to be globally rigid in $\mathbb {R} $.Open AccessSharp thresholds for NAC-colourings and stable cuts in random graphs
NAC-colourings of graphs correspond to flexible quasi-injective realisations in $\mathbb {R} ^2$. A special class of NAC-colourings are those that arise from stable cuts. We give sharp thresholds for the random graph to have no stable cut and to have no NAC-colouring via exact hitting-time results: with high probability, the random graph process gains both properties at the precise time that every vertex is in a triangle. Our thresholds complement recent results on the thresholds for the random graph to be generically or globally rigid in $\mathbb {R} ^d$, and for all injective realisations to be globally rigid in $\mathbb {R} $. - Open Access
- 19 May 2025
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 194 (3-4) , 1287-1326
Dissipative particle systems on expanders
We consider a general framework for multi-type interacting particle systems on graphs, where particles move one at a time by random walk steps, different types may have different speeds, and may interact, possibly randomly, when they meet. We study the equilibrium time of the process, by which we mean the number of steps taken until no further interactions can occur. Under a rather general framework, we obtain high probability upper and lower bounds on the equilibrium time that match up to a constant factor and are of order $$n\log n$$ if there are order n vertices and particles. We also obtain similar results for the balanced two-type annihilation model of chemical reactions; here, the balanced case (equal density of types) does not fit into our general framework and makes the analysis considerably more difficult. Our models do not admit any exact solution as for integrable systems or the duality approach available for some other particle systems, so we develop a variety of combinatorial tools for comparing processes in the absence of monotonicity.- 19 May 2025
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 194 (3-4) , 1287-1326
Open AccessDissipative particle systems on expanders
We consider a general framework for multi-type interacting particle systems on graphs, where particles move one at a time by random walk steps, different types may have different speeds, and may interact, possibly randomly, when they meet. We study the equilibrium time of the process, by which we mean the number of steps taken until no further interactions can occur. Under a rather general framework, we obtain high probability upper and lower bounds on the equilibrium time that match up to a constant factor and are of order $$n\log n$$ if there are order n vertices and particles. We also obtain similar results for the balanced two-type annihilation model of chemical reactions; here, the balanced case (equal density of types) does not fit into our general framework and makes the analysis considerably more difficult. Our models do not admit any exact solution as for integrable systems or the duality approach available for some other particle systems, so we develop a variety of combinatorial tools for comparing processes in the absence of monotonicity. - Open Access
- 12 March 2025
- Published by University of Primorska Press in The Art of Discrete and Applied Mathematics
- Vol. 8 (2) , #P2.02
The extremal generalised Randić index for a given degree range
The Art of Discrete and Applied Mathematics (ADAM) is a modern, dynamic, platinum open access, electronic journal that will publish high-quality articles of arbitrary length in contemporary discrete and applied mathematics in which neither the authors nor the readers incur any costs.
- 12 March 2025
- Published by University of Primorska Press in The Art of Discrete and Applied Mathematics
- Vol. 8 (2) , #P2.02
Open AccessThe extremal generalised Randić index for a given degree range
The Art of Discrete and Applied Mathematics (ADAM) is a modern, dynamic, platinum open access, electronic journal that will publish high-quality articles of arbitrary length in contemporary discrete and applied mathematics in which neither the authors nor the readers incur any costs.
- Open Access
- 1 January 2025
- Published by Institute of Mathematical Statistics in Electronic Communications in Probability
- Vol. 30 (none) , 1-4
Lonely passengers: A short proof
A fixed number of passengers independently board one of several buses uniformly at random. The lonely passenger problem is to prove that the probability of at least one passenger being the only one in their bus is increasing in the number of buses. It was solved in a strong form by Imre Péter Tóth, who proved stochastic dominance of the number of such passengers as the number of buses increases, but observed that, surprisingly, no short proof was known “despite the efforts of several experts”. We give a very short proof of the weaker result. The proof of the strong form, using the same idea, is more involved but still relatively short.
- 1 January 2025
- Published by Institute of Mathematical Statistics in Electronic Communications in Probability
- Vol. 30 (none) , 1-4
Open AccessLonely passengers: A short proof
A fixed number of passengers independently board one of several buses uniformly at random. The lonely passenger problem is to prove that the probability of at least one passenger being the only one in their bus is increasing in the number of buses. It was solved in a strong form by Imre Péter Tóth, who proved stochastic dominance of the number of such passengers as the number of buses increases, but observed that, surprisingly, no short proof was known “despite the efforts of several experts”. We give a very short proof of the weaker result. The proof of the strong form, using the same idea, is more involved but still relatively short.
- Open Access
- 1 October 2024
- Published by Elsevier in European Journal of Combinatorics
- Vol. 124
Boundary rigidity of 3D CAT(0) cube complexes
- 1 October 2024
- Published by Elsevier in European Journal of Combinatorics
- Vol. 124
Open AccessBoundary rigidity of 3D CAT(0) cube complexes
- Open Access
The extremal generalised Randić index for a given degree range
O and Shi proved that the Randić index of any graph $G$ with minimum degree at least $δ$ and maximum degree at most $Δ$ is at least $\frac{\sqrt{δΔ}}{δ+Δ}|G|$, with equality if and only if the graph is $(δ,Δ)$-biregular. In this note we give a short proof via a more general statement. We apply the latter to classify the graphs in any given degree range which minimise (or maximise) the generalised Randić index for any exponent, and describe the transitions between different types of behaviour precisely.Open AccessThe extremal generalised Randić index for a given degree range
O and Shi proved that the Randić index of any graph $G$ with minimum degree at least $δ$ and maximum degree at most $Δ$ is at least $\frac{\sqrt{δΔ}}{δ+Δ}|G|$, with equality if and only if the graph is $(δ,Δ)$-biregular. In this note we give a short proof via a more general statement. We apply the latter to classify the graphs in any given degree range which minimise (or maximise) the generalised Randić index for any exponent, and describe the transitions between different types of behaviour precisely. - Open Access
Tight Bounds on the Chromatic Edge Stability Index of Graphs
The chromatic edge stability index $\mathrm{es}_{\chi'}(G)$ of a graph $G$ is the minimum number of edges whose removal results in a graph with smaller chromatic index. We give best-possible upper bounds on $\mathrm{es}_{\chi'}(G)$ in terms of the number of vertices of degree $\Delta(G)$ (if $G$ is Class 2), and the numbers of vertices of degree $\Delta(G)$ and ${\Delta(G)-1}$ (if $G$ is Class 1). If $G$ is bipartite we give an exact expression for $\mathrm{es}_{\chi'}(G)$ involving the maximum size of a matching in the subgraph induced by vertices of degree $\Delta(G)$. Finally, we consider whether a minimum mitigating set, that is a set of size $\mathrm{es}_{\chi'}(G)$ whose removal reduces the chromatic index, has the property that every edge meets a vertex of degree at least $\Delta(G)-1$; we prove that this is true for some minimum mitigating set of $G$, but not necessarily for every minimum mitigating set of $G$.Open AccessTight Bounds on the Chromatic Edge Stability Index of Graphs
The chromatic edge stability index $\mathrm{es}_{\chi'}(G)$ of a graph $G$ is the minimum number of edges whose removal results in a graph with smaller chromatic index. We give best-possible upper bounds on $\mathrm{es}_{\chi'}(G)$ in terms of the number of vertices of degree $\Delta(G)$ (if $G$ is Class 2), and the numbers of vertices of degree $\Delta(G)$ and ${\Delta(G)-1}$ (if $G$ is Class 1). If $G$ is bipartite we give an exact expression for $\mathrm{es}_{\chi'}(G)$ involving the maximum size of a matching in the subgraph induced by vertices of degree $\Delta(G)$. Finally, we consider whether a minimum mitigating set, that is a set of size $\mathrm{es}_{\chi'}(G)$ whose removal reduces the chromatic index, has the property that every edge meets a vertex of degree at least $\Delta(G)-1$; we prove that this is true for some minimum mitigating set of $G$, but not necessarily for every minimum mitigating set of $G$. - Open Access
- 21 December 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (4)
Tight bounds on the chromatic edge stability index of graphs
- 21 December 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (4)
Open AccessTight bounds on the chromatic edge stability index of graphs
- Open Access
- 31 August 2023
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 163, 233-255
Determining triangulations and quadrangulations by boundary distances
- 31 August 2023
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 163, 233-255
Open AccessDetermining triangulations and quadrangulations by boundary distances