T. Johansson

activity

20142020

most citedInversions in split trees and conditional Galton--Watson trees

5 citations · 8 across the 6 of their papers we have counts for

collaborators

12 papers

math.CO2020

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

Tony Johansson

Given a symmetric $n \times n$ matrix $P$ with $0 \leq P (u, v) \leq 1$ , we define a random graph $G_{n, P}$ on $[n]$ by independently including any edge ${u, v}$ with probability $P(…

math.CO2020★ 1 cited

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

Tony Johansson

We consider the random graph $G_{n, d}$ chosen uniformly at random from the set of all graphs with a given sparse degree sequence $d$ . We assume $d$ has minimum d…

math.PR2019

Embedding small digraphs and permutations in binary trees and split trees

Michael Albert, Cecilia Holmgren, Tony Johansson +1

We investigate the number of permutations that occur in random labellings of trees. This is a generalisation of the number of subpermutations occurring in a random permutation. It…

math.CO2018★ 1 cited

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

Tony Johansson

Given a graph $Γ = (V, E)$ on $n$ vertices and $m$ edges, we define the Erdős-Rényi graph process with host $Γ$ as follows. A permutation $e_{1}, \dots, e_{m}$ of $E$ is chosen uniformly…

math.CO2018

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

Tony Johansson

We consider a random walk process which prefers to visit previously unvisited edges, on the random $r$ -regular graph $G_{r}$ for any odd $r \geq 3$ . We show that this random walk proc…

math.CO2018

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

Colin Cooper, Alan Frieze, Tony Johansson

We study a random walk that prefers tou se unvisited edges in the context of random cubic graphs. We establish asymptotically correct estimates for the vertex and edge cover times,…

math.PR2017★ 5 cited

Inversions in split trees and conditional Galton--Watson trees

Xing Shi Cai, Cecilia Holmgren, Svante Janson +2

We study $I (T)$ , the number of inversions in a tree $T$ with its vertices labeled uniformly at random, which is a generalization of inversions in permutations. We first show that t…

math.CO2016★ 1 cited

Deletion of oldest edges in a preferential attachment graph

Tony Johansson

We consider a variation on the Barabási-Albert random graph process with fixed parameters $m \in N$ and $1/2 < p < 1$ . With probability $p$ a vertex is added along with $m$ …

cs.DS2016

On the insertion time of random walk cuckoo hashing

Alan Frieze, Tony Johansson

Cuckoo Hashing is a hashing scheme invented by Pagh and Rodler. It uses $d \geq 2$ distinct hash functions to insert items into the hash table. It has been an open question for some…

math.CO2015

On edge disjoint spanning trees in a randomly weighted complete graph

Alan Frieze, Tony Johansson

Assume that the edges of the complete graph $K_{n}$ are given independent uniform $[0, 1]$ edges weights. We consider the expected minimum total weight $μ_{k}$ of $k \geq 2$ edge disjoin…

math.CO2015

Minimum-cost matching in a random graph with random costs

Alan Frieze, Tony Johansson

Let $G_{n, p}$ be the standard Erdős-Rényi-Gilbert random graph and let $G_{n, n, p}$ be the random bipartite graph on $n + n$ vertices, where each $e \in [n]^{2}$ appears as an edge indep…

math.CO2014

On random k-out sub-graphs of large graphs

Alan Frieze, Tony Johansson

We consider random sub-graphs of a fixed graph $G = (V, E)$ with large minimum degree. We fix a positive integer $k$ and let $G_{k}$ be the random sub-graph where each $v \in V$ independ…