Fiona Skerman

Masaryk University

I am currently a postdoc with Dan Kral' at Masaryk University. Before that I was in Uppsala Universitet and also held a position 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 the likely degree sequences in random bipartite graphs [thesis].

ALEA Young Workshop

Here are the lecture notes for course in Random Graphs, Thresholds and Phase transitions. These will be updated during the course.

Publications and preprints

Modularity of Erdos-Renyi random graphs

with Colin McDiarmid; Submitted, conference version accepted to AofA 2018.
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).
[AofA] [arXiv] [pdf]

The parameterised complexity of computing the maximum modularity of a graph

with Kitty Meeks; accepted to IPEC 2018.
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 G.
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.

Random tree recursions: which fixed points correspond to tangible sets of trees?

with Toby Johnson and Moumanti Podder;
figure We 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? [arXiv] [pdf]

Permutations in binary trees and split trees

with Michael Albert, Cecilia Holmgren and Tony Johansson; Submitted, conference version accepted to AofA 2018.
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$. [AofA][arXiv] [pdf]

Cutting resilient networks

with Xing Shi Cai, Cecilia Holmgren and Luc Devroye;
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. [arXiv] [pdf]

Inversions in split trees and conditional Galton--Watson trees

with Xing Shi Cai, Cecilia Holmgren, Svante Janson and Tony Johansson.
Combinatorics, Probability and Computing, to appear; conference version accepted to AofA 2018.
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.
[AofA][arXiv] [pdf]

Modularity of regular and treelike graphs

with Colin McDiarmid; Oxford Journal of Complex Networks (6) 4 (2018)
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.
[journal] [arXiv] [pdf]

Guessing Numbers of Odd Cycles

with Ross Atkins and Puck Rombach; Electronic Journal of Combinatorics 24:1 (2017)
W3Schools 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. [journal] [arXiv] [pdf]
Degree sequences of random digraphs and bipartite graphs
with Brendan McKay; Journal of Combinatorics 7:1 (2016)
W3Schools 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. This problem can alternatively be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can also be cast as a problem in random hypergraphs, or as a classical occupancy, allocation, or coupon collection problem.

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. [journal] [arXiv] [pdf]

Avoider-Enforcer Star Games

with Andrzej Grzesik, Mirjana Mikalacki, Zoltan Nagy, Alon Naor, Balazs Patkos;
Discrete Mathematics and Theoretical Computer Science 17:1 (2015), pp. 145-160
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. [journal] [arXiv]

Modularity in random regular graphs and lattices

with Colin McDiarmid; Electronic Notes in Discrete Mathematics 43 (2013) pp. 431-437
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)$.