Homomorphism and sigma polynomials.
Let be a fixed rooted digraph. The -coloring problem is the problem of deciding for which rooted digraphs there is a homomorphism which maps the vertex to the vertex . Let be a rooted oriented path. In this case we characterize the nonexistence of such a homomorphism by the existence of a rooted oriented cycle , which is homomorphic to but not homomorphic to . Such a property of the digraph is called rooted cycle duality or -cycle duality. This extends the analogical result for...
We introduce a graded Hopf algebra based on the set of parking functions (hence of dimension in degree n). This algebra can be embedded into a noncommutative polynomial algebra in infinitely many variables. We determine its structure, and show that it admits natural quotients and subalgebras whose graded components have dimensions respectively given by the Schröder numbers (plane trees), the Catalan numbers, and powers of 3. These smaller algebras are always bialgebras and belong to some family...
Let be homogeneous trees with degrees , respectively. For each tree, let be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of is the graph consisting of all -tuples with , equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If and then we obtain a Cayley graph of the...