DGDarij Grinberg

Darij Grinberg

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Darij Grinberg has a total of 32 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Top to random and reverse: analysis of a new descent algebra shuffle

    by Darij Grinberg, Jonathan Parlett

    We study the "top-to-random-and-reverse shuffle", defined as the top-to-random shuffle in the symmetric group algebra composed with the permutation $w_0$ (which sends each $i$ to $n+1-i$). More generally, we analyze the composition of any B-basis element of the descent algebra with $w_0$. We show that the minimal polynomial of any such composition (over $\mathbb{Q}$) factors into distinct linear factors, which correspond to the "signed knapsack numbers" of set compositions. This is a counterpart to an analogous property of the B-basis elements themselves, which was proved by Brown using Bidigare's face monoid. In the case of the top-to-random-and-reverse shuffle, the minimal polynomial turns out to be $\prod_{k \in \set{-n+2} \cup \interval{-n+4, n-3} \cup \set{0} \cup \set{n}} \tup{x-k}$.

  • Open Access

    An Introduction to Algebraic Combinatorics

    by Darij Grinberg

    This is an introduction to algebraic combinatorics, written for a quarter-long graduate course. It starts with a rigorous introduction to formal power series with some combinatorial applications, then discusses integer partitions (proving Jacobi's triple product identity), permutations (Lehmer codes, cycles) and subtractive methods (alternating sums, cancellations and inclusion-exclusion principles, with a particular focus on sign-reversing involutions and determinants). The last chapter introduces symmetric polynomials and proves the Littlewood--Richardson rule using Bender--Knuth involutions (a la Stembridge). The appendix contains over 200 exercises (without solutions).

  • Open Access

    A permutation based approach to the $q$-deformation of the Dynkin Operator

    by Darij Grinberg, Ekaterina A. Vassilieva

    Introduced by Solomon, the descent algebra is a significant subalgebra of the group algebra of the symmetric group $\mathbf{k}S_n$ related to many important algebraic and combinatorial topics. It contains all the classical Lie idempotents of $\mathbf{k}S_n$, in particular the Dynkin operator, a fundamental tool for studying the free Lie algebra. We look at a $q$-deformation of the Dynkin operator and study its action over the descent algebra with classical combinatorial tools like Solomon's Mackey formula. This leads to elementary proofs that the operator is indeed an idempotent for $q=1$ as well as to interesting formulas and algebraic structures especially when $q$ is a root of unity.

  • Open Access

    The Enriched $q$-Monomial Basis of the Quasisymmetric Functions

    by Darij Grinberg, Ekaterina Vassilieva

    We construct a new family $\left( \eta_{\alpha}^{\left( q\right) }\right)_{\alpha\in\operatorname*{Comp}}$ of quasisymmetric functions for each element $q$ of the base ring. We call them the "enriched $q$-monomial quasisymmetric functions". When $r:=q+1$ is invertible, this family is a basis of $\operatorname*{QSym}$. It generalizes Hoffman's "essential quasi-symmetric functions" (obtained for $q=0$) and Hsiao's "monomial peak functions" (obtained for $q=1$), but also includes the monomial quasisymmetric functions as a limiting case. We describe these functions $\eta_{\alpha}^{\left( q\right) }$ by several formulas, and compute their products, coproducts and antipodes. The product expansion is given by an exotic variant of the shuffle product which we callthe "stufufuffle product'' due to its ability to pick several consecutive entries from each composition. This "stufufuffle product'' has previously appeared in recent work by Bouillot, Novelli and Thibon, generalizing the "block shuffle product'' from the theory of multizeta values.


  • Open Access

    The Dowker theorem via discrete Morse theory

    by Morten Brun, Darij Grinberg

    The Dowker theorem is a classical result in the topology of finite spaces, claiming that any binary relation between two finite spaces defines two homotopy-equivalent complexes (the Dowker complexes). Recently, Barmak strengthened this to a simple-homotopy-equivalence. We reprove Barmak's result using a combinatorial argument that constructs an explicit acyclic matching in the sense of discrete Morse theory.

  • Open Access

    The Bhargava Greedoid as a Gaussian Elimination Greedoid

    by Darij Grinberg

    Inspired by Manjul Bhargava's theory of generalized factorials, Grinberg and Petrov have defined the Bhargava greedoid - a greedoid (a matroid-like set system on a finite set) assigned to any "ultra triple" (a somewhat extended variant of a finite ultrametric space). Here we show that the Bhargava greedoid of a finite ultra triple is always a Gaussian elimination greedoid over any sufficiently large (e.g., infinite) field; this is a greedoid analogue of a representable matroid. We find necessary and sufficient conditions on the size of the field to ensure this.

  • Open Access

    The path-missing and path-free complexes of a directed graph

    by Darij Grinberg, Lukas Katthän, Joel Brewster Lewis

    We study two simplicial complexes arising from a directed graph $G = (V, E)$ with two chosen vertices $s$ and $t$: the *path-free complex*, consisting of all subsets $F \subseteq E$ that contain no path from $s$ to $t$, and the *path-missing complex*, its Alexander dual. Using discrete Morse theory, we prove that both complexes have well-behaved homotopy types -- either contractible or homotopy-equivalent to spheres.

  • Open Access

    The diagonal derivative of a skew Schur polynomial

    by Darij Grinberg, Nazar Korniichuk, Kostiantyn Molokanov, Severyn Khomych

    We prove a formula for the image of a skew Schur polynomial $s_{λ/μ}\left( x_{1}, x_{2}, \ldots, x_{N}\right) $ under the differential operator $\nabla:= \dfrac{\partial}{\partial x_{1}} +\dfrac{\partial}{\partial x_{2}}+\cdots+\dfrac{\partial}{\partial x_{N}}$. This generalizes a formula of Weigandt for $\nabla\left( s_λ\right) $.

  • Open Access

    Birational rowmotion on a rectangle over a noncommutative ring

    by Darij Grinberg, Tom Roby

    We extend the periodicity of birational rowmotion for rectangular posets to the case when the base field is replaced by a noncommutative ring (under appropriate conditions). This resolves a conjecture from 2014. The proof uses a novel approach and is fully self-contained. Consider labelings of a finite poset \(P\) by \(\left\vert P\right\vert + 2\) elements of a ring \(\mathbb{K}\): one label associated with each poset element and two constant labels for the added top and bottom elements in \(\widehat{P}\). Birational rowmotion is a partial map on such labelings. It was originally defined by Einstein and Propp for \(\mathbb{K}=\mathbb{R}\) as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope \(\mathcal{O}(P) := \{\text{order-preserving } f: P \to[0,1]\}\). The latter, in turn, extends the well-studied rowmotion map on the set of order ideals (or more properly, the set of order filters) of \(P\), which correspond to the vertices of \(\mathcal{O}(P)\). Dynamical properties of these combinatorial maps sometimes (but not always) extend to the birational level, while results proven at the birational level always imply their combinatorial counterparts. Allowing \(\mathbb{K}\) to be noncommutative, we generalize the birational level even further, and some properties are in fact lost at this step.In 2014, the authors gave the first proof of periodicity for birational rowmotion on rectangular posets (when \(P\) is a product of two chains) for \(\mathbb{K}\) a field, and conjectured that it survives (in an appropriately twisted form) in the noncommutative case. In this paper, we prove this noncommutative periodicity and a concomitant antipodal reciprocity formula. We end with some conjectures about periodicity for other posets, and the question of whether our results can be extended to (noncommutative) semirings.It has been observed by Glick and Grinberg that, in the commutative case, periodicity of birational rowmotion can be used to derive Zamolodchikov periodicity in the type \(AA\) case, and vice-versa. However, for noncommutative \(\mathbb{K}\), Zamolodchikov periodicity fails even in small examples (no matter what order the factors are multiplied), while noncommutative birational rowmotion continues to exhibit periodicity. Thus, our result can be viewed as a lateral generalization of Zamolodchikov periodicity to the noncommutative setting.Mathematics Subject Classifications: 06A07, 05E99Keywords: Rowmotion, posets, noncommutative rings, semirings, Zamolodchikov periodicity, root systems, promotion, trees, graded posets, Grassmannian, tropicalization