Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCompatibility of Partitions, Hierarchies, and Split Systems
78
0
0.0
(
0
)
Added by
Marc Hellmuth
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The question whether a partition $mathcal{P}$ and a hierarchy $mathcal{H}$ or a tree-like split system $mathfrak{S}$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $mathcal{P}$ coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $mathcal{H}$ or $mathfrak{S}$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $mathcal{P}$ are compatible. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (sets of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a set of partitions is considered instead of a single partition. We finally explore the close relationship of the concept of compatibility and so-called Fitch maps.
rate research
Read More
For an integer $ellgeqslant 2$, the $ell$-component connectivity of a graph $G$, denoted by $kappa_{ell}(G)$, is the minimum number of vertices whose removal from $G$ results in a disconnected graph with at least $ell$ components or a graph with fewer than $ell$ vertices. This is a natural generalization of the classical connectivity of graphs defined in term of the minimum vertex-cut and is a good measure of robustness for the graph corresponding to a network. So far, the exact values of $ell$-connectivity are known only for a few classes of networks and small $ell$s. It has been pointed out in~[Component connectivity of the hypercubes, Int. J. Comput. Math. 89 (2012) 137--145] that determining $ell$-connectivity is still unsolved for most interconnection networks, such as alternating group graphs and star graphs. In this paper, by exploring the combinatorial properties and fault-tolerance of the alternating group graphs $AG_n$ and a variation of the star graphs called split-stars $S_n^2$, we study their $ell$-component connectivities. We obtain the following results: (i) $kappa_3(AG_n)=4n-10$ and $kappa_4(AG_n)=6n-16$ for $ngeqslant 4$, and $kappa_5(AG_n)=8n-24$ for $ngeqslant 5$; (ii) $kappa_3(S_n^2)=4n-8$, $kappa_4(S_n^2)=6n-14$, and $kappa_5(S_n^2)=8n-20$ for $ngeqslant 4$.
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $kgeq 1$, a $k$-district map of $G$ is a partition of $V(G)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is NP-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial length is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that takes a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.
In recent work, M. Schneider and the first author studied a curious class of integer partitions called sequentially congruent partitions: the $m$th part is congruent to the $(m+1)$th part modulo $m$, with the smallest part congruent to zero modulo the number of parts. Let $p_{mathcal S}(n)$ be the number of sequentially congruent partitions of $n,$ and let $p_{square}(n)$ be the number of partitions of $n$ wherein all parts are squares. In this note we prove bijectively, for all $ngeq 1,$ that $p_{mathcal S}(n) = p_{square}(n).$ Our proof naturally extends to show other exotic classes of partitions of $n$ are in bijection with certain partitions of $n$ into $k$th powers.
Let $G$ be a graph(directed or undirected) having $k$ number of blocks. A $mathcal{B}$-partition of $G$ is a partition into $k$ vertex-disjoint subgraph $(hat{B_1},hat{B_1},hdots,hat{B_k})$ such that $hat{B}_i$ is induced subgraph of $B_i$ for $i=1,2,hdots,k.$ The terms $prod_{i=1}^{k}det(hat{B}_i), prod_{i=1}^{k}text{per}(hat{B}_i)$ are det-summands and per-summands, respectively, corresponding to the $mathcal{B}$-partition. The determinant and permanent of a graph having no loops on its cut-vertices is equal to summation of det-summands and per-summands, respectively, corresponding to all possible $mathcal{B}$-partitions. Thus, in this paper we calculate determinant and permanent of some graphs, which include block graph with negatives cliques, signed unicyclic graph, mix complete graph, negative mix complete graph, and star mix block graphs.
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in one single theorem. While this unification process is definitely good, their main theorem remains quite technical and does not give a real insight of why some decompositions admit dual objects and why others do not. The goal of this paper is both to generalise a little this framework and to give an enlightening simple proof of its central theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
