%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{19}
\addbibresource{19.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\usepackage{shuffle}
\usepackage{paralist}
\usepackage{xargs}
\usepackage{ulem}\normalem
\usepackage{wrapfig}
\usepackage{lipsum}

\graphicspath{{figures/}}

%%%%% AUTHOR'S COMMANDS %%%%%

% special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\bk}{\mathbf{k}} % field

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;|\; #2 \big\}} % big set notation
\newcommand{\biggset}[2]{\bigg\{ #1 \;\bigg|\; #2 \bigg\}} % bigg set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\langle \, #1 \; | \; #2 \, \rangle} % dot product
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
\newcommand{\one}{{1\!\!1}} % the all one vector
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:

% others
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % Exempli gratia
\newcommand{\viceversa}{\textit{vice versa}} % exempli gratia
\definecolor{PineGreen}{RGB}{2,120,120} % pinegreen color
\newcommand{\red}{\color{red}} % red command
\newcommand{\blue}{\color{blue}} % blue command
\newcommand{\defn}[1]{\uline{\textit{#1}}} % emphasis of a definition

% colors
\definecolor{DarkGreen}{RGB}{57,181,74} % darkgreen color
\renewcommand{\b}[1]{{\color{blue} #1}} % blue
\renewcommand{\r}[1]{{\color{red} #1}} % red
\newcommand{\g}[1]{{\color{DarkGreen} #1}} % green

% algebra
\newcommand{\product}{\cdot} % product
\newcommand{\coproduct}{\triangle} % coproduct
\newcommand{\cA}{\mathcal{A}} % algebra

% permutations
\newcommand{\fS}{\mathfrak{S}} % symmetric group
\newcommand{\gdproduct}{\bullet} % global descent product
\newcommand{\gdshuffle}{\shuffle_\gdproduct} % global descent shuffle product
\newcommand{\gddeconcat}{\coproduct_\gdproduct} % global descent deconcatenation coproduct
\newcommand{\HS}{{\bk\fS}} % Hopf Algebra of permutations
\newcommand{\shiftedShuffle}{\,\bar\shuffle\,} % shifted shuffle
\newcommand{\convolution}{\star} % convolution

% pipe dreams
\newcommand{\cross}{\raisebox{-.1cm}{\includegraphics[scale=.8]{cross}}\,}
\newcommand{\elbow}{\raisebox{-.1cm}{\includegraphics[scale=.8]{elbow}}\,}
\newcommand{\pipeDreams}{\Pi} % set of pipe dreams
\newcommand{\indecomposablePipeDreams}{\Lambda} % reversing pipe dreams
\usepackage{tikz}\usetikzlibrary{trees,snakes,shapes,arrows,matrix,calc}
\input{figures/pipeDreamsTikz}
\newcommand{\crossBiColor}[2]{\raisebox{.1cm}{\pipeDreamBiColor{#1}{#2}{black}{c/l/r}}}
\newcommand{\elbowBiColor}[2]{\raisebox{.1cm}{\pipeDreamBiColor{#1}{#2}{black}{e/l/r}}}
\newcommand{\lrot}{\rotatebox{90}{$\mathsf{L}$}}
\newcommand{\lmir}{\reflectbox{$\mathsf{L}$}}
\newcommand{\HP}{{\bk\pipeDreams}} % Hopf algebra of pipe dreams
\newcommand{\gammainsertion}{\ll}  % Q insertion in P
\newcommand{\Sdom}{\fS^{\operatorname{dom}}} % dominant permutations
\newcommand{\pipeDreamsDom}{\pipeDreams^{\operatorname{dom}}} % dominant pipe dreams
\newcommand{\HSdom}{{\bk\fS}^{\operatorname{dom}}} % Hopf Algebra of permutations
\newcommand{\HPdom}{\bk\pipeDreamsDom} % Hopf Algebra of pipe dreams
\newcommand{\HT}{{\bk\nuTrees}} % Hopf algebra of nu-trees
\newcommand{\nuTrees}{\Theta} % all nu-Trees

% diagonal harmonics
\newcommand{\DiagHarm}[2]{\mathrm{DH}_{#1,#2}} % diagonal harmonics space
\newcommand{\area}{\operatorname{area}} % area statistic
\newcommand{\dinv}{\operatorname{dinv}} % dinv statistic
\newcommand{\bounce}{\operatorname{bounce}} % bounce statistic
\newcommand{\steep}{\operatorname{steep}} % steep statistic
\newcommand{\col}{\operatorname{col}} % collar statistic
\newcommand{\type}{\operatorname{type}} % type of a partition
\newcommand{\Sym}[2]{\mathrm{Sym}_{#1,#2}} % symmetric functions
\newcommand{\Alt}{\mathrm{Alt}} % alternating component
\newcommand{\TC}[2]{\mathrm{TC}_{#1,#2}} % Tamari chains
\newcommand{\HC}[2]{\mathrm{HC}_{#1,#2}} % Hopf chains
\newcommand{\bpi}{\boldsymbol \pi} % bold pi


%%%%% END AUTHOR'S COMMANDS %%%%%

%% define your title in the usual way
\title[Hopf dreams]{Hopf dreams}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
	Nantel Bergeron\thanks{\href{mailto:bergeron@mathstat.yorku.ca}{bergeron@mathstat.yorku.ca}. Supp. by NSERC and a York Research Chair.}\addressmark{1},
	Cesar Ceballos\thanks{\href{mailto:cesar.ceballos@univie.ac.at}{cesar.ceballos@univie.ac.at}. Supp. by the Austrian Science Foundation FWF, grant F 5008-N15, in the framework of the Special Research Program Algorithmic and Enumerative Combinatorics.}\addressmark{2},
	\and
	Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. Supp. by ANR SC3A~15\,CE40\,0004\,01 and CAPPS~17\,CE40\,0018.}\addressmark{3}
}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1}Department of Mathematics and Statistics, York University, Toronto \\
	\addressmark{2}Faculty of Mathematics, University of Vienna, Vienna, Austria \\
	\addressmark{3}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau, France
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
We introduce a Hopf algebra structure on a family of reduced pipe dreams with a natural surjection onto a commutative Hopf algebra of permutations.
We then study three Hopf subalgebras of permutations whose preimages by the surjection yield three relevant Hopf subalgebras of pipe dreams.
The first is the Loday--Ronco Hopf algebra on binary trees, the second is related to a special family of lattice walks on the quarter plane, and the third is a Hopf algebra on $\nu$-trees related to $\nu$-Tamari lattices. 
The latter motivates a new notion of Hopf chains in the Tamari lattice with applications in the theory of multivariate diagonal harmonics. 
}

%% put your French abstract here, or comment this out if you don't have one
\resumetitle{R\'esum\'e}
\resume{
Nous introduisons une structure d'alg\`ebre de Hopf sur une famille d'arran\-gements de tuyaux, avec une surjection naturelle sur une alg\`ebre de Hopf commutative de permutations.
Nous \'etudions ensuite trois sous-alg\`ebres de Hopf de permutations dont les pr\'eimages par la surjection donnent trois sous-alg\`ebres de Hopf d'arrange\-ments de tuyaux int\'eressantes.
La premi\`ere est l'alg\`ebre de Hopf de Loday--Ronco sur les arbres binaires, la seconde est reli\'ee \`a une famille sp\'eciale de chemins dans le quart de plan, et la troisi\`eme est une alg\`ebre de Hopf sur des $\nu$-arbres reli\'ee aux treillis de $\nu$-Tamari.
Cette derni\`ere motive une nouvelle notion de cha\^ines de Hopf dans le treillis de Tamari, avec des applications \`a la th\'eorie des harmoniques diagonaux multivari\'es.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Pipe dream, Hopf algebra, Tamari lattice, Multivariate diagonal harmonics}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex, firstinits=true]{biblatex}
%\DeclareFieldFormat[article,inbook,incollection,inproceedings,patent,thesis,unpublished]{title}{\textit{#1}\isdot}
%\renewbibmacro{in:}{}
%\addbibresource{pipeDreamAlgebraFPSAC.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\makeatletter
\def\blfootnote{\xdef\@thefnmark{}\@footnotetext}
\makeatother

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Pipe\blfootnote{Project partially supported by the project ``Austria/France Scientific \& Technological Cooperation'' (Austrian BMWFW Project No. FR 10/2018 and French PHC Amadeus 2018 Project No. 39444WJ).} dreams are combinatorial objects related to reduced expressions of permutations in terms of simple transpositions.
They were introduced by N.~Bergeron and S.~Billey in~\cite{BergeronBilley} to compute Schubert polynomials and later revisited in the context of Gr\"obner geometry by A.~Knutson and E.~Miller~\cite{KnutsonMiller-GroebnerGeometry}, who coined the name \emph{pipe dreams} in reference to a game involving pipe connections. In brief, a pipe dream is an arrangement of pipes, each connecting an entry on the vertical axis to an exit on the horizontal axis, and remaining in a triangular shape of the grid.
Pipe dreams are grouped according to their exiting permutation, given by the order in which the pipes appear along the horizontal axis.
%Pipe dreams have important connections and applications to various areas related to Schubert calculus and Schubert varieties~\cite{LascouxSchutzenberger-PolynomesSchubert, LascouxSchutzenberger-SchubertLittlewoudRichardson}. 
%They have a rich combinatorial and geometric structure but their algebraic structure was less considered.

This paper introduces a Hopf algebra structure on pipe dreams.
Hopf algebras are rather rigid structures which often reveal deep combinatorial properties and connections.
This paper contributes to this general philosophy: the Hopf algebra of pipe dreams will give us insight  on a special family of lattice walks on the quarter plane studied in~\cite{BousquetMelouMishna}, as well as applications to the still emerging theory of multivariate diagonal harmonics~\cite{Bergeron-multivariateDiagonalCoinvariantSpaces}.

Our compass for this construction is the Hopf algebra of J.-L.~Loday and M.~Ronco on complete binary trees~\cite{LodayRonco}.
There is a strong correspondence~\cite{Woo, PilaudPocchiola, SerranoStump} between the complete binary trees with $n$ internal nodes and the reduced pipe dreams with exiting permutation~$0 n \dots 1$.
This correspondence allows to interpret the product and the coproduct of the Loday--Ronco Hopf algebra in terms of pipe dreams.
This interpretation yields to an extension of the Loday--Ronco Hopf algebra on a bigger family~$\pipeDreams$ consisting of reduced pipe dreams with an elbow in the top left corner.
We show that it results in a free and cofree Hopf algebra structure~$(\HP, \product, \coproduct)$, and that mapping a pipe dream to its exiting permutation defines a surjective morphism from the Hopf algebra~$(\HP, \product, \coproduct)$ of pipe dreams to a commutative Hopf algebra~$(\HS, \gdshuffle, \gddeconcat)$ of permutations.

We then study relevant Hopf subalgebras of~$\HP$ obtained from pipe dreams whose exiting permutations belong to a given Hopf subalgebra of~$\HS$.
We obtain this way:
\begin{compactenum}
\item the Loday--Ronco Hopf algebra on complete binary trees~\cite{LodayRonco},
\item a Hopf algebra related to a special family of lattice walks on the quarter plane~\cite{BousquetMelouMishna},
\item a Hopf algebra on $\nu$-trees connected to the $\nu$-Tamari lattices~\cite{PrevilleRatelleViennot}.
\end{compactenum}

\medskip
Finally, one of our most important contributions is the application of the Hopf algebra of dominant pipe dreams to the theory of multivariate diagonal harmonics.
The space of diagonal harmonics is an $\mathfrak{S}_n$-module of polynomials in two sets of variables that satisfy some harmonic properties.
The dimensions of these spaces led to numerous important conjectures, including the $(n+1)^{n-1}$-conjecture by A.~Garsia and M.~Haiman proved by M.~Haiman using properties of the Hilbert scheme in algebraic geometry~\cite{Haiman-vanishingTheorems}, and the shuffle conjecture by J.~Haglund et al.~\cite{HaglundHaimanLoehrRemmelUlyanov}, recently proved by E.~Carlsson and A.~Mellit in~\cite{CarlssonMellit}.
%The bigraded Hilbert series of the alternating component of the space of diagonal harmonics also gave rise to the now famous \mbox{$q,t$-Catalan} polynomials.
The module of diagonal harmonics has natural generalizations in three or more sets of variables.
Computational experiments by M.~Haiman from the early 1990's suggest explicit simple dimension formulas for the space of diagonal harmonics and its alternating component in the trivariate case.
F.~Bergeron noticed that these formulas coincide with formulas counting labeled and unlabeled intervals in the classical Tamari lattice, and opened the door to a more systematic study of the $r$-variate case in terms of certain suitable $(r-1)$-chains in the Tamari lattice~\cite{BergeronPrevilleRatelle,Bergeron-multivariateDiagonalCoinvariantSpaces}.
In this paper we present a milestone towards this understanding by introducing a new class of chains in the Tamari lattice that was motivated by our Hopf algebra construction, see \cref{thm:eExpansion}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The pipe dream Hopf algebra}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{A Hopf algebra on permutations}
\label{subsec:HopfAlgebraPermutations}

Let~$\fS_n$ be the set of permutations of~$[n] \eqdef \{1,2,\ldots,n\}$, and~$\fS \eqdef \bigsqcup_{n \ge 0} \fS_n$. We consider the graded vector space~$\HS \eqdef \bigoplus_{n\ge 0} \HS_n$, where~$\HS_n$ is the~$\bk$-span of~$\fS_n$.

%%%%%%%

\paragraph{Global descents and atomic permutations.}

Consider~$\omega \in \fS_n$. Index by~$\{0, \dots, n\}$ from left to right the \defn{gaps} before the first position, between two consecutive positions, or after the last position of~$\omega$. A gap~$\gamma$ is a \defn{global descent} if~${\omega([\gamma]) = [n] \ssm [n-\gamma]}$. In other words, the first~$\gamma$ positions are sent to the last~$\gamma$ values. For example, the global descents in the permutation~$\omega = 635421$ are~$0, 1, 4, 5, 6$. Note that the gaps~$0$ and~$n$ are always global descents. A permutation with no other global descent is called \defn{atomic}.

For two permutations~$\mu \in \fS_m$ and~$\nu \in \fS_n$ we define the permutation~$\mu \gdproduct \nu \in \fS_{m+n}$ by~$\mu \gdproduct \nu(i) \eqdef \mu(i)+n$ if~$1   \le i \le m$, and~$\mu \gdproduct \nu(i) \eqdef \nu(i-m)$ if~$m+1 \le i \le m+n$.
Observe that~$\mu \gdproduct \nu$ has a global descent in position~$m$. Conversely, given a permutation~$\omega \in \fS_{m+n}$ with a global descent in position~$m$, there exist a unique pair of permutations~${\mu \in \fS_m}$ and~${\nu \in \fS_{n}}$ such that~${\omega = \mu \gdproduct \nu}$. Therefore any permutation~$\omega \in \fS$ factorizes in a unique way as a product~${\omega = \omega_1 \gdproduct \omega_2 \gdproduct \cdots \gdproduct \omega_\ell}$ of atomic permutations~$\omega_i$. For example, we have~$\b{6}\r{354}\g{2}\o{1} = \b{1} \gdproduct \r{132} \gdproduct \g{1} \gdproduct \o{1}$. For such a factorization, we denote by~$\omega^{\gdproduct} \eqdef \{\omega_1, \omega_2, \dots, \omega_\ell\}$ the set of its atomic factors.

%%%%%%%

\paragraph{Coproduct on permutations.}

Consider a permutation~$\omega \in \fS$, and let~${\omega = \omega_1 \gdproduct \cdots \gdproduct \omega_\ell}$ be its unique factorization into atomic permutations. We define the coproduct~$\gddeconcat(\omega)$ by
\(
\gddeconcat(\omega) \eqdef \sum_{i=0}^\ell (\omega_1 \gdproduct \cdots \gdproduct \omega_i) \otimes (\omega_{i+1} \gdproduct \cdots \gdproduct \omega_\ell),
\)
where an empty $\gdproduct\,$-product is the neutral element~$\epsilon$ for~$\gdproduct$. This coproduct extends to~$\HS$ by linearity and is clearly coassociative.

\begin{example} 
For the permutation~$635421 \in \fS_6$, we have~$\b{6}\r{354}\g{2}\o{1} = \b{1} \gdproduct \r{132} \gdproduct \g{1} \gdproduct \o{1}$. Therefore,
\(
\gddeconcat(\b{6}\r{354}\g{2}\o{1}) = \epsilon \otimes \b{6}\r{354}\g{2}\o{1} + \b{1} \otimes \r{354}\g{2}\o{1} + \b{4}\r{132} \otimes \g{2}\o{1} + \b{5}\r{243}\g{1} \otimes \o{1} + \b{6}\r{354}\g{2}\o{1} \otimes \epsilon.
\)
\end{example}

%%%%%%%

\paragraph{Product on permutations.}

Consider two permutations~$\b{\pi}, \r{\omega} \in \fS$. Define~$\b{\pi} \gdshuffle \r{\epsilon} \eqdef \b{\pi}$ and~$\b{\epsilon} \gdshuffle \r{\omega} \eqdef \r{\omega}$. Assume now that~$\b{\pi} = \b{\mu} \gdproduct \b{\nu}$ and~$\r{\omega} = \r{\sigma} \gdproduct \r{\tau}$ where~$\b{\mu}$ and~$\r{\sigma}$ are non-trivial atomic permutations, and define
\(
\b{\pi} \gdshuffle \r{\omega} \eqdef \b{\mu} \gdproduct (\b{\nu} \gdshuffle \r{\omega}) + \r{\sigma} \gdproduct (\b{\pi} \gdshuffle \r{\tau}).
\)
This product extends to~$\HS$ by linearity and is clearly associative.
This is the standard shuffle product, but performed on the atomic factorizations of the factors.

\begin{example} 
 For the permutations~$\b{2431} = \b{132} \gdproduct \b{1} \in \fS_4$ and~$\r{312} = \r{1} \gdproduct \r{12} \in \fS_3$, we have 
\(
\b{2431} \gdshuffle \r{312} = \b{576}\b{4}\r{3}\r{12} + \b{576}\r{4}\b{3}\r{12} + \b{576}\r{4}\r{23}\b{1} + \r{7}\b{465}\b{3}\r{12} + \r{7}\b{465}\r{23}\b{1} + \r{7}\r{56}\b{243}\b{1}
\)
\end{example}

The product~$\gdproduct$ and the coproduct~$\gddeconcat$ are compatible:~${\gddeconcat(\b{\pi} \gdshuffle \r{\omega}) = \gddeconcat(\b{\pi}) \gdshuffle \gddeconcat(\r{\omega})}$, where the right hand side product has to be understood componentwise. This structure is thus a graded and connected commutative Hopf algebra~$(\HS, \gdshuffle, \gddeconcat)$. See~\cite{Vargas}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{A Hopf algebra on pipe dreams}
\label{subsec:HopfAlgebraPipeDreams}

A \defn{pipe dream}~$P$ is a filling of a triangular shape with crosses~\cross{} and elbows~\elbow{} so that all pipes entering on the left side exit on the top side~\cite{BergeronBilley, KnutsonMiller-GroebnerGeometry}.
%See \fref{fig:pipeDreams}.
We only consider \defn{reduced} pipe dreams, where two pipes have at most one intersection. We also restrict to pipe dreams with an elbow~\elbow{} in the top left corner. In particular the pipe entering in the topmost row always exits in the leftmost column. We label this pipe with~$0$ and the other pipes with~$1, 2, \dots, n$ in the order of their entry points from top to bottom. We also label accordingly the rows and the columns of the pipe dream~$P$ from~$0$ to~$n$. We denote by~$\omega_P \in \fS_n$ the order of the exit points of the non-zero pipes of~$P$ from left to right. In other words, the pipe entering at row~$i > 0$ exits at column~$\omega^{-1}_P(i) > 0$. See \cref{fig:packingsPipeDream}. For a permutation~$\omega \in \fS_n$, we denote by~$\pipeDreams(\omega)$ the set of reduced pipe dreams~$P$ with an elbow~\elbow{} in the top left corner and such that~$\omega_P = \omega$. We let~$\pipeDreams_n \eqdef \bigsqcup_{\omega \in \fS_n} \pipeDreams(\omega)$~and~$\pipeDreams \eqdef \bigsqcup_{n \in \N} \pipeDreams_n$. 
We consider the graded vector space~$\HP = \bigoplus_{n\ge 0} \HP_n$, where~$\HP_n$ is the~$\bk$-span of~$\pipeDreams_n$. 

%%%%%%%

\paragraph{Horizontal and vertical packing.}

Let~$P \in \pipeDreams_n$ and~$k \in \{0,\dots, n\}$.
We color plain \r{red} the pipes entering in the rows $1, 2, \dots, k$ and dashed \b{blue} the pipes entering in the rows $k+1, k+2, \dots, n$.
The \defn{horizontal packing}~$\r{\lrot_k(P)}$ is obtained by removing all blue pipes and contracting the horizontal parts of the red pipes that were contained in a cell~\crossBiColor{red}{blue,dashed} (\ie red horizontal steps that are crossed vertically by a blue pipe).
%
The \defn{vertical packing}~$\b{\lmir_k(P)}$ is defined symmetrically: it keeps the pipes exiting through the columns~$1, 2, \dots, k$ and contracts the vertical steps that are crossed horizontally by the pipes exiting through the columns~$k+1, k+2, \dots, n$. The remaining pipes need to be relabeled from~$1$~to~$k$.

\begin{figure}[ht]
\centering
\resizebox{0.9\textwidth}{!}{
	\centerline{
%		\input{figures/horizontalPackingPipeDream}
%		\qquad\quad
%		\input{figures/verticalPackingPipeDream}
		\includegraphics[scale=.7]{horizontalPackingPipeDream}
		\qquad\quad
		\includegraphics[scale=.7]{verticalPackingPipeDream}
	}
	}
	\caption{Horizontal packing at~$k=3$ (left) and vertical packing at~$k = 4$ (right).}
	\label{fig:packingsPipeDream}
\end{figure}

%%%%%%%

\vspace{-4ex}
\paragraph{Coproduct on pipe dreams.}

Consider a reduced pipe dream~$P \in \pipeDreams_n$, and a global descent~$\gamma$ of the permutation~$\omega_P$.
Since~$\gamma$ is a global descent of~$\omega_P$, the relevant pipes of~$P$ are split into two disjoint tangled sets of pipes: those entering in the first~$n-\gamma$ rows (plain \r{red}) and those exiting in the first~$\gamma$ columns (dashed \b{blue}).
The horizontal and vertical packings~$\r{\lrot_{n-\gamma}(P)}$ and~$\b{\lmir_\gamma(P)}$ should thus be regarded as a way to untangle these two disjoint sets of pipes.
We denote by~$\coproduct_{\gamma,n-\gamma}(P)$ the tensor product~$\b{\lmir_\gamma(P)} \otimes \r{\lrot_{n-\gamma}(P)}$ and we say that~$\coproduct_{\gamma,n-\gamma}$ \defn{untangles}~$P$.
This operation is illustrated on \cref{fig:operationsPipeDreams}\,(left).
%
\begin{figure}[t]
\centering
	\resizebox{0.95\textwidth}{!}{
	\centerline{
		\includegraphics[scale=.7]{untanglePipeDream}
		\qquad\quad
		\includegraphics[scale=.7]{insertionPipeDreams}
	}}
	\caption{Untangling a pipe dream (left). Inserting a pipe dream~(right).}
	\label{fig:operationsPipeDreams}
\end{figure}
%
If $\gamma$ is not a global descent of~$\omega_P$, then the pipes of~$P$ are not split by~$\gamma$, and we therefore define $\coproduct_{\gamma,n-\gamma}(P) = 0$.
Finally, we define the coproduct on~$\pipeDreams$ as
\(
\coproduct \eqdef \sum_{m,n \in \N} \coproduct_{m,n}.
\)
See \cref{fig:coproductPipeDreams}.
Extended by linearity, the map~$\coproduct : \HP \to \HP \otimes \HP$ defines a comultiplication~on~$\HP$.

\begin{proposition}[{\cite[Props.\,1.2.2 \& 1.2.3]{BergeronCeballosPilaud}}]
The coproduct~$\coproduct$ defines a coassociative graded coalgebra structure on $\HP$.
The map $\omega \colon (\HP, \coproduct) \to (\HS, \gddeconcat)$ is a graded morphism of coalgebras.
\end{proposition}

\begin{figure}[h]
	\centerline{
		%\input{figures/coproductPipeDreams}
		\includegraphics[scale=.75]{coproductPipeDreams}		
	}
	\caption{Coproduct of a pipe dream.}
	\label{fig:coproductPipeDreams}
\end{figure}

%%%%%%%
\vspace{-2ex}
\paragraph{Product on pipe dreams.}

Let~$\b{P} \in \pipeDreams_\b{m}$ and~$\r{Q} \in \pipeDreams_\r{n}$ be two pipe dreams, and let~$\b{\gamma}$ be a global descent of~$\omega_\b{P}$. We denote by~$\b{P} \gammainsertion_\b{\gamma} \r{Q}$ the pipe dream of~$\pipeDreams_{\b{m}+\r{n}}$ obtained from~$\b{P}$~by
\begin{compactitem}
\item inserting~$\r{n}$ columns after column~$\b{\gamma}$ and~$\r{n}$ rows after row~$\b{m}-\b{\gamma}$,
\item filling with~$\r{Q}$ the triangle of boxes located both in one of the rows~$\gamma, \dots, n+\gamma$ and in one of the columns~$m-\gamma, \dots, m+n-\gamma$,
\item filling with crosses~\crossBiColor{blue,dashed}{red} the remaining boxes located in a new column, 
\item filling with crosses~\crossBiColor{red}{blue,dashed} the remaining boxes located in a new row. 
\end{compactitem}
We say that~$\gammainsertion_\b{\gamma}$ \defn{inserts}~$\r{Q}$ at gap~$\b{\gamma}$ in~$\b{P}$. 
This operation is illustrated in \cref{fig:operationsPipeDreams}\,(right).

Consider now a word~$s$ on the alphabet~$\{\b{p}, \r{q}\}$ with~$\b{m}$ letters~$\b{p}$ and~$\r{n}$ letters~$\r{q}$. We call \defn{$\b{p}$-blocks} (resp.~\defn{$\r{q}$-blocks}) the blocks of consecutive letters~$\b{p}$ (resp.~$\r{q}$).
%We consider that the $\b{p}$-blocks in~$s$ mark gaps of the permutation~$\omega_{\r{Q}}$ while the $\r{q}$-blocks in~$s$ mark gaps of the permutation~$\omega_{\b{P}}$. 
We say that~$s$ is a $\b{P}/\r{Q}$-\defn{shuffle} if all $\b{p}$-blocks appear at global descents of~$\omega_\r{Q}$ while all $\r{q}$-blocks appear at global descents of~$\omega_\b{P}$. \Eg, for~$\omega_\b{P} = 53412= 1 \gdproduct 12 \gdproduct 12$ and~$\omega_\r{Q} = 635421 = 1 \gdproduct 132 \gdproduct 1 \gdproduct 1$, then~$\r{q}\b{p}\r{qqq}\b{pp}\r{q}\b{pp}\r{q}$ and~$\r{q}\b{ppp}\r{qqqqq}\b{pp}$ are~$\b{P}/\r{Q}$-shuffles, while $\r{qqq}\b{pp}\r{qqq}\b{ppp}$ is not.

For a $\b{P}/\r{Q}$-shuffle~$s$ with~$\ell$ $\r{q}$-blocks, we denote by~$\b{P} \star_{s} \r{Q}$ the pipe dream obtained by
\begin{compactitem}
\item untangling~$\r{Q}$ at all gaps of~$\omega_\r{Q}$ marked by $\b{p}$-blocks in~$s$, resulting to~$\r{Q_1}, \dots, \r{Q_\ell}$,
\item inserting successively the pipe dreams~$\r{Q_1}, \dots, \r{Q_\ell}$ in~$\b{P}$ at the positions of the $\r{q}$-blocks in~$s$ (it does not matter in which order we insert the pipe dreams~$\r{Q_1}, \dots, \r{Q_\ell}$).
\end{compactitem}
We say that~$\star_{s}$ \defn{tangles} the pipe dreams~$\b{P}$ and~$\r{Q}$ according to the $\b{P}/\r{Q}$-shuffle~$s$.
%This operation is illustrated in \fref{fig:pipeDreamsTangle}. 
%
We define the product of~$\b{P} \in \pipeDreams_\b{m}$ and~$\r{Q} \in \pipeDreams_\r{n}$ by
\(
\b{P} \product \r{Q} = \sum_{s}  \b{P} \star_{s} \r{Q},
\)
where~$s$ ranges over all possible $\b{P}/\r{Q}$-shuffles. 
See \cref{fig:productPipeDreams}. 
Note that it always contains~${\b{P} \gammainsertion_0 \r{Q}}$ and~${\b{P} \gammainsertion_\b{m} \r{Q}}$ corresponding to the $\b{P}/\r{Q}$-shuffles~$\r{q^n}\b{p^m}$ and~$\b{p^m}\r{q^n}$.

\begin{proposition}[{\cite[Props.\,1.2.6 \& 1.2.7]{BergeronCeballosPilaud}}]
The product~$\product$ defines an associative graded algebra structure on~$\HP$.
The map $\omega\colon (\HP, \product) \to (\HS, \gdshuffle)$ is a graded morphism of algebras.
\end{proposition}

\begin{figure}[ht]
	\centerline{
		%\input{figures/productPipeDreams}
		\includegraphics[width=0.9\textwidth]{productPipeDreams}
	}
	\caption{Product of two pipe dreams.}
	\label{fig:productPipeDreams}
\end{figure}

%%%%%%%

\paragraph{Hopf structure.}

We now describe the properties of the product~$\product$ and coproduct~$\coproduct$.

\begin{proposition}[{\cite[Props.\,1.2.8 \& 1.2.9]{BergeronCeballosPilaud}}]
The product~$\product$ and coproduct~$\coproduct$ endow the family~$\pipeDreams$ of all pipe dreams with a graded Hopf algebra structure.
The map~${\omega \colon (\HP, \product, \coproduct) \to (\HS, \gdshuffle, \gddeconcat)}$ is a morphism of graded Hopf algebras.
\end{proposition}

A pipe dream~$P \in \pipeDreams_n$ is \defn{$\gammainsertion_0$-decomposable} if it can be written as~$P = Q \gammainsertion_0 R$ for some~${Q \in \pipeDreams_r}$ and~$R \in \pipeDreams_{n-r}$ where~${0 < r < n}$. Otherwise, we say~$P$ is \defn{$\gammainsertion_0$-indecomposable}. Define~$\indecomposablePipeDreams_n \eqdef \set{P \in \pipeDreams_n}{\text{$P$ is $\gammainsertion_0$-indecomposable}}$ and~$\indecomposablePipeDreams \eqdef \bigcup_{n \in \N} \indecomposablePipeDreams_n$.

\begin{theorem}[{\cite[Thms.\,1.2.11 \& 1.3.15]{BergeronCeballosPilaud}}]
The algebra~$\HP$ is free with generators~$\indecomposablePipeDreams$.
The dual Hopf algebra~$\HP^*$ is free with generators~$\indecomposablePipeDreams^* \eqdef \set{P^*}{P \in \indecomposablePipeDreams}$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Some relevant subalgebras}
\label{subsec:relevantSubalgebras}

Recall from \cref{subsec:HopfAlgebraPermutations} that a permutation~$\omega \in \fS$ has a unique factorization into atomic permutations~${\omega = \nu_1 \gdproduct \nu_2 \gdproduct \cdots \gdproduct \nu_\ell}$ and that we denote by~$\omega^\gdproduct \eqdef \{\nu_1, \nu_2, \dots, \nu_\ell\}$ the set of atomic permutations that appear in its factorization.
Given a subset~$S$ of atomic permutations, we define~$\fS_n \langle S \rangle \eqdef \set{\omega \in \fS_n}{\omega^{\gdproduct} \subseteq S}$ and~$\fS \langle S \rangle \eqdef \bigsqcup_{n \in \N} \fS_n \langle S \rangle$, from which we derive~$\pipeDreams_n \langle S \rangle \eqdef \set{P \in \pipeDreams_n}{\omega_P \in \fS_n \langle S \rangle}$ and~$\pipeDreams \langle S \rangle \eqdef \bigsqcup_{n \in \N} \pipeDreams_n \langle S \rangle$.
%The following statement is immediate from Proposition~\ref{prop:descentproduct}.

\begin{theorem}[{\cite[Thm.\,2.1.1]{BergeronCeballosPilaud}}]
\label{thm:subalgebraFixedAtoms}
For any set~$S$ of atomic permutations,
\begin{compactitem}
\item the subspace~$\HS \langle S \rangle$ defines a Hopf subalgebra of~$(\HS, \gdshuffle, \gddeconcat)$,
\item the subspace~$\HP \langle S \rangle$ defines a Hopf subalgebra of~$(\HP, \product, \coproduct)$.
\end{compactitem}
\end{theorem}

\begin{theorem}[{\cite[Thm.\,2.1.2]{BergeronCeballosPilaud}}]
The Hopf subalgebra~$\HP \langle S \rangle$ is free and cofree. The generators and cogenerators of~$\HP \langle S \rangle$ are exactly the $\gammainsertion_0$-indecomposable pipe dreams in~$\pipeDreams \langle S \rangle$.
\end{theorem}

In the following, we exploit \cref{thm:subalgebraFixedAtoms} to construct relevant subalgebras of~$(\HP, \product, \coproduct)$.

%%%%%%%

\paragraph{Hopf subalgebra~$\HP \langle 1 \rangle$ and Loday--Ronco algebra.}

A pipe dream~$P \in \pipeDreams_n$ is \defn{reversing} if it reverses the order of its relevant pipes. That is, ${\omega_P = [n, n-1, \dots, 1]= 1 \gdproduct 1 \gdproduct \cdots \gdproduct 1}$, or equivalently~$P \in \HP \langle 1 \rangle$.
As observed in~\cite{Woo, PilaudPocchiola, SerranoStump} reversing pipe dreams belong to the Catalan family.
In particular, there is a bijection~$\Psi$ from pipe dreams in~$\HP_n \langle 1 \rangle$ to complete binary trees with $n$ internal nodes.
Namely, given a reversing pipe dream~$P$, replace each elbow of~$P$ by a node in the tree, and connect each node with the next node below it (if any) and with the next node to its right (if any). 
See \cref{subsec:dominantVSnuTrees} for illustrations.

\begin{proposition}[{\cite[Prop.\,2.1.3]{BergeronCeballosPilaud}}]
\label{prop:reversingLodayRonco}
The map $\Psi$ is a Hopf algebra isomorphism between the Hopf subalgebra~$\HP \langle 1 \rangle$ of reversing pipe dreams and the Loday--Ronco Hopf algebra on  binary trees~\cite{LodayRonco}.
\end{proposition}

%%%%%%%

\paragraph{Hopf subalgebra~$\HP \langle 1, 12, 123, \dots \rangle$ and lattice walks on the quarter plane.}

We now consider the subalgebra~$\HP \langle 1, 12, 123, \dots \rangle$ corresponding to permutations whose atoms are identity permutations of arbitrary size.
Experimental computations show that the dimensions of the graded components of this Hopf subalgebra are given by the sequence 
\(1, 1, 3, 12, 57, 301, 1707, 10191, 63244, 404503, 2650293, \dots\)
which coincides with the sequence determined by the number of walks in a special family of walks in the quarter plane considered by M.~Bousquet-M\'elou and M.~Mishna in~\cite{BousquetMelouMishna}.

\begin{conjecture}[{\cite[Conj.\,2.2.1]{BergeronCeballosPilaud}}]
\label{conj:walks1}
The dimension of $\HP_n \langle 1, 12, 123, \dots \rangle$ is equal the number of walks in the quarter plane (within~$\mathbb{N}^2\subset \mathbb{Z}^2$) starting at $(0,0)$, ending on the horizontal axis, and consisting of $2n$ steps taken from $\{(-1, 1), (1, -1), (0, 1)\}$.
\end{conjecture}

Refining by the number of atomics gives the following stronger conjecture.

\begin{conjecture}[{\cite[Conj.\,2.2.3]{BergeronCeballosPilaud}}]
\label{conj:walks2}
The following two families have the same cardinality:
\begin{compactenum}
\item Pipe dreams $P$ such that $\omega_P\in \fS_n$ is a permutation whose factorization into atomics consists of $k$ identity permutations.
\item Walks in the quarter plane starting at $(0,0)$ and ending on the horizontal axis, consisting of $2n$ steps taken from $\{(-1, 1), (1, -1), (0, 1)\}$ from which $k$ of them are $(0,1)$. 
\end{compactenum}
\end{conjecture}

Finally, this conjecture has a natural translation in the world of Dyck paths (see~\cite[Sects.\,2.2.2 \& 2.2.3]{BergeronCeballosPilaud} for details on this translation).
A pair of Dyck paths $(\pi_1,\pi_2)$ is said to be \defn{nested} if $\pi_1$ is weakly below $\pi_2$.
We say that a Dyck path $\pi$ is 
\begin{compactitem}
\item \defn{bounce} if it is of the form~$N^{i_1}E^{i_1} N^{i_2}E^{i_2} \dots N^{i_k}E^{i_k}$ for some positive integers $i_1, \dots, i_k$,
\item \defn{steep} if it contains no consecutive east steps $EE$, except at the end on top of the grid. 
\end{compactitem}


\begin{conjecture}[{\cite[Conj.\,2.2.8]{BergeronCeballosPilaud}}]
\label{conj:SteepBounce}
For any $k\le n$, there is a bijection between:
\begin{compactenum}
\item Nested pairs of Dyck paths $(\pi_1,\pi_2)$ of size $n$ such that $\pi_1$ is a bounce path with $k$ parts.
\item Nested pairs of Dyck paths $(\pi'_1,\pi'_2)$ of size $n$ such that $\pi'_2$ is a steep path ending with $k$ east steps on top of the grid.
\end{compactenum}
\end{conjecture}

Evidences for this conjecture, and a discussion on its connection to the zeta map can be found in~\cite[Sect.\,2.2.4]{BergeronCeballosPilaud}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Dominant pipe dreams, $\nu$-Tamari lattices, and multivariate diagonal harmonics}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Dominant permutations and dominant pipe dreams}
\label{subsec:dominantPipeDreams}

\begingroup
\setlength\intextsep{0pt}

\begin{wrapfigure}[6]{r}{3cm}
	\includegraphics[scale=.75]{dominantPermutation}
\end{wrapfigure}

Recall that the \defn{Rothe diagram} of a permutation~$\omega \in \fS_n$ is the set
\(
R_\omega \eqdef \set{\big( \omega(i), j \big)}{i > j \text{ and } \omega(i) < \omega(j)}.
\)
If we represent this diagram in matrix notation (\ie the box~$(i,j)$ appears in row~$i$ and column~$j$), then the Rothe diagram of~$\omega$ is 
the set of boxes which are not weakly below or weakly to the right of a box~$\big( \omega(i), i \big)$ for all~$i \in [n]$.
A permutation~$\omega \in \fS_n$ is \defn{dominant} if its Rothe diagram~$R_\omega$ is a partition containing the top-left corner. Such a permutation is uniquely determined by its Rothe diagram~$R_\omega$, or equivalently by the Dyck path~$\pi_\omega$ delimiting the boundary of its Rothe diagram. 
Define~$\Sdom_n \eqdef \set{\omega \in \fS_n}{\omega \text{ is dominant}}$ and~$\Sdom \eqdef \bigsqcup_{n \in \N} \Sdom_n$.

\endgroup

\begin{proposition}[{\cite[Coro.\,3.1.2]{BergeronCeballosPilaud}}]
The subspace~$\HSdom$ is a Hopf subalgebra of~$(\HS, \gdshuffle, \gddeconcat)$. The dimension of the homogeneous component~$\HSdom_n$ is the Catalan number~$C_n \eqdef \frac{1}{n+1} \binom{2n}{n}$.
\end{proposition}

Finally, we pull back this Hopf subalgebra of dominant permutations of~$\HS$ to a Hopf subalgebra of~$\HP$ via the Hopf morphism $\omega \colon \HP \to \HS$. 
A \defn{dominant pipe dream} is a pipe dream~$P$ whose permutation~$\omega_P$ is dominant. We denote the set of dominant pipe dreams by~$\pipeDreamsDom_n  \eqdef \set{P \in \pipeDreams_n}{\omega_P \in \Sdom_n}$ and~$\pipeDreamsDom \eqdef \bigsqcup_{n \in \N} \pipeDreamsDom_n$.

\begin{corollary}[{\cite[Coro.\,3.1.4]{BergeronCeballosPilaud}}]
The subspace~$\HPdom$ defines a Hopf subalgebra of~$(\HP, \product, \coproduct)$.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$\nu$-trees}
\label{subsec:nuTrees}

We now consider the following family of combinatorial objects defined by C.~Ceballos, A.~Padrol and C.~Sarmiento in~\cite{CeballosPadrolSarmiento-nuTamariSubwordComplexes}.
In the following, we consider a Dyck path drawn on the semi-integer lattice~$(1/2, 1/2) + \Z^2$ and points on the lattice~$\Z^2$.

\begin{definition}[\cite{CeballosPadrolSarmiento-nuTamariSubwordComplexes}]
\label{def:nuTrees}
Let~$\nu$ be a Dyck path of size~$n$ drawn on the semi-integer lattice.
\begin{compactenum}
\item Two lattice points~$p,q$ inside the $n \times n$ grid and weakly above $\nu$ are said \defn{$\nu$-incompatible} if~$p$ is located strictly southwest or northeast to~$q$, and the smallest rectangle containing~$p$ and~$q$ lies above~$\nu$. Otherwise, $p$ and $q$ are called \defn{$\nu$-compatible}.
\item A \defn{$\nu$-tree} is a maximal collection of pairwise $\nu$-compatible lattice points, called \defn{nodes}.
\item Two $\nu$-trees are related by a \defn{rotation} if they differ by only two nodes.
\end{compactenum}
We let~$\nuTrees(\nu)$ the set of $\nu$-trees and we let~$\nuTrees_n \eqdef \bigsqcup_{\nu} \nuTrees(\nu)$ and~$\nuTrees \eqdef \bigsqcup_{n \in \N} \nuTrees_n$.
\end{definition}

A $\nu$-tree $T$ can be viewed as a tree in the graph-theoretical sense by connecting each node~$p$ of~$T$ with the next node of~$T$ below it (if any), and with the next node of~$T$ to its right (if any).
For example, we obtain classical binary trees when~$\nu = (NE)^n$ is the staircase Dyck path. See \cref{subsec:relevantSubalgebras}.
We consider the graded space~$\HT = \bigoplus_{n\ge 0} \HT_n$, where~$\HT_n$ is the~$\bk$-span of~$\nuTrees_n$ and define a product and coproduct similar to \cref{subsec:HopfAlgebraPipeDreams}.

%%%%%%%

\paragraph{Horizontal and vertical packing.}

A leaf of a $\nu$-tree~$T$ is called a \defn{diagonal leaf} if it belongs to the main diagonal of the $n\times n$ grid. A diagonal leaf~$b$ in~$T$ divides the path~$\nu$ into two paths~$\b{\nu_\ell}$ (on the left) and~$\r{\nu_r}$ (on the right). Cutting the tree~$T$ along the path from~$b$ to its root gives rise to two trees~$\b{\tilde T_\ell}$ (on the left) and $\r{\tilde T_r}$ (on the right). We define the \defn{vertical packing}~$\b{\lmir_b(T)}$ as the $\b{\nu_\ell}$-tree obtained by contracting all vertical segments of $\b{\tilde T_\ell}$ that are above~$b$. Similarly, the \defn{horizontal packing}~$\r{\lrot_b(T)}$ is the $\r{\nu_r}$-tree obtained by contracting all horizontal segments of~$\r{\tilde T_r}$ that are on the left of~$b$. 

\begin{figure}[ht]
\centering
\resizebox{0.8\textwidth}{!}{
	\centerline{
	$\r{\lrot_b}\left( \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreePacking1}} \right) 
%	= \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreePacking2}} 
	= \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreePacking3}}$
	\qquad\quad
	$\b{\lmir_b}\left( \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreePacking1}} \right) 
%	= \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreePacking4}} 
	= \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreePacking5}}$}
	}
	\caption{The horizontal and vertical packings of a $\nu$-tree at a diagonal leaf~$b$.}
	\label{fig:packingNuTree}
\end{figure}

%%%%%%%

\paragraph{Coproduct.}

We define the coproduct of a $\nu$-tree~$T$ as
\(
\coproduct(T)= \sum \b{\lmir_b(T)} \otimes \r{\lrot_b(T)},
\)
where the sum runs over all diagonal leaves~$b$ of~$T$. See \cref{fig:coproductNuTrees}.

\begin{figure}[ht]
	\centerline{$\coproduct \left( \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct1}} \right) = \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct1}} \otimes \epsilon + \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct2}} \otimes \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct3}} + \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct4}} \otimes \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct5}} + \epsilon \otimes \raisebox{-.5\height}{\includegraphics[scale=.3]{nuTreeCoproduct1}}$}
	\caption{The coproduct of a $\nu$-tree.}
	\label{fig:coproductNuTrees}
\end{figure}

%%%%%%%

\paragraph{Product.}

Let~${\bf b} = (b_1, \dots, b_{\ell-1})$ be a tuple of $\ell-1$ diagonal leaves of a $\nu$-tree~$T$ which are located in order along the main diagonal with possible repetitions. They partition~$\nu$ into~$\ell$ Dyck paths $\nu_1, \dots, \nu_\ell$. The tree~$T$ is subdivided into~$\ell$ trees~$\tilde T_1, \dots, \tilde T_\ell$ by cutting along the paths from the leaves~$b_i$ to the root. Define~$T_i$ to be the $\nu_i$-tree obtained by contracting segments of~$\tilde T_i$ that are either horizontal on the left of~$b_{i-1}$ or vertical above~$b_i$. By convention, $b_0$~and~$b_\ell$ denote two extra leaves at coordinates~$(0,0)$ and~$(n,n)$ respectively. 

Given a $\mu$-tree~$S$ and a $\nu$-tree~$T$ we will define the product~$S\cdot T$ as follows.
If~$S$ has~$\ell$ diagonal leaves, we choose a tuple~${\bf b} = (b_1, \dots, b_{\ell-1})$ of $\ell-1$ leaves of~$T$ and we ``cut''~$T$ along~$\bf b$ to produce~$\ell$ trees~$T_1, \dots, T_\ell$ as described above. 
We then ``glue" these trees~$T_1, \dots, T_\ell$ on the~$\ell$ diagonal leaves of~$S$. The resulting tree~$S \star_{\bf b} T$ is a $\lambda$-tree for some Dyck path~$\lambda$ obtained as a shuffle of~$\mu$ and~$\nu$ with cuts at diagonal leaves.

If~$S$ has~$\ell$ diagonal leaves, we define the product of~$S$ and~$T$ by
\(
S\cdot T = \sum_{\bf b} S \star_{\bf b} T,
\)
where the sum ranges over all ordered tuples~${\bf b}=(b_1,\dots ,b_{\ell-1})$ of~$\ell-1$ diagonal leaves in~$T$ with possible repetitions. An example of this product is illustrated in \cref{fig:productNuTrees}.

\begin{figure}[t]
\centering
\resizebox{0.9\textwidth}{!}{
	\centerline{$
		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct1}}
		\product
		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct2}}
		=
		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct3}} +
		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct4}} +
		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct5}} +
		\dots + 
%		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct6}} +
%		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct7}} +
		\raisebox{-.5\height}{\includegraphics[scale=0.3]{nuTreeProduct8}}
	$}
	}
	\caption{The product of a $\mu$-tree and a $\nu$-tree.}
	\label{fig:productNuTrees}
\end{figure}

%%%%%%%

\subsection{Dominant pipe dreams versus $\nu$-trees.}
\label{subsec:dominantVSnuTrees}

\begingroup
\setlength\intextsep{0pt}

\begin{wrapfigure}[10]{r}{2cm}
	\includegraphics[scale=.3]{bijectionNuTreeDominantPipeDreamVertical}
\end{wrapfigure}

We now connect dominant pipe dreams with $\nu$-trees and show that the Hopf algebras considered in the previous two sections are isomorphic. 
As illustrated on the right, we consider the map~$\Psi$ that sends a pipe dream~${P \in \pipeDreams(\omega)}$ with dominant permutation $\omega$ to a $\nu$-tree $T$ where $\nu=\pi_\omega$ is the Dyck path associated to $\omega$.
This $\nu$-tree is defined as the set of lattice points~$\Psi(P)$ given by the elbows of~$P$ located in the topmost row or leftmost column, or inside the Rothe diagram~of~$\omega_P$.

\endgroup

%\begin{figure}[h]
%	\centerline{\includegraphics[scale=0.4]{bijectionNuTreeDominantPipeDream}}
%	\caption{The bijection between dominant pipe dreams and $\nu$-trees: replace each elbow of $P$ that are in the Rothe diagram of~$\omega$ by a node.}
%	\label{fig:bijectionNuTreeDominantPipeDream}
%\end{figure}

\begin{proposition}[\cite{SerranoStump,CeballosPadrolSarmiento-nuTamariSubwordComplexes}]
\label{prop:bijectionDominantPipeDreamsNuTrees}
For any dominant permutation~$\omega$ with corresponding Dyck path~${\nu=\pi_\omega}$, the map~$\Psi$ is a bijection between the dominant pipe dreams in~$\pipeDreams(\omega)$ and the $\nu$-trees of~$\nuTrees(\nu)$.
% which sends flips in dominant pipe dreams to rotations in~$\nu$-trees.
\end{proposition}

\begin{theorem}[{\cite[Coro.\,3.1.9]{BergeronCeballosPilaud}}]
\label{thm:dominantPipeDreamsVSNuTrees}
The map~$\Psi$ is a Hopf algebra isomorphism between the Hopf algebra~$(\HPdom, \product, \coproduct)$ of dominant pipe dreams and the Hopf algebra~$(\HT, \product, \coproduct)$ of~$\nu$-trees.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Hopf chains and multivariate diagonal harmonics}

We conclude this extended abstract with a surprising connection to the multivariate diagonal harmonic spaces~\cite{Bergeron-multivariateDiagonalCoinvariantSpaces}. 
Let~$X=[x_{ij}]$ be a set of $nr$ variables for~$i \in [r]$ and~${j \in [n]}$. 
We refer to $r$ as the number of sets of variables and to $n$ as the number of variables in each of the sets.
The symmetric group~$\fS_n$ acts on the polynomial ring~$\C[X]$ by permuting the $n$ columns of the matrix $X$. 
Let~$\Sym{n}{r}$ be the subring of polynomials~$f(X)$ invariant under the action of~$\fS_n$.
The \defn{multivariate diagonal harmonic space}~$\DiagHarm{n}{r}$ is~the~space
\[
\DiagHarm{n}{r} = \bigset{p\in \C[X]}{f(\partial)p = 0 \text{ for all } f\in \Sym{n}{r} \text{ such that } f({\bf 0}) = 0},
\]
where $f(\partial)$ is the partial differential operator obtained by replacing the variables $x_{ij}$ by $\partial/\partial x_{ij}$ in~$f(X)$.
This space is closed under the action of the symmetric group $\fS_n$, and thus defines a representation of~$\fS_n$. 
For small fixed values of $r$, the dimension of $\DiagHarm{n}{r}$ and 
the multiplicity of the sign representation~$\Alt(\DiagHarm{n}{r})$ satisfy beautiful formulas: 
%
\[
\begin{array}{|c|c|c|c|c|}
\hline
r & r = 1 & r = 2 & r = 3 \text{ (conj.)} & r \ge 4 \\
\hline
\dim \big( \DiagHarm{n}{r} \big) & n! & (n+1)^{n-1} & 2^n (n+1)^{n-2} & ? \\
\hline
\dim \big( \Alt(\DiagHarm{n}{r}) \big) & 1 & \frac{1}{n+1}{2n\choose n} & \frac{2}{n(n+1)} {4n+1\choose n-1} & ? \\
\hline
\end{array}
\]
%
When $r = 2$ (resp.~$r = 3$), the dimension of~$\Alt(\DiagHarm{n}{r})$ is the number of elements (resp.~intervals) in the Tamari lattice.
The dimension of~$\DiagHarm{n}{r}$ can be interpreted by labeled versions of the latter.
In fact, the spaces $\DiagHarm{n}{r}$ and $\Alt(\DiagHarm{n}{r})$ can be further decomposed into homogeneous components invariant under the action of the symmetric group.
Let the degree of a monomial~$X^A=\prod x_{ij}^{a_{ij}}$ be
\(
\deg_{r}(X^A) = \big( \sum_{j=1}^n a_{1j}, \dots, \sum_{j=1}^n a_{rj} \big).
\)
The subspaces of $\DiagHarm{n}{r}$ and $\Alt(\DiagHarm{n}{r})$ of fixed degree are clearly invariant under the action of~$\fS_n$.
The weighted sum of the dimensions of these subspaces for $\DiagHarm{n}{r}$ and $\Alt(\DiagHarm{n}{r})$ give two polynomials in $r$ variables $q_1,\dots,q_r$, whose evaluations at $q_i=1$ for all $i$ recover their total dimensions.
For $r=2$, an expression of the resulting $q,t$-polynomial for $\DiagHarm{n}{r}$ in terms of Macdonald polynomials was conjectured by A.~Garsia and M.~Haiman~\cite{GarsiaHaiman-remarkableCatalanSequence} and proved by M.~Haiman in~\cite{Haiman-vanishingTheorems}.
A combinatorial description of this polynomial, involving a pair of statistics $\area$ and $\dinv$ on parking functions, is described by the former shuffle conjecture of J.~Haglund et al.~\cite{HaglundHaimanLoehrRemmelUlyanov} which was recently proved by E.~Carlsson and A.~Mellit~\cite{CarlssonMellit}.
For $r=3$, there is no known triple of statistics on labeled and unlabeled intervals in the Tamari lattice that would match the tri-degree of $\DiagHarm{n}{3}$ and $\Alt(\DiagHarm{n}{3})$.
F.~Bergeron and L.-F.~Pr\'eville-Ratelle conjectured in~\cite{BergeronPrevilleRatelle} that length of a longest chain in the interval and $\dinv$ are two of the statistics.
Using combinatorial objects arising from the pipe dream algebra, we now provide an interpretation of the dimensions of~$\DiagHarm{n}{r}$ and~$\Alt(\DiagHarm{n}{r})$ and their $q$-Frobenius characteristic for any~${n \le 4}$.
The details on the definitions and the proof can be found in~\cite[Sect.\,3.2.2]{BergeronCeballosPilaud}.

\begin{definition}
\label{def:HopfChains}
A \defn{Hopf chain} is a nested tuple $(\pi_1,\pi_2,\dots ,\pi_r)$ of Dyck paths of size~$n$ such that:
\begin{compactenum}
\item $\pi_1$ is the bottom diagonal path~$(NE)^n$,
\item for every~$1 \le i < j < k \le r$, the subtriple~$(\pi_i,\pi_j,\pi_k)$ comes from an interval of dominant pipe dreams. In other words, the pair $(\pi_j,\pi_k)$ is an interval in the $\pi_i$-Tamari lattice of~\cite{PrevilleRatelleViennot}.
\end{compactenum}
We denote by~$\HC{n}{r}$ the set of Hopf chains of length~$r$ and size~$n$.
\end{definition}

\begin{definition}
The \defn{collar}~$\col(\bpi)$ of a Hopf chain $\bpi=(\pi_1,\pi_2,\dots ,\pi_r)$ is one plus the maximal number of distinct Dyck paths that can be inserted in~$\bpi$ strictly between~$\pi_{r-1}$ and~$\pi_r$ such that the result is a Hopf chain. 
\end{definition} 

\begin{theorem}[{\cite[Thm.\,3.2.5]{BergeronCeballosPilaud}}]
\label{thm:eExpansion}
For degree~$n \le 4$ and \textbf{any number $r$ of sets of variables}, the following two symmetric functions coincide:
\begin{compactitem}
\item the $q$-Frobenius characteristic~$\Phi_{n,r}(q)$ of~$\DiagHarm{n}{r}$ expanded in the elementary basis, and
\item the sum over Hopf chains of~$\HC{n}{r}$ given by
\[
\Psi_{n,r}(q) \eqdef \sum_{\substack{\bpi=(\pi_1,\pi_2,\dots ,\pi_r) \\ \text{Hopf chain of } \HC{n}{r}}}  q^{\col( \bpi)} e_{\type(\pi_r)},
\]
where $\type(\pi_r)$ is the partition of the connected $N$ steps lengths in $\pi_r$.
\end{compactitem}
\end{theorem}

\begin{corollary}[{\cite[Coro.\,3.2.6]{BergeronCeballosPilaud}}]
\label{cor:dim}
For~$n \le 4$ and any~$r \in \N$, the dimension of~$\Alt(\DiagHarm{n}{r})$ (resp.~of~$\DiagHarm{n}{r}$) is the number of Hopf chains (resp.~labelled Hopf chains) of length~$r$ and size~$n$. 
\end{corollary}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\sloppy
\printbibliography
\fussy


\end{document}
