\documentclass{beamer}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{setspace}
\usepackage{graphicx}
%\usepackage{tikz}
%\usetikzlibrary{matrix,arrows,backgrounds,shapes.misc,shapes.geometric,fit}
\usepackage{etex}
\usepackage{amsthm}
\usepackage{color}
\usepackage{wasysym}
\usepackage{allrunes}
\usepackage[all]{xy}
\usepackage{textpos}
\usepackage{ytableau}
%\usetikzlibrary{calc,through,backgrounds}
%\CompileMatrices

\definecolor{grau}{rgb}{.5 , .5 , .5}
\definecolor{dunkelgrau}{rgb}{.35 , .35 , .35}
\definecolor{schwarz}{rgb}{0 , 0 , 0}
\definecolor{violet}{RGB}{143,0,255}
\definecolor{forestgreen}{RGB}{34, 100, 34}

\newcommand{\red}{\color{red}}
\newcommand{\grey}{\color{grau}}
\newcommand{\green}{\color{forestgreen}}
\newcommand{\violet}{\color{violet}}
\newcommand{\blue}{\color{blue}}

\newcommand{\bIf}{\textbf{If} }
\newcommand{\bif}{\textbf{if} }
\newcommand{\bthen}{\textbf{then} }

\newcommand{\EE}{{\mathbf{E}}}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\QQ}{{\mathbb Q}}
\newcommand{\kk}{{\mathbf k}}
\newcommand{\OO}{\operatorname {O}}
\newcommand{\Nm}{\operatorname {N}}
\newcommand{\Par}{\operatorname{Par}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\Stab}{\operatorname {Stab}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Sym}{\operatorname{Sym}}
\newcommand{\QSym}{\operatorname{QSym}}
\newcommand{\Mat}{\operatorname{M}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newcommand{\Orb}{{\mathcal O}}
\newcommand{\GL}{\operatorname {GL}}
\newcommand{\SL}{\operatorname {SL}}
\newcommand{\Or}{\operatorname {O}}
\newcommand{\im}{\operatorname {Im}}
\newcommand{\Iso}{\operatorname {Iso}}
\newcommand{\Adm}{\operatorname{Adm}}
\newcommand{\Supp}{\operatorname{Supp}}
\newcommand{\Powser}{\mathbf{k}\left[\left[x_1,x_2,x_3,\ldots\right]\right]}
\newcommand{\rad}{\operatorname {rad}}
\newcommand{\zero}{\mathbf{0}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\ord}{\operatorname*{ord}}
\newcommand{\bbK}{{\mathbb{K}}}
\newcommand{\whP}{{\widehat{P}}}
%\newcommand{\Trop}{\operatorname*{Trop}}
%\newcommand{\TropZ}{{\operatorname*{Trop}\mathbb{Z}}}
\newcommand{\rato}{\dashrightarrow}
\newcommand{\lcm}{\operatorname*{lcm}}
\newcommand{\tlab}{\operatorname*{tlab}}
\newcommand{\tvi}{\textarm{\tvimadur}}
\newcommand{\bel}{\textarm{\belgthor}}

\newcommand{\fti}[1]{\frametitle{\ \ \ \ \ #1}}
\newenvironment{iframe}[1][]{\begin{frame} \fti{[#1]} \begin{itemize}}{\end{frame}\end{itemize}}

\setbeamertemplate{itemize/enumerate body begin}{\large}
\setbeamertemplate{itemize/enumerate subbody begin}{\large}
\setbeamertemplate{itemize/enumerate subsubbody begin}{\large}

\usepackage{url}%this line and the next are related to hyperlinks
%\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blur]{hyperref}

\usepackage{color}

%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}[frame number]
\setbeamertemplate{itemize/enumerate body begin}{}
\setbeamertemplate{itemize/enumerate subbody begin}{\normalsize}
%\setbeamertemplate{section in head/foot shaded}[default][60]
%\setbeamertemplate{subsection in head/foot shaded}[default][60]
\beamersetuncovermixins{\opaqueness<1>{0}}{\opaqueness<2->{15}}

%\usepackage{beamerthemesplit}
\usepackage{epsfig,amsfonts,bbm,mathrsfs}
\usepackage{verbatim} 



\newcommand{\STRUT}{\vrule width 0pt depth 8pt height 0pt}
\newcommand{\ASTRUT}{\vrule width 0pt depth 0pt height 11pt}


\theoremstyle{plain}
\newtheorem{conj}[theorem]{Conjecture}


\setbeamertemplate{headline}{}
%This removes a black stripe from the top of the slides.


\author{Darij Grinberg (MIT)
%\\ \textit{joint work with Tom Roby (UConn)}
}
\title[Quasisymmetric functions]{Three etudes on quasisymmetric functions}
%\title[Quasisymmetric functions]{$\EE$-partitions and the antipode of the quasisymmetric functions}

\date{5 April 2016 \\ Combinatorics Seminar, Brandeis University (Chapter 1) \\
11 April 2016 \\ Massachusetts Institute of Technology (Chapters 1-3)}

\begin{document}

\frame{\titlepage
\textbf{slides:} \\ {\red \url{http://mit.edu/~darij/www/algebra/brandeis06.pdf}} \\
\textbf{papers:} \\ {\red \url{http://mit.edu/~darij/www/algebra/dp-abstr.pdf} \\
                  \url{http://mit.edu/~darij/www/algebra/bernsteinproof.pdf} \\
                  \url{http://mit.edu/~darij/www/algebra/dimcreation.pdf}}
}

\begin{frame}
\fti{Prologue}
\begin{center}
{\Huge \bf \sc Prologue} \\
\noindent\rule[0.5ex]{\linewidth}{1pt}
{\Large \bf Quasisymmetric functions and Hopf algebras}
\end{center}
\vspace{1cm}
References: (e.g.)
\begin{itemize}
\item \href{http://arxiv.org/abs/1409.8356}{\red Darij Grinberg, Victor Reiner, \textit{Hopf Algebras in Combinatorics}, arXiv:1409.8356}.
\item \href{http://arxiv.org/abs/0804.3888}{\red Michiel Hazewinkel, \textit{Witt vectors. Part 1}, arXiv:0804.3888}.
\item M. Hazewinkel, N. Gubareni, V.V. Kirichenko, \textit{Algebras, rings and modules. Lie algebras and Hopf algebras}, AMS 2010.
\end{itemize}
\end{frame}

\begin{frame}
\fti{Symmetric functions, part 1: definition}

\begin{itemize}

\item Fix a commutative ring $\kk$ with unity. We shall do everything over $\kk$.

\item Consider the ring $\kk\left[\left[x_1,x_2,x_3,\ldots\right]\right]$ of formal power series in countably many indeterminates.

\pause

\item A formal power series $f$ is said to be \textit{bounded-degree} if the monomials it contains are bounded (from above) in degree.

\pause

\item A formal power series $f$ is said to be \textit{symmetric} if it is invariant under permutations of the indeterminates. \\ Equivalently, if its coefficients in front of $x_{i_1}^{a_1} x_{i_2}^{a_2} \cdots x_{i_k}^{a_k}$ and $x_{j_1}^{a_1} x_{j_2}^{a_2} \cdots x_{j_k}^{a_k}$ are equal whenever $i_1, i_2, \ldots, i_k$ are distinct and $j_1, j_2, \ldots, j_k$ are distinct.

\only<1-3>{\item For example:
\begin{itemize}
\item $1 + x_1 + x_2^3$ is bounded-degree but not symmetric.
\item $\left(1+x_1\right)\left(1+x_2\right)\left(1+x_3\right) \cdots $ is symmetric  but not bounded-degree.
\end{itemize}}
\only<4>{\item Let $\Lambda$ be the set of all symmetric bounded-degree power series in $\kk\left[\left[x_1,x_2,x_3,\ldots\right]\right]$. This is a $\kk$-subalgebra, called the \textit{ring of symmetric functions} over $\kk$. \\ It is also known as $\operatorname{Sym}$.}

\vspace{3cm}
\end{itemize}

\end{frame}

\begin{frame}
\fti{Symmetric functions, part 2: partitions}

\begin{itemize}

\item The $\kk$-module $\Lambda$ has several bases. All the important ones are indexed by partitions.

\item A \textit{partition} is a weakly decreasing sequence $\lambda = \left(\lambda_1, \lambda_2, \lambda_3, \ldots\right)$ of nonnegative integers such that $\lambda_i = 0$ for all sufficiently high $i$.

\item For example, $\left(3,2,2,0,0,0,\ldots\right)$ is a partition.

\pause

\item Always write $\lambda_i$ for the $i$-th entry of a sequence $\lambda$.

\item We identify a partition $\lambda$ with the finite sequence $\left(\lambda_1, \lambda_2, \ldots, \lambda_k\right)$ whenever $\lambda_{k+1} = \lambda_{k+2} = \lambda_{k+3} = \cdots = 0$.

\item For example, $\left(3,2,2,0,0,0\right) = \left(3,2,2\right) = \left(3,2,2,0\right)$.

\pause

\item Let $\Par$ be the set of all partitions.

\end{itemize}

\end{frame}

\begin{frame}
\fti{Symmetric functions, part 3: bases}

\begin{itemize}

\item For every $\lambda \in \Par$, define
\begin{align*}
m_\lambda &= \text{sum of all \textbf{distinct} monomials obtained by } \\
&\qquad \text{permuting } x_1^{\lambda_1} x_2^{\lambda_2} x_3^{\lambda_3} \cdots .
\end{align*}
This is a homogeneous power series lying in $\Lambda$. Its degree is $\left|\lambda\right| := \lambda_1 + \lambda_2 + \lambda_3 + \cdots$, known as the \textit{size} of $\lambda$.

\only<1>{\item Examples:
\begin{itemize}
\item $m_{\left(\right)} = 1$.
\item $m_{\left(1,1\right)} = \sum\limits_{i<j} x_i x_j = x_1 x_2 + x_1 x_3 + x_2 x_3 + x_1 x_4 + x_2 x_4 + \cdots$.
\item $m_{\left(2,1\right)} = \sum\limits_{i\neq j} x_i^2 x_j = x_1^2 x_2 + x_1 x_2^2 + x_1^2 x_3 + x_1 x_3^2 + x_2^2 x_3 + \cdots$.
\item $m_{\left(3\right)} = \sum\limits_i x_i^3 = x_1^3 + x_2^3 + x_3^3 + \cdots$.
\end{itemize}
Note: No repeated monomials even if the partition contains repeated entries!
}
\only<2>{\item In other words,
\begin{align*}
m_\lambda &= \text{sum of all monomials whose exponents } \\
&\qquad \text{are } \lambda_1, \lambda_2, \lambda_3, \ldots \text{ in some order}.
\end{align*}
}
\only<3-4>{
\item The family $\left(m_\lambda\right)_{\lambda \in \Par}$ is a basis of the $\kk$-module $\Lambda$, called the \textit{monomial basis} (or $m$-basis).

\pause

\item There are many more, e.g.:
\begin{itemize}
\item the $h$-basis (complete homogeneous symmetric functions), 
\item the $e$-basis (elementary symmetric functions),
\item the $s$-basis (Schur functions),
\item the $p$-basis (power-sum symmetric functions; these are a basis only when $\QQ \subseteq \kk$).
\end{itemize}
}

\end{itemize}

\vspace{3cm}
\end{frame}

\begin{frame}
\fti{Quasisymmetric functions, part 1: definition}

\begin{itemize}

\item We shall now define the quasisymmetric functions -- a bigger algebra than $\Lambda$, but still with many of its nice properties.

\item A formal power series $f$ (still in $\kk\left[\left[x_1,x_2,x_3,\ldots\right]\right]$) is said to be \textit{quasisymmetric} if its coefficients in front of $x_{i_1}^{a_1} x_{i_2}^{a_2} \cdots x_{i_k}^{a_k}$ and $x_{j_1}^{a_1} x_{j_2}^{a_2} \cdots x_{j_k}^{a_k}$ are equal whenever $i_1 < i_2 < \cdots < i_k$ and $j_1 < j_2 < \cdots < j_k$.

\item For example:
\begin{itemize}
\item Every symmetric power series is quasisymmetric.

\item $\sum\limits_{i<j} x_i^2 x_j = x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_3 + x_1^2 x_4 + \cdots$ is quasisymmetric, but not symmetric.

\end{itemize}

\pause

\item Let $\QSym$ be the set of all quasisymmetric bounded-degree power series in $\kk\left[\left[x_1,x_2,x_3,\ldots\right]\right]$. This is a $\kk$-subalgebra, called the \textit{ring of quasisymmetric functions} over $\kk$. (Gessel, 1980s.)

\item We have $\Lambda \subseteq \QSym \subseteq \kk\left[\left[x_1,x_2,x_3,\ldots\right]\right]$.

\end{itemize}

\end{frame}

\begin{frame}
\fti{Quasisymmetric functions, part 2: compositions}

\begin{itemize}

\item The $\kk$-module $\QSym$ has several bases. All the important ones are indexed by compositions.

\item A \textit{composition} is a finite list of positive integers.

\item For example, $\left(1,3,2\right)$ is a composition.

\pause

\item Let $\Comp$ be the set of all compositions.

\end{itemize}

\end{frame}

\begin{frame}
\fti{Quasisymmetric functions, part 3: bases}

\begin{itemize}

\item For every $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right) \in \Comp$, define
\begin{align*}
M_\alpha &= \sum\limits_{i_1 < i_2 < \cdots < i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k} \\
&= \text{sum of all monomials whose nonzero exponents } \\
& \qquad \text{are } \alpha_1, \alpha_2, \ldots, \alpha_k \text{ in \textbf{this} order}.
\end{align*}
This is a homogeneous power series lying in $\QSym$. Its degree is $\left|\alpha\right| := \alpha_1 + \alpha_2 + \cdots + \alpha_k$, known as the \textit{size} of $\alpha$.

\only<1>{\item Examples:
\begin{itemize}
\item $M_{\left(\right)} = 1$.
\item $M_{\left(1,1\right)} = \sum\limits_{i<j} x_i x_j = x_1 x_2 + x_1 x_3 + x_2 x_3 + x_1 x_4 + x_2 x_4 + \cdots$.
\item $M_{\left(2,1\right)} = \sum\limits_{i<j} x_i^2 x_j = x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_3 + \cdots$.
\item $M_{\left(3\right)} = \sum\limits_i x_i^3 = x_1^3 + x_2^3 + x_3^3 + \cdots$.
\end{itemize}
Note: $m_{\left(2,1\right)} = M_{\left(2,1\right)} + M_{\left(1,2\right)}$.
}
\only<2-3>{
\item The family $\left(M_\alpha\right)_{\alpha \in \Comp}$ is a basis of the $\kk$-module $\QSym$, called the \textit{monomial basis} (or $M$-basis).
}

\only<3>{
\item There are many more, e.g.:
\begin{itemize}
\item the $F$-basis (Gessel's fundamental basis, aka the $L$-basis), 
\item the ``quasisymmetric Schur basis'', % (an analogue of the Schur functions),
\item the ``dual immaculate basis'', % (an analogue of the Schur functions)
\item the $\Psi$-basis (only when $\QQ \subseteq \kk$).
\end{itemize}
}

\end{itemize}

\vspace{4cm}

\end{frame}

\begin{frame}
\fti{Hopf algebras, part 1: introduction}

\begin{itemize}

\item But the $\kk$-algebra structures are not the only structures on $\Lambda$ and $\QSym$. We shall also use the \textit{Hopf algebra} structures.

\pause

\item Roughly speaking:

\begin{itemize}

\item {\bf algebra} = $\kk$-module $A$ with a multiplication map $m : A \otimes A \to A$ and a unit map $u : \kk \to A$ satisfying some axioms;

\pause

\item {\bf coalgebra} = $\kk$-module $C$ with a comultiplication map $\Delta : C \to C \otimes C$ and a counit map $\varepsilon : C \to \kk$ satisfying the duals of these axioms;

\pause

\item {\bf bialgebra} = $\kk$-module $H$ with both an algebra structure and a coalgebra structure which ``commute'' in a certain sense;

\pause

\item {\bf Hopf algebra} = $\kk$-bialgebra $H$ with an ``antipode'' map $S : H \to H$ \\
(compare with: {\bf group} = monoid $M$ with an ``inverse'' map $\left(\right)^{-1} : M \to M$).

\end{itemize}

\pause
\item In some more detail...

\end{itemize}
\end{frame}

\begin{frame}
\fti{Hopf algebras, part 2: algebras}

\begin{itemize}

\item The snob's definition of an algebra (associative, unital): \\
A \textit{$\kk$-algebra} is a $\kk$-module $A$ equipped with a $\kk$-linear map $m : A \otimes A \to A$ (called ``multiplication'') and a $\kk$-linear map $u : \kk \to A$ (called ``unit'') such that the diagrams
\[
\xymatrix@C=4pc{ A\otimes A\otimes A \ar[r]^-{m \otimes\operatorname*{id}} \ar[d]_{\operatorname*{id}\otimes m} & A\otimes A \ar[d]^{m} \\ A\otimes A \ar[r]_{m} & A }
\]
and
\[
\xymatrix{ 
\kk \otimes A \ar[r]^{\cong} \ar[dr]_{u \otimes \id} & A & A \otimes \kk \ar[l]_{\cong} \ar[dl]^{\id \otimes u} \\
& A \otimes A \ar[u]^m
}
\]
commute. (All $\otimes$ signs are over $\kk$.)
\pause
\item NB: The domain of $m$ is $A \otimes A$, not $A \times A$. Thus, everything is $\kk$-linear!

\end{itemize}

\end{frame}

\begin{frame}
\fti{Hopf algebras, part 3: coalgebras}

\begin{itemize}

\item Turning all arrows around, we can define coalgebras: \\
A \textit{$\kk$-coalgebra} is a $\kk$-module $C$ equipped with a $\kk$-linear map $\Delta : C \to C \otimes C$ (called ``comultiplication'') and a $\kk$-linear map $\varepsilon : C \to \kk$ (called ``counit'') such that the diagrams
\[
\xymatrix@C=4pc{ C\otimes C\otimes C & C\otimes C \ar[l]_-{\Delta \otimes\operatorname*{id}} \\ C\otimes C \ar[u]^{\operatorname*{id}\otimes \Delta} & C \ar[l]^{\Delta} \ar[u]^{\Delta}}
\]
and
\[
\xymatrix{ 
\kk \otimes C & C \ar[l]_{\cong} \ar[r]^{\cong} \ar[d]_{\Delta} & C \otimes \kk \ar[l]_{\cong} \\
& C \otimes C \ar[lu]^{\varepsilon \otimes \id} \ar[ru]_{\id \otimes \varepsilon}
}
\]
commute.
\only<1>{\vspace{2cm}}
\only<2>{\item No way to restate this without tensor products anymore! \\ \phantom{ooooooo}}
\only<3>{\item If $C$ is a free $\kk$-module of finite rank, then $C$
coalgebra $\Longleftrightarrow$ $C^\ast = \operatorname{Hom}\left(C, \kk\right)$ algebra.
Not in general!}

\end{itemize}

\end{frame}

\begin{frame}
\fti{Hopf algebras, part 4: bialgebras}

\begin{itemize}

\item A \textit{$\kk$-bialgebra} is a $\kk$-module $H$ equipped with:
\begin{itemize}
\item the structure of a $\kk$-algebra (i.e., suitable maps $m$ and $u$);
\item the structure of a $\kk$-coalgebra (i.e., suitable maps $\Delta$ and $\varepsilon$)
\end{itemize}
such that the following equivalent statements hold:
\begin{itemize}
\item The maps $\Delta$ and $\varepsilon$ are $\kk$-algebra homomorphisms (where $H \otimes H$ becomes a $\kk$-algebra in an appropriate way).
\item The maps $m$ and $u$ are $\kk$-coalgebra homomorphisms (where $H \otimes H$ becomes a $\kk$-coalgebra in an appropriate way).
\item Some four diagrams commute.
\end{itemize}
(We won't need these statements much.)
\end{itemize}

\end{frame}

\begin{frame}
\fti{Hopf algebras, part 5: Hopf algebras}

\begin{itemize}

\item A \textit{Hopf algebra} is a $\kk$-bialgebra $H$ such that there exists a $\kk$-linear map $S : H \to H$ for which the diagram
\[
\xymatrix@C=4pc@R=1pc{
& H \ar[dl]_-{\Delta} \ar[dr]^-{\Delta} \ar[dd]^{\varepsilon} & \\
H \otimes H \ar[dd]_{\operatorname*{id}\otimes S} & & H \otimes H \ar[dd]^{S\otimes\operatorname*{id}} \\
& \kk \ar[dd]^{u} & \\
H \otimes H \ar[dr]_{m} & & H \otimes H \ar[dl]^{m} \\
& H &
}
\]
commutes.

\item If $S$ exists, then it is unique, so $S$ can be regarded as part of the Hopf algebra structure. (And should be.) It's called the \textit{antipode} of $H$.

\end{itemize}

\end{frame}

\begin{frame}
\fti{Hopf algebras, part 6: grading}

\begin{itemize}

\item A \textit{graded} $\kk$-bialgebra is a $\kk$-bialgebra $H$ which is graded as $\kk$-module, in the sense that
\[
H = \bigoplus\limits_{n \geq 0} H_n ,
\]
and whose structure maps $m$, $u$, $\Delta$ and $\varepsilon$ all are graded.

\only<1>{\item No Koszul signs here! (If you don't know what I mean, ignore this.)}
\only<2>{\item For example, the gradedness of $\Delta$ means that
\[
\Delta\left(H_n\right) \subseteq \sum_{k=0}^n H_k \otimes H_{n-k} ,
\]
where $H_k \otimes H_{n-k}$ is canonically embedded into $H \otimes H$.}
\only<3>{\item The gradedness of $m$ is the usual condition you know from
the definition of a graded algebra: $H_a H_b \subseteq H_{a+b}$.}
\only<4-6>{\item A graded $\kk$-bialgebra $H$ is said to be \textit{connected} if
$\left(1_H\right)$ is a basis of the $\kk$-module $H_0$.}
\only<5>{\item \textbf{Takeuchi's theorem (and slightly more):} If $H$ is a connected graded $\kk$-bialgebra,
then $H$ is a Hopf algebra and its antipode $S$ is graded and invertible.}
\only<6>{\item Connected graded Hopf algebras tend to appear in combinatorics
a lot. We shall now see that $\Lambda$ and $\QSym$ are two such beasts.}

\end{itemize}

\vspace{5cm}

\end{frame}

\begin{frame}
\fti{Hopf structure on $\Lambda$: coalgebra structure}

\begin{itemize}

\item So how does $\Lambda$ become a Hopf algebra?

\item The counit is easy to define:
\[
\varepsilon\left(f\right) = f\left(0,0,0,\ldots\right) = \text{constant term of } f.
\]

\only<2-3>{
\item The comultiplication, the safe way: If $\lambda = \left(\lambda_1, \lambda_2, \ldots, \lambda_k\right) \in \Par$ with $\lambda_1, \lambda_2, \ldots, \lambda_k > 0$, then set
\[
\Delta\left( m_\lambda \right) = \sum m_\mu \otimes m_\nu ,
\]
where the sum is over all pairs $\left(\mu, \nu\right)$ of partitions such that concatenating the lists $\mu$ and $\nu$ and then sorting the result in decreasing order gives $\lambda$. \\
Don't worry, I'll make sense of this shortly.}

\only<3>{
\item Example (writing $m_{\lambda_1, \lambda_2, \ldots, \lambda_k}$ for $m_{\left(\lambda_1, \lambda_2, \ldots, \lambda_k\right)}$, and writing $\varnothing$ for the empty partition $\left(\right)$):
\begin{align*}
\Delta\left(m_{3,2,2}\right) &= m_{\varnothing} \otimes m_{3,2,2} + m_3 \otimes m_{2,2} + m_2 \otimes m_{3,2} \\
& \qquad + m_{3,2} \otimes m_2 + m_{2,2} \otimes m_3 + m_{3,2,2} \otimes m_{\varnothing} .
\end{align*}
}

\only<4>{
\item The comultiplication, the ``right'' way:
\[
\Delta\left(f\right) = f\left(x_1, x_2, x_3, \ldots, y_1, y_2, y_3, \ldots\right) ,
\]
where we pretend that $\kk\left[\left[x_1, x_2, x_3, \ldots, y_1, y_2, y_3, \ldots\right]\right] \cong \kk\left[\left[x_1, x_2, x_3, \ldots\right]\right] \otimes \kk\left[\left[y_1, y_2, y_3, \ldots\right]\right]$ (although it is not true). \\

Making this formal requires work, but this is the actual meaning of comultiplication: it ``doubles the alphabet'', i.e., splits the indeterminates into two groups. Note that symmetry of $f$ is used here.
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Hopf structure on $\Lambda$: the antipode}

\begin{itemize}

\item Equipped with these $\Delta$ and $\varepsilon$, the $\kk$-algebra $\Lambda$ becomes a connected graded $\kk$-bialgebra. Thus, it is a Hopf algebra (by Takeuchi's theorem). What is its antipode?

\pause

\item The antipode $S$ of $\Lambda$ is given by
\begin{align*}
S\left(f\right) &= \left(-1\right)^n \omega\left(f\right) \\
& \qquad \text{for every homogeneous } f \in \Lambda \text{ of degree } n,
\end{align*}
where $\omega$ is the ``omega involution''. \\
One way to define $\omega$: It is the $\kk$-algebra endomorphism of
$\Lambda$ sending each $h_n$ to $e_n$, where
\begin{align*}
h_n & = \sum\limits_{i_1 \leq i_2 \leq \cdots \leq i_n} x_{i_1} x_{i_2} \cdots x_{i_n} \in \Lambda \qquad \text{and} \\
e_n & = \sum\limits_{i_1 < i_2 < \cdots < i_n} x_{i_1} x_{i_2} \cdots x_{i_n} \in \Lambda .
\end{align*}
As the name says, it is an involution, and so is $S$.
\end{itemize}

\vspace{5cm}

\end{frame}

\begin{frame}
\fti{Hopf structure on $\QSym$: coalgebra structure}

\begin{itemize}

\item So how does $\QSym$ become a Hopf algebra?

\item The counit is easy to define:
\[
\varepsilon\left(f\right) = f\left(0,0,0,\ldots\right) = \text{constant term of } f.
\]

\only<2-3>{
\item The comultiplication, the safe way: If $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right) \in \Comp$, then set
\[
\Delta\left( M_\alpha \right) = \sum_{i=0}^k M_{\left(\alpha_1, \alpha_2, \ldots, \alpha_i\right)} \otimes M_{\left(\alpha_{i+1}, \alpha_{i+2}, \ldots, \alpha_k\right)} .
\]}

\only<3>{
\item Example (writing $M_{\alpha_1, \alpha_2, \ldots, \alpha_k}$ for $M_{\left(\alpha_1, \alpha_2, \ldots, \alpha_k\right)}$, and writing $\varnothing$ for the empty composition $\left(\right)$):
\begin{align*}
\Delta\left(M_{2,3,2}\right) &= M_{\varnothing} \otimes M_{2,3,2} + M_2 \otimes M_{3,2} \\
& \qquad + M_{2,3} \otimes M_2 + M_{2,3,2} \otimes M_{\varnothing} .
\end{align*}
}

\only<4>{
\item The comultiplication, the ``right'' way:
\[
\Delta\left(f\right) = f\left(x_1 < x_2 < x_3 < \cdots < y_1 < y_2 < y_3 < \cdots\right) .
\]
This is even harder to rigorously justify than for $\Lambda$, since $f$ is no longer symmetric. We can still apply $f$ to a totally ordered set of indeterminates (thus the $<$ signs), but this is not a-priori clear.

The ``safe'' way is the better one here for most purposes.
}

\end{itemize}

\vspace{9cm}

\end{frame}
\begin{frame}

\fti{Hopf structure on $\QSym$: the antipode}

\begin{itemize}

\item Equipped with these $\Delta$ and $\varepsilon$, the $\kk$-algebra $\QSym$ becomes a connected graded $\kk$-bialgebra. Thus, it is a Hopf algebra (by Takeuchi's theorem). What is its antipode?

\pause

\item The antipode $S$ of $\QSym$ is given by
\begin{align*}
S\left( M_\alpha \right) &= \left(-1\right)^k \sum_{i_1 \geq i_2 \geq \cdots \geq i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k}
\end{align*}
for every $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right) \in \Comp$.

\item Alternatively, this can be written
\begin{align*}
S\left( M_\alpha \right) &= \left(-1\right)^k \sum_{\gamma \in \Comp; \  \gamma \preceq \operatorname{rev}\alpha} M_\gamma ,
\end{align*}
where $\preceq$ is a certain partial order on $\Comp$, and where $\operatorname{rev} \alpha = \left(\alpha_k, \alpha_{k-1}, \ldots, \alpha_1\right)$.
\\ (Classical result. Malvenuto? Reutenauer? Gessel?)

\pause
\item Again, the antipode is just a sign away from the ``omega involution'', if you know the latter.
\end{itemize}

\vspace{5cm}

\end{frame}

\begin{frame}
\fti{Homomorphisms preserve antipodes}

\begin{itemize}

\item \textbf{Standard theorem:} If $A$ and $B$ are two Hopf algebras, and $f : A \to B$ is a $\kk$-bialgebra homomorphism (i.e., a $\kk$-linear map preserving $m$, $u$, $\Delta$ and $\varepsilon$),
then $f$ is a Hopf algebra homomorphism (i.e., also preserves $S$).

\pause
\item \textbf{Corollary:} If $A$ is a Hopf subalgebra of a Hopf algebra $B$, then the antipode of $A$ is the restriction of the antipode of $B$.

\pause
\item Thus, the antipode of $\Lambda$ is the restriction of the antipode of $\QSym$.

\end{itemize}

\vspace{5cm}

\end{frame}

\begin{frame}
\fti{Chapter 1}
\begin{center}
{\Huge \bf \sc Chapter 1} \\
\noindent\rule[0.5ex]{\linewidth}{1pt}
{\Large \bf $\EE$-partitions and the antipode}
\end{center}
\vspace{1cm}
Reference:
\begin{itemize}
\item \href{http://web.mit.edu/~darij/www/algebra/dp-abstr.pdf}{\red Darij Grinberg, \textit{Double posets and the antipode of
QSym}, arXiv:1509.08355}. \\
(The version on my website is newer than the arXiv one, currently at least.)
\end{itemize}
\end{frame}

\begin{frame}
\fti{Hopf structure on $\QSym$: the antipode, again}

\begin{itemize}

\only<1>
{\item Recall: The antipode $S$ of $\QSym$ sends
\begin{align*}
& M_\alpha \\
& \mapsto \left(-1\right)^k \sum_{i_1 \geq i_2 \geq \cdots \geq i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k}
\end{align*}
for every $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right) \in \Comp$.
}
\only<2-4>
{\item Recall: The antipode $S$ of $\QSym$ sends
\begin{align*}
& M_\alpha = \sum_{i_1 < i_2 < \cdots < i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k} \\
& \mapsto \left(-1\right)^k \sum_{i_1 \geq i_2 \geq \cdots \geq i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k}
\end{align*}
for every $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right) \in \Comp$.
}
\only<3-4>{\item Thus, $<$ becomes $\geq$, and a sign appears. This is a classical phenomenon (e.g., Ehrhart reciprocity). Is this specific to the $M_\alpha$'s?}
\only<4>{\item \textbf{It isn't.} Numerous antipode formulas for power series in $\QSym$ and in other combinatorial Hopf algebras share the same pattern. We shall show what might be the most general such result for $\QSym$.
(See \href{http://arxiv.org/abs/1410.5023}{\red Carolina Benedetti, Bruce Sagan, \textit{Antipodes and involutions}, arXiv:1410.5023} for other Hopf algebras.)}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Double posets and $\EE$-partitions}

\begin{itemize}

\item A \textit{double poset} is a triple $\left(E, <_1, <_2\right)$, where $E$ is a finite set, and where $<_1$ and $<_2$ are two strict partial orders on $E$. (``Strict'' means ``smaller'', not ``smaller or equal''.)

\pause
\item Let $\EE = \left(E, <_1, <_2\right)$ be a double poset.
An \textit{$\EE$-partition} shall mean a map
$\phi : E \to \left\{ 1,2,3,\ldots\right\}$ such that:
\begin{itemize}
\item every $e \in E$ and $f \in E$ satisfying $e <_1 f$ satisfy
$\phi\left(e\right) \leq \phi\left(f\right)$;
\item every $e \in E$ and $f \in E$ satisfying $e <_1 f$ and
$f <_2 e$ satisfy $\phi\left(e\right) < \phi\left(f\right)$.
\end{itemize}

\only<3>{\item \textbf{Examples:}

\begin{itemize}

\item If $<_2$ is the same as $<_1$ (or, more, generally, if $<_2$ extends $<_1$), then the $\EE$-partitions are the {\bf weakly} increasing maps $\left(E, <_1\right) \to \left\{1,2,3,\ldots\right\}$ (also known as poset homomorphisms).

\item If $<_2$ is the same as $>_1$ (or, more, generally, if $<_2$ extends $>_1$), then the $\EE$-partitions are the {\bf strictly} increasing maps $\left(E, <_1\right) \to \left\{1,2,3,\ldots\right\}$.

\end{itemize}
}

\only<4>{\item \textbf{Examples:}

\begin{itemize}

\item In the general case, you get ``something inbetween'': weakly increasing maps $\left(E, <_1\right) \to \left\{1,2,3,\ldots\right\}$ satisfying some strict inequalities.

\item One specific examples: Semistandard tableaux of shape $\lambda / \mu$ are $\EE$-partitions for a special choice of $\EE$.

\end{itemize}
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Double posets: $\Gamma\left(\EE, w\right)$}

\begin{itemize}

\item
\only<1>{Double posets are a generous source of quasisymmetric functions. To wit: \\ }
If $\EE = \left(E, <_1, <_2\right)$ is a double poset, and
$w : E \to \left\{1, 2, 3, \ldots\right\}$ is a map, then we define
a power series $\Gamma\left(\EE , w\right) \in \kk\left[\left[x_1,x_2,x_3,\ldots\right]\right]$ by
\[
\Gamma\left(\EE , w\right)
= \sum_{\pi\text{ is an }\EE\text{-partition}}
  \xx_{\pi, w} ,
\qquad
\text{where } \xx_{\pi, w}
= \prod_{e \in E} x_{\pi\left(e\right)}^{w\left(e\right)} .
\]

\item Easy to see: $\Gamma\left(\EE, w\right) \in \QSym$.

\pause

\item \textbf{Examples:}
\begin{itemize}
\only<1>{\item \phantom{...}}
\only<2>{\item Let $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right)$
be a composition. Let $E = \left\{1, 2, \ldots, k\right\}$. Let $<_1$
be the usual $<$ relation, and let $<_2$ be the $>$ relation.
Let $w : E \to \left\{1, 2, 3, \ldots\right\}$ send each $i$ to $\alpha_i$.
Then,
\[
\Gamma\left(\EE, w\right) = M_\alpha .
\]
}
\only<3>{\item Let $n \in \NN$ and $I \subseteq \left\{1, 2, \ldots, n-1\right\}$.
Then, there exists a double poset $\EE$ and a map $w$ with
\begin{align*}
\Gamma\left(\EE, w\right)
&= \sum_{\substack{i_1 \leq i_2 \leq \cdots \leq i_n; \\
                  i_j < i_{j+1} \text{ whenever } j \in I}}
  x_{i_1} x_{i_2} \cdots x_{i_n} .
\end{align*}
This power series is known as the $\alpha$-th
\textit{fundamental quasisymmetric function}, usually called
$F_\alpha$ or $L_\alpha$. Here, $\alpha$ is a composition formed by
the ``gaps'' between the elements of $I \cup \left\{0, n\right\}$.
}
\only<4>{\item Schur functions (including those of skew shapes and worse).
\item Dual immaculate functions.
\item $P$-partition enumerators (in Gessel's language), or $\left(P, \omega\right)$-partition enumerators (in Stanley's).
\item ``Weighted'' versions of the above.
}
\end{itemize}
\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Double posets: $\Gamma\left(\EE, w\right)$}

\begin{itemize}

\item \textbf{What is the antipode of $\Gamma\left(\EE, w\right)$ ?}
\pause
\item No general answer, but one for \textit{tertispecial} double posets.

\end{itemize}

\end{frame}

\begin{frame}
\fti{Tertispecial double posets}

\begin{itemize}

\item A double poset $\EE = \left(E, <_1, <_2\right)$ is called:
\begin{itemize}
\item \textit{special} if the relation $<_2$ is a total order.
\pause
\item \textit{semispecial} if every two $<_1$-comparable elements of $E$ are $<_2$-comparable.
\pause
\item \textit{tertispecial} if it satisfies the following condition: If $a$ and $b$ are two
elements of $E$ such that $a$ is $<_1$-covered by $b$ (that is, $a <_1 b$, but no $c \in E$ satisfies $a <_1 c <_1 b$), then $a$ and $b$ are $<_2$-comparable.
\end{itemize}

\pause
\item Special $\Longrightarrow$ semispecial $\Longrightarrow$ tertispecial.
\pause
\item {\bf WANTED: } a better name!
\pause
\item \textbf{Examples:}
\begin{itemize}
\item The posets whose $\EE$-partitions are semistandard tableaux are tertispecial.
\item The posets generating $M_\alpha$ and $F_\alpha$ are special (at least if appropriately chosen).
\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{The antipode of $\Gamma\left(\EE, w\right)$}

\begin{itemize}

\item \textbf{Theorem (\href{http://www.sciencedirect.com/science/article/pii/S0012365X98001423}{\red Malvenuto, Reutenauer, 1998}).}
Let $\left(E, <_1, <_2\right)$ be a tertispecial double poset.
Let $w : E \to \left\{1, 2, 3, \ldots\right\}$. Then, the antipode $S$ of $\QSym$ satisfies
\[
S\left(\Gamma\left(\left(E, {\blue <_1}, <_2\right), w\right)\right)
= \left(-1\right)^{\left|E\right|}
\Gamma\left(\left(E, {\blue >_1}, <_2\right), w\right) ,
\]
where $>_1$ denotes the opposite relation of $<_1$.

\pause
\item \textbf{Examples:}

\begin{itemize}

\item The formula for $S\left(M_\alpha\right)$ given above.
\pause
\item A classical formula for $S\left(F_\alpha\right)$.
\item The formula $S\left(s_{\lambda / \mu}\right) = \left(-1\right)^{\left|\lambda/\mu\right|} s_{\lambda^t / \mu^t}$ for skew Schur functions.
\item Benedetti's and Sagan's formulas for antipodes of dual immaculate functions (only for a few simple shapes).
\item Gessel's(?) formula for the antipode of a $P$-partition enumerator.

\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Generalizing further: $\EE$-partitions meet P\'olya enumeration}

\begin{itemize}

\item \textbf{Theorem (G.).} Let $\EE = \left(E, <_1, <_2\right)$ be a tertispecial double poset.
Let $\Par \EE$ denote the set of all $\EE$-partitions.
Let $w : E \to \left\{1, 2, 3, \ldots\right\}$. Let $G$ be a finite
group which acts on $E$. Assume that $G$ preserves both
relations $<_1$ and $<_2$, and also preserves $w$.
Then, $G$ acts also on the set $\Par \EE$.
\pause
\\ For any $G$-orbit $O$ on
$\operatorname{Par}\EE$, we define a monomial $\xx_{O, w}$
by
\[ \xx_{O, w} = \xx_{\pi, w} \qquad \text{ for some element }
\pi \text{ of } O
\]
(this does not depend on the choice of $\pi$).
Let
\begin{align*}
\Gamma\left(\EE, w, G\right) &= \sum_{O\text{ is a }
G\text{-orbit on } \operatorname{Par}\EE} \xx_{O, w} ; \\
\Gamma^+\left(\EE, w, G\right) &= \sum_{O\text{ is an }E\text{-coeven }
G\text{-orbit on } \operatorname{Par}\EE} \xx_{O, w} .
\end{align*}
\only<2>{Here, an orbit $O$ is said to be \textit{$E$-coeven}
if for every $g \in G$ and every $\pi \in O$ satisfying $g\pi = \pi$,
the action of $g$ on $E$ is an even permutation of $E$.}
\only<3-4>{Then, $\Gamma\left(\EE, w, G\right) \in \QSym$,
$\Gamma^+\left(\EE, w, G\right) \in \QSym$, and
\[
S\left(\Gamma\left(\EE, w, G\right)\right)
= \left(-1\right)^{\left|E\right|}
\Gamma^+\left(\left(E, >_1, <_2\right), w, G\right) .
\]}
\only<4>{
Inspired by Katharina Jochemko's work (\href{http://arxiv.org/abs/1310.0838}{\red arXiv:1310.0838}).
}
\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of Malvenuto-Reutenauer formula: preliminaries}

\begin{itemize}

\item I am not going to focus on my generalization. Instead I shall sketch my proof of the Malvenuto-Reutenauer result, which I consider the better part of my paper.
\pause
\item \textbf{More notations:}
Let $\EE = \left(E, <_1, <_2\right)$ be a double poset.

\begin{itemize}

\item
Then, $\Adm \EE$ will mean the set of all pairs
$\left(P, Q\right)$, where $P$ and $Q$ are subsets of $E$ such that:
\begin{itemize}
\item $P \cap Q = \varnothing$,
\item $P \cup Q = E$,
\item no $p \in P$ and $q \in Q$ satisfy $q <_1 p$.
\end{itemize}
These pairs $\left(P, Q\right)$ are
called the \textit{admissible partitions} of $\EE$.

\pause
\item For
any $T \subseteq E$, we let $\EE\mid_T$ denote the double poset
$\left(T, <_1, <_2\right)$, where $<_1$ and $<_2$ (by abuse of
notation) denote the restrictions of the relations $<_1$ and $<_2$
to $T$.

\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of Malvenuto-Reutenauer formula: $\Delta\left(\Gamma\left(\EE, w\right)\right)$}

\begin{itemize}

\item \textbf{Lemma.} Let $\EE = \left(E, <_1, <_2\right)$ be a double poset. Let
$w : E \to \left\{1, 2, 3, \ldots\right\}$ be a map.
Then,
\[
\Delta\left(\Gamma\left(\EE, w\right)\right)
= \sum_{\left(P, Q\right) \in \Adm \EE}
\Gamma\left(\EE\mid_P, w\mid_P\right)
\otimes \Gamma\left(\EE\mid_Q, w\mid_Q\right) .
\]

\pause
\item This is easy to prove if you believe in the formula
\[
\Delta\left(f\right) = f\left(x_1 < x_2 < x_3 < \cdots < y_1 < y_2 < y_3 < \cdots\right) .
\]
This formula would suggest that $\Delta\left(\Gamma\left(\EE, w\right)\right)$
is a sum over ``$\EE$-partitions into the totally ordered set
$\left\{x_1 < x_2 < x_3 < \cdots < y_1 < y_2 < y_3 < \cdots\right\}$''.
Any such $\EE$-partition $\pi$ splits $E$ into two subsets
$P = \pi^{-1}\left(\left\{x_1 < x_2 < x_3 < \cdots\right\}\right)$ and
$Q = \pi^{-1}\left(\left\{y_1 < y_2 < y_3 < \cdots\right\}\right)$, which
satisfy $\left(P, Q\right) \in \Adm \EE$.

\pause

\item There is also a pedestrian proof in my preprint, which needs no
such witchcraft.

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of Malvenuto-Reutenauer formula: Strategy, part 1}

\begin{itemize}

\item Once again, this is what we are proving: \\
\only<1>{\textbf{Theorem (\href{http://www.sciencedirect.com/science/article/pii/S0012365X98001423}{\red Malvenuto, Reutenauer, 1998}).}
Let $\left(E, <_1, <_2\right)$ be a tertispecial double poset.
Let $w : E \to \left\{1, 2, 3, \ldots\right\}$. Then, the antipode $S$ of $\QSym$ satisfies
\[
S\left(\Gamma\left(\left(E, {\blue <_1}, <_2\right), w\right)\right)
= \left(-1\right)^{\left|E\right|}
\Gamma\left(\left(E, {\blue >_1}, <_2\right), w\right) ,
\]
where $>_1$ denotes the opposite relation of $<_1$.}
\only<2->{\textbf{Notation:} If $\EE = \left(E, {\blue <_1}, <_2\right)$, then write $\EE^c$ for
$\left(E, {\blue >_1}, <_2\right)$. \\
\textbf{Theorem (\href{http://www.sciencedirect.com/science/article/pii/S0012365X98001423}{\red Malvenuto, Reutenauer, 1998}).}
Let $\EE = \left(E, <_1, <_2\right)$ be a tertispecial double poset.
Let $w : E \to \left\{1, 2, 3, \ldots\right\}$. Then, the antipode $S$ of $\QSym$ satisfies
\[
S\left(\Gamma\left(\EE, w\right)\right)
= \left(-1\right)^{\left|E\right|}
\Gamma\left(\EE^c, w\right) ,
\]
}

\only<3>{
\item Proceed by strong induction over $\left|E\right|$. So, WLOG,
the Theorem is proven for all smaller tertispecial double posets.

\item The case $\left|E\right| = 0$ is easy, so WLOG assume
$\left|E\right| > 0$.
}
\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of Malvenuto-Reutenauer formula: Strategy, part 2}

\begin{itemize}

\item Recall the commutative diagram for the antipode:

\[
\xymatrix@C=4pc@R=1pc{
& H \ar[dl]_-{\Delta} \ar[dr]^-{\Delta} \ar[dd]^{\varepsilon} & \\
H \otimes H \ar[dd]_{\operatorname*{id}\otimes S} & & H \otimes H \ar[dd]^{S\otimes\operatorname*{id}} \\
& \kk \ar[dd]^{u} & \\
H \otimes H \ar[dr]_{m} & & H \otimes H \ar[dl]^{m} \\
& H &
}
\]

It yields $m \circ \left(S \otimes \id\right) \circ \Delta = u \circ \varepsilon$. Thus,
\[
\left(m \circ \left(S \otimes \id\right) \circ \Delta\right) \left(\Gamma\left(\EE, w\right)\right)
= \left(u \circ \varepsilon\right) \left(\Gamma\left(\EE, w\right)\right)
= 0
\]
(since $\Gamma\left(\EE, w\right)$ has no constant term, and thus is
annihilated by $\varepsilon$).

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of Malvenuto-Reutenauer formula: Strategy, part 3}

\begin{itemize}

\item Thus,
\begin{align}
0
&= \left(m \circ \left(S \otimes \id\right) \circ
\Delta\right) \left(\Gamma\left(\EE, w\right)\right)
= m \left(\left(S \otimes \id\right) \left(
\Delta \left(\Gamma\left(\EE, w\right)\right)\right)\right)
\nonumber\\
&= m \left(\left(S \otimes \id\right) \left(
\sum_{\left(P, Q\right) \in \Adm \EE}
\Gamma\left(\EE\mid_P, w\mid_P\right)
\otimes \Gamma\left(\EE\mid_Q, w\mid_Q\right) \right) \right)
\nonumber \\
& \qquad \left(\text{by the lemma on } \Delta \left(\Gamma\left(\EE, w\right)\right)
\right)
\nonumber\\
&= \sum_{\left(P, Q\right) \in \Adm \EE}
S\left(\Gamma\left(\EE\mid_P, w\mid_P\right)\right)
\Gamma\left(\EE\mid_Q, w\mid_Q\right)
\nonumber
\end{align}

\pause
\item On the other hand, let's say that we can show
\begin{align*}
0
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\Gamma\left(\EE^c\mid_P, w\mid_P\right)
\Gamma\left(\EE\mid_Q, w\mid_Q\right)
\end{align*}
Then, I claim, we will be done!

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of Malvenuto-Reutenauer formula: Strategy, part 4}

\begin{itemize}

\item Why will we be done?

\item The two equalities
\begin{align*}
0
&= \sum_{\left(P, Q\right) \in \Adm \EE}
S\left(\Gamma\left(\EE\mid_P, w\mid_P\right)\right)
\Gamma\left(\EE\mid_Q, w\mid_Q\right)
;\\
0
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\Gamma\left(\EE^c\mid_P, w\mid_P\right)
\Gamma\left(\EE\mid_Q, w\mid_Q\right)
\end{align*}
have the same LHS. The sums on their RHSes are equal to each other term by term
\textbf{except possibly} the $\left(P, Q\right) = \left(E, \varnothing\right)$ terms.
\only<2>{
\begin{itemize}
\item Why? We need to show that if $\left(P, Q\right) \in \Adm \EE$ satisfies
$\left(P, Q\right) \neq \left(E, \varnothing\right)$, then
$S\left(\Gamma\left(\EE\mid_P, w\mid_P\right)\right) 
= \left(-1\right)^{\left|P\right|}
\Gamma\left(\EE^c\mid_P, w\mid_P\right)$).
\item This is easy: Check that $\EE\mid_P$ is tertispecial and that
$\left(\EE\mid_P\right)^c = \EE^c\mid_P$. Now, $\left|P\right| < \left|E\right|$,
so the induction hypothesis yields
$S\left(\Gamma\left(\EE\mid_P, w\mid_P\right)\right) = \left(-1\right)^{\left|P\right|}
\Gamma\left(\left(\EE\mid_P\right)^c, w\mid_P\right)
= \left(-1\right)^{\left|P\right|}
\Gamma\left(\EE^c\mid_P, w\mid_P\right)$).
\end{itemize}
}
\only<3>{
\item So the $\left(P, Q\right) = \left(E, \varnothing\right)$ terms must also
be equal. But this means $S\left(\Gamma\left(\EE, w\right)\right) = \left(-1\right)^{\left|E\right|} \Gamma\left(\EE^c, w\right)$.
\\ So, yeah, we will be done then.
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{The crucial identity}

\begin{itemize}

\item So it remains to prove
\begin{align*}
0
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\Gamma\left(\EE^c\mid_P, w\mid_P\right)
\Gamma\left(\EE\mid_Q, w\mid_Q\right) .
\end{align*}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of the crucial identity, part 1}

\begin{itemize}

\item We have
\begin{align*}
& \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\Gamma\left(\EE^c\mid_P, w\mid_P\right)
\Gamma\left(\EE\mid_Q, w\mid_Q\right)
\end{align*}
\only<1>{
\begin{align*}
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\left(\sum_{\sigma \text{ is a }\left(P, >_1, <_2\right)\text{-partition}}
\xx_{\sigma, w\mid_P}\right) \\
& \qquad\qquad
\left(\sum_{\tau \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}
\xx_{\tau, w\mid_Q}\right)
\end{align*}
}
\only<2>{
\begin{align*}
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\sum_{\substack{\left(\sigma, \tau\right); \\
                \sigma : P \to \left\{1, 2, 3, \ldots\right\}; \\
                \tau : Q \to \left\{1, 2, 3, \ldots\right\}; \\
                \sigma \text{ is a }\left(P, >_1, <_2\right)\text{-partition;} \\
                \tau \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}}
\xx_{\sigma, w\mid_P} \xx_{\tau, w\mid_Q}
\end{align*}
}
\only<3>{
\begin{align*}
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\sum_{\substack{\pi : E \to \left\{1, 2, 3, \ldots\right\}; \\
                \pi\mid_P \text{ is a }\left(P, >_1, <_2\right)\text{-partition;} \\
                \pi\mid_Q \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}}
\underbrace{\xx_{\pi\mid_P, w\mid_P} \xx_{\pi\mid_Q, w\mid_Q}}_{=\xx_{\pi, w}}
\end{align*}
}
\only<4>{
\begin{align*}
&= \sum_{\left(P, Q\right) \in \Adm \EE}
\left(-1\right)^{\left|P\right|}
\sum_{\substack{\pi : E \to \left\{1, 2, 3, \ldots\right\}; \\
                \pi\mid_P \text{ is a }\left(P, >_1, <_2\right)\text{-partition;} \\
                \pi\mid_Q \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}}
\xx_{\pi, w} .
\end{align*}
}
\only<5->{
\begin{align*}
&= \sum_{\pi : E \to \left\{1, 2, 3, \ldots\right\}}
\left(
\sum_{\substack{\left(P, Q\right) \in \Adm \EE; \\
                \pi\mid_P \text{ is a }\left(P, >_1, <_2\right)\text{-partition;} \\
                \pi\mid_Q \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}}
\left(-1\right)^{\left|P\right|} \right)
\xx_{\pi, w} .
\end{align*}
}
\only<6>{
\item So it suffices to prove that, for every map
$\pi : E \to \left\{1,2,3,\ldots\right\}$, we have
\[
\sum_{\substack{\left(P, Q\right) \in \Adm \EE ; \\
                \pi\mid_P \text{ is a }\left(P, >_1, <_2\right)\text{-partition;} \\
                \pi\mid_Q \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}}
\left(-1\right)^{\left|P\right|}
= 0 .
\]
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Proof of the crucial identity, part 2}

\begin{itemize}

\item We must prove that, for every map
$\pi : E \to \left\{1,2,3,\ldots\right\}$, we have
\[
\sum_{\substack{\left(P, Q\right) \in \Adm \EE ; \\
                \pi\mid_P \text{ is a }\left(P, >_1, <_2\right)\text{-partition;} \\
                \pi\mid_Q \text{ is a }\left(Q, <_1, <_2\right)\text{-partition}}}
\left(-1\right)^{\left|P\right|}
= 0 .
\]

\pause

\item The strategy: Find an involution $T$ on the set of all
$\left(P, Q\right) \in \Adm \EE$ satisfying the two conditions under
the summation sign. Show that this $T$ reverses the sign of
$\left(-1\right)^{\left|P\right|}$.

\pause

\item The definition of $T$ is simple: Let
\[
F = \left\{e \in E \mid \pi\left(e\right) \text{ is minimum}\right\} .
\]
Choose \textbf{minimal} element $f$ of the poset $\left(F, <_2\right)$
(that is, no $g \in F$ satisfies $g <_2 f$).
Now, the map $T$ sends a $\left(  P,Q\right)  \in Z$ to
$
\begin{cases}
\left(  P\cup\left\{  f\right\}  ,Q\setminus\left\{  f\right\}  \right)  , &
\text{if }f\notin P;\\
\left(  P\setminus\left\{  f\right\}  ,Q\cup\left\{  f\right\}  \right)  , &
\text{if }f\in P
\end{cases}
$.

\item Not so simple: the proof that it works. See the preprint.

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{A few words on the generalization with the group action}

\begin{itemize}

\item The generalization where $G$ acts on $E$ is proven by reduction to
the Malvenuto-Reutenauer formula. The reduction uses a ``quotient poset''
construction (idea from Jochemko).

\pause

\item Neat exercise (a classical lemma used in the proof): \\ Let $\left(E, <\right)$ be a poset, and $G$ be a finite
group acting on $E$, preserving $<$. Let $g \in G$. Let $E^g$ be the
set of all orbits of $g$ on $E$. Define a binary relation $<^g$ on $E^g$ by
\[
\left(u <^g v\right) \Longleftrightarrow \left(\text{there exist }a \in u\text{ and } b \in v \text{ such that } a < b \right).
\]
Then, $\left(E^g, <^g\right)$ is a poset. \\
Actually, $g$ can be replaced by a subgroup here.

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{References}

\only<1,3->{
This chapter was about:

\begin{itemize}

\item {\red\href{http://web.mit.edu/~darij/www/algebra/dp-abstr.pdf}{Darij Grinberg, \textit{Double posets and the antipode of
QSym}}}.

\end{itemize}
}

\only<2>{
The work incorporated ideas from:

\begin{itemize}

\item {\red \href{http://people.brandeis.edu/~gessel/homepage/papers/multipartite.pdf}{Ira M. Gessel, \textit{Multipartite
P-partitions and Inner Products of Skew Schur Functions}}, 1984.} (I think $\QSym$ originates here. Antipodes are not studied, but lots of the groundwork is laid.)

\item {\red \href{http://www.sciencedirect.com/science/article/pii/S0012365X98001423}{Claudia Malvenuto, Christophe Reutenauer,
\textit{Plethysm and conjugation of quasi-symmetric functions}}, 1995.} (Original statement of Malvenuto-Reutenauer antipode formula, relatively clumsy (IMHO).)

\item {\red \href{http://www.sciencedirect.com/science/article/pii/S0097316510001652}{Claudia Malvenuto, Christophe Reutenauer,
\textit{A self paired Hopf algebra on double posets and
a Littlewood-Richardson rule}}, 2011.} (The notion of a double poset is introduced here, along with the $\Gamma\left(\EE, w\right)$
and the lemma about $\Delta\left(\Gamma\left(\EE, w\right)\right)$.
Surprisingly, no connection is made to the antipode formula!)

\item {\red \href{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p52/pdf}{Katharina Jochemko, \textit{Order polynomials and
P\'{o}lya's enumeration theorem}}, 2014.} (The group action comes from here, though the setting is a lot less general and the claims weaker.)

\end{itemize}
}

\only<3>{
Related work:

\begin{itemize}

\item {\red \href{http://arxiv.org/abs/1410.5023v3}{Carolina Benedetti, Bruce Sagan, \textit{Antipodes
and involutions}}, 2015.} (Other Hopf algebras. For $\QSym$, much weaker result, but the method is more combinatorial.)

\item See references in my preprint for more.

\end{itemize}

\textbf{Thanks} to Katharina Jochemko for the original inspiration, to Victor Reiner for teaching me $P$-partitions, and to you for listening!
}
\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Chapter 2}
\begin{center}
{\Huge \bf \sc Chapter 2} \\
\noindent\rule[0.5ex]{\linewidth}{1pt}
{\Large \bf The Bernstein homomorphism}
\end{center}
\vspace{1cm}
Reference:
\begin{itemize}
\item \href{http://web.mit.edu/~darij/www/algebra/bernsteinproof.pdf}{\red Darij Grinberg, \textit{The Bernstein homomorphism via
Aguiar-Bergeron-Sottile universality}}. \\
\end{itemize}
\end{frame}

\begin{frame}
\fti{More on graded modules}

\begin{itemize}

\item We shall need some more general Hopf algebra theory.

\item If $H$ is a graded $\kk$-module ($H = \bigoplus\limits_{n \in \NN} H_n$, where $0 \in \NN$), then
\begin{itemize}
\item for any $n \in \NN$, we let $\pi_n : H \to H$ denote the canonical projection onto $H_n$;
\item for any composition $\alpha = \left(a_1, a_2, \ldots, a_k\right)$, we let
$\pi_\alpha : H^{\otimes k} \to H^{\otimes k}$ denote the map
$\pi_{a_1} \otimes \pi_{a_2} \otimes \cdots \otimes \pi_{a_k}$.
\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{More on algebras}

\begin{itemize}

\item For any $\kk$-algebra $A$ and any $k \in \NN$, we define a $\kk$-linear
$m^{\left(k-1\right)} : A^{\otimes k} \to k$ recursively
as follows: We set $m^{\left(  -1\right)  }=u_{A}$ (the unity map,
sending $1_{\kk}$ to $1_A$), $m^{\left(  1\right)
}=\id_{A}$ and%
\[
m^{\left(  k\right)  }=m\circ\left(  \id_{A}\otimes
m^{\left(  k-1\right)  }\right)  \ \ \ \ \ \ \ \ \ \ \text{for every }k\geq1.
\]
The maps $m^{\left(  k-1\right)  }:A^{\otimes k}\rightarrow A$ are called the
\textit{iterated multiplication maps} of $A$.

\item Or, in simpler language: $m^{\left(k-1\right)}$ is the
$\kk$-linear map $A^{\otimes k}\to A$
which sends every $a_{1}\otimes a_{2}\otimes\cdots\otimes a_{k}\in A^{\otimes
k}$ to $a_{1}a_{2}\cdots a_{k}$.

\pause

\item But we want to dualize... and the simpler language won't help us
do this.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{More on coalgebras}

\begin{itemize}

\item For any $\kk$-coalgebra $C$ and any $k \in \NN$, we define a
$\kk$-linear map
$\Delta^{\left( k-1\right)  }:C\rightarrow C^{\otimes k}$ recursively
as follows: We set
$\Delta^{\left(  -1\right)  }=\varepsilon_{C}$ (the counit),
$\Delta^{\left(  1\right) }=\id_{C}$ and
\[
\Delta^{\left(  k\right)  }=\left(  \operatorname*{id}\nolimits_{C}%
\otimes\Delta^{\left(  k-1\right)  }\right)  \circ\Delta
\ \ \ \ \ \ \ \ \ \ \text{for every }k\geq1.
\]
The maps $\Delta^{\left(  k-1\right)  }:C\rightarrow C^{\otimes k}$ are called
the \textit{iterated comultiplication maps} of $C$.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The second (internal) coalgebra structure on $\QSym$, part 1}

\begin{itemize}

\item Now to ``something completely different'': a second way to
turn $\QSym$ into a $\kk$-bialgebra. (Implicit in Gessel's 1984 paper.)

\item The counit, again, is easy to define:
\[
\varepsilon_P\left(f\right) = f\left(1,0,0,0,\ldots\right).
\]

Equivalently, $\varepsilon_P\left(M_\alpha\right) = 1$ if the
composition $\alpha$ has $\leq 1$ entry, and $= 0$ otherwise.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The second (internal) coalgebra structure on $\QSym$, part 2}

\begin{itemize}

\only<1>{
\item The comultiplication, the safe way: If $\alpha$ is a composition,
then set
\[
\Delta_{P}\left(  M_{\alpha}\right)  =\sum_{A} M_{\operatorname*{row}A}\otimes
M_{\operatorname*{column}A}
\]
where the sum is over all matrices $A$ with entries in $\NN$ such that
\begin{itemize}
\item no row of $A$ is the zero vector;
\item no column of $A$ is the zero vector;
\item reading the entries of $A$ (from left to right, row by row,
starting with the top row) gives the composition $\alpha$, possibly
with some zeroes interspersed.
\end{itemize}
Here,
\begin{itemize}
\item $\operatorname{row} A$ denotes the entrywise sum of all columns
of $A$;
\item $\operatorname{column} A$ denotes the entrywise sum of all rows
of $A$.
\end{itemize}
}

\only<2-3>{
\item The comultiplication, the ``right'' way:
\begin{align*}
\Delta\left(f\right) &= f\left(x_1 y_1 < x_1 y_2 < x_1 y_3 < \cdots \right. \\
                      & \qquad \left.       < x_2 y_1 < x_2 y_2 < x_2 y_3 < \cdots \right. \\
                      & \qquad \left.        < x_3 y_1 < x_3 y_2 < x_3 y_3 < \cdots \right)
\end{align*}
(these are all products $x_i y_j$ in lexicographic order).
Again, we pretend that this is all well-defined.
}

\only<3>{
\item The comultiplication $\Delta_P$ and the counit $\varepsilon_P$
make the $\kk$-algebra $\QSym$ into a $\kk$-bialgebra (but not graded
and not a Hopf algebra). They are called the \textit{second}, or
\textit{internal}, comultiplication and counit.
}

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{ABS (Aguiar-Bergeron-Sottile) universal property, part 1}

\begin{itemize}

\item Aguiar, Bergeron and Sottile, in their 2003 paper
``Combinatorial Hopf algebras and generalized Dehn-Sommerville
relations'' (updated version:
{\red \url{http://www.math.cornell.edu/~maguiar/CHalgebra.pdf}})
proved a
universal property (henceforth \textit{ABS property}) for $\QSym$.

\item The proof is surprisingly simple (the dual of $\QSym$ is
$\operatorname{NSym}$, which is a free algebra and thus has a
universal property; there are a few more details, but that's basically
it), but the property quite useful.

\pause

\item The version you'll see here is not the strongest.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{ABS (Aguiar-Bergeron-Sottile) universal property, part 2}

\begin{itemize}

\item \textbf{ABS property:} \\
Let $H$ be a connected graded Hopf algebra (over the commutative ring
$\kk$). Let $\zeta : H \to \kk$ be a $\kk$-algebra homomorphism. \\

\pause

\textbf{(a)} Then, there exists a unique graded $\kk$-coalgebra
homomorphism $\Psi : H \to \QSym$ for
which the diagram
\[
\xymatrix{
H \ar[rr]^-{\Psi} \ar[dr]_{\zeta} & & \QSym\ar[dl]^{\varepsilon_P} \\
& \kk&
}
\]
is commutative.

\pause

\textbf{(b)} This $\Psi$ is a $\kk$-Hopf algebra homomorphism.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{ABS (Aguiar-Bergeron-Sottile) universal property, part 3}

\begin{itemize}

\item \textbf{ABS property (continued):}

\textbf{(c)} For every composition $\alpha=\left(  a_{1},a_{2},\ldots
,a_{k}\right)  $, define a $\kk$-linear map $\zeta_{\alpha
}:H\rightarrow\kk$ as the composition
\[
\xymatrixcolsep{3pc}
\xymatrix{
H \ar[r]^-{\Delta^{(k-1)}} & H^{\otimes k} \ar[r]^-{\pi_\alpha} & H^{\otimes
k}
\ar[r]^-{\zeta^{\otimes k}} & \kk^{\otimes k} \ar[r]_{\cong}^{m^{\left(k-1\right)}} & \kk}%
.
\]
(Most of these arrows have been defined a few slides before.)

Then, the unique $\Psi$ above is given by the formula
\[
\Psi\left(  h\right)  =\sum_{\alpha\in\operatorname*{Comp}}\zeta_{\alpha
}\left(  h\right)  \cdot M_{\alpha}\ \ \ \ \ \ \ \ \ \ \text{for every }h\in
H
\]
(in particular, the sum on the right hand side of this equality has only
finitely many nonzero addends).

\only<2>{\textbf{Note:} Alternative definition of $\zeta_\alpha$,
if you know about convolution:
\[
\zeta_\alpha = \left(\zeta \circ \pi_{a_1}\right)
               \bigstar \left(\zeta \circ \pi_{a_2}\right)
               \bigstar \cdots
               \bigstar \left(\zeta \circ \pi_{a_k} \right).
\]
}
\only<3>{
\textbf{(d)} Assume that the $\mathbf{k}$-coalgebra $H$ is cocommutative.
Then, the unique $\Psi$ above satisfies $\Psi\left(  H\right)
\subseteq\Lambda$, where $\Lambda$ is the
$\mathbf{k}$-algebra of symmetric functions over $\mathbf{k}$.
}

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{What is the connection?}

\begin{itemize}

\item So the ABS property involves the second counit, $\varepsilon_P$.
It characterizes $\left(\QSym, \varepsilon_P\right)$ as a terminal
object in an arrow category (of connected graded Hopf algebras with
a $\kk$-algebra homomorphism to $\kk$).

\item What about the second comultiplication, $\Delta_P$ ?

\pause

\item \textbf{Surprising (for me) observation:} We get $\Delta_P$
``for free'' from the ABS property.

\item How?

\pause

\item
\begin{align*}
\Delta_P & : \QSym \to \QSym \otimes \QSym ; \\
\Psi & : H \to \QSym .
\end{align*}

These don't look like they match...

\pause

\item ... until we change the base ring (a.k.a. extend scalars).

\item Idea: Regard $\QSym \otimes \QSym$ as ``$\QSym$ over $\QSym$''.

\item For greater generality, we can replace some of the $\QSym$s by
a commutative algebra $A$.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Some notations}

\begin{itemize}

\item Let $A$ be a commutative $\kk$-algebra. Then, $A$ is just as good
a base ring as $\kk$. Every $\kk$-coalgebra
$H$ gives rise to an
$A$-coalgebra
$\underline{A} \otimes H$ by extension of scalars. \\
Here, $\underline{A}$ just denotes the $\kk$-algebra $A$, with all its
additional structure forgotten. (So far $A$ has no additional structure,
but we will later set $A = \QSym$, and then there will be a grading
and a coalgebra structure to forget.)

\item Similarly, every $\kk$-Hopf algebra $H$ induces an
$A$-Hopf algebra $\underline{A} \otimes H$. \\
Similarly for algebras, bialgebras, graded Hopf algebras, ...

\item For example, $\underline{A} \otimes \QSym \cong \QSym_A$, where
$\QSym_A$ denotes the graded Hopf algebra $\QSym$ defined over $A$
instead of $\kk$.

\pause

\item Let $H$ be a $\kk$-coalgebra, and let $G$ be an
$A$-coalgebra. A $\kk$-linear map $f:H\rightarrow G$ is said to be a
$\left(  \kk,\underline{A}\right)  $\textit{-coalgebra homomorphism} if
the $A$-linear map
\[
\underline{A}\otimes H\rightarrow G, \qquad a \otimes h \mapsto a f\left(h\right)
\]
is an $A$-coalgebra homomorphism.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{ABS property after change of bases, part 1}

\begin{itemize}

\item \textbf{Consequence of ABS property:} \\
Let $A$ be a commutative $\kk$-algebra.
Let $H$ be a connected graded Hopf algebra (over the commutative ring
$\kk$). Let $\xi : H \to A$ be a $\kk$-algebra homomorphism.

\textbf{(a)} Then, there exists a unique graded $\left(\kk, A\right)$-coalgebra
homomorphism $\Xi : H \to \underline{A} \otimes \QSym$ for
which the diagram
\[
\xymatrix{
H \ar[rr]^-{\Xi} \ar[dr]_{\xi} & & \underline{A} \otimes\QSym\ar
[dl]^{\id_A \otimes\varepsilon_P} \\
& \underline{A} &
}
\]
is commutative.

\pause

\textbf{(b)} This $\Xi$ is a $\kk$-algebra homomorphism.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{ABS property after change of bases, part 2}

\begin{itemize}

\item \textbf{Consequence of ABS property (continued):}

\textbf{(c)} For every composition $\alpha=\left(  a_{1},a_{2},\ldots
,a_{k}\right)  $, define a $\kk$-linear map
$\xi_\alpha : H \to A$ as the composition
\[
\xymatrixcolsep{3pc}
\xymatrix{
H \ar[r]^-{\Delta^{(k-1)}} & H^{\otimes k} \ar[r]^-{\pi_\alpha} & H^{\otimes
k}
\ar[r]^-{\xi^{\otimes k}} & A^{\otimes k} \ar[r]^-{m^{(k-1)}} & A}
.
\]

Then, the unique $\Xi$ above is given by the formula
\[
\Xi\left(  h\right)  =\sum_{\alpha\in\operatorname*{Comp}}\xi_{\alpha}\left(
h\right)  \otimes M_{\alpha}\ \ \ \ \ \ \ \ \ \ \text{for every }h\in H
\]
(in particular, the sum on the right hand side of this equality has only
finitely many nonzero addends).

\only<1>{\textbf{Note:} Alternative definition of $\xi_\alpha$,
if you know about convolution:
\[
\xi_\alpha = \left(\xi \circ \pi_{a_1}\right)
               \bigstar \left(\xi \circ \pi_{a_2}\right)
               \bigstar \cdots
               \bigstar \left(\xi \circ \pi_{a_k}\right) .
\]
}
\only<2>{
\textbf{(d)} Assume that the $\mathbf{k}$-coalgebra $H$ is cocommutative.
Then, the unique $\Xi$ above satisfies $\Xi\left(  H\right)
\subseteq \underline{A} \otimes \Lambda$, where $\Lambda$ is the
$\mathbf{k}$-algebra of symmetric functions over $\mathbf{k}$.
}

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{ABS property after change of bases, part 3}

\begin{itemize}

\item \textbf{Proof idea:} Apply the ABS property to
$\underline{A}$, $\underline{A}\otimes H$ and $\xi^\sharp$ instead of
$\kk$, $H$ and $\zeta$, where
\[
\xi^\sharp : \underline{A} \otimes H \to \underline{A}, \qquad
a \otimes h \mapsto a \xi\left(h\right) .
\]

\item There is a bijection between the $\kk$-linear maps
$H \to \underline{A} \otimes G$ and the $A$-linear maps
$\underline{A} \otimes H \to \underline{A} \otimes G$ (where
$G$ is any $A$-module). (This is just the adjointness of induction
and restriction.) Use it back and forth, many times.

\item Some amount of work required to check that this bijection takes
maps where you expect it to take them, and that all the identifications
(e.g., $\varepsilon_P$ defined over $A$ is identified with
$\id_A \otimes \varepsilon_P$) play well together. (See the preprint.)

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The Bernstein homomorphism, part 1}

\begin{itemize}

\item Apply the Consequence of ABS property to $A = H$ and $\xi = \id$.
Obtain the following:

\item \textbf{Bernstein homomorphism theorem:} \\
Let $H$ be a \textbf{commutative} connected graded Hopf algebra (over
the commutative ring $\kk$).

\textbf{(a)} Then, there exists a unique graded $\left(\kk, H\right)$-coalgebra
homomorphism $\Xi : H \to \underline{H} \otimes \QSym$ for
which the diagram
\[
\xymatrix{
H \ar[rr]^-{\Xi} \ar[dr]_{\id} & & \underline{H} \otimes\QSym\ar
[dl]^{\id_H \otimes\varepsilon_P} \\
& \underline{H} &
}
\]
is commutative (that is, we have
$\id_H = \left(\id_H \otimes\varepsilon_P\right) \circ \Xi$). \\

Denote this $\Xi$ by $\beta_H$.

\pause

\textbf{(b)} This $\beta_H$ is a $\kk$-algebra homomorphism.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The Bernstein homomorphism, part 2}

\begin{itemize}

\item \textbf{Bernstein homomorphism theorem (continued):} \\

\textbf{(c)} For every composition $\alpha=\left(  a_{1},a_{2},\ldots
,a_{k}\right)  $, define a $\kk$-linear map $\xi_{\alpha
}:H\rightarrow\kk$ as the composition
\[
\xymatrixcolsep{3pc}
\xymatrix{
H \ar[r]^-{\Delta^{(k-1)}} & H^{\otimes k} \ar[r]^-{\pi_\alpha} & H^{\otimes
k} \ar[r]^-{m^{(k-1)}} & A}
.
\]

Then, $\beta_H$ (= the unique $\Xi$ above) is given by the formula
\[
\beta_H\left(  h\right)  =\sum_{\alpha\in\operatorname*{Comp}}\xi_{\alpha}\left(
h\right)  \otimes M_{\alpha}\ \ \ \ \ \ \ \ \ \ \text{for every }h\in H
\]
(in particular, the sum on the right hand side of this equality has only
finitely many nonzero addends).

\only<1>{\textbf{Note:} Alternative definition of $\xi_\alpha$,
if you know about convolution:
\[
\xi_\alpha = \pi_{a_1} \bigstar \pi_{a_2} \bigstar \cdots \bigstar \pi_{a_k} .
\]
}
\only<2>{
\textbf{(d)} Assume that the $\mathbf{k}$-coalgebra $H$ is cocommutative.
Then, $\beta_H\left(  H\right)
\subseteq \underline{H} \otimes \Lambda$, where $\Lambda$ is the
$\mathbf{k}$-algebra of symmetric functions over $\mathbf{k}$.
}

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The Bernstein homomorphism, part 3}

\begin{itemize}

\item \textbf{Bernstein homomorphism theorem (continued):} \\

Additionally, it is not hard to show:

\textbf{(e)} Let $\tau$ denote the twist map
$\QSym \otimes \QSym \to \QSym \otimes \QSym, \  a \otimes b \mapsto b \otimes a$.
Let $\Delta'_P = \tau \circ \Delta_P$ be the ``twisted second
comultiplication'' of $\QSym$. \\
Then, \[\beta_{\QSym} = \Delta'_P .\]
Thus, we have obtained $\Delta'_P$ as a particular case of the
Bernstein homomorphism.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The Bernstein homomorphism, part 4}

\begin{itemize}

\item \textbf{Bernstein homomorphism theorem (continued):} \\

\item The uniqueness part of the Consequence of ABS property can be
used to prove identities with $\beta_H$. For example: \\
\textbf{(f)} The diagram
\[
\xymatrixcolsep{5pc}\xymatrix{
H \ar[r]^{\beta_H} \ar[d]_{\beta_H} & \underline{H} \otimes \QSym \ar[d]_{\beta_H\otimes\id} \\
\underline{H} \otimes \QSym \ar[r]_-{\id\otimes\Delta'_P} & \underline{H} \otimes \underline{\QSym} \otimes \QSym
}
\]
is commutative.
\\
Thus, every commutative connected graded Hopf algebra $H$ becomes
a comodule over the ``second bialgebra'' $\QSym$.

\item This easily gives an alternative proof of the fact that the
second bialgebra is indeed a bialgebra (coassociative, etc.).

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The Bernstein homomorphism, history}

\begin{itemize}

\item The (restricted) Bernstein homomorphism $\beta_H : H \to
\underline{H} \otimes \Lambda$ for commutative-and-cocommutative $H$
appeared in
{\red \href{http://arxiv.org/abs/0804.3888}{Hazewinkel's ``Witt vectors''}},
\textsection 18.24. It is attributed to
Joseph N. Bernstein (who apparently used it to classify
PSH-algebras -- see Zelevinsky's LNM book).

\item I think the more general ``Bernstein homomorphism''
$\beta_H : H \to \underline{H} \otimes \QSym$ constructed above
(not assuming cocommutativity) is new.

\item That said, the Marne-la-Vall\'ee school has its own methods
(alphabets, generalized
Cauchy kernels, etc.)
which
probably lead to many of the same results. I don't know the details :(

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{The Bernstein homomorphism, part 5}

\begin{itemize}

\item \textbf{Bernstein homomorphism theorem (continued):} \\

\textbf{(g)} (Same notations as before.) We have
\[
\beta_{H}\circ S_{H}=\left(  \operatorname*{id}\nolimits_{H}\otimes
S_{\QSym}\right)  \circ\beta_{H},
\]
where $S_G$ means the antipode of a Hopf algebra $G$.

\item Again, this comes ``for free'' out of universal properties.

\item Probably more can be gotten this way. Idea: \\
$\beta_H$ is injective (since
$\left(\id_H \otimes \varepsilon_P\right) \circ \beta_H = \id_H$), and thus
``embeds'' $H$ into $\underline{H}\otimes\QSym \cong \QSym_H$.
Scare quotes because the ``embedding'' changes the base ring.
But $\underline{H} \otimes H \to \underline{H}\otimes\QSym \cong \QSym_H,
\ a \otimes b \mapsto a \beta_H\left(b\right)$ is a honest
graded $H$-Hopf algebra homomorphism. \\
\pause
$\Longrightarrow$ \textbf{Propagandistic slogan:} Every commutative
connected graded Hopf algebra embeds into $\QSym$. (Fine print: over
itself. But this should still be useful!)

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{References}

This chapter was about:

\begin{itemize}

\item {\red\href{http://web.mit.edu/~darij/www/algebra/bernsteinproof.pdf}{Darij Grinberg, \textit{The Bernstein homomorphism via
Aguiar-Bergeron-Sottile
universality}}}.

\end{itemize}

The work incorporated ideas from:

\begin{itemize}

\item Andrey V. Zelevinsky, \textit{Representations of Finite Classical Groups -- A Hopf Algebra Approach}, LNM \#869, Springer 1981.
(This is where the first ``Bernstein homomorphism'' appeared.)

\item {\red \href{http://arxiv.org/abs/0804.3888}{Michiel Hazewinkel, \textit{Witt vectors. Part 1}, arXiv:0804.3888}}.
(An unusual introduction to symmetric functions, emphasizing categorical
methods (among other things).)

\item {\red \href{http://www.math.cornell.edu/~maguiar/CHalgebra.pdf}{Marcelo Aguiar, Nantel Bergeron, Frank Sottile,
\textit{Combinatorial Hopf algebras and generalized Dehn-Sommerville
relations}}}. (The universal property of $\QSym$ with several
applications.)

\end{itemize}

\textbf{Thanks} to Marcelo Aguiar for helpful emails!

\end{frame}

\begin{frame}
\fti{Chapter 3}
\begin{center}
{\Huge \bf \sc Chapter 3} \\
\noindent\rule[0.5ex]{\linewidth}{1pt}
{\Large \bf On dual immaculate functions}
\end{center}
\vspace{1cm}
Reference:
\begin{itemize}
\item \href{http://web.mit.edu/~darij/www/algebra/dimcreation.pdf}{\red Darij Grinberg, \textit{Dual immaculate creation operators and a dendriform algebra structure on the quasisymmetric functions}}. \\
\end{itemize}

\end{frame}


\begin{frame}
\fti{Schur functions, part 1}

\begin{itemize}

\item I won't actually use Schur functions, but I'll talk about an
analogue; so let me recall their definition.

\item Let $\lambda$ be a partition. The \textit{Young diagram} of
$\lambda$ is like a matrix, but the rows have different lengths, and
are left-aligned; the $i$-th row has $\lambda_i$ cells.
\\
\textbf{Examples:}
\begin{itemize}
\item The Young diagram of $\left(3,2\right)$ has the form
\[
\ydiagram{3, 2} .
\]
\item The Young diagram of $\left(4,2,1\right)$ has the form
\[
\ydiagram{4, 2, 1}.
\]
\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Schur functions, part 2}

\begin{itemize}

\item A \textit{semistandard tableau} of shape $\lambda$ is the
Young diagram of $\lambda$, filled with positive integers, such that
\begin{itemize}
\item the entries in each \textbf{row} are \textbf{weakly} increasing;
\item the entries in each \textbf{column} are \textbf{strictly}
increasing.
\end{itemize}
\textbf{Examples:}
\only<1>{
\begin{itemize}
\item A semistandard tableau of shape $\left(3,2\right)$ is
\[
\begin{ytableau}
2 & 3 & 3 \\
3 & 5
\end{ytableau} .
\]
\item A semistandard tableau of shape $\left(4,2,1\right)$ is
\[
\begin{ytableau}
2 & 2 & 3 & 4 \\
3 & 4 \\
5
\end{ytableau} .
\]
\end{itemize}
}
\only<2-3>{
\begin{itemize}
\item The semistandard tableaux of shape $\left(3,2\right)$ are the arrays of
the form
\[
\begin{ytableau}
a & b & c \\
d & e
\end{ytableau}
\]
with $a \leq b \leq c$ and $d \leq e$ and $a < d$ and $b < e$.
\end{itemize}
}
\only<3>{
\item So the semistandard tableaux of a given shape $\lambda$ are the
$\EE$-partitions, for a certain double poset $\EE$ (which we can
choose to be special).
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Schur functions, part 3}

\begin{itemize}

\item Given a partition $\lambda$, we define the
\textit{Schur function} $s_\lambda$ as the power series
\[
s_\lambda = \sum\limits_{\substack{T \text{ is a semistandard} \\
\text{tableau of shape } \lambda}} \xx_T, \qquad
\text{where } \xx_T = \prod\limits_{p \text{ is a cell of }T} x_{T\left(p\right)}
\]
(where $T\left(p\right)$ denotes the entry of $T$ in $p$).

\item \textbf{Example:}

\begin{itemize}

\item
\[
s_{\left(3,2\right)} = \sum\limits_{\substack{a \leq b \leq c,\ d \leq e,\\
a < d,\  b < e}} x_a x_b x_c x_d x_e ,
\]
because the semistandard tableau
\[
T = \begin{ytableau}
a & b & c \\
d & e
\end{ytableau}
\]
contributes the addend $\xx_T = x_a x_b x_c x_d x_e$.

\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Schur functions, part 4}

\begin{itemize}

\item \textbf{Classical theorem:} The Schur function $s_\lambda$ is
a symmetric function (= an element of $\Lambda$)
for any partition $\lambda$.

\item \textbf{Classical theorem:} The family
$\left(s_\lambda\right)_{\lambda \in \Par}$ is a basis of the
$\kk$-module $\Lambda$.

% \item See any text on symmetric functions (e.g., Stanley's EC2, or
% Grinberg-Reiner) for the proof.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Dual immaculate functions, part 1}

\begin{itemize}

\item Dual immaculate functions are a quasisymmetric analogue (one
of several) of the Schur functions. They have been introduced
{\red \href{http://arxiv.org/abs/1208.5191v3}{in 2012 by
Berg, Bergeron, Saliola, Serrano and Zabrocki
(arXiv:1208.5191v3)}}.

\item Their original definition is complicated (they are defined as
the dual basis to a basis of $\operatorname{NSym}$, which is defined
using ``creation operators'' -- thus the name). We shall give an
equivalent definition.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Dual immaculate functions, part 2}

\begin{itemize}

\item Let $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right)$
be a composition. The \textit{Young diagram} of
$\alpha$ is like a matrix, but the rows have different lengths, and
are left-aligned; the $i$-th row has $\alpha_i$ cells (there are $k$
rows in total).
\\
\textbf{Examples:}
\begin{itemize}
\item The Young diagram of $\left(3,2\right)$ has the form
\[
\ydiagram{3, 2} .
\]
\item The Young diagram of $\left(4,1,2\right)$ has the form
\[
\ydiagram{4, 1, 2}.
\]
\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Dual immaculate functions, part 3}

\begin{itemize}

\item An \textit{immaculate tableau} of shape $\alpha$ is the
Young diagram of $\alpha$, filled with positive integers, such that
\begin{itemize}
\item the entries in each \textbf{row} are \textbf{weakly} increasing;
\item the entries in \textbf{the first column} are \textbf{strictly}
increasing.
\end{itemize}
No requirements on the second, third, etc. columns!
\textbf{Examples:}
\only<1>{
\begin{itemize}
\item An immaculate tableau of shape $\left(3,2\right)$ is
\[
\begin{ytableau}
2 & 3 & 3 \\
3 & 3
\end{ytableau} .
\]
\item An immaculate tableau of shape $\left(4,1,2\right)$ is
\[
\begin{ytableau}
2 & 6 & 7 & 7 \\
3 \\
5 & 5
\end{ytableau} .
\]
\end{itemize}
}
\only<2-3>{
\begin{itemize}
\item The immaculate tableaux of shape $\left(3,2\right)$ are the arrays of
the form
\[
\begin{ytableau}
a & b & c \\
d & e
\end{ytableau}
\]
with $a \leq b \leq c$ and $d \leq e$ and $a < d$.
\end{itemize}
}
\only<3>{
\item So the immaculate tableaux of a given shape $\alpha$ are the
$\EE$-partitions, for a certain double poset $\EE$ (which we can
choose to be special).

\item Immaculate tableaux can also be viewed as certain labellings of
a binary tree (a special one -- a ``comb'').
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Dual immaculate functions, digression}

\begin{itemize}

\only<1>{
\item \textbf{Digression} (won't be used, but good to know): \\
I just said that immaculate tableaux can be viewed as certain
labellings of a binary tree; here is what I mean:
}
\only<2>{
\item The immaculate tableaux of shape $\left(3,1,2\right)$ are the
arrays
\[
\begin{ytableau}
a & b & c \\
d \\
e & f
\end{ytableau}
\]
satisfying $a \leq b \leq c$ and $e \leq f$ and $a < d < e$. In other
words, they are labellings
\[
\xymatrix@C=0.8pc@R=0.8pc{
& f \ar@{-}[dl] \\
e \ar@{-}[dr] & & & & c \ar@{-}[dl] \\
& d \ar@{-}[dr] & & b \ar@{-}[dl] \\
& & a
}
\text{ of the binary tree }
\xymatrix@C=0.8pc@R=0.8pc{
& \bullet \ar@{-}[dl] \\
\bullet \ar@{-}[dr] & & & & \bullet \ar@{-}[dl] \\
& \bullet \ar@{-}[dr] & & \bullet \ar@{-}[dl] \\
& & \bullet
}
\]
such that the label on each node is $<$ to the
label on its left child and $\leq$ to the label on its right child.
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Dual immaculate functions, part 4}

\begin{itemize}

\item Given a composition $\alpha$, we define the
\textit{dual immaculate function} $\mathfrak{S}^\ast_\alpha$ as the power series
\[
\mathfrak{S}^\ast_\alpha = \sum\limits_{\substack{T \text{ is an immaculate} \\
\text{tableau of shape } \alpha}} \xx_T, \qquad
\text{where } \xx_T = \prod\limits_{p \text{ is a cell of }T} x_{T\left(p\right)}
\]
(where $T\left(p\right)$ denotes the entry of $T$ in $p$).

\item \textbf{Example:}

\begin{itemize}

\item
\[
\mathfrak{S}^\ast_{\left(3,2\right)} = \sum\limits_{\substack{a \leq b \leq c,\ d \leq e,\\
a < d}} x_a x_b x_c x_d x_e ,
\]
because the immaculate tableau
\[
T = \begin{ytableau}
a & b & c \\
d & e
\end{ytableau}
\]
contributes the addend $\xx_T = x_a x_b x_c x_d x_e$.

\end{itemize}

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Dual immaculate functions, part 5}

\begin{itemize}

\item \textbf{Theorem:} The dual immaculate function $\mathfrak{S}^\ast_\alpha$ is
a quasisymmetric function (= an element of $\QSym$)
for any composition $\alpha$. \\
(This is actually pretty obvious, since the immaculate tableaux
are $\EE$-partitions.)

\item \textbf{Theorem:} The family
$\left(\mathfrak{S}^\ast_\alpha\right)_{\alpha \in \Comp}$ is a basis of the
$\kk$-module $\QSym$.

\item It is natural to consider this basis an analogue of the Schur
functions (although there are other contenders whose claims are
equally valid).

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Fundamental quasisymmetric functions, part 1}

\begin{itemize}

\item I mentioned the fundamental quasisymmetric functions $F_\alpha$
in Chapter 1, but now I'll need to define them in detail.

\pause

\item Let $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right)$
be a composition of size $n = \alpha_1 + \alpha_2 + \cdots + \alpha_k$.
Define a subset $D\left(\alpha\right)$ of $\left\{1,2,\ldots,n-1\right\}$
by
\begin{align*}
D\left(\alpha\right)
&= \left\{ \alpha_1, \alpha_1 + \alpha_2, \alpha_1 + \alpha_2 + \alpha_3,
          \ldots, \alpha_1 + \alpha_2 + \cdots + \alpha_{k-1} \right\} \\
&= \left\{\text{all nonempty partial sums of } \alpha \text{, except }\right. \\
& \qquad \qquad \left. \text{ for the total sum}\right\} .
\end{align*}

\item Define a power series $F_\alpha$ (also known as $L_\alpha$) by
\begin{align*}
F_\alpha
&= \sum_{\substack{i_1 \leq i_2 \leq \cdots \leq i_n; \\
                  i_j < i_{j+1} \text{ whenever } j \in D\left(\alpha\right)}}
  x_{i_1} x_{i_2} \cdots x_{i_n} .
\end{align*}

\pause

\item \textbf{Theorem:} The family $\left(F_\alpha\right)_{\alpha\in\Comp}$
is a basis of the $\kk$-module $\QSym$, called \textit{Gessel's
Fundamental basis}.

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Fundamental quasisymmetric functions, part 2}

\begin{itemize}

\item \textbf{Theorem.} For any composition $\alpha$, we have
\[
F_\alpha = \sum\limits_{\substack{\beta \in \Comp; \\ \beta \text{ refines } \alpha}} M_\beta .
\]

Here, a composition $\beta$ is said to \textit{refine} $\alpha$ if and
only if $\beta$ can be obtained by splitting each entry $\alpha_i$
of $\alpha$ into several which sum to $\alpha_i$.
\\
\only<1>{\textbf{Example.} $\left(2,1,3,4,2,2,1,3\right)$ refines $\left(3,3,8,4\right)$, because ...}
\only<2>{\textbf{Example.} $\left(\underbrace{2,1}_{\text{sum } 3},
\underbrace{3}_{\text{sum } 3},
\underbrace{4,2,2}_{\text{sum } 8},
\underbrace{1,3}_{\text{sum } 4}\right)$ refines $\left(3,3,8,4\right)$.}

\only<3>{
\item The antipode $S$ of $\QSym$ satisfies
\[
S\left(F_\alpha\right) = \left(-1\right)^{\left|\alpha\right|} F_{\omega\left(\alpha\right)}
\]
for each $\alpha \in \Comp$. Here, if $\alpha$ is a composition of $n$,
then $\omega\left(\alpha\right)$ is the composition of $n$ defined by
$D\left(\omega\left(\alpha\right)\right) = \left\{1,2,\ldots,n-1\right\}
\setminus \underbrace{\left(n-D\left(\alpha\right)\right)}_{=\left\{n-g\mid g \in D\left(\alpha\right)\right\}}$. \\
(This follows from Chapter 1.)
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Skewing by $R_\beta$: a quick definition}

\begin{itemize}

\item Let $\beta$ be a composition. We define the $\kk$-linear map
$R_\beta^\perp : \QSym \to \QSym$
(called \textit{skewing by the ribbon function $R_\beta$}) by
\[
R_{\beta}^{\perp}\left(  F_{\alpha}\right)  =%
\begin{cases}
F_{\left(  \alpha_{i+1},\alpha_{i+2},\ldots\alpha_{k}\right)  }, & \text{if
}\beta=\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{i}\right)  \text{ for } \\
& \qquad \text{ some }0\leq i\leq k;\\
0, & \text{otherwise}%
\end{cases}
\]
for every composition $\alpha = \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right)$.
\\
(This works because $\left(F_\alpha\right)_{\alpha\in\Comp}$
is a basis of the $\kk$-module $\QSym$.)

\item This is not the ``official'' definition of $R_\beta^\perp$, but
is equivalent and self-contained. (The ``official'' definition involves
the Hopf algebra $\operatorname{NSym}$, which is the graded dual of
$\QSym$.)

\pause

\item Note: $R_\beta^\perp$ lowers the degree by $\left|\beta\right|$.

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Zabrocki's ``dual creation operators''}

\begin{itemize}

\item For each composition $\alpha$, define a composition
$\alpha\odot\left(  m\right)$ as follows: If $\alpha
= \left(\alpha_1, \alpha_2, \ldots, \alpha_k\right)$, then
$\alpha\odot\left(  m\right)
= \left(\alpha_1, \alpha_2, \ldots, \alpha_{k-1}, \alpha_k + m\right)$.
(If $\alpha$ is the empty composition, then
$\alpha\odot\left(  m\right) = \left(m\right)$.)

\pause

\item For each positive integer $m$, define a $\kk$-linear map
$\mathbf{W}_m : \QSym \to \QSym$ by
\[
\mathbf{W}_m = \sum_{\alpha \in \Comp} \left(-1\right)^{\left|\alpha\right|} 
F_{\alpha\odot\left(  m\right)  } R_{\omega\left(  \alpha\right)  }^{\perp} .
\]
(The right hand side converges pointwise: Every $f \in \QSym$
is annihilated by all but finitely many addends.)

\only<2>{\item This construction is similar to the creation operators
defined on $\operatorname{NSym}$ for the (non-dual) immaculate
functions, and to the Bernstein creation operators on $\Lambda$
(\textbf{not} the Bernstein homomorphism of Chapter 2, but due to
the same Bernstein, and also appearing in Zelevinsky's book).}

\only<3>{\item \textbf{Theorem (Zabrocki, G.).} For every composition
$\alpha=\left(
\alpha_{1},\alpha_{2},\ldots,\alpha_k\right)  $, the dual
immaculate function $\mathfrak{S}_{\alpha}^{\ast}$ is
\[
\mathfrak{S}_{\alpha}^{\ast}=\left(  \mathbf{W}_{\alpha_{1}}\circ
\mathbf{W}_{\alpha_{2}}\circ\cdots\circ\mathbf{W}_{\alpha_k}\right)
\left(  1\right)  .
\]
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Dendriform structure on $\QSym$, introduction}

\begin{itemize}

\item My proof uses a \textit{dendriform algebra} structure on $\QSym$.
I won't explain the proof here, but I will define this structure.

\item I think the structure is foreshadowed (if not implicitly
introduced) in the works of Gl\^anffrwd P. Thomas (mainly
{\red \href{http://www.sciencedirect.com/science/article/pii/0001870877900421}{\textit{Frames, Young tableaux, and Baxter sequences}}}).
But I need to think about it more carefully.
\\
(There are well-known adjoint functors between Rota-Baxter algebras and
dendriform algebras:
{\red \href{http://arxiv.org/abs/math/0503647}{Kurusch Ebrahimi-Fard, Li Guo,
\textit{Rota-Baxter Algebras and Dendriform Algebras},
arXiv:math/0503647}})

\pause

\item Also, does anyone have a copy of Thomas's thesis? \\
({\blue Gl\^anffrwd P. Thomas,
\textit{Baxter Algebras and Schur Functions},
Ph.D. Thesis,  University College  of Swansea,  September  1974.})

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Dendriform structure on $\QSym$, part 1}

\begin{itemize}

\item For any monomial $\mathfrak{m}$, let $\Supp \mathfrak{m}$
denote the set $\left\{i \mid x_i \text{ appears in } \mathfrak{m}\right\}$.

\item \textbf{Example.} $\Supp \left(x_3^5 x_6 x_8\right) = \left\{3,6,8\right\}$.

\only<2>{
\item We define a binary operation $\left.  \prec\right.$ on the
$\kk$-module $\Powser$ as follows:

\begin{itemize}
\item On monomials, it should be given by
\[
\mathfrak{m}\left.  \prec\right.  \mathfrak{n}=\left\{
\begin{array}
[c]{c}%
\mathfrak{m}\cdot\mathfrak{n},\ \ \ \ \ \ \ \ \ \ \text{if }\min\left(
\operatorname*{Supp}\mathfrak{m}\right)  <\min\left(  \operatorname*{Supp}%
\mathfrak{n}\right)  ;\\
0,\ \ \ \ \ \ \ \ \ \ \text{if }\min\left(  \operatorname*{Supp}%
\mathfrak{m}\right)  \geq\min\left(  \operatorname*{Supp}\mathfrak{n}\right)
\end{array}
\right.
\]
for any two monomials $\mathfrak{m}$ and $\mathfrak{n}$.
\item It should be $\kk$-bilinear.
\item It should be continuous (i.e., its $\kk$-bilinearity also
applies to infinite $\kk$-linear combinations).
\end{itemize}

\item Well-definedness is pretty clear.

\item \textbf{Example.} $\left(x_2^2 x_4\right) \left.\prec\right. \left(x_3^2 x_5\right) = x_2^2 x_3^2 x_4 x_5$, but
$\left(x_2^2 x_4\right) \left.\prec\right. \left(x_2^2 x_5\right) = 0$.
}
\only<3>{
\item We define a binary operation $\left.  \succeq\right.$ on the
$\kk$-module $\Powser$ as follows:

\begin{itemize}
\item On monomials, it should be given by
\[
\mathfrak{m}\left.  \succeq\right.  \mathfrak{n}=\left\{
\begin{array}
[c]{c}%
\mathfrak{m}\cdot\mathfrak{n},\ \ \ \ \ \ \ \ \ \ \text{if }\min\left(
\operatorname*{Supp}\mathfrak{m}\right) \geq \min\left(  \operatorname*{Supp}%
\mathfrak{n}\right)  ;\\
0,\ \ \ \ \ \ \ \ \ \ \text{if }\min\left(  \operatorname*{Supp}%
\mathfrak{m}\right) < \min\left(  \operatorname*{Supp}\mathfrak{n}\right)
\end{array}
\right.
\]
for any two monomials $\mathfrak{m}$ and $\mathfrak{n}$.
\item It should be $\kk$-bilinear.
\item It should be continuous (i.e., its $\kk$-bilinearity also
applies to infinite $\kk$-linear combinations).
\end{itemize}

\item Well-definedness is pretty clear.

\item \textbf{Example.} $\left(x_2^2 x_4\right) \left.\succeq\right. \left(x_3^2 x_5\right) = 0$, but
$\left(x_2^2 x_4\right) \left.\succeq\right. \left(x_2^2 x_5\right) = x_2^4 x_4 x_5$.
}


\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Dendriform structure on $\QSym$, part 2}

\begin{itemize}

\item We now have defined two binary operations $\left.\prec\right.$
and $\left.\succeq\right.$ on $\Powser$. They satisfy:
\begin{align*}
a\left.  \prec\right.  b+a \left.  \succeq\right.b  &  =ab;\\
\left(  a\left.  \prec\right.  b\right)  \left.  \prec\right.  c  &  =a\left.
\prec\right.  \left(  bc\right)  ;\\
\left(  a \left.  \succeq\right.  b\right)  \left.  \prec\right.  c
&  =a \left.  \succeq\right. \left(  b\left.  \prec\right.
c\right)  ;\\
a \left.  \succeq\right.  \left(  b \left.  \succeq\right.
c\right)   &  =\left(  ab\right)  \left.  \succeq\right.  c.
\end{align*}

\pause

\item This says that $\left(\Powser, \left.\prec\right., \left.\succeq\right.\right)$
is a \textit{dendriform algebra} in the sense of Loday
(see, e.g., {\red \href{http://arxiv.org/abs/1101.0267}{Zinbiel,
\textit{Encyclopedia of types of algebras 2010},
arXiv:1101.0267}}).

\pause

\item $\QSym$ becomes a dendriform subalgebra of $\Powser$. \\
(This is somewhat tangential to the actual proof.)

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Main ideas of the proof, part 1}

\begin{itemize}

\item \textbf{Crucial lemma 1.} For every positive integer $m$ and
every $f \in \QSym$, we have
\[
\mathbf{W}_m f = h_m \left.\prec\right. f ,
\]
where $h_m$ is the $m$-th complete homogeneous symmetric function
(that is, $\sum\limits_{i_1 \leq i_2 \leq \cdots \leq i_m}
x_{i_1} x_{i_2} \cdots x_{i_m}$).

\pause

\item \textbf{Crucial lemma 2.} For every composition
$\alpha=\left(
\alpha_{1},\alpha_{2},\ldots,\alpha_k\right)  $, the dual
immaculate function $\mathfrak{S}_{\alpha}^{\ast}$ is
\[
\mathfrak{S}_{\alpha}^{\ast}
= h_{\alpha_1} \left.\prec\right.
\left(h_{\alpha_2} \left.\prec\right.
\left( \cdots \left.\prec\right.
\left(h_{\alpha_k} \left.\prec\right. 1\right)
\cdots \right) \right) .
\]
(This actually follows easily from our definition of
$\mathfrak{S}^\ast_\alpha$.)

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Main ideas of the proof, part 2}

\begin{itemize}

\item In the proof of Crucial lemma 1, another binary operation on
$\Powser$ appears, which I call $\bel$.

\only<1>{
\item We define a binary operation $\bel$ on the
$\kk$-module $\Powser$ as follows:

\begin{itemize}
\item On monomials, it should be given by
\[
\mathfrak{m}\bel \mathfrak{n}=\left\{
\begin{array}
[c]{c}%
\mathfrak{m}\cdot\mathfrak{n},\ \ \ \ \ \ \ \ \ \ \text{if }\max\left(
\operatorname*{Supp}\mathfrak{m}\right)  \leq \min\left(  \operatorname*{Supp}%
\mathfrak{n}\right)  ;\\
0,\ \ \ \ \ \ \ \ \ \ \text{if }\max\left(  \operatorname*{Supp}%
\mathfrak{m}\right)  >\min\left(  \operatorname*{Supp}\mathfrak{n}\right)
\end{array}
\right.
\]
for any two monomials $\mathfrak{m}$ and $\mathfrak{n}$.
\item It should be $\kk$-bilinear.
\item It should be continuous (i.e., its $\kk$-bilinearity also
applies to infinite $\kk$-linear combinations).
\end{itemize}

\item Well-definedness is pretty clear.

\item \textbf{Example.} $\left(x_2^2 x_4\right) \bel \left(x_4^2 x_5\right) = x_2^2 x_4^3 x_5$ and
$\left(x_2^2 x_4\right) \bel \left(x_3^2 x_5\right) = 0$.
}
\only<2>{
\item We define a binary operation $\tvi$ on the
$\kk$-module $\Powser$ as follows:

\begin{itemize}
\item On monomials, it should be given by
\[
\mathfrak{m}\tvi  \mathfrak{n}=\left\{
\begin{array}
[c]{c}%
\mathfrak{m}\cdot\mathfrak{n},\ \ \ \ \ \ \ \ \ \ \text{if }\max\left(
\operatorname*{Supp}\mathfrak{m}\right) < \min\left(  \operatorname*{Supp}%
\mathfrak{n}\right)  ;\\
0,\ \ \ \ \ \ \ \ \ \ \text{if }\max\left(  \operatorname*{Supp}%
\mathfrak{m}\right) \geq \min\left(  \operatorname*{Supp}\mathfrak{n}\right)
\end{array}
\right.
\]
for any two monomials $\mathfrak{m}$ and $\mathfrak{n}$.
\item It should be $\kk$-bilinear.
\item It should be continuous (i.e., its $\kk$-bilinearity also
applies to infinite $\kk$-linear combinations).
\end{itemize}

\item Well-definedness is pretty clear.

\item \textbf{Example.} $\left(x_2^2 x_4\right) \tvi \left(x_4^2 x_5\right) = 0$, but
$\left(x_2^2 x_4\right) \tvi \left(x_5^2 x_6\right) = x_2^2 x_4 x_5^2 x_6$.
}

\only<3->{
\item Belgthor ($\bel$) and Tvimadur ($\tvi$) are two calendar runes
signifying two of the 19 years of the Metonic cycle.
I sought two (unused) symbols that (roughly) look like ``putting one
thing (monomial) atop another'', allowing overlap ($\bel$) and
disallowing overlap ($\tvi$). \\
You be the judge whether I succeeded...
}
\only<4>{
\item My apologies to the editors of the Canadian Journal of
Mathematics who'll have to put up with a LaTeX package for runes in
a mathematical document.
}

\end{itemize}

\vspace{9cm}

\end{frame}

\begin{frame}
\fti{Main ideas of the proof, part 3}

\begin{itemize}

\item A lemma (for Crucial lemma 1): For any $a \in \Powser$
and $b \in \QSym$, we have
\[
\sum_{\left(  b\right)  }\left(  S\left(  b_{\left(  1\right)  }\right)
\bel a\right)  b_{\left(  2\right)  }=a\left.  \prec\right.  b ,
\]
where we use Sweedler's notation $\sum\limits_{\left(
b\right)  }b_{\left(  1\right)  }\otimes b_{\left(  2\right)  }$ for
$\Delta\left(  b\right)  $.

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{A few more words about the runes}

\begin{itemize}

\item The operations $\bel$ and $\tvi$ restrict to $\QSym$.

\item They are associative and unital (with unity $1$).

\item They satisfy
\begin{align*}
\left(  a\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  b\right)  \left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  c-a\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  \left(  b\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  c\right)   &  =\varepsilon\left(  b\right)  \left(  a\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  c-a\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  c\right)  ;\\
\left(  a\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  b\right)  \left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  c-a\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  \left(  b\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  c\right)   &  =\varepsilon\left(  b\right)  \left(  a\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  c-a\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  c\right)  ,
\end{align*}
where $\varepsilon:\Powser\to\kk$ sends $f$ to $f\left(0,0,0,\ldots\right)$
as before.

\pause

\item As a consequence,
\[
\left(  a\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  b\right)  \left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  c+\left(  a\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  b\right)  \left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  c=a\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  \left(  b\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  c\right)  +a\left.
%TCIMACRO{\TeXButton{tvi}{\textarm{\tvimadur}}}%
%BeginExpansion
\textarm{\tvimadur}%
%EndExpansion
\right.  \left(  b\left.
%TCIMACRO{\TeXButton{bel}{\textarm{\belgthor}}}%
%BeginExpansion
\textarm{\belgthor}%
%EndExpansion
\right.  c\right)  .
\]
This says that $\left(\QSym, \bel, \tvi\right)$ is a
$As^{\left\langle 2\right\rangle }$\textit{-algebra}
(in the sense of Loday).

\pause

\item What other identities do they satisfy? What identities do
$\bel$, $\tvi$, $\prec$ and $\succeq$ satisfy together?

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{Higher combinatorial Hopf algebras}

\begin{itemize}

\item $\Lambda \subseteq \QSym$ is not the end of the road.

\item There are higher ``combinatorial Hopf algebras'' around, such
as the noncommutative algebras
$\operatorname{FQSym}$ and $\operatorname{WQSym}$.

\item All above-mentioned operations can be lifted to
$\operatorname{WQSym}$. Some also to $\operatorname{FQSym}$.
(See the preprint.)

\item Actually, dendriform structures on $\operatorname{WQSym}$
and $\operatorname{FQSym}$ are known (Foissy, Novelli, Thibon).

\end{itemize}

\vspace{9cm}

\end{frame}


\begin{frame}
\fti{References}

This chapter was about:

\begin{itemize}

\item {\red\href{http://web.mit.edu/~darij/www/algebra/dimcreation.pdf}{Darij Grinberg, \textit{Dual immaculate creation
operators and a dendriform algebra structure on the
quasisymmetric functions}}}, to appear in the Canadian Journal of
Mathematics.

\end{itemize}

Related work:

\begin{itemize}

\item {\red \href{http://arxiv.org/abs/math/0510218}{Jean-Christophe Novelli, Jean-Yves Thibon,
\textit{Construction of dendriform trialgebras}, arXiv:math/0510218}}.

\item {\red \href{http://www.sciencedirect.com/science/article/pii/0001870877900421}{Gl\^anffrwd P. Thomas,
\textit{Frames, Young tableaux, and Baxter sequences}}}.

\item {\red \href{http://arxiv.org/abs/1208.5191}{Chris Berg, Nantel Bergeron,
Franco Saliola, Luis Serrano, Mike Zabrocki,
\textit{A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions},
arXiv:1208.5191}}.

\end{itemize}

\textbf{Thanks} to Mike Zabrocki for the conjecture and to Nantel
Bergeron for an invitation to Toronto. \\
And thanks to you for surviving!

\end{frame}

\end{document}
