The Hopf algebra of integer binary relations (Q776420)

For each non-negative integer \(n\) let \(R_n\) be the set of all reflexive binary relations on the set \([n]\) of the first \(n\) positive integers, and let \(R=\coprod_{n\geq 0}R_n\). The authors define a bialgebra structure on the vector space \(\mathbf{k}R\) with basis \(R\) over a field \(\mathbf{k}\). The product is defined by using the shifted shuffle of two relations, and this makes \(\mathbf{k}R\) a graded algebra, while the coproduct is defined by using total cuts of a relation, and it makes \(\mathbf{k}R\) a graded coalgebra. The same kind of results are obtained when considering the set \(P_n\) of all posets on \([n]\) instead of \(R_n\), and \(P=\coprod_{n\geq 0}P_n\) instead of \(R\). Several bialgebras related to combinatorial structures are reinterpreted either as quotients or as subobjects of the bialgebra \(\mathbf{k}P\), for example the bialgebras on permutations of \textit{C. Malvenuto} and \textit{C. Reutenauer} [J. Algebra 177, No. 3, 967--982 (1995; Zbl 0838.05100)], on ordered partitions and on Schröder trees of \textit{F. Chapoton} [Adv. Math. 150, No. 2, 264--275 (2000; Zbl 0958.16038)], on binary trees of \textit{J.-L. Loday} and \textit{M. O. Ronco} [Adv. Math. 139, No. 2, 293--309 (1998; Zbl 0926.16032)]. Also, new bialgebra structures are obtained on the intervals of the weak order and on the intervals of the Tamari lattice. For the entire collection see [Zbl 1437.05003].