Search

The theory of flows was used as a crucial tool in the recent proof by Margolis, Rhodes and Schilling that Krohn-Rhodes complexity is decidable. In this paper we begin a systematic study of aperiodic flows. We give the foundations of the theory of flows and give a unified approach to the Presentation Lemma and its relations to flows and the Slice Theorem. We completely describe semigroups having a flow over the trivial semigroup and connect this to classical results in inverse semigroup theory. We reinterpret Tilson's Theorem on the complexity of small monoids in terms of flows. We conclude with examples of semigroups built from the character table of Abelian Groups that have an aperiodic flows.

The Krohn-Rhodes Theorem proves that a finite semigroup divides a wreath product of groups and aperiodic semigroups. Krohn-Rhodes complexity equals the minimal number of groups that are needed. Determining an algorithm to compute complexity has been an open problem for more than 50 years. The main result of this paper proves that it is decidable whether a semigroup has complexity k for any k greater than or equal to 0. This builds on our previous work for complexity 1. In that paper we proved using profinite methods and results on free Burnside semigroups by McCammond and others that the lower bound from a 2012 paper by Henckell, Rhodes and Steinberg is precise for complexity 1. In this paper we define an improved version of the lower bound from the 2012 paper and prove that it is exact for arbitrary complexity.

Interest in the inference of evolutionary networks relating species or populations has grown with the increasing recognition of the importance of hybridization, gene flow and admixture, and the availability of large-scale genomic data. However, what network features may be validly inferred from various data types under different models remains poorly understood. Previous work has largely focused on level-1 networks, in which reticulation events are well separated, and on a general network's tree of blobs, the tree obtained by contracting every blob to a node. An open question is the identifiability of the topology of a blob of unknown level. We consider the identifiability of the circular order in which subnetworks attach to a blob, first proving that this order is well-defined for outer-labeled planar blobs. For this class of blobs, we show that the circular order information from 4-taxon subnetworks identifies the full circular order of the blob. Similarly, the circular order from 3-taxon rooted subnetworks identifies the full circular order of a rooted blob. We then show that subnetwork circular information is identifiable from certain data types and evolutionary models. This provides a general positive result for high-level networks, on the identifiability of the ordering in which taxon blocks attach to blobs in outer-labeled planar networks. Finally, we give examples of blobs with different internal structures which cannot be distinguished under many models and data types.

When hybridization or other forms of lateral gene transfer have occurred, evolutionary relationships of species are better represented by phylogenetic networks than by trees. While inference of such networks remains challenging, several recently proposed methods are based on quartet concordance factors -- the probabilities that a tree relating a gene sampled from the species displays the possible 4-taxon relationships. Building on earlier results, we investigate what level-1 network features are identifiable from concordance factors under the network multispecies coalescent model. We obtain results on both topological features of the network, and numerical parameters, uncovering a number of failures of identifiability related to 3-cycles in the network., Comment: 27 pages + 11 pages Supplementary Materials

We study a number of topics in the theory of Boolean Representable Simplicial Complexes (BRSC). These include various operators on BRSC. We look at shellability in higher dimensions and propose a number of new conjectures.

A model of genomic sequence evolution on a species tree should include not only a sequence substitution process, but also a coalescent process, since different sites may evolve on different gene trees due to incomplete lineage sorting. Chifman and Kubatko initiated the study of such models, leading to the development of the SVDquartets methods of species tree inference. A key observation was that symmetries in an ultrametric species tree led to symmetries in the joint distribution of bases at the taxa. In this work, we explore the implications of such symmetry more fully, defining new models incorporating only the symmetries of this distribution, regardless of the mechanism that might have produced them. The models are thus supermodels of many standard ones with mechanistic parameterizations. We study phylogenetic invariants for the models, and establish identifiability of species tree topologies using them., Comment: 20 pages, 0 figures

The Akaike information criterion (AIC) is a common tool for model selection. It is frequently used in violation of regularity conditions at parameter space singularities and boundaries. The expected AIC is generally not asymptotically equivalent to its target at singularities and boundaries, and convergence to the target at nearby parameter points may be slow. We develop a generalized AIC for candidate models with or without singularities and boundaries. We show that the expectation of this generalized form converges everywhere in the parameter space, and its convergence can be faster than that of the AIC. We illustrate the generalized AIC on example models from phylogenomics, showing that it can outperform the AIC and gives rise to an interpolated effective number of model parameters, which can differ substantially from the number of parameters near singularities and boundaries. We outline methods for estimating the often unknown generating parameter and bias correction term of the generalized AIC., Comment: 21 pages, 5 figures

Diversification models describe the random growth of evolutionary trees, modeling the historical relationships of species through speciation and extinction events. One class of such models allows for independently changing traits, or types, of the species within the tree, upon which speciation and extinction rates depend. Although identifiability of parameters is necessary to justify parameter estimation with a model, it has not been formally established for these models, despite their adoption for inference. This work establishes generic identifiability up to label swapping for the parameters of one of the simpler forms of such a model, a multitype pure birth model of speciation, from an asymptotic distribution derived from a single tree observation as its depth goes to infinity. Crucially for applications to available data, no observation of types is needed at any internal points in the tree, nor even at the leaves., Comment: 16 pages

Inference of species networks from genomic data under the Network Multispecies Coalescent Model is currently severely limited by heavy computational demands. It also remains unclear how complicated networks can be for consistent inference to be possible. As a step toward inferring a general species network, this work considers its tree of blobs, in which non-cut edges are contracted to nodes, so only tree-like relationships between the taxa are shown. An identifiability theorem, that most features of the unrooted tree of blobs can be determined from the distribution of gene quartet topologies, is established. This depends upon an analysis of gene quartet concordance factors under the model, together with a new combinatorial inference rule. The arguments for this theoretical result suggest a practical algorithm for tree of blobs inference, to be fully developed in a subsequent work., Comment: 18 pages, 8 figures