Research works

Burman and Kulishov defined Lie elements in the group algebra k[S_n] by comparing, on every exterior power of the reflection representation V, the usual action of k[S_n] with the infinitesimal action induced by its action on V. They conjectured that the Lie algebra of all Lie elements is generated by the Kirchhoff differences 1 - (i j). We disprove this conjecture for n = 4 by exhibiting an explicit counterexample arising from the (2,2)-block of k[S₄]. More generally, we describe this Lie algebra in terms of the Artin--Wedderburn decomposition of k[S_n]: its hook blocks are determined by the action on V, whereas its non-hook blocks are arbitrary. Consequently, the primitive central idempotents of the non-hook blocks yield linearly independent obstructions to the conjecture. We also identify the Lie algebra generated by the Kirchhoff differences in terms of the derived algebra of the Lie algebra generated by transpositions. Along the way, we give an integral, and hence characteristic-free, proof that the exterior powers of V are the hook-shaped Specht modules.

Consider the group algebra k[S_n] of the symmetric group S_n over a field k of characteristic 0. In this algebra, we define the dyadic shuffles S_n,k by

S_n,k = sum of incmat_k (w) w over all w ∈ S_n,

where incmat_k (w) is the number of k-tuples of disjoint 2-element subsets of [n] on which w increases (i.e., of all 2k-tuples (i₁, i₂, ..., i_k, j₁, j₂, ..., j_k) of distinct elements of [n] such that each p satisfies i_p < j_p and w(i_p) < w(j_p)).

These shuffles were already defined by Reiner, Saliola and Welker in 2011, who showed that these shuffles commute and have integer eigenvalues (acting on any representation of S_n).

We recover these results by showing that all these shuffles lie in a left ideal of k[S_n] that is a Gelfand model of S_n (that is, a representation that contains each irreducible representation exactly once). This Gelfand model is equipped with a natural filtration, and its associated graded module is the involution-based Gelfand model studied by Kodiyalam and Verma (2004) and by Adin, Postnikov and Roichman (2008).

We furthermore prove a number of general properties of multiplicity-free left ideals of k[S_n], as well as a few specific properties of our Gelfand model.

Let R be a commutative ring. We show that every homogeneous multivariate polynomial f over R of degree n splits into a product of n homogeneous linear forms over a suitable noncommutative ring extension of R.

The proof uses Bergman's Diamond Lemma: we define S by generators and relations, and the relations form a terminating reduction system that has no ambiguities and thus is confluent. An analogous result is also shown for inhomogeneous polynomials (with inhomogeneous factors). This easily follows from the homogeneous case by homogenizing and then setting the homogenizing variable equal to 1.

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".

Let E be a nonempty finite set. A shade map on E is a map T : P(E) → P(E) such that toggling an element u ∉ T(F) in the input F does not change T(F). We prove that, if T is an inclusion-reversing shade map and G ⊆ E, then the simplicial complex

{F ⊆ E ∣ G ⊆ T(F)}

is collapsible. Equivalently, if S is an inclusion-preserving shade map, then the Alexander dual of

{F ⊆ E ∣ G ⊈ S(F)}

is collapsible. This is an Alexander-dual companion to the shade-map collapsibility theorem in The Elser nuclei sum revisited.

We study n-homomorphisms in the sense of Khudaverdian--Voronov, but generalized to maps from arbitrary rings to arbitrary commutative rings. We show that the sum of an n-homomorphism and an m-homomorphism is an n+m-homomorphism, and that the composition of an n-homomorphism and an m-homomorphism is an nm-homomorphism. The proofs are entirely combinatorial.

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.

We construct a surjective filtered morphism of connected graded coalgebras over Z that is injective on primitive elements but is not injective. As a consequence, we construct a nonzero coideal containing no nonzero primitive element. All tensor factors occurring in the coproduct of the source are direct summands, so the construction does not rely on any ambiguity in the notion of a subcoalgebra in the absence of flatness.

Given a finite Coxeter group W and a scalar q, we define the element L_q to be the sum of q^ℓ(w) w over all w ∈ W in the group algebra of W. We say that an element w ∈ W is W-length-symmetric if its coefficient in the commutator [L_a, L_b] is 0 for all scalars a, b in any commutative ring. We prove several sufficient criteria for elements to be W-length-symmetric. In particular, we show that any separable permutation (i.e., permutation avoiding the patterns 2413 and 3142) in the symmetric group S_n is S_n-length-symmetric. This is only a sufficient condition; other W-length-symmetric elements include (twisted) involutions and elements of dihedral parabolic subgroups.

Consider a square matrix A whose all principal minors are equal to 1. Over a field, this property is inherited by any integer power of A, but this is not the case over an arbitrary commutative ring. We show that it is the case over any well-behaved ring, including all reduced rings and quotients of commutative rings modulo integrally closed ideals. This generalizes Problem B5 of the 2021 Putnam contest.

Over arbitrary commutative rings, we identify a stronger property that is always inherited by powers: We say that a matrix A with entries a_i,j is 1-nullcyclic if all its diagonal entries are 1 and if all the cyclic products a_i1,i2 a_i2,i3 ... a_ik,i1 with k > 1 vanish. We show that the latter products are always integral over the ideal generated by the principal minors of A minus 1.

We also prove variants of the above results for matrices A whose diagonal entries can be arbitrary, and whose principal minors are equal to the corresponding products of principal minors.

We show that every polynomial of degree ≤ m over a commutative ring R can be split into a product of m factors of degree ≤ 1 over an extension S of R. This answers MathOverflow question #429134.

The proof involves diagonal symmetric polynomials in 2m variables and a variant of Garsia-Stanton descent monomials, but nothing beyond basic algebra is used without proof.

The above note has been edited for clarity, but I plan to write up my own version of this proof.

We introduce a new basis of the group algebra of the symmetric group, built using the left-to-right minima sets of permutations. We show that on this basis, the descent algebra acts by triangular operators, thus making it an analogue of a cellular basis. The proof involves Dynkin elements (nested commutators) of the free algebra and their interactions with the B-basis.

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.

Graduate-level introduction to rings and fields, assuming familiarity with groups. Contains some new results on strong gcd-sequences.

Let 𝒜 be the group algebra k[S_n] of the n-th symmetric group S_n over a commutative ring k. For any two subsets A and B of [n] = {1, 2, ..., n}, we define the elements

∇_B,A := sum of all permutations w ∈ S_n satisfying w(A) = B

and

˜∇_B,A := sum of all permutations w ∈ S_n satisfying w(A) ⊆ B

of 𝒜. We study these elements, showing in particular that their minimal polynomials factor into linear factors (with integer coefficients). We express the product ∇_D,C ∇_B,A as a Z-linear combination of ∇_U,V's.

More generally, for any two set compositions (i.e., ordered set partitions) A and B of [n], we define ∇_B,A to be the sum of all permutations w ∈ S_n that send each block of A to the corresponding block of B. This generalizes ∇_B,A. The factorization property of minimal polynomials does not extend to the ∇_B,A, but we describe the ideal spanned by the ∇_B,A and a further ideal complementary to it. These two ideals have a "mutually annihilative" relationship, are free as k-modules, and appear as annihilators of tensor product S_n-representations; they are also closely related to Murphy's cellular bases, Specht modules, pattern-avoiding permutations and even some algebras appearing in quantum information theory.

We generalize Reiner-Saliola-Welker's well-known but mysterious family of k-random-to-random shuffles from Markov chains on symmetric groups to Markov chains on the Type-A Iwahori–Hecke algebras. We prove that the family of operators pairwise commutes and has eigenvalues that are polynomials in q with non-negative integer coefficients. Our work generalizes work of Reiner–Saliola–Welker and Lafrenière for the symmetric group, and simplifies all known proofs in this case.

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₀ (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₀. We show that the minimal polynomial of any such composition (over 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 ∏_{k ∈ {-n + 2} ∪ [-n + 4, n - 3] ∪ {0} ∪ {n}} (x - k).

Given a graded bialgebra H, we define maps p_α,σ : H → H using iterated (co)multiplications, multigraded projections and permutations of tensor factors. We prove formulas for the composition and convolution of two such maps. When H is cocommutative, these generalize Patras's 1994 results, which in turn generalize Solomon's Mackey formula.

We also construct a combinatorial Hopf algebra PNSym ("permuted noncommutative symmetric functions") that governs these maps for arbitrary connected graded bialgebras in the same way as the well-known NSym does in the cocommutative case. We end by outlining an application to checking identities for connected graded Hopf algebras.

Motivated by a question and some enumerative conjectures of Richard Stanley, we explore the equivalence classes of words in the Weyl algebra, k < D,U | DU - UD = 1 >. We show that each class is generated by the swapping of adjacent balanced subwords, i.e., those which have the same number of D's as U's, and give several other characterizations, as well as a linear-time algorithm for equivalence checking. Armed with this, we deduce several enumerative results about such equivalence classes and their sizes. We extend these results to the class of c-Dyck words, where every prefix has at least c times as many U's as D's. We also connect these results to previous work on bond percolation and rook theory, and generalize them to some other algebras.

Part of a student project mentored via the Yulia's Dream program 2022-2023.

We prove a formula for the image of a skew Schur polynomial s_λ/μ (x₁, x₂, ..., x_N) under the differential operator ∇ = ∂ / ∂x₁ + ∂ / ∂x₂ + ... + ∂ / ∂x_N. This generalizes a formula of Weigandt for ∇(s_λ).

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.

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.

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.

Given a positive integer n, we consider the group algebra of the symmetric group S_n. In this algebra, we define n elements t₁, t₂, ..., t_n by the formula

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

where cyc_{ℓ, ℓ+1, ..., k} denotes the cycle that sends ℓ, ℓ+1, ..., k-1, k to ℓ+1, ℓ+2, ..., k, ℓ (respectively). These n elements are called the somewhere-to-below shuffles due to an interpretation as card-shuffling operators. In this paper, we show that their commutators [t_i, t_j] are nilpotent, and specifically satisfy the equalities

[t_i, t_j]^{ceiling((n-j)/2) + 1} = 0 for any i, j ∈ [n]

and

[t_i, t_j]^{j - i + 1} = 0 for i < j.

We discuss some further identities and possible generalizations.

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 D = (V, A) be a digraph with n vertices, where each arc a ∈ A is a pair (u, v) of two vertices. We study the Redei--Berge symmetric function U_D, defined as the quasisymmetric function ∑ L_{Des(w, D), n} ∈ QSym. Here, the sum ranges over all lists w = (w₁, w₂, ..., w_n) that contain each vertex of D exactly once, and the corresponding addend is L_{Des(w, D), n} := ∑ x_i1 x_i2 ... x_in summed over all n-tuples (i₁ ≤ i₂ ≤ ... ≤ i_n) of positive integers that satisfy i_p < i_p+1 for each p satisfying (w_p, w_p+1) ∈ A (an instance of Gessel's fundamental quasisymmetric functions).

While U_D is a specialization of Chow's path-cycle symmetric function, which has been studied before, we prove some new formulas that express U_D in terms of the power-sum symmetric functions. We show that U_D is always p-integral, and furthermore is p-positive whenever D has no 2-cycles. When D is a tournament, U_D can be written as a polynomial in p₁, 2p₃, 2p₅, 2p₇, ... with nonnegative integer coefficients. By specializing these results, we obtain the famous theorems of Redei and Berge on the number of Hamiltonian paths in digraphs and tournaments, as well as a modulo-4 refinement of Redei's theorem.

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.

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 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 ⊆ 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.

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).

The grouplike elements of a coalgebra over a field are known to be linearly independent over that field. We prove three variants of this result: a generalization to coalgebras over a commutative ring, where linear independence is replaced by a weaker statement; a stronger statement for commutative bialgebras under stronger assumptions; and a linear-independence result for characters of a bialgebra.

Fix integers n ≥ k ≥ 0. Consider the ring S of symmetric polynomials in k variables over an arbitrary base ring k. Fix k scalars a₁, a₂, ..., a_k ∈ k.

Let I be the ideal of S generated by h_n-k+1 - a₁, h_n-k+2 - a₂, ..., h_n - a_k (where h_i stands for the i-th complete homogeneous symmetric polynomial).

The quotient ring S/I generalizes both the usual and the quantum cohomology of the Grassmannian.

We show that S/I has a k-module basis consisting of (residue classes of) Schur polynomials fitting into a k × (n-k)-rectangle; and that its multiplicative structure constants satisfy the same S₃-symmetry as those of the Grassmannian cohomology. We furthermore find an analogue of the Pieri rule for complete homogeneous symmetric polynomials and a few other formulas.

We also study the quotient of the whole polynomial ring (not just the symmetric polynomials) by the ideal generated by the same k polynomials as I.

I prove an identity for matrices over noncommutative rings, generalizing a MathOverflow question by Tom Copeland.

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.

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 well-known objects such as monomial and fundamental quasisymmetric functions, (skew) Schur functions, dual immaculate functions, and quasisymmetric (P, ω)-partition enumerators. We then prove a formula for the antipode of this function that holds under certain conditions (which are satisfied when the second order of the double poset is total, but also in some other cases); this restates (in a way that to us seems more natural) a result by Malvenuto and Reutenauer, but our proof is new and self-contained. We generalize it further to an even more comprehensive setting, where 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.

The Chio pivotal condensation theorem is the fact that every n × n matrix A = (a_i,j)_{1 ≤ i ≤ n, 1 ≤ j ≤ n} with n ≥ 2 satisfies

det ( (a_i,j a_n,n - a_i,n a_n,j)_{1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1} ) = a_n,n^n-2 det A.

On the other hand, the Matrix-Tree theorem expresses the number (and, more generally, a weighted sum) of spanning trees of a graph as a determinant. In this note, we show that these two results have a common generalization. In its simplest form, the generalization computes

det ( (a_i,j a_f(i),n - a_i,n a_f(i),j)_{1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1} ),

where f : {1, 2, ..., n} → {1, 2, ..., n} is a map satisfying f(n) = n. The result depends on whether the map f is "n-potent" (i.e., every element gets sent to n by a sufficiently high power of f) or not; the n-potent maps are in bijection with the trees on {1, 2, ..., n}.

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.

This is an attempt to construct an object which relates to the ring of symmetric functions in the same way as the polynomial ring F_q[T] (over a finite field) relates to the ring of integers. So, for example, while the ring of symmetric functions has bases indexed by partitions (~ conjugacy classes of permutations), this mythical object would have bases indexed by "function-field partitions" (~ conjugacy classes of matrices in GL_n(F_q)).

I have not been able to say much about this object so far; the construction I have is rather indirect and the combinatorial meaning is yet to be found. But along the way, I found a nice (I believe) F_q[T]-analogue of Witt vectors in which the Carlitz action replaces exponentiation.

This is far from finished, and most proofs have yet to be written up.

This paper was formerly known as "A note on non-broken-circuit sets and the chromatic polynomial".

We explore several generalizations of Whitney's theorem -- a classical formula for the chromatic polynomial of a graph. Following Stanley, we replace the chromatic polynomial by the chromatic symmetric function. Following Dohmen and Trinks, we exclude not all but only an (arbitrarily selected) set of broken circuits, or even weigh these broken circuits with weight monomials instead of excluding them. Following Crew and Spirkl, we put weights on the vertices of the graph. Following Gebhard and Sagan, we lift the chromatic symmetric function to noncommuting variables. In addition, we replace the graph by an "ambigraph", an apparently new concept that includes both hypergraphs and multigraphs as particular cases. We show that Whitney's formula endures all these generalizations, and a fairly simple sign-reversing involution can be used to prove it in each setting. Furthermore, if we restrict ourselves to the chromatic polynomial, then the graph can be replaced by a matroid. We discuss an application to transitive digraphs (i.e., posets), and reprove an alternating-sum identity by Dahlberg and van Willigenburg.

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.

If H is a commutative connected graded Hopf algebra over a commutative ring k, then a certain canonical k-algebra homomorphism H → H ⊗ QSym is defined. This homomorphism generalizes the "internal comultiplication" on QSym, and extends what Hazewinkel (in Section 18.24 of his "Witt vectors") calls the Bernstein homomorphism.

We construct this homomorphism with the help of the universal property of QSym as a combinatorial Hopf algebra (a well-known result by Aguiar, Bergeron and Sottile) and extension of scalars (the commutativity of H allows us to consider, for example, H ⊗ QSym as an H-Hopf algebra, and this change of viewpoint significantly extends the reach of the universal property).

This note answers a question I asked in 2010 on MathOverflow. It concerns the kernel of a certain operator on the tensor algebra T(L) of a free module L over a commutative ring k (an operator that picks out a factor from a tensor and moves it to the front, and takes an alternating sum of the results ranging over all factors -- an algebraic version of what probabilists call the "random-to-top shuffle", albeit with signs).

These notes -- originating from a one-semester class by Victor Reiner at the University of Minnesota -- survey some of the most important Hopf algebras appearing in combinatorics. After introducing coalgebras, bialgebras and Hopf algebras in general, we study the Hopf algebra of symmetric functions, including Zelevinsky's axiomatic characterization of it as a "positive self-adjoint Hopf algebra" and its application to the representation theory of symmetric and (briefly) finite general linear groups. The notes then continue with the quasisymmetric and the noncommutative symmetric functions, some Hopf algebras formed from graphs, posets and matroids, and the Malvenuto-Reutenauer Hopf algebra of permutations. Among the results surveyed are the Littlewood-Richardson rule and other symmetric function identities, Zelevinsky's structure theorem for PSHs, the antipode formula for P-partition enumerators, the Aguiar-Bergeron-Sottile universal property of QSym, the theory of Lyndon words, the Gessel-Reutenauer bijection, and Hazewinkel's polynomial freeness of QSym. The notes are written with a graduate student reader in mind, being mostly self-contained but requiring a good familiarity with multilinear algebra and -- for the representation-theory applications -- basic group representation theory.

Problem U275 in Mathematical Reflections 4/2013, with solution.

Let μ be the number-theoretical Möbius function, and let a_f be a real number for every positive integer f. Prove that, for all positive integers m and n,

∑_{d ∣ m} ∑_{e ∣ n} ∑_{g ∣ gcd(d, e)} (μ(g)/g) d e a_de/g = ∑_{f ∣ mn} f a_f.

This note provides three solutions to the following problem:

Let L/K be a separable algebraic extension of fields and let V, W and U be L-vector spaces.

Let h : V × W → U be a K-bilinear map satisfying

h(xa, xb) = x² h(a, b) for every x ∈ L, a ∈ V and b ∈ W.

Prove that h is L-bilinear.

One of the solutions generalizes the problem from separable algebraic field extensions to commutative separable algebras over commutative rings. Along the way, some basic properties of separable field extensions are shown.

Problem O222 in Mathematical Reflections 1/2012, with solution.

Let (a₁, a₂, ..., a_n) and (b₁, b₂, ..., b_n) be n-tuples of nonnegative reals, and let σ be a permutation of {1, 2, ..., n}. For each k in {1, 2, ..., n}, let c_k be the maximum of {a₁b_k, a₂b_k, ..., a_kb_k} ∪ {a_kb₁, a_kb₂, ..., a_kb_k}.

Prove that a₁b_σ(1) + a₂b_σ(2) + ... + a_nb_σ(n) ≤ c₁ + c₂ + ... + c_n. The solution file contains background on the problem.

Let k be a commutative ring (with 1), L some k-module, and f : L × L → k be a bilinear form (not necessarily symmetric). We define the Clifford algebra Cl(L, f) as the tensor algebra ⊗ L of L, divided by the two-sided ideal generated by all terms of the form u ⊗ u - f(u, u) with u being a vector in L.

This note shows that, as a k-module, Cl(L, f) is isomorphic to the exterior algebra ∧ L of L. This is a standard result in case of k being a field of characteristic 0 and f being symmetric, but we establish it independently of these assumptions. Moreover, the isomorphism ∧ L → Cl(L, f) that we construct (inductively) is a projection of a k-module automorphism α^f : ⊗ L → ⊗ L. Considering this α^f for different f, we notice the surprising fact that the composition α^f α^g equals α^f+g for any two bilinear forms f and g on L. We show that our isomorphism ∧ L → Cl(L, f) is indeed the antisymmetrization map that is usually constructed in textbooks on Clifford algebras, if k is a field of characteristic 0 (or, at least, (dim L)! is invertible in k). We also show that the k-module Cl(L, f) has a basis similar to the standard basis of ∧ L if L itself is a free k-module.

[Update (2013): The results just listed are wellknown. They appear in Bourbaki's Algèbre IX, §9, no. 2-3, and in Chapter 2 of Ricardo Baeza's Quadratic Forms over Semilocal Rings, Lecture Notes in Mathematics 655, Springer 1978. The results listed below have a better chance to be new.]

A further section describes some elements of Fix α^symm, which is the space of all tensors in ⊗ L that are fixed under α^f for all symmetric bilinear forms f. Finally it is shown that if L is a direct sum of two k-submodules M and N and h is a bilinear form on L such that h (M × M) = 0, then there exists an isomorphism of k-modules ∧ L → Cl(L, h) which sends (∧ L) M to (Cl(L, h)) M.

Philip Matchett Wood and Doron Zeilberger have constructed identities for the Fibonacci numbers f_n of the form

1f_n = f_n;

2f_n = f_n-2 + f_n+1;

3f_n = f_n-2 + f_n+2;

4f_n = f_n-2 + f_n + f_n+2;

...;

kf_n = sum of f_n-i over all i from a fixed finite "lacunar" set of integers ("lacunar" means that no two elements of this set are consecutive integers).

This lacunar set depends on k only, and is unique for every k.

In this note we prove a generalization of these identities: For any family (a₁, a₂, ..., a_p) of integers, there exists one and only one finite lacunar set S of integers such that every high enough n satisfies

f_n+a1 + f_n+a2 + ... + f_n+ap = sum of f_n+s over all s in S.

("High enough" means high enough that all f_n+ai and all f_n+s are well-defined (some a_i as well as some elements of S may be negative).)

The proof uses the Fibonacci-approximating properties of the golden ratio φ; it would be interesting to find a purely combinatorial proof.

The main result of this note is the following inequality:

Theorem 1.1. Let a₁, a₂, ..., a_n, b₁, b₂, ..., b_n be 2n reals. Assume that ∑_{1 ≤ i < j ≤ n} a_ia_j ≥ 0 or ∑_{1 ≤ i < j ≤ n} b_ib_j ≥ 0. Then,

(∑_{1 ≤ i ≤ n, 1 ≤ j ≤ n, i ≠ j} a_ib_j)² ≥ 4 ∑_{1 ≤ i < j ≤ n} a_ia_j ∑_{1 ≤ i < j ≤ n} b_ib_j.

This result can either be deduced from the Aczel inequality (one of the many variations on Cauchy-Schwarz), or verified more directly by algebraic manipulation. It appeared in the 39th Yugoslav Federal Mathematical Competition 1998 as problem 1 for the 3rd and 4th grades, but in a weaker form (the reals a₁, a₂, ..., a_n, b₁, b₂, ..., b_n were required to be nonnegative, while we only require ∑_{1 ≤ i < j ≤ n} a_ia_j ≥ 0 or ∑_{1 ≤ i < j ≤ n} b_ib_j ≥ 0).

After proving Theorem 1.1, we apply it to establish some inequalities, including an n-variable generalization of Walther Janous'

a / (b + c) · (v + w) + b / (c + a) · (w + u) + c / (a + b) · (u + v) ≥ √(3(vw + wu + uv)) ≥ 3(vw + wu + uv) / (u + v + w).

Let x₁, x₂, ..., x_n be real numbers such that x₁ + x₂ + ... + x_n = 1 and such that x_i < 1 for every i in {1, 2, ..., n}. Prove that

∑_{1 ≤ i < j ≤ n} x_ix_j / ((1 - x_i)(1 - x_j)) ≥ n / (2(n - 1)).

[Note that we do not require x₁, x₂, ..., x_n to be nonnegative — otherwise, the problem would be much easier.]