# Questions tagged [algebraic-combinatorics]

The algebraic-combinatorics tag has no usage guidance.

240
questions

**57**

votes

**1**answer

3k views

### How to be rigorous about combinatorial algorithms?

1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...

**41**

votes

**4**answers

4k views

### How to constructively/combinatorially prove Schur-Weyl duality?

How is Schur-Weyl duality (specifically, the fact that the actions of the group ring $\mathbb{K}\left[ S_{n}\right] $ and the monoid ring
$\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\...

**34**

votes

**1**answer

2k views

### Updates to Stanley's 1999 survey of positivity problems in algebraic combinatorics?

[I am a co-moderator of the recently started Open Problems in Algebraic Combinatorics blog and as a result starting doing some searching for existing surveys of open problems in algebraic ...

**31**

votes

**3**answers

2k views

### "Nyldon words": understanding a class of words factorizing the free monoid increasingly

BACKGROUND.
Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner'...

**29**

votes

**2**answers

4k views

### Regular, Gorenstein and Cohen-Macaulay

All the statements below are considered over local rings, so by regular, I mean a regular local ring and so on;
It is well-known that every regular ring is Gorenstein and every Gorenstein ring is ...

**27**

votes

**2**answers

2k views

### Have you seen my matroid?

Let $M(n,k)$ be the matroid on the ground set $\{\pm 1,\ldots,\pm n\}$ for which a set is independent if and only if it contains at most $k$ pairs $\pm i$. Note that the signed permutation group (the ...

**27**

votes

**2**answers

1k views

### Inequality for hook numbers in Young diagrams

Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$, define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $...

**25**

votes

**0**answers

815 views

### A question on simultaneous conjugation of permutations

Given $a,b\in S_n$ such that their commutator has at least $n-4$ fixed points, is there an element $z\in S_n$ such that $a^z=a^{-1}$, and $b^z=b^{-1}$? Here $a^z:=z^{-1}az$.
Magma says that the ...

**24**

votes

**3**answers

1k views

### Is the Ford-Fulkerson algorithm a tropical rational function?

The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...

**24**

votes

**0**answers

836 views

### Nekrasov-Okounkov hook length formula

I am now reading the paper An explicit expansion formula for the powers of the Euler Product in terms of partition hook lengths by Guo-Niu Han. The author rediscovered what he calls the Nekrasov-...

**23**

votes

**6**answers

2k views

### Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...

**22**

votes

**2**answers

1k views

### Why is the catalecticant invariant under coordinate changes?

Let $\mathbf{k}$ be a commutative $\mathbb{Q}$-algebra. (We could play the
same game over any commutative ring $\mathbf{k}$, but this would be a bit more
technical, so let me avoid it.)
Fix a ...

**21**

votes

**2**answers

1k views

### A new combinatorial property for the character table of a finite group?

Let $G$ be a finite group and $\Lambda = (\lambda_{i,j})$ its character table with $\lambda_{i,1}$ the degree of the ith character.
Consider the following combinatorial property of $\Lambda$: for ...

**21**

votes

**1**answer

1k views

### A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...

**20**

votes

**14**answers

2k views

### Applications of Representation Theory in Combinatorics

What are the examples of interesting combinatorial identities (e.g. bijection between two sets of combinatorial objects) that can be proved using representation theory, or has some representation ...

**20**

votes

**1**answer

1k views

### Conjectural identities for Young symmetrizers and Young-Jucys-Murphy elements

The following questions I have found in my own notes from about 3 years ago. Unfortunately, I lost much of the context; I believe I made these conjectures reading Okounkov-Vershik, arXiv:0503040v3, ...

**20**

votes

**0**answers

348 views

### A spin extension of a Coxeter group?

Consider a Coxeter group $W$ with simple generators $S$ and Coxeter matrix $\left( m_{s,t}\right) _{\left( s,t\right) \in S\times S}$.
Let $\mathfrak{M}$ be the set of all pairs $\left(s, t\right) ...

**19**

votes

**1**answer

1k views

### Why are the power symmetric functions sums of hook Schur functions only?

One interesting fact in symmetric function theory is that the power symmetric function $p_n$ can be written as an alternating sum of hook Schur functions $s_{\lambda}$:
$$
p_n = \sum_{k+\ell = n} (-1)^...

**19**

votes

**1**answer

807 views

### Lang's Jacobian identity: slicker, elementary proof?

In Jeffrey Lang, A Jacobian identity in positive characteristic, J. Commut. Algebra, Volume 7, Number 3 (2015), pp. 393--409, the following result is proven:
Theorem 1. Let $p$ be a prime. Let $\...

**18**

votes

**0**answers

336 views

### Deforming a basis of a polynomial ring

The ring $Symm$ of symmetric functions in infinitely many variables is well-known to be a polynomial ring in the elementary symmetric functions, and has a $\mathbb Z$-basis of Schur functions $\{S_\...

**17**

votes

**2**answers

2k views

### Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?

For the notations I am using, I refer to the Appendix at the end of this post.
Here is what, for the sake of this post, I consider to be Reifegerste's theorem:
Theorem 1. Let $n\in\mathbb N$ and $i\...

**16**

votes

**2**answers

436 views

### Eigenvalues and eigenvectors of the matrix with entries $\dbinom{n+1}{2j-i}$ for $i, j = 1, 2, \ldots, n$

Let $n$ be a nonnegative integer, and let $B$ be the $n \times n$-matrix (over the rational numbers) whose $\left(i, j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{ 1, 2, \ldots, ...

**16**

votes

**0**answers

440 views

### A Product Related to Unrestricted Partitions

Start with the product for unrestricted partitions:
$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$
Now replace some of the plus signs with minus signs and expand the product into a series. Is it ...

**15**

votes

**2**answers

576 views

### The finite groups with a zero entry in each column of its character table (except the first one)

$\DeclareMathOperator\PSL{PSL}\DeclareMathOperator\Aut{Aut}$Consider the class of finite groups $G$ having a zero entry in each column of its character table (except the first one), i.e. for all $g \...

**15**

votes

**2**answers

1k views

### hook-length formula: "Fibonaccized" Part I

Consider the Young diagram of a partition $\lambda = (\lambda_1,\ldots,\lambda_k)$. For a square $(i,j) \in \lambda$, define the hook numbers $h_{(i,j)} = \lambda_i + \lambda_j' -i - j +1$ where $\...

**15**

votes

**1**answer

512 views

### a Vandermonde-type of determinants summed over permutations

Let $S_n$ be the symmetric group. Consider
$$D:=\sum_{\sigma\in S_n} \text{sgn}(\sigma)\cdot \det\begin{pmatrix}1 & a_{\sigma(1)}-0 & (a_{\sigma(1)}-0)^2 & \cdots & (a_{\sigma(1)}-0)^{...

**14**

votes

**4**answers

5k views

### When is an algebra of commuting matrices (contained in one) generated by a single matrix?

Let C be an nxn matrix, then the polynomials in C (with appropriate coefficients) form an algebra of commuting matrices. I feel that I should know if the converse is true but I do not. So my first ...

**14**

votes

**3**answers

604 views

### How few $k$-dimensional subspaces of $V$ are enough to have a complement to each $n-k$-dimensional subspace?

Let $n$ and $k$ be nonnegative integers such that $k\leq n$. Let $F$ be a field, and let $V$ be an $n$-dimensional $F$-vector space. A set $\mathcal{S}$ of $k$-dimensional subspaces of $V$ is said to ...

**14**

votes

**2**answers

745 views

### Do you know an elegant proof for this expression for a Schur function?

I know that the identity
$$
s_\mu = \sum_{\mu-\lambda \text{ is a horizontal strip}} \;\sum_{\alpha\vdash|\lambda|} \frac{\chi^\lambda_\alpha}{z_\alpha} \prod_i(p_i-1)^{a_i}
$$
holds.
Here $\alpha=1^{...

**14**

votes

**1**answer

356 views

### What is the smallest cardinality of a self-linked set in a finite cyclic group?

A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$.
For a finite group $G$ denote by $sl(G)$ the smallest ...

**14**

votes

**1**answer

265 views

### Another characterization of matroids

Has anyone seen the following characterization of matroids?
Let $\Delta$ be a simplicial complex on finite ground set $E$. Then $\Delta$ is a matroid complex if and only if, for every $X\subseteq E$ ...

**14**

votes

**1**answer

310 views

### Hilbert series of graded Cohen-Macaulay domains, 28 years later?

I am reading through Richard Stanley's 1990 paper "On the Hilbert Function of a Graded Cohen-Macaulay Domain" to present in a seminar. I am trying to provide a reasonable conclusion for this talk, and ...

**14**

votes

**1**answer

1k views

### Sublattices of Young's Lattice

Young's Lattice is the lattice of inclusions of Young tableaux, or integer partitions.
In R. Stanley's Enumerative Combinatorics Vol. 1, Proposition 1.4.4., there is a generalization of integer ...

**13**

votes

**3**answers

491 views

### Is this sum of cycles invertible in $\mathbb QS_n$?

I am interested the following element of the group algebra $\mathbb{Q}S_n$:
\begin{align}
\phi_n=2e+(1\ 2)+(1\ 2\ 3)+\dotsb+(1\ldots n)
\end{align}
where $e$ is the identity permutation. My question ...

**13**

votes

**2**answers

818 views

### On the finite simple groups with an irreducible complex representation of a given dimension

This answer of Geoff Robinson shows that a finite simple group admits an irreducible complex representation (irrep) of dimension $3$ if and only if it is isomorphic to $A_5$ or $\mathrm{PSL}(2,7)$.
...

**13**

votes

**1**answer

566 views

### The Möbius number of the nonabelian finite simple groups

Let $L$ be a finite lattice with minimum $\hat{0}$ and maximum $\hat{1}$. The Möbius function $\mu$ for $L$ is defined recursively by: for $\forall a,b \in L$ with $a<b$, $\mu(b,b) = 1$ and $\mu(...

**13**

votes

**2**answers

413 views

### On the sum of the subgroup orders of a finite group

Let $G$ be a finite group. Consider the function providing the sum of the subgroups orders
$$\sigma(G) = \sum_{H \le G} |H|.$$
Note that if $C_n$ is cyclic of order $n$ then $\sigma(C_n) = \sigma(n)$, ...

**13**

votes

**1**answer

898 views

### Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds (...

**13**

votes

**0**answers

165 views

### Relationship between crystal root operators and usual $e_i, f_i$?

Suppose I am working in a symmetrizable Kac–Moody Lie algebra $\mathfrak{g}$. Let $e_1,\dotsc,e_n,f_1,\dotsc,f_n$ denote the usual Chevalley generators of $\mathfrak{g}$. Let $V$ be a highest weight ...

**12**

votes

**1**answer

335 views

### Reference request: Heyting algebra structure on Catalan numbers

I've noticed that for every natural number $n\in\mathbb{N}$, there is a finite Heyting algebra with cardinality $C(n)$, where $C(n)$ is the $n$th Catalan number,
$$1,1,2,5,14,42,132,\ldots$$
I'm ...

**12**

votes

**1**answer

595 views

### Determinants: periodic entries $0,1,2,3$

Consider an $n\times n$ matrix $M_n$ where the sequence
$$\{1,2,3,\dots,n^2\} \mod 4=\{1,2,3,0,1,2,3,\dots\}$$ forms a clock-wise spiral, in that given order. For example,
$$M_4=\begin{bmatrix} 1&...

**12**

votes

**1**answer

1k views

### A dual version of a theorem of Øystein Ore in group theory

This post is a dual version for the Generalization of a theorem of Øystein Ore in which it's proved:
Theorem: Let $[H, G]$ be a distributive interval of finite groups. Then $\exists g \in G$ such ...

**12**

votes

**0**answers

185 views

### Non-Boolean Eulerian interval of finite groups

An Eulerian subgroup lattice is Boolean (see here), so it is natural to wonder whether it is also true for an interval of finite groups. The smallest non-Boolean Eulerian lattice is the following:
It ...

**11**

votes

**2**answers

758 views

### How exactly does Schützenberger promotion relate to Striker-Williams promotion?

Schützenberger promotion, studied (for example) in Richard Stanley, Promotion and Evacuation, 2009, is a permutation of the set of all linear extensions of a finite poset. Since one can identify the ...

**11**

votes

**1**answer

586 views

### Detailed modern references for basic properties of Pfaffians over commutative rings

Pfaffians are important to algebraic combinatorics, at least.
This is to propose the making of a 'wiki' list, more modern, precise and compressed than e.g. the relevant Wikipedia page (nothing against ...

**11**

votes

**1**answer

843 views

### Connected graded involutive bialgebras (Hopf algebras) sought (for Dynkin idempotent checking)

Again, there is a general and a concrete question:
Concrete question. Let $H$ be a connected graded bialgebra over a commutative ring $k$ with unity (where graded means $\mathbb N$-graded). Then, it ...

**11**

votes

**0**answers

555 views

### Product of a Schubert polynomial and a double Schubert polynomial

Let $S_u(x)$ be a Schubert polynomial and let $S_v(x;y)$ be a double Schubert polynomial. Then their product can be expressed in terms of the double Schubert polynomials as
$$S_u(x)S_v(x;y)=\sum_w{c_{...

**10**

votes

**2**answers

953 views

### Ubiquitous Zimin words

Let $w$ be a word in letters $x_1,...,x_n$. A value of $w$ is any word of the form $w(u_1,...,u_n)$ where $u_1,...,u_n$ are words. For example, $abaaba$ is a value of $x^2$. A word $u$ is called ...

**10**

votes

**1**answer

330 views

### Generalization of symmetric functions

A $n$-variable function $f$ is a symmetric function if
$$f(x_1,x_2, \ldots, x_n) = f(x_{\sigma(1)}, x_{\sigma(2)}, \ldots, x_{\sigma(n)})$$
for every permutation $\sigma \in S_n$.
In particular, if $f$...

**10**

votes

**1**answer

796 views

### Open problems concerning all the finite groups

What are the open problems concerning all the finite groups?
The references will be appreciated. Here are two examples:
Aschbacher-Guralnick conjecture (AG1984 p.447): the number of conjugacy ...