Fiona Skerman

Bristol University

I am currently a Heilbronn Research Fellow at Bristol University. Before this I was a postdoc with Dan Kráľ at Masaryk University, with Cecilia Holmgran at Uppsala University and with the Heilbronn Institute at Bristol University. My DPhil with Colin McDiarmid researched the modularity of networks and for which I was awarded the Corcoran Memorial Prize for the best thesis in the Oxford Statistics Department [thesis].

Before coming to Oxford, I did my honours thesis with Brendan McKay at the Australian National University, looking at likely degree sequences in random bipartite graphs [thesis].


ALEA Young Workshop Normandy 2019

Here are the lecture notes and the exercises for course in Random Graphs, Thresholds and Phase transitions.


Preprints

Click on arrows to expand.

Assigning times to minimise reachability in temporal graphs with Kitty Meeks and Jess Enright;
Submitted. [arXiv] [pdf]

figure Temporal graphs, in which edges are active at specified times, are of relevance for spreading processes on graphs. In our setting the number of active times for each edge is fixed, but we can change the relative order in which (sets of) edges are active. We investigate the problem of determining an ordering of edges that minimises the maximum number of vertices reachable from any single starting vertex. Epidemiologically, this corresponds to the worst-case number of vertices infected in a single disease outbreak.

Permutations in binary trees and split trees with Michael Albert, Cecilia Holmgren and Tony Johansson;
Submitted + conference Analysis of Algorithms (2018). [AofA] [arXiv] [pdf]

figure Given a tree on $n$ vertices, we randomly label the vertices 1 to $n$. An occurence of a length $k$ permutation $\sigma$ is a sequence of vertices on a common descending path in the tree whose labels, when read from root to leaf, are ordered according to $\sigma$. We calculate the number of occurences of fixed length permutations in binary trees and split trees. For the trees considered, this generalizes the inversion results below from $\sigma=21$ to more general permutations $\sigma$.


Publications and accepted manuscripts

Do not hesitate to email if you have trouble accessing any of the manuscripts listed below.

The parameterised complexity of computing the maximum modularity of a graph with Kitty Meeks;
Algorithmica: accepted + conference International Symposium on Parameterized & Exact Computation (2018). [IPEC] [arXiv] [pdf]

figure Determining the maximum modularity of a graph is known to be NP-complete in general, even to find a multiplicative approximation, but we show it has reduced complexity with respect to some structural parameterisations of the input graph.

On the other hand we prove modularity is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.

Modularity of Erdos-Renyi random graphs with Colin McDiarmid;
Random Structures and Algorithms: accepted + conference Analysis of Algorithms (2018). [AofA] [arXiv] [pdf]

figure Modularity introduced by Newman and Girvan (in this paper) is a popular metric in community detection.
Two key features which we find for Erdos-Renyi random graphs are that the modularity is $1+o(1)$ with high probability (whp) for $np$ up to $1+o(1)$ (and no further); and when $np\geq 1$ and $p$ is bounded below 1, it has order $(np)^{-1/2}$ whp, in accord with a conjecture by Reichardt and Bornholdt in 2006 (and disproving another conjecture from the physics literature).

Random tree recursions: which fixed points correspond to tangible sets of trees? with Toby Johnson and Moumanti Podder;
Random Structures and Algorithms: accepted [arXiv] [pdf]
figureWe answer the following question of Joel Spencer:
Say that a set of trees $\mathcal{B}$ follows the at-least-two rule if $t \in \mathcal{B}$ if and only if the root of $t$ has two children $u$ and $v$ such that the subtrees rooted at $u$ and $v$ are also in $\mathcal{B}$. Suppose that $\lambda > \lambda_{crit}$. Does there exist a set of trees $\mathcal{B}$ with this metaproperty such that for random tree $T_\lambda$, we have that $\mathbb{P}[T_\lambda \in \mathcal{B}]$ is the middle solution of the classical fixed point equation?

$k$ cuts on paths and some trees with Xing Shi Cai, Cecilia Holmgren and Luc Devroye;
Electronic Journal of Probability 24 (2019) [journal] [arXiv] [pdf]

figure We define a new cutting process on trees the `blunt scissors' or $k$-cut model where each node must be cut $k$ times before it is destroyed. For $k=1$ this is the model of Meir and Moon. This paper studies the distribution of the $k$-cut number of a path on $n$ vertices.

Inversions in split trees and Galton-Watson trees with Xing Shi Cai, Cecilia Holmgren, Svante Janson and Tony Johansson.
Combinatorics, Probability and Computing 28:3 (2019) + conference Analysis of Algorithms (2018). [journal] [AofA] [arXiv] [pdf]

figure 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 the cumulants of $I(T)$ have explicit formulas involving the $k$-total common ancestors of $T$ (an extension of the total path length). For three sequence of trees $T_n$ we consider $X_n$ the normalized version of $I(T_n)$.
We identify the limit of $X_n$ for complete $b$-ary trees. For $T_n$ being split trees, we show that $X_n$ converges to the unique solution of a distributional equation and when $T_n$’s are conditional Galton–Watson trees, we show that $X_n$ converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we extend earlier results by Panholzer and Seitz.

Modularity of regular and treelike graphs with Colin McDiarmid;
Oxford Journal of Complex Networks (6) 4 (2018) [journal] [arXiv] [pdf]

figure Modularity introduced by Newman and Girvan (in this paper) is a popular metric in community detection.
We show that random cubic graphs usually have modularity in the interval (0.666, 0.804); and random $r$-regular graphs for large $r$ usually have modularity $\Theta(1/\sqrt{r})$. Our results give thresholds for the statistical significance of clustering found in large regular networks.
The modularity of cycles and low degree trees is known to be asymptotically 1. We extend these results to all graphs whose product of treewidth and maximum degree is much less than the number of edges. This shows for example that random planar graphs typically have modularity close to 1.

Guessing Numbers of Odd Cycles with Ross Atkins and Puck Rombach;
Electronic Journal of Combinatorics 24:1 (2017) [journal] [arXiv] [pdf]

protocol For a given number of colours, $s$, the guessing number of a graph is the base $s$ logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. We show that, for any given integer $s \geq 2$, if $a$ is the largest factor of $s$ less than or equal to $\sqrt{s}$, for sufficiently large odd $n$, the guessing number of the cycle $C_n$ with $s$ colours is $(n -1)/2 + \log_s (a)$. This answers a question posed in this paper by Christofides and Markstrom in 2011.

Degree sequences of random digraphs and bipartite graphs with Brendan McKay;
Journal of Combinatorics 7:1 (2016) [journal] [arXiv] [pdf]

bipartitepng We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a specified number of edges, or specify the vertex degrees in one of the two colour classes.

In each case, provided the two colour classes are not too different in size nor the number of edges too low, we define a probability space based on independent binomial variables and show that its probability masses asymptotically equal those of the degrees in the graph model almost everywhere. The accuracy is sufficient to asymptotically determine the expectation of any joint function of the degrees whose maximum is at most polynomially greater than its expectation.


Avoider-Enforcer Star Games with Andrzej Grzesik, Mirjana Mikalacki, Zoltan Nagy, Alon Naor, Balazs Patkos;
Discrete Mathematics and Theoretical Computer Science 17:1 (2015) [journal] [arXiv]

In this paper, we study $(1 : b)$ Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant $k \geq 3$ we analyse the $k$-star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We consider both versions of Avoider-Enforcer games - the strict and the monotone - and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases $f_\mathcal{F}^{mon}$, $f_\mathcal{F}^{-}$ and $f_\mathcal{F}^{+}$, where $\mathcal{F}$ is the hypergraph of the game.


Modularity in random regular graphs and lattices with Colin McDiarmid;
Electronic Notes in Discrete Mathematics 43 (2013) [journal]

W3Schools Given a graph $G$, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of $G$ is the maximum modularity of a partition.
We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random $r$-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval $(0.66, 0.88)$.