BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ross Atkins

Ross Atkins appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COInformation Theorymath.ITData Structures and Algorithms

Catalog footprint

What is connected

4works
4topics
3close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

4 published item(s)

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

0 citations0 reviewsNo code linkedOpen access
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}.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access