Source author record

Ross Atkins

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT Data Structures and Algorithms

Catalog footprint

Research overview

4works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Betweenness and Nonbetweenness

The betweenness function $bet(n)$ is the minimum number of total orderings of $n$ objects such that for any three distinct objects $a$ , $b$ and $c$ , there is an ordering in which $b$ is between $a$ and $c$ . The nonbetweenness function $nbet(n)$ is the minimum number of total orderings such that for any three distinct objects $a$ , $b$ and $c$ , there is an ordering in which $b$ is not between $a$ and $c$ . We show that $nbet(n) = \left\lceil \log_2\log_2n \right\rceil+1$ and $bet(n) = Θ(\log n)$ . Betweenness and Nonbetweenness are specific cases of a more general extreme value function called the `extreme ternary constraint function'. The asymptotic value of this generalisation is computed using the values of $nbet(n)$ and $bet(n)$ . This result demonstrates that the minimum size of a set of rooted phylogenetic trees is consistent with all phylogenetic triplets is $Θ(\log\log n)$ .

preprint2016arXiv

Guessing Numbers of Odd Cycles

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. An upper bound for the guessing number of the $n$ -vertex cycle graph $C_n$ is $n/2$ . It is known that the guessing number equals $n/2$ whenever $n$ is even or $s$ is a perfect square \cite{Christofides2011guessing}. 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 $C_n$ with $s$ colours is $(n-1)/2 + \log_s(a)$ . This answers a question posed by Christofides and Markström in 2011 \cite{Christofides2011guessing}. We also present an explicit protocol which achieves this bound for every $n$ . Linking this to index coding with side information, we deduce that the information defect of $C_n$ with $s$ colours is $(n+1)/2 - \log_s(a)$ for sufficiently large odd $n$ . Our results are a generalisation of the $s=2$ case which was proven in \cite{bar2011index}.

preprint2016arXiv

The Information Flow Problem on Clock Networks

The information flow problem on a network asks whether $r$ senders, $v_1,v_2, \ldots ,v_r$ can each send messages to $r$ corresponding receivers $v_{n+1}, \ldots ,v_{n+r}$ via intermediate nodes $v_{r+1}, \ldots ,v_n$ . For a given finite $R \subset \mathbb{Z}^+$ , the clock network $N_n(R)$ has edge $v_iv_k$ if and only if $k>r$ and $k-i \in R$ . We show that the information flow problem on $N_n(\{1,2, \ldots ,r\})$ can be solved for all $n \geq r$ . We also show that for any finite $R$ such that $\gcd(R)=1$ and $r = \max(R)$ , we show that the information flow problem can be solved on $N_n(R)$ for all $n \geq 3r^3$ .

preprint2015arXiv

Extremal Distances for Subtree Transfer Operations in Binary Trees

Three standard subtree transfer operations for binary trees, used in particular for phylogenetic trees, are: tree bisection and reconnection ( $TBR$ ), subtree prune and regraft ( $SPR$ ) and rooted subtree prune and regraft ( $rSPR$ ). For a pair of leaf-labelled binary trees with $n$ leaves, the maximum number of such moves required to transform one into the other is $n-Θ(\sqrt{n})$ , extending a result of Ding, Grunewald and Humphries. We show that if the pair is chosen uniformly at random, then the expected number of moves required to transfer one into the other is $n-Θ(n^{2/3})$ . These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ross Atkins

Research overview

Is this your work?

4 publications

Betweenness and Nonbetweenness

Guessing Numbers of Odd Cycles

The Information Flow Problem on Clock Networks

Extremal Distances for Subtree Transfer Operations in Binary Trees

See the researcher in context

Building this map preview