Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReconstructing trees from small cards
90
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The $ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $ell$ vertices. In 1976, Giles proved that any tree on $ngeq 6$ vertices can be reconstructed from its $ell$-deck for $ell geq n-2$. Our main theorem states that it is enough to have $ellgeq (8/9+o(1))n$, making substantial progress towards a conjecture of Nydl from 1990. In addition, we can recognise connectedness from the $ell$-deck if $ellgeq 9n/10$, and reconstruct the degree sequence from the $ell$-deck if $ellge sqrt{2nlog(2n)}$. All of these results are significant improvements on previous bounds.
rate research
Read More
In this paper we study the minimum number of reversals needed to transform a unicellular fatgraph into a tree. We consider reversals acting on boundary components, having the natural interpretation as gluing, slicing or half-flipping of vertices. Our main result is an expression for the minimum number of reversals needed to transform a unicellular fatgraph to a plane tree. The expression involves the Euler genus of the fatgraph and an additional parameter, which counts the number of certain orientable blocks in the decomposition of the fatgraph. In the process we derive a constructive proof of how to decompose non-orientable, irreducible, unicellular fatgraphs into smaller fatgraphs of the same type or trivial fatgraphs, consisting of a single ribbon. We furthermore provide a detailed analysis how reversals affect the component-structure of the underlying fatgraphs. Our results generalize the Hannenhalli-Pevzner formula for the reversal distance of signed permutations.
For non-negative integers $n$ and $k$ with $n ge k$, a {em $k$-minor} of a partition $lambda = [lambda_1, lambda_2, dots]$ of $n$ is a partition $mu = [mu_1, mu_2, dots]$ of $n-k$ such that $mu_i le lambda_i$ for all $i$. The multiset $widehat{M}_k(lambda)$ of $k$-minors of $lambda$ is defined as the multiset of $k$-minors $mu$ with multiplicity of $mu$ equal to the number of standard Young tableaux of skew shape $lambda / mu$. We show that there exists a function $G(n)$ such that the partitions of $n$ can be reconstructed from their multisets of $k$-minors if and only if $k le G(n)$. Furthermore, we prove that $lim_{n rightarrow infty} G(n)/n = 1$ with $n-G(n) = O(n/log n)$. As a direct consequence of this result, the irreducible representations of the symmetric group $S_n$ can be reconstructed from their restrictions to $S_{n-k}$ if and only if $k le G(n)$ for the same function $G(n)$. For a minor $mu$ of the partition $lambda$, we study the excitation factor $E_mu (lambda)$, which appears as a crucial part in Naruses Skew-Shape Hook Length Formula. We observe that certain excitation factors of $lambda$ can be expressed as a $mathbb{Q}[k]$-linear combination of the elementary symmetric polynomials of the hook lengths in the first row of $lambda$ where $k = lambda_1$ is the number of cells in the first row of $lambda$.
This paper completely characterizes the standard Young tableaux that can be reconstructed from their sets or multisets of $1$-minors. In particular, any standard Young tableau with at least $5$ entries can be reconstructed from its set of $1$-minors.
The modular decomposition of a symmetric map $deltacolon Xtimes X to Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $delta$ in labeled trees. A map $delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $delta(x,y)=t(mathrm{lca}(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by extended hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $delta$. We argue that the resulting tree-like median graphs may be of use in phylogenetics as a model of evolutionary relationships.
In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from computational biology, data protection, and computer security settings, which can be abstracted in terms of two parties, a responder, Alice, who must correctly answer queries of a given type regarding a degree-d tree, T, and a querier, Bob, who issues batches of queries, with each query in a batch being independent of the others, so as to eventually infer the structure of T. We show that a querier can efficiently reconstruct an n-node degree-d tree, T, with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries, including relative-distance queries and path queries. Our results are all asymptotically optimal and improve the asymptotic (sequential) query complexity for one of the problems we study. Moreover, through an experimental analysis using both real-world and synthetic data, we provide empirical evidence that our algorithms provide significant parallel speedups while also improving the total query complexities for the problems we study.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
