Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCambrian acyclic domains: counting $c$-singletons
126
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the size of certain acyclic domains that arise from geometric and combinatorial constructions. These acyclic domains consist of all permutations visited by commuting equivalence classes of maximal reduced decompositions if we consider the symmetric group and, more generally, of all c-singletons of a Cambrian lattice associated to the weak order of a finite Coxeter group. For this reason, we call these sets Cambrian acyclic domains. Extending a closed formula of Galambos--Reiner for a particular acyclic domain called Fishburns alternating scheme, we provide explicit formulae for the size of any Cambrian acyclic domain and characterize the Cambrian acyclic domains of minimum or maximum size.
rate research
Read More
Recently, Deutsch and Elizalde studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in set partitions. Let $A_{n,k}$ denote the number of partitions of ${1,2,dots, n+1}$ with the largest singleton ${k+1}$ for $0leq kleq n$. In this paper, several explicit formulas for $A_{n,k}$, involving a Dobinski-type analog, are obtained by algebraic and combinatorial methods, many combinatorial identities involving $A_{n,k}$ and Bell numbers are presented by operator methods, and congruence properties of $A_{n,k}$ are also investigated. It will been showed that the sequences $(A_{n+k,k})_{ngeq 0}$ and $(A_{n+k,k})_{kgeq 0}$ (mod $p$) are periodic for any prime $p$, and contain a string of $p-1$ consecutive zeroes. Moreover their minimum periods are conjectured to be $N_p=frac{p^p-1}{p-1}$ for any prime $p$.
We prove that one can count in polynomial time the number of minimal transversals of $beta$-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in [M.M. Kante and T. Uno, Counting Minimal Dominating Sets, TAMC17].
The Cambrian explosion is a grand challenge to science today and involves multidisciplinary study. This event is generally believed as a result of genetic innovations, environmental factors and ecological interactions, even though there are many conflicts on nature and timing of metazoan origins. The crux of the matter is that an entire roadmap of the evolution is missing to discern the biological complexity transition and to evaluate the critical role of the Cambrian explosion in the overall evolutionary context. Here we calculate the time of the Cambrian explosion by an innovative and accurate C-value clock; our result (560 million years ago) quite fits the fossil records. We clarify that the intrinsic reason of genome evolution determined the Cambrian explosion. A general formula for evaluating genome size of different species has been found, by which major questions of the C-value enigma can be solved and the genome size evolution can be illustrated. The Cambrian explosion is essentially a major transition of biological complexity, which corresponds to a turning point in genome size evolution. The observed maximum prokaryotic complexity is just a relic of the Cambrian explosion and it is supervised by the maximum information storage capability in the observed universe. Our results open a new prospect of studying metazoan origins and molecular evolution.
Recently, Deutsch and Elizalde studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let $A_{n,k}(mathbf{t})$ denote the total weight of partitions on $[n+1]$ with the largest singleton ${k+1}$. In this paper, explicit formulas for $A_{n,k}(mathbf{t})$ and many combinatorial identities involving $A_{n,k}(mathbf{t})$ are obtained by umbral operators and combinatorial methods. As applications, we investigate three special cases such as permutations, involutions and labeled forests. Particularly in the permutation case, we derive a surprising identity analogous to the Riordan identity related to tree enumerations, namely, begin{eqnarray*} sum_{k=0}^{n}binom{n}{k}D_{k+1}(n+1)^{n-k} &=& n^{n+1}, end{eqnarray*} where $D_{k}$ is the $k$-th derangement number or the number of permutations of ${1,2,dots, k}$ with no fixed points.
Given a set $F$ of words, one associates to each word $w$ in $F$ an undirected graph, called its extension graph, and which describes the possible extensions of $w$ on the left and on the right. We investigate the family of sets of words defined by the property of the extension graph of each word in the set to be acyclic or connected or a tree. We prove that in a uniformly recurrent tree set, the sets of first return words are bases of the free group on the alphabet. Concerning acyclic sets, we prove as a main result that a set $F$ is acyclic if and only if any bifix code included in $F$ is a basis of the subgroup that it generates.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
