Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCaterpillars on three and four leaves are sufficient to reconstruct normal networks
63
0
0.0
(
0
)
Added by
Charles Semple
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
While every rooted binary phylogenetic tree is determined by its set of displayed rooted triples, such a result does not hold for an arbitrary rooted binary phylogenetic network. In particular, there exist two non-isomorphic rooted binary temporal normal networks that display the same set of rooted triples. Moreover, without any structural constraint on the rooted phylogenetic networks under consideration, similarly negative results have also been established for binets and trinets which are rooted subnetworks on two and three leaves, respectively. Hence, in general, piecing together a rooted phylogenetic network from such a set of small building blocks appears insurmountable. In contrast to these results, in this paper, we show that a rooted binary normal network is determined by its sets of displayed caterpillars (particular type of subtrees) on three and four leaves. The proof is constructive and realises a polynomial-time algorithm that takes the sets of caterpillars on three and four leaves displayed by a rooted binary normal network and, up to isomorphism, reconstructs this network.
rate research
Read More
This paper deals with the so-called Stanley conjecture, which asks whether they are non-isomorphic trees with the same symmetric function generalization of the chromatic polynomial. By establishing a correspondence between caterpillars trees and integer compositions, we prove that caterpillars in a large class (we call trees in this class proper) have the same symmetric chromatic function generalization of the chromatic polynomial if and only if they are isomorphic.
Let $p(m)$ (respectively, $q(m)$) be the maximum number $k$ such that any tree with $m$ edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with $k$ edges. We derive closed-form expressions for $p(m)$ and $q(m)$ for all $m ge 1$. The two functions $p(n)$ and $q(n)$ can also be interpreted in terms of alternating paths among $n$ disjoint line segments in the plane, whose $2n$ endpoints are in convex position.
We show that a Boolean degree $d$ function on the slice $binom{[n]}{k} = { (x_1,ldots,x_n) in {0,1} : sum_{i=1}^n x_i = k }$ is a junta, assuming that $k,n-k$ are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube. Moreover, we show that the maximum number of coordinates that a Boolean degree $d$ function can depend on is the same on the slice and the hypercube.
We show that if $fcolon S_n to {0,1}$ is $epsilon$-close to linear in $L_2$ and $mathbb{E}[f] leq 1/2$ then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $fcolon S_n to mathbb{R}$ is linear, $Pr[f otin {0,1}] leq epsilon$, and $Pr[f = 1] leq 1/2$, then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $fcolon S_n to mathbb{R}$ is linear and $epsilon$-close to ${0,1}$ in $L_infty$ then $f$ is $O(epsilon)$-close in $L_infty$ to a union of disjoint cosets.
Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying m <= d <= M. A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
