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

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 Sequence arXiv

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 graph arXiv

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$.

---

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

Random Structures & Algorithms RSA arXiv

Slides: Probabilistic Midwinter Meeting 2019, Umeå (Pauseless version)

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.

---

Random Graphs and Algorithms PDF

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 graph Chalmers

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.

---