Tony Johansson

Guest lecturer

Göteborgs Universitet

Gothenburg, Sweden

first.last@gu.se

Random graphs, randomized algorithms

Google Scholar page

Past Employment

Stockholm University 2019–2021
Department of Mathematical Statistics
Postdoctoral Researcher in Infectious Disease Dynamics

Uppsala University 2017–2019
Department of Mathematics
Postdoctoral Researcher in Discrete Probability

Education

Carnegie Mellon University 2013–2017
Department of Mathematics
Ph.D. in Algorithms, Combinatorics and Optimization
Ph.D. advisor: Alan Frieze
Thesis title: Random Graphs and Algorithms

Chalmers University of Technology 2008–2013
BSc, MSc, MSE in Engineering Mathematics

Teaching

arXiv preprints

Hamilton cycles in weighted Erdős-Rényi graphsarXiv

Given a symmetric matrix $P$ with values $P_{uv}\in [0, 1]$, let $G_{n, P}$ be the random graph obtained by independently including any edge $uv$ with probability $P_{uv}$. We study Hamiltonicity in this graph, mainly using an eigenvalue condition on $P$ and assumptions about fairly similar expected degrees.

A condition for Hamiltonicity in Sparse Random Graphs with a Fixed Degree SequencearXiv

For a degree sequence ${\bf d} = (d_1,\dots,d_n)$, let $G_{n, {\bf d}}$ denote the graph chosen uniformly at random from the set of (simple) graphs with degree sequence ${\bf d}$. The aim of this paper is to determine for which ${\bf d}$ the graph is Hamiltonian whp, generalizing from regular graphs to general sparse ${\bf d}$.

We show that if the minimum degree is at least 4, and a few milder conditions on ${\bf d}$ hold, then the problem boils down to determining the sign of the parameter $$\beta_2(G_{n, {\bf d}}) = \max_{A\cap B = \emptyset} e(A, B) + 2(|A| - |B|) - d(A).$$ If this is positive then there is no Hamilton cycle, and if it is at most $-\theta n$ for some $\theta > 0$, then at least one exists. Determining the value of $\beta_2(G_{n, {\bf d}})$ is left open.

Deletion of oldest edges in a preferential attachment grapharXiv

Slides: RSA 2017, Gniezno

We consider the Barabási-Albert preferential attachment graph with edge deletion. The graph is generated on-line, and at any time with probability $1/2 < p < 1$ add a vertex along with a constant number $m$ of edges which attach preferentially to pre-existing vertices, and with probability $1-p$ we remove the $m$ oldest edges in the graph. We calculate the degree sequence of this graph, showing that there exists a threshold $p_0 \approx 0.83113$ such that if $p > p_0$ then the degree sequence follows a power law, and if $p < p_0$ then the degree sequence decreases exponentially, regardless of $m$. We further show that if $m = 1$ then all connected components have size $o(|V|)$, and if $m \geq 2$ then there exists a unique linear-sized component, regardless of $p$.

Publications

On Hamilton cycles in Erdős-Rényi subgraphs of large graphs

Random Structures & Algorithms RSA arXiv

Suppose $\Gamma = (V, E)$ is a graph with minimum degree $\beta n$ for some $\beta > 1/2$. Starting with the empty graph $\Gamma_0 = (V,\emptyset)$, we add a random edge from $\Gamma$ to $\Gamma_{t-1}$ to form $\Gamma_t$. We show that with high probability, the smallest $t$ for which $\Gamma_t$ has minimum degree $2$ equals the smallest $t$ for which $\Gamma_t$ contains a Hamilton cycle.

This generalizes a classical result, independently proved by Ajtai–Komlós–Szemerédi and Bollobás, concerning $\Gamma = K_n$.

The cover time of a biased random walk on a random regular graph of odd degree

Electronic Journal of Combinatorics Elec. J. Comb. arXiv

Slides: RANDOM 2018, Princeton

We consider a random walk on the random $r$-regular graph for odd $r\geq 5$. This random walk moves from its current vertex along a previously unvisited edge whenever possible, and otherwise chooses a visited edge uniformly at random. The expected vertex and edge cover times are calculated by analyzing properties of the set of partially visited vertices at any given time.

The cover time of a biased random walk on a random cubic graph

Extended abstract in Proceedings of AofA 2018 AofA arXiv

With Alan Frieze and Colin Cooper

Slides: AofA 2018, Uppsala

See the similarly titled paper above. In this one we cover the case $r = 3$.

Permutations in binary trees and split trees

Algorithmica Algorithmica arXiv

Note: the AofA version contains errors. The corrected version is on ArXiV and has been submitted for review.

With Michael Albert, Cecilia Holmgren and Fiona Skerman

Given a tree on $n$ vertices, we randomly label the vertices $1$ through $n$. An occurence of a $k$-length permutation $\pi$ is a sequence of $k$ vertices on a common descending path whose labels, when read from root to leaf, are ordered according to $\pi$. We calculate the number of occurences of certain short permutations in binary trees and split trees.

For the trees considered, this generalizes the inversion results below from $\pi = 21$ to more general permutations $\pi$.

Inversions in split trees and conditional Galton–Watson trees

Combinatorics, Probability and Computing; extended abstract in Proceedings of AofA 2018 CPC AofA arXiv

With Xing Shi Cai, Cecilia Holmgren, Svante Janson and Fiona Skerman

Given a tree on $n$ vertices, we randomly label the vertices $1$ through $n$. An inversion is a pair of vertices $u, v$ where $u$ is a descendant of $v$ and $u$ receives a label greater than that of $v$. We calculate the number of inversions in split trees and conditional Galton–Watson trees, as well as some classes of fixed trees.

On the insertion time of random walk cuckoo hashing

Random Structures and Algorithms; Proceedings of SODA 2017 RSA SODA arXiv

With Alan Frieze

Slides: SODA 2017, Barcelona

We consider a bipartite graph on vertex sets $L, R$ where $L = \{x_1,\dots,x_m\}$ and $R = \{y_1,\dots,y_n\}$, $m\leq n$. The vertices of $L$ are presented one by one, and each $v\in L$ has $d$ random neighbours $h_1(v), \dots, h_d(v)$ in $R$. Assuming there is a matching $M_{k-1}$ of $\{x_1,\dots,x_{k-1}\}$ into $R$, we extend the matching as follows. The vertex $x_k$ is matched to one of $h_1(x_k),\dots,h_d(x_k)$, chosen uniformly at random, call that vertex $y$. If $y$ is already covered by $M_{k-1}$, say by the edge $x'y$, we remove that edge from $M_{k-1}$ and match $x'$ to one of $h_1(x'),\dots,h_d(x')$ uniformly at random. Continuing until there is no conflict, we effectively build $M_k$ from $M_{k-1}$ by a random augmenting path.

We show that if $m = (1-\varepsilon)n$ for some $\varepsilon > 0$ and $d = \Omega(1/\varepsilon)$ is large enough, then the expected length of the augmenting path is constant.

On random $k$-out sub-graphs of large graphs

Random Structures and Algorithms RSA arXiv

With Alan Frieze

Given a host graph $G$ on $n$ vertices and a fixed integer $k$, we define the random $k$-out subgraph of $G$ as follows. Each vertex of $G$ protects $k$ of its incident edges, chosen uniformly at random and independently. After removing all unprotected edges, the resulting graph $G_k$ is the random $k$-out subgraph of $G$. We show that if the minimum degree $\delta(G)$ is at least $(1/2 + \varepsilon)n$ for some constant $\varepsilon > 0$, then with high probability $G_k$ is $k$-connected, and if $k$ is large enough then $G_k$ is Hamiltonian with high probability. We move on to showing that if $\delta(G) \geq m$ for some $m$ which tends to infinity with $n$, and $k$ is large enough, then with high probability $G_k$ contains a cycle of length at least $(1-\varepsilon)m$.

Minimum-cost matching in a random graph with random costs

SIAM Journal on Discrete Mathematics SIDMA arXiv

With Alan Frieze

Given a graph $G$ containing a perfect matching, we independently assign exponentially distributed costs with mean $1$ to each edge of $G$. Let $C(G)$ denote the expected minimum total cost of a perfect matching in $G$. We show that if $G_{n, n, p}$ is the bipartite Erdős-Rényi graph on $2n$ vertices then with high probability $C(G_{n, n, p}) \sim \pi^2/6p$, and if $G_{n, p}$ denotes the classical Erdős-Rényi graph then with high probability $C(G_{n, p}) \sim \pi^2 / 12p$.

This generalizes results by Johan Wästlund from $p=1$ to general $(\log n)^2 / n \ll p \leq 1$.

On edge disjoint spanning trees in a randomly weighted complete graph

Combinatorics, Probability and Computing CPC arXiv

With Alan Frieze

Each edge of the complete graph $K_n$ is independently assigned a uniformly random cost in $(0, 1)$. We consider the expected minimum total weight $\mu_k$ of $k\geq 2$ edge disjoint spanning trees. When $k$ is large we show that $\mu_k \approx k^2$. Most of the paper is concerned with calculating $\mu_2$ exactly, and we show that $\mu_2 \approx 4.1704288\dots$.

Alan Frieze previously showed that $\mu_1 \to \zeta(3)$, where $\zeta$ denotes the Riemann zeta function.

Theses

Random Graphs and AlgorithmsPDF

Doctoral Thesis, defended January 26, 2017.
Department of Mathematics, Carnegie Mellon University.

Supervisor: Alan Frieze.

This doctoral thesis is a compilation of five papers completed during my PhD: Deletion of oldest edges in a preferential attachment graph, On the insertion time of random walk cuckoo hashing, On random $k$–out sub–graphs of large graphs, Minimum–cost matching in a random graph with random costs and On edge disjoint spanning trees in a randomly weighted complete graph. These all have individual entries on this page.

The giant component of the random bipartite graphChalmers

Master's Thesis in Engineering Mathematics and Computational Science.
Defended December 7, 2012, at Chalmers University of Technology.

Supervisor: Olle Häggström.

In this Master's thesis we consider random subgraphs of the complete bipartite graph $K_{m, n}$, where $m, n$ both grow to infinity, not necessarily at similar rates. The giant component is studied under the Erdős-Rényi model, as well as a certain parameter range of the random-cluster model, which includes the Ising model as a special case.

Note that this thesis has not been subjected to peer-review.