Published works

Consider a directed multigraph D that is balanced (i.e., at each vertex, the indegree equals the outdegree). Let A be its set of arcs. Fix an integer k. Let s be a vertex of D. We show that the number of k-element subsets B of A that contain no cycles but contain a path from each vertex to s (we call them "s-convergences") is independent of s. This generalizes known facts about spanning arborescences, acyclic orientations and maximal acyclic subdigraphs. Moreover, this result can be generalized even further, replacing "contain no cycles" with "have a given set of cycles".

We address two variants of the classical necklace counting problem from enumerative combinatorics. In both cases, we fix a finite group G and a positive integer n. In the first variant, we count the “identity-product n-necklaces” — that is, the orbits of n-tuples (a₁, a₂, ..., a_n) ∈ Gⁿ that satisfy a₁a₂...a_n = 1 under cyclic rotation.

In the second, we count the orbits of all n-tuples (a₁, a₂, ..., a_n) ∈ Gⁿ under cyclic rotation and left multiplication (i.e., the operation of G on Gⁿ given by h · (a₁, a₂, ..., a_n) = (ha₁, ha₂, ..., ha_n)). We prove bijectively that both answers are the same, and express them as a sum over divisors of n.

Consequently, we generalize the first problem to n-necklaces whose product of entries lies in a given subset of G (closed under conjugation), and we connect a particular case to the enumeration of irreducible polynomials over a finite field with given degree and second-highest coefficient 0.

The somewhere-to-below shuffles are the elements

t_ℓ := cyc_ℓ + cyc_ℓ,ℓ+1 + cyc_{ℓ,ℓ+1,ℓ+2} + ... + cyc_{ℓ,ℓ+1,...,n}

(for ℓ ∈ {1, 2, ..., n}) in the group algebra k[S_n] of the symmetric group S_n. Their linear combinations are called the one-sided cycle shuffles. We determine the eigenvalues of the action of any one-sided cycle shuffle on any Specht module S^λ of S_n.

We construct a new family (η_α^(q))_{α ∈ 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 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 η_α^(q) 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 call the "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.

The Cauchy matrix is the n×n-matrix whose (i, j)-th entry is 1 / (x_i + y_j), where x₁, x₂, ..., x_n, y₁, y₂, ..., y_n are 2n given numbers. A folklore theorem claims that if this matrix is invertible, then the sum of all entries of its inverse is x₁ + x₂ + ... + x_n + y₁ + y₂ + ... + y_n. In this brief expository note, we give a short and simple proof of this fact (using nothing but the definition of inverse matrices). We also discuss some properties of the matrix with entries min{x_i, y_j} (proofs left to the reader).

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 labellings of a finite poset P by |P| + 2 elements of a ring K: one label associated with each poset element and two constant labels for the added top and bottom elements. Birational rowmotion is a partial map on such labellings. It was originally defined by Einstein and Propp for K = R as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope O(P) := {order-preserving f : P → [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 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 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 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.

The problem of counting the F_q-valued points of a variety has been well-studied from algebro-geometric, topological, and combinatorial perspectives. We explore a combinatorially flavored version of this problem studied by Anzis et al. (2018), which is similar to work of Kontsevich, Elkies, and Haglund.

Anzis et al. considered the question: what is the probability that the determinant of a Jacobi--Trudi matrix vanishes if the variables are chosen uniformly at random from a finite field? They gave a formula for various partitions such as hooks, staircases, and rectangles. We give a formula for partitions whose parts form an arithmetic progression, verifying and generalizing one of their conjectures. More generally, we compute the probability of the determinant vanishing for a class of matrices (“multislant matrices”) made of Toeplitz blocks with certain properties.

We furthermore show that the determinant of a skew Jacobi--Trudi matrix is equidistributed across the finite field if the skew partition is a ribbon.

Marcelo Aguiar and Aaron Lauve have shown that if H is a connected graded Hopf algebra over a field, then its antipode S satisfies (id - S²)ⁿ (H_n) = 0 for any positive integer n, where H_n denotes the n-th graded component of H. In later work, Aguiar improved this to (id + S) (id - S²)^n-1 (H_n) = 0. For the Malvenuto-Reutenauer Hopf algebra, Aguiar and Lauve have furthermore shown the stronger claim (id - S²)^n-1 (H_n) = 0 for n > 1.

In this note, we generalize these results in several directions and reprove them using elementary manipulations of tensors. In particular, the connected graded Hopf algebra is replaced by a connected filtered coalgebra (with S² becoming a coalgebra homomorphism satisfying certain conditions).

Let n be a positive integer. Let A be an n×n matrix with integer entries, and let v be a column vector of size n with integer entries. For each integer m ≥ 0, define g_m to be the greatest common divisor of the n entries of A^mv.

Prove that if g_m = 1 for at least one integer m ≥ n, then g_m = 1 for every integer m ≥ 0.

We show that if A is an n × n-matrix, then the diagonal entries of each power A^m are uniquely determined by the principal minors of A, and can be written as universal (integral) polynomials in the latter. Furthermore, if the latter all equal 1, then so do the former. These results are inspired by Problem B5 on the Putnam contest 2021, and shed a new light on the behavior of minors under matrix multiplication.

Given three nonnegative integers p, q, r and a finite field F, how many Hankel matrices (x_i+j)_{0 ≤ i ≤ p, 0 ≤ j ≤ q} over F have rank at most r? The classical answer is |F|^2r when r ≤ min {p, q}; this was obtained using different tools by Daykin, Elkies, Garcia Armas, Ghorpade and Ram.

We prove a refinement: if the first k entries x₀, x₁, ..., x_k-1 are fixed, where k ≤ r ≤ min {p, q}, then there are |F|^2r-k ways to choose the remaining entries x_k, x_k+1, ..., x_p+q so that the resulting Hankel matrix has rank at most r. This generalizes, and gives an alternative proof of, a result by Anzis, Chen, Gao, Kim, Li and Patrias on evaluations of Jacobi-Trudi determinants over finite fields.

For any positive integer k and nonnegative integer m, we consider the symmetric function G(k, m) defined as the sum of all monomials of degree m that involve only exponents smaller than k. We call G(k, m) a Petrie symmetric function in honor of Flinders Petrie, as the coefficients in its expansion in the Schur basis are determinants of Petrie matrices (and thus belong to {0, 1, -1} by a classical result of Gordon and Wilkinson). More generally, we prove a Pieri-like rule for expanding a product of the form G(k, m) · s_μ in the Schur basis whenever μ is a partition; all coefficients in this expansion belong to {0, 1, -1}. We also show that G(k, 1), G(k, 2), G(k, 3), ... form an algebraically independent generating set for the symmetric functions when 1 - k is invertible in the base ring, and we prove a conjecture of Liu and Polo about the expansion of G(k, 2k-1) in the Schur basis.

We confirm three conjectures of Z.-W. Sun on determinants. First, we show that any odd integer n > 3 divides a determinant involving the Jacobi symbol. We then prove divisibility results concerning two families of determinants. Finally, for any odd prime p and integers c and d not divisible by p, we completely determine the Legendre symbol of a further determinant S_c(d, p).

We study an infinite family of shuffling operators on the symmetric group S_n, which includes the well-studied top-to-random shuffle. The general shuffling scheme consists of removing one card at a time from the deck (according to some probability distribution) and re-inserting it at a position chosen uniformly at random among the positions below. Rewritten in terms of the group algebra R[S_n], our shuffle corresponds to right multiplication by a linear combination of the elements

t_ℓ := cyc_ℓ + cyc_ℓ,ℓ+1 + cyc_{ℓ,ℓ+1,ℓ+2} + ... + cyc_{ℓ,ℓ+1,...,n} ∈ R[S_n]

for all ℓ ∈ {1, 2, ..., n} (where cyc_{i1, i2, ..., ip} denotes the permutation in S_n that cycles through i₁, i₂, ..., i_p).

We compute the eigenvalues of these shuffling operators and of all their linear combinations. In particular, we show that the eigenvalues of right multiplication by a linear combination λ₁t₁ + λ₂t₂ + ... + λ_nt_n (with λ₁, λ₂, ..., λ_n being reals) are the numbers λ₁m_I,1 + λ₂m_I,2 + ... + λ_nm_I,n, where I ranges over the lacunar subsets of {1, 2, ..., n-1} (i.e., over the subsets that contain no two consecutive integers), and where m_I,ℓ denotes the distance from ℓ to the next-higher element of I (which element is understood to be ℓ itself if ℓ ∈ I, and to be n+1 if ℓ > max I). We compute the multiplicities of these eigenvalues and show that if they are all distinct, the shuffling operator is diagonalizable. To this purpose, we show that the operators of right multiplication by t₁, t₂, ..., t_n on R[S_n] are simultaneously triangularizable, and in fact there is a combinatorially defined basis (the "descent-destroying basis", as we call it) of R[S_n] in which they are represented by upper-triangular matrices. The results stated here over R for convenience are actually stated and proved over an arbitrary commutative ring. We finish by describing a strong stationary time for the random-to-below shuffle, which is the shuffle in which the card that moves below is selected uniformly at random, and we give the waiting time for this event to happen.

We prove the vanishing of a determinant whose entries themselves are products of minors of two matrices. This generalizes one of the main results in Peter Olver's and my The n body matrix and its determinant.

Consider a finite set E. Assume that each e ∈ E has a "weight" w(e) ∈ ℝ assigned to it, and any two distinct e, f ∈ E have a "distance" d(e, f) = d(f, e) ∈ ℝ assigned to them, such that the distances satisfy the ultrametric triangle inequality d(a, b) ≤ max {d(a, c), d(b, c)}.

We look for a subset of E of given size with maximum perimeter, defined by summing the weights of all elements and their pairwise distances. We show that any such subset can be found by a greedy algorithm, which starts with the empty set and adds new elements one by one while maximizing the perimeter at each step.

We use this to define numerical invariants, and show that the maximum-perimeter subsets of all sizes form a strong greedoid, while the maximum-perimeter subsets of any given size are the bases of a matroid. This essentially generalizes the "P-orderings" constructed by Bhargava to define generalized factorials, and is also similar to the strong greedoid of maximum-diversity subsets in phylogenetic trees studied by Moulton, Semple and Steel.

We further discuss numerical invariants of E, w, and d arising from this construction, along with an analogue in which maximum-perimeter subsets are replaced by maximum-perimeter tuples, allowing repeated elements.

Let K be a finite commutative ring, and let L be a commutative K-algebra. Let A and B be two n × n-matrices over L that have the same characteristic polynomial. The main result of this paper states that the set {A⁰, A¹, A², ...} is finite if and only if the set {B⁰, B¹, B², ...} is finite. We apply this result to the theory of discrete time dynamical systems. Indeed, it gives a complete and easy-to-check characterization of sensitivity to initial conditions and equicontinuity for linear cellular automata over the alphabet Kⁿ for K = Z/mZ, i.e. cellular automata in which the local rule is defined by n × n-matrices with elements in Z/mZ.

To prove our main result, we derive an integrality criterion for matrices that is likely of independent interest. Namely, let K be any commutative ring (not necessarily finite), and let L be a commutative K-algebra. Consider any n × n-matrix A over L. Then, A ∈ L^{n × n} is integral over K (that is, there exists a monic polynomial f ∈ K[t] satisfying f(A) = 0) if and only if all coefficients of the characteristic polynomial of A are integral over K. The proof of this fact relies on a strategic use of exterior powers (a trick pioneered by Gert Almkvist).

Fix a finite undirected graph G and a vertex v of G. Let E be the set of edges of G; assume that E ≠ ∅. We call a subset F of E pandemic if each of edge G has at least one endpoint that can be connected to v by an F-path (i.e., a path using edges from F only). In 1984, Elser showed that the sum of (-1)^|F| over all pandemic subsets F of E is 0. We give a simpler proof and discuss variants and generalizations.

We prove an identity for Littlewood--Richardson coefficients conjectured by Pelletier and Ressayre. The proof relies on an (apparently novel) birational involution defined over any semifield.

Here we consider an invariant of a module over a finite-dimensional Hopf algebra, called the critical group. This generalizes the critical groups of complex finite group representations studied by Benkart, Klivans, Reiner and Gaetz. A formula is given for the cardinality of the critical group generally, and the critical group for the regular representation is described completely. A key role in the formulas is played by the greatest common divisor of the dimensions of the indecomposable projective representations.

Using the description of multiline queues as functions on words, we introduce the notion of a spectral weight of a word by defining a new weighting on multiline queues. We show that the spectral weight of a word is invariant under a natural action of the symmetric group, giving a proof of the commutativity conjecture of Arita, Ayyer, Mallick, and Prolhac. We give a determinant formula for the spectral weight of a word, which gives a proof of a conjecture of the first author and Linusson.

This is an algebraic approach to the Bhargava greedoid introduced previously in a joint paper with Fedor Petrov. Here I show that any Bhargava greedoid is a Gaussian elimination greedoid (a greedoidal analogue of a representable matroid).

We show that if N is a n×n-matrix over a commutative ring K, and if f is a univariate polynomial over K, then there exist two univariate polynomials a and b over K such that det(f(N)) = f a + χ_N b, where χ_N denotes the characteristic polynomial of N.

The primary purpose of this note is to prove two recent conjectures concerning the n-body matrix that arose in recent papers of Escobar-Ruiz, Miller, and Turbiner on the classical and quantum n-body problem in d-dimensional space. First, whenever the positions of the masses are in a nonsingular configuration, meaning that they do not lie on an affine subspace of dimension ≤ n - 2, the n-body matrix is positive definite and, hence, defines a Riemannian metric on the space coordinatized by their interpoint distances. Second, its determinant can be factored into the product of the order-n Cayley--Menger determinant and a mass-dependent factor that is also of one sign on all nonsingular mass configurations. The factorization of the n-body determinant is shown to be a special case of an intriguing general result proving the factorization of determinants of a certain form.

This is a continuation of the paper "Shuffle-compatible permutation statistics" by Ira M. Gessel and Yan Zhuang. We show that the exterior peak set is a shuffle-compatible permutation statistic (as conjectured by Gessel and Zhuang), using a notion of "Z-enriched (P, γ)-partitions" that generalizes the concepts of "P-partitions", "enriched P-partitions" and "left enriched P-partitions". Furthermore, we introduce the notion of "LR-shuffle-compatibility", which is a property stronger than shuffle-compatibility, and which we also verify for the permutation statistics Des, des, Lpk and Epk (but not maj, Rpk and Pk). Furthermore, we describe the kernel of the homomorphism from QSym to the shuffle algebra of the exterior peak set statistic (by finding two generating sets for this kernel), and we relate LR-shuffle-compatibility to dendriform algebra quotients of QSym in the same way as shuffle-compatibility itself relates to algebra quotients of QSym. We pose various questions about these concepts.

We assign a quasisymmetric function to any double poset (that is, every finite set endowed with two partial orders) and any weight function on its ground set. This generalizes monomial and fundamental quasisymmetric functions, (skew) Schur functions, dual immaculate functions, and quasisymmetric (P, ω)-partition enumerators.

We prove an antipode formula under conditions that include the case where the second order is total, giving a new self-contained proof of a result of Malvenuto and Reutenauer. We then generalize the formula to a setting in which a group acts on the double poset by automorphisms.

The dual immaculate functions are a basis of the ring QSym of quasisymmetric functions, and form one of the most natural analogues of the Schur functions. The dual immaculate function corresponding to a composition is a weighted generating function for immaculate tableaux in the same way as a Schur function is for semistandard Young tableaux; an "immaculate tableau" is defined similarly to a semistandard Young tableau, but the shape is a composition rather than a partition, and only the first column is required to strictly increase (whereas the other columns can be arbitrary; but each row has to weakly increase). Dual immaculate functions have been introduced by Berg, Bergeron, Saliola, Serrano and Zabrocki in arXiv:1208.5191, and have since been found to possess numerous nontrivial properties.

In this note, we prove a conjecture of Mike Zabrocki which provides an alternative construction for the dual immaculate functions in terms of certain "vertex operators" (Corollary 4.7 in the paper). The proof uses a dendriform structure on the ring QSym; we discuss the relation of this structure to known dendriform structures on the combinatorial Hopf algebras FQSym and WQSym.

The reduced expressions for a given element w of a Coxeter group (W, S) can be regarded as the vertices of a directed graph R(w); its arcs correspond to the braid moves. Specifically, an arc goes from a reduced expression a to a reduced expression b when b is obtained from a by replacing a contiguous subword of the form stst... (for some distinct s, t ∈ S) by tsts... (where both subwords have length m_{s, t}, the order of st ∈ W). We prove a strong bipartiteness-type result for this graph R(w): Not only does every cycle of R(w) have even length; actually, the arcs of R(w) can be colored (with colors corresponding to the type of braid moves used), and to every color c corresponds an "opposite" color c^op (corresponding to the reverses of the braid moves with color c), and for any color c, the number of arcs in any given cycle of R(w) having color in {c, c^op} is even. This is a generalization and strengthening of a 2014 result by Bergeron, Ceballos and Labbé.

Fix a commutative ring k, two elements β ∈ k and α ∈ k and a positive integer n. Let X be the polynomial ring over k in the n(n-1)/2 indeterminates x_i,j for all 1 ≤ i < j ≤ n. Consider the ideal J of X generated by all polynomials of the form x_i,j x_j,k - x_i,k (x_i,j + x_j,k + β) - α for 1 ≤ i < j < k ≤ n. The quotient algebra X / J (in some specific cases) has been introduced by Karola Mészáros as a commutative analogue of Anatol Kirillov's quasi-classical Yang-Baxter algebra. A natural question is to find a combinatorial basis of this quotient algebra. One can define the pathless monomials, i.e., the monomials in X that have no divisors of the form x_i,j x_j,k with 1 ≤ i < j < k ≤ n. The residue classes of these pathless monomials indeed span the k-module X / J; however, they turn out (in general) to be k-linearly dependent. More combinatorially: Reducing a given monomial in X modulo the ideal J by applying replacements of the form x_i,j x_j,k ↦ x_i,k (x_i,j + x_j,k + β) + α always eventually leads to a k-linear combination of pathless monomials, but the result may depend on the choices made in the process.

More recently, the study of Grothendieck polynomials has led Laura Escobar and Karola Mészáros to defining a k-algebra homomorphism D from X into the polynomial ring k[t₁, t₂, ..., t_n-1] that sends each x_i,j to t_i. For a certain class of monomials (those corresponding to "noncrossing trees"), they have shown that whatever result one gets by reducing the monomial modulo J, the image of this result under D is independent of the choices made in the reduction process. Mészáros has conjectured that this property holds not only for this class of monomials, but for any polynomial p ∈ X. We prove this result, in the following slightly stronger form: If p ∈ X, and if q ∈ X is a k-linear combination of pathless monomials satisfying p ≡ q mod J, then D(q) does not depend on q (as long as β, α and p are fixed).

We also find an actual basis of the k-module X / J, using what we call forkless monomials.

This is a spin-off from James Borger, Witt vectors, semirings, and total positivity.

We give explicit descriptions of the Witt vectors of the Boolean semiring. This includes the big Witt vectors, the Schur Witt vectors, and the p-typical Witt vectors. We use this to determine the Schur Witt vectors of the natural numbers. This can be viewed as an integral variant of the Edrei-Thoma theorem on totally positive power series. We also determine the cardinality of the Witt vectors of the semiring quotient of the natural numbers by a single relation of the form n = n + 1. It is countable for n = 0, 1, 2 but uncountable after that.

A number of authors have studied a natural operation (under various names) on the order ideals (equivalently, antichains) of a finite poset, here called rowmotion. For certain posets of interest, the order of this map is much smaller than one would naively expect, and the orbits exhibit unexpected properties. In recent work (inspired by discussions with Berenstein) Einstein and Propp describe how rowmotion can be generalized: first to the piecewise-linear setting of order polytopes (instead of acting on order ideals, the operation here acts on points inside the order polytope of the poset), then via detropicalization to the birational setting (here, the operation acts -- more or less -- on maps from the poset to an arbitrary field).

In the latter setting, it is no longer a priori clear even that birational rowmotion has finite order, and for many posets the order is indeed infinite. However, we show that, for the poset P = [p] × [q] (product of two chains), birational rowmotion has the same order, p+q, as ordinary rowmotion. We also show that birational (hence also ordinary) rowmotion has finite order for some other classes of posets, e.g., the upper, lower, right and left halves of the poset above, and trees having all leaves on the same level. Our methods are based on those used by Volkov to resolve the type AA (rectangular) Zamolodchikov Periodicity Conjecture, of which our result can be considered an analogue.

The proofs are at most sketched in the above abstract, while the main paper offers more detail.

The dual stable Grothendieck polynomials are a deformation of the Schur functions, originating in the study of the K-theory of the Grassmannian. We generalize these polynomials by introducing a countable family of additional parameters, and we prove that this generalization still defines symmetric functions. For this fact, we give two self-contained proofs, one of which constructs a family of involutions on the set of reverse plane partitions generalizing the Bender-Knuth involutions on semistandard tableaux, whereas the other classifies the structure of reverse plane partitions with entries 1 and 2.