|
Abstract:
|
Multiplication and comultiplication, which de ne the structure of a Hopf algebra,
can naturally be introduced over many classes of combinatorial objects. Among such
Hopf algebras are well-known examples of Hopf algebras of posets, permutations,
trees, graphs. Many classical combinatorial invariants, such as M obius function
of poset, the chromatic polynomial of graphs, the generalized Dehn-Sommerville
relations and other, are derived from the corresponding Hopf algebra. Theory of
combinatorial Hopf algebras is developed by Aguiar, Bergerone and Sottille in the
paper from 2003. The terminal objects in the category of combinatorial Hopf algebras
are algebras of quasisymmetric and symmetric functions. These functions
appear as generating functions in combinatorics.
The subject of study in this thesis is the combinatorial Hopf algebra of hypergraphs
and its subalgebras of building sets and clutters. These algebras appear in
di erent combinatorial problems, such as colorings of hypergraphs, partitions of simplicial
complexes and combinatorics of simple polytopes. The structural connections
among these algebras and among their odd subalgebras are derived. By applying
the character theory, a method for obtaining interesting numerical identities is presented.
The generalized Dehn-Sommerville relations for
ag f-vectors of eulerian posets
are proven by Bayer and Billera. These relations are de ned in an arbitrary combinatorial
Hopf algebra and they determine its odd subalgebra. In this thesis, the
generalized Dehn-Sommerville relations for the combinatorial Hopf algebra of hypergraphs
are solved. By analogy with Rota's Hopf algebra of posets, the eulerian
subalgebra of the Hopf algebra of hypergraphs is de ned. The combinatorial characterization
of eulerian hypergraphs, which depends on the nerve of the underlying
clutter, is obtained. In this way we obtain a class of solutions of the generalized
Dehn-Sommerviller relations for hypergraphs. These results are applied on the Hopf
algebra of simplicial complexes. |