A combinatorial Hopf algebra is a graded connected Hopf algebra H
over a field k equipped with a character (multiplicative linear
functional) \zeta : H --> b.
We show that the terminal object in the category of combinatorial Hopf
algebras is the algebra QSym of quasi-symmetric functions; this explains the
ubiquity of quasi-symmetric functions as generating functions in
combinatorics.
We illustrate this with several examples.
We prove that every character decomposes uniquely as a product of an even
character and an odd character.
Correspondingly, every combinatorial Hopf algebra (H, \zeta) possesses
two canonical Hopf subalgebras on which the character \zeta is even
(respectively, odd).
The odd subalgebra is defined by certain canonical relations which we call the
generalized Dehn-Sommerville relations.
We show that the generalized Dehn-Sommerville relations for \QSym are the
Bayer-Billera relations and the odd subalgebra is the peak Hopf algebra of
Stembridge.
We prove that QSym is the product (in the categorical sense) of its even and
odd Hopf subalgebras.
We also calculate the odd subalgebras of various related combinatorial Hopf
algebras: the Malvenuto-Reutenauer Hopf algebra of permutations, the
Loday-Ronco Hopf algebra of planar binary trees, the Hopf algebras of symmetric
functions and of non-commutative symmetric functions.