Source author record

Jordan Barrett

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

ResearcherUnclaimed source record

math.PR math.CO Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Finding minimum spanning trees via local improvements

We consider a family of local search algorithms for the minimum-weight spanning tree, indexed by a parameter $ρ$ . One step of the local search corresponds to replacing a connected induced subgraph of the current candidate graph whose total weight is at most $ρ$ by the minimum spanning tree (MST) on the same vertex set. Fix a non-negative random variable $X$ , and consider this local search problem on the complete graph $K_n$ with independent $X$ -distributed edge weights. Under rather weak conditions on the distribution of $X$ , we determine a threshold value $ρ^*$ such that the following holds. If the starting graph (the "initial candidate MST") is independent of the edge weights, then if $ρ> ρ^*$ local search can construct the MST with high probability (tending to $1$ as $n \to \infty$ ), whereas if $ρ< ρ^*$ it cannot with high probability.

preprint2022arXiv

Multi-source invasion percolation on the complete graph

We consider invasion percolation on the randomly-weighted complete graph $K_n$ , started from some number $k(n)$ of distinct source vertices. The outcome of the process is a forest consisting of $k(n)$ trees, each containing exactly one source. Let $M_n$ be the size of the largest tree in this forest. Logan, Molloy and Pralat (arXiv:1806.10975) proved that if $k(n)/n^{1/3} \to 0$ then $M_n/n \to 1$ in probability. In this paper we prove a complementary result: if $k(n)/n^{1/3} \to \infty$ then $M_n/n \to 0$ in probability. This establishes the existence of a phase transition in the structure of the invasion percolation forest around $k(n) \asymp n^{1/3}$ . Our arguments rely on the connection between invasion percolation and critical percolation, and on a coupling between multi-source invasion percolation with differently-sized source sets. A substantial part of the proof is devoted to showing that, with high probability, a certain fragmentation process on large random binary trees leaves no components of macroscopic size.

preprint2021arXiv

Random tree-weighted graphs

For each $n \ge 1$ , let $\mathrm{d}^n=(d^{n}(i),1 \le i \le n)$ be a sequence of positive integers with even sum $\sum_{i=1}^n d^n(i) \ge 2n$ . Let $(G_n,T_n,Γ_n)$ be uniformly distributed over the set of simple graphs $G_n$ with degree sequence $\mathrm{d}^n$ , endowed with a spanning tree $T_n$ and rooted along an oriented edge $Γ_n$ of $G_n$ which is not an edge of $T_n$ . Under a finite variance assumption on degrees in $G_n$ , we show that, after rescaling, $T_n$ converges in distribution to the Brownian continuum random tree as $n \to \infty$ . Our main tool is a new version of Pitman's additive coalescent (https://doi.org/10.1006/jcta.1998.2919), which can be used to build both random trees with a fixed degree sequence, and random tree-weighted graphs with a fixed degree sequence. As an input to the proof, we also derive a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph with a given degree sequence sampled according to the configuration model; we find this to be of independent interest.

preprint2020arXiv

The Spread of Voting Attitudes in Social Networks

The Shapley-Shubik power index is a measure of each voters power in the passage or failure of a vote. We extend this measure to graphs and consider a discrete-time process in which voters may change their vote based on the outcome of the previous vote. We use this model to study how voter influence can spread through a network. We find conditions under which a vanishingly small portion of consenting voters can change the votes of the entirety of the network. For a particular family of graphs, this process can be modelled using cellular automata. In particular, we find a connection between this process and the well-studied cellular automata, Rule 90. We use this connection to show that such processes can exhibit arbitrarily-long periods.

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.