اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPreordered forests, packed words and contraction algebras
35
0
0.0
(
0
)
تأليف
Anthony Mansuy
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce the notions of preordered and heap-preordered forests, generalizing the construction of ordered and heap-ordered forests. We prove that the algebras of preordered and heap-preordered forests are Hopf for the cut coproduct, and we construct a Hopf morphism to the Hopf algebra of packed words. Moreover, we define another coproduct on the preordered forests given by the contraction of edges. Finally, we give a combinatorial description of morphims defined on Hopf algebras of forests with values in the Hopf algebras of shuffes or quasi-shuffles.
قيم البحث
اقرأ أيضاً
We endow the set of isomorphic classes of matroids with a new Hopf algebra structure, in which the coproduct is implemented via the combinatorial operations of restriction and deletion. We also initiate the investigation of dendriform coalgebra struc
tures on matroids and introduce a monomial invariant which satisfy a convolution identity with respect to restriction and deletion.
We prove new results concerning the relation between bifix codes, episturmian words and subgroups offree groups. We study bifix codes in factorial sets of words. We generalize most properties of ordinary maximal bifix codes to bifix codes maximal in
a recurrent set $F$ of words ($F$-maximal bifix codes). In the case of bifix codes contained in Sturmian sets of words, we obtain several new results. Let $F$ be a Sturmian set of words, defined as the set of factors of a strict episturmian word. Our results express the fact that an $F$-maximal bifix code of degree $d$ behaves just as the set of words of $F$ of length $d$. An $F$-maximal bifix code of degree $d$ in a Sturmian set of words on an alphabet with $k$ letters has $(k-1)d+1$ elements. This generalizes the fact that a Sturmian set contains $(k-1)d+1$ words of length $d$. Moreover, given an infinite word $x$, if there is a finite maximal bifix code $X$ of degree $d$ such that $x$ has at most $d$ factors of length $d$ in $X$, then $x$ is ultimately periodic. Our main result states that any $F$-maximal bifix code of degree $d$ on the alphabet $A$ is the basis of a subgroup of index $d$ of the free group on~$A$.
A word $sigma=sigma_1...sigma_n$ over the alphabet $[k]={1,2,...,k}$ is said to be {em smooth} if there are no two adjacent letters with difference greater than 1. A word $sigma$ is said to be {em smooth cyclic} if it is a smooth word and in addition
satisfies $|sigma_n-sigma_1|le 1$. We find the explicit generating functions for the number of smooth words and cyclic smooth words in $[k]^n$, in terms of {it Chebyshev polynomials of the second kind}. Additionally, we find explicit formula for the numbers themselves, as trigonometric sums. These lead to immediate asymptotic corollaries. We also enumerate smooth necklaces, which are cyclic smooth words that are not equivalent up to rotation.
We prove that for $k in mathbb{N}$ and $d leq 2k+2$, if a graph has maximum average degree at most $2k + frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests, where one of the pseudoforests has all connected components having at most $d$ edges.
Let $G$ be a graph on $n$ vertices. For $iin {0,1}$ and a connected graph $G$, a spanning forest $F$ of $G$ is called an $i$-perfect forest if every tree in $F$ is an induced subgraph of $G$ and exactly $i$ vertices of $F$ have even degree (including
zero). A $i$-perfect forest of $G$ is proper if it has no vertices of degree zero. Scott (2001) showed that every connected graph with even number of vertices contains a (proper) 0-perfect forest. We prove that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges. Moreover, we show that to decide whether $G$ has a 0-perfect forest with at least $|V(G)|/2+k$ edges, where $k$ is the parameter, is W[1]-hard. We also prove that for a prescribed edge $e$ of $G,$ it is NP-hard to obtain a 0-perfect forest containing $e,$ but one can decide if there existsa 0-perfect forest not containing $e$ in polynomial time. It is easy to see that every graph with odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We give a characterization of when a connected graph has a proper 1-perfect forest.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
