Shuffles of deformed permutahedra, multiplihedra, constrainahedra, and biassociahedra

We introduce the shuffle of deformed permutahedra (a.k.a. generalized permutahedra), a simple associative operation obtained as the Cartesian product followed by the Minkowski sum with the graphical zonotope of a complete bipartite graph. Besides preserving the class of graphical zonotopes (the shuffle of two graphical zonotopes is the graphical zonotope of the join of the graphs), this operation is particularly relevant when applied to the classical permutahedra and associahedra. First, the shuffle of an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> -permutahedron with an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -associahedron gives the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -multiplihedron, whose face structure is encoded by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> -painted <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -trees, generalizing the classical multiplihedron. We show in particular that the graph of the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -multiplihedron is the Hasse diagram of a lattice generalizing the weak order on permutations and the Tamari lattice on binary trees. Second, the shuffle of an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> -associahedron with an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -associahedron gives the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -constrainahedron, whose face structure is encoded by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -cotrees, and reflects collisions of particles constrained on a grid. Third, the shuffle of an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> -anti-associahedron with an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -associahedron gives the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -biassociahedron, whose face structure is encoded by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -bitrees, with relevant connections to bialgebras up to homotopy. We provide explicit vertex, facet, and Minkowski sum descriptions of these polytopes, as well as summation formulas for their <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>f</mml:mi> </mml:math> -polynomials based on generating functionology of decorated trees.