Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial invariants and reciprocity theorems for the Hopf monoid of hypergraphs and its sub-monoids
156
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In arXiv:1709.07504 Aguiar and Ardila give a Hopf monoid structure on hypergraphs as well as a general construction of polynomial invariants on Hopf monoids. Using these results, we define in this paper a new polynomial invariant on hypergraphs. We give a combinatorial interpretation of this invariant on negative integers which leads to a reciprocity theorem on hypergraphs. Finally, we use this invariant to recover well-known invariants on other combinatorial objects (graphs, simplicial complexes, building sets etc) as well as the associated reciprocity theorems.
rate research
Read More
In arXiv:1709.07504 Ardila and Aguiar give a Hopf monoid structure on hypergraphs as well as a general construction of polynomial invariants on Hopf monoids. Using these results, we define in this paper a new polynomial invariant on hypergraphs. We give a combinatorial interpretation of this invariant on negative integers which leads to a reciprocity theorem on hypergraphs. Finally, we use this invariant to recover well-known invariants on other combinatorial objects (graphs, simplicial complexes, building sets etc) as well as the associated reciprocity theorems.
From a recent paper, we recall the Hopf monoid structure on the supercharacters of the unipotent uppertriangular groups over a finite field. We give cancelation free formula for the antipode applied to the bases of class functions and power sum functions, giving new cancelation free formulae for the standard Hopf algebra of supercharacters and symmetric functions in noncommuting variables. We also give partial results for the antipode on the supercharacter basis, and explicitly describe the primitives of this Hopf monoid.
Many combinatorial Hopf algebras $H$ in the literature are the functorial image of a linearized Hopf monoid $bf H$. That is, $H={mathcal K} ({bf H})$ or $H=overline{mathcal K} ({bf H})$. Unlike the functor $overline{mathcal K}$, the functor ${mathcal K}$ applied to ${bf H}$ may not preserve the antipode of ${bf H}$. In this case, one needs to consider the larger Hopf monoid ${bf L}times{bf H}$ to get $H={mathcal K} ({bf H})=overline{mathcal K}({bf L}times{bf H})$ and study the antipode in ${bf L}times{bf H}$. One of the main results in this paper provides a cancelation free and multiplicity free formula for the antipode of ${bf L}times{bf H}$. From this formula we obtain a new antipode formula for $H$. We also explore the case when ${bf H}$ is commutative and cocommutative. In this situation we get new antipode formulas that despite of not being cancelation free, can be used to obtain one for $overline{mathcal K}({bf H})$ in some cases. We recover as well many of the well-known cancelation free formulas in the literature. One of our formulas for computing the antipode in ${bf H}$ involves acyclic orientations of hypergraphs as the central tool. In this vein, we obtain polynomials analogous to the chromatic polynomial of a graph, and also identities parallel to Stanleys (-1)-color theorem. One of our examples introduces a {it chromatic} polynomial for permutations which counts increasing sequences of the permutation satisfying a pattern. We also study the statistic obtained after evaluating such polynomial at $-1$. Finally, we sketch $q$ deformations and geometric interpretations of our results. This last part will appear in a sequel paper in joint work with J. Machacek.
A $d$-partite hypergraph is called fractionally balanced if there exists a non-negative function on its edge set that has constant degrees in each vertex side. Using a topological version of Halls theorem we prove lower bounds on the matching number of such hypergraphs. These, in turn, yield results on mulitple-cake division problems and rainbow matchings in families of $d$-intervals.
An oriented hypergraph is an oriented incidence structure that allows for the generalization of graph theoretic concepts to integer matrices through its locally signed graphic substructure. The locally graphic behaviors are formalized in the subobject classifier of incidence hypergraphs. Moreover, the injective envelope is calculated and shown to contain the class of uniform hypergraphs -- providing a combinatorial framework for the entries of incidence matrices. A multivariable all-minors characteristic polynomial is obtained for both the determinant and permanent of the oriented hypergraphic Laplacian and adjacency matrices arising from any integer incidence matrix. The coefficients of each polynomial are shown to be submonic maps from the same family into the injective envelope limited by the subobject classifier. These results provide a unifying theorem for oriented hypergraphic matrix-tree-type and Sachs-coefficient-type theorems. Finally, by specializing to bidirected graphs, the trivial subclasses for the degree-$k$ monomials of the Laplacian are shown to be in one-to-one correspondence with $k$-arborescences.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
