Combinatorial threshold-linear networks (CTLNs) are a special class of recurrent neural networks whose dynamics are tightly controlled by an underlying directed graph. Recurrent networks have long been used as models for associative memory and pattern completion, with stable fixed points playing the role of stored memory patterns in the network. In prior work, we showed that of the graph correspond to stable fixed points of the dynamics, and we conjectured that these are the only stable fixed points possible [1, 2]. In this paper, we prove that the conjecture holds in a variety of special cases, including for networks with very strong inhibition and graphs of size . We also provide further evi-dence for the conjecture by showing that sparse graphs and graphs that are nearly cliques can never support stable fixed points. Finally, we translate some results from extremal com-binatorics to obtain an upper bound on the number of stable fixed points of CTLNs in cases where the conjecture holds.

For a fixed set containing taxon labels, an ordered pair consisting of a gene tree topology and a species tree topology bijectively labeled with the labels of possesses a set of coalescent histories-mappings from the set of internal nodes of to the set of edges of describing possible lists of edges in on which the coalescences in take place. Enumerations of coalescent histories for gene trees and species trees have produced suggestive results regarding the pairs () that, for a fixed , have the largest number of coalescent histories. We define a class of 2-cherry binary tree topologies that we term , examining coalescent histories for non-matching pairs () in the case in which has a caterpillar shape and has a -pseudocaterpillar shape. Using a construction that associates coalescent histories for () with a class of "roadblocked" monotonic paths, we identify the -pseudocaterpillar labeled gene tree topology that, for a fixed caterpillar labeled species tree topology, gives rise to the largest number of coalescent histories. The shape that maximizes the number of coalescent histories places the "second" cherry of the -pseudocaterpillar equidistantly from the root of the "first" cherry and from the tree root. A symmetry in the numbers of coalescent histories for -pseudocaterpillar gene trees and caterpillar species trees is seen to exist around the maximizing value of the parameter . The results provide insight into the factors that influence the number of coalescent histories possible for a given gene tree and species tree.

We study the distributional properties of horizontal visibility graphs associated with random restrictive growth sequences and random set partitions of size . Our main results are formulas expressing the expected degree of graph nodes in terms of simple explicit functions of a finite collection of Stirling and Bernoulli numbers.

Given a gene tree topology and a species tree topology, a coalescent history represents a possible mapping of the list of gene tree coalescences to associated branches of a species tree on which those coalescences take place. Enumerative properties of coalescent histories have been of interest in the analysis of relationships between gene trees and species trees. The simplest enumerative result identifies a bijection between coalescent histories for a matching caterpillar gene tree and species tree with monotonic paths that do not cross the diagonal of a square lattice, establishing that the associated number of coalescent histories for -taxon matching caterpillar trees ( ⩾ 2) is the Catalan number . Here, we show that a similar bijection applies for caterpillars, connecting coalescent histories for a non-matching caterpillar gene tree and species tree to a class of monotonic paths. The result provides a simplified algorithm for enumerating coalescent histories in the non-matching caterpillar case. It enables a rapid proof of a known result that given a caterpillar species tree, no non-matching caterpillar gene tree has a number of coalescent histories exceeding that of the matching gene tree. Additional results on coalescent histories can be obtained by a bijection between permissible roadblocked monotonic paths and Dyck paths. We study the number of coalescent histories for non-matching caterpillar gene trees that differ from the species tree by nearest-neighbor-interchange and subtree-prune-and-regraft moves, characterizing the non-matching caterpillar with the largest number of coalescent histories. We discuss the implications of the results for the study of the combinatorics of gene trees and species trees.

In mathematical phylogenetics, given a rooted binary leaf-labeled gene tree topology and a rooted binary leaf-labeled species tree topology with the same leaf labels, a coalescent history represents a possible mapping of the list of gene tree coalescences to the associated branches of the species tree on which those coalescences take place. For certain families of ordered pairs (), the number of coalescent histories increases exponentially or even faster than exponentially with the number of leaves . Other pairs have only a single coalescent history. We term a pair () if it has only one coalescent history. Here, we characterize the set of all lonely pairs (). Further, we characterize the set of pairs of rooted binary unlabeled tree shapes at least one of the labelings of which is lonely. We provide formulas for counting lonely pairs and pairs of unlabeled tree shapes with at least one lonely labeling. The lonely pairs provide a set of examples of pairs () for which the number of compact coalescent histories-which condense coalescent histories into a set of equivalence classes-is equal to the number of coalescent histories. Application of the condition that characterizes lonely pairs can also be used to reduce computation time for the enumeration of coalescent histories.

Given an edge-weighted tree with leaves, sample the leaves uniformly at random without replacement and let , 2 ≤ ≤ , be the length of the subtree spanned by the first leaves. We consider the question, "Can be identified (up to isomorphism) by the joint probability distribution of the random vector (, …, )?" We show that if is known to belong to one of various families of edge-weighted trees, then the answer is, "Yes." These families include the edge-weighted trees with edge-weights in general position, the ultrametric edge-weighted trees, and certain families with equal weights on all edges such as ( + 1)-valent and rooted -ary trees for ≥ 2 and caterpillars.

In this paper we discuss the question of how to decide when a general chemical reaction system is incapable of admitting multiple equilibria, regardless of parameter values such as reaction rate constants, and regardless of the type of chemical kinetics, such as mass-action kinetics, Michaelis-Menten kinetics, etc. Our results relate previously described linear algebraic and graph-theoretic conditions for injectivity of chemical reaction systems. After developing a translation between the two formalisms, we show that a graph-theoretic test developed earlier in the context of systems with mass action kinetics, can be applied to reaction systems with arbitrary kinetics. The test, which is easy to implement algorithmically, and can often be decided without the need for any computation, rules out the possibility of multiple equilibria for the systems in question.