Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDuality of graded graphs through operads
107
0
0.0
(
0
)
Authors
Samuele Giraudo
Ask ChatGPT about the research
No Arabic abstract
Pairs of graded graphs, together with the Fomin property of graded graph duality, are rich combinatorial structures providing among other a framework for enumeration. The prototypical example is the one of the Young graded graph of integer partitions, allowing us to connect number of standard Young tableaux and numbers of permutations. Here, we use operads, that algebraic devices abstracting the notion of composition of combinatorial objects, to build pairs of graded graphs. For this, we first construct a pair of graded graphs where vertices are syntax trees, the elements of free nonsymmetric operads. This pair of graphs is dual for a new notion of duality called $phi$-diagonal duality, similar to the ones introduced by Fomin. We also provide a general way to build pairs of graded graphs from operads, wherein underlying posets are analogous to the Young lattice. Some examples of operads leading to new pairs of graded graphs involving integer compositions, Motzkin paths, and $m$-trees are considered.
rate research
Read More
A new hierarchy of operads over the linear spans of $delta$-cliffs, which are some words of integers, is introduced. These operads are intended to be analogues of the operad of permutations, also known as the associative symmetric operad. We obtain operads whose partial compositions can be described in terms of intervals of the lattice of $delta$-cliffs. These operads are very peculiar in the world of the combinatorial operads since, despite to the relative simplicity for their construction, they are infinitely generated and they have nonquadratic and nonhomogeneous nontrivial relations. We provide a general construction for some of their quotients. We use it to endow the spaces of permutations, $m$-increasing trees, $c$-rectangular paths, and $m$-Dyck paths with operad structures. The operads on $c$-rectangular paths admit, as Koszul duals, operads generalizing the duplicial and triplicial operads.
Using the combinatorial species setting, we propose two new operad structures on multigraphs and on pointed oriented multigraphs. The former can be considered as a canonical operad on multigraphs, directly generalizing the Kontsevich-Willwacher operad, and has many interesting suboperads. The latter is a natural extension of the pre-Lie operad in a sense developed here and related to the multigraph operad. We study some of the finitely generated suboperads of the multigraph operad and establish links between them and the commutative operad and the commutative magmatic operad.
We introduce a functorial construction $mathsf{C}$ which takes unitary magmas $mathcal{M}$ as input and produces operads. The obtained operads involve configurations of chords labeled by elements of $mathcal{M}$, called $mathcal{M}$-decorated cliques and generalizing usual configurations of chords. By considering combinatorial subfamilies of $mathcal{M}$-decorated cliques defined, for instance, by limiting the maximal number of crossing diagonals or the maximal degree of the vertices, we obtain suboperads and quotients of $mathsf{C} mathcal{M}$. This leads to a new hierarchy of operads containing, among others, operads on noncrossing configurations, Motzkin configurations, forests, dissections of polygons, and involutions. Besides, the construction $mathsf{C}$ leads to alternative definitions of the operads of simple and double multi-tildes, and of the gravity operad.
Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called {bf graded sparse graphs}, arising from generically pinned (completely immobilized) bar-and-joint frameworks and prove that they also form matroids. We address five problems on graded sparse graphs: {bf Decision}, {bf Extraction}, {bf Components}, {bf Optimization}, and {bf Extension}. We extend our {bf pebble game algorithms} to solve them.
We consider two operations on an edge of an embedded graph (or equivalently a ribbon graph): giving a half-twist to the edge and taking the partial dual with respect to the edge. These two operations give rise to an action of S_3^{|E(G)|}, the ribbon group, on G. The action of the ribbon group on embedded graphs extends the concepts of duality, partial duality and Petrie duality. We show that this ribbon group action gives a complete characterization of duality in that if G is any cellularly embedded graph with medial graph G_m, then the orbit of G under the group action is precisely the set of all graphs with medial graphs isomorphic (as abstract graphs) to G_m. We provide characterizations of special sets of twisted duals, such as the partial duals, of embedded graphs in terms of medial graphs and we show how different kinds of graph isomorphism give rise to these various notions of duality. The ribbon group action then leads to a deeper understanding of the properties of, and relationships among, various graph polynomials via the generalized transition polynomial which interacts naturally with the ribbon group action.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
