Questions tagged [algebraic-combinatorics]
The algebraic-combinatorics tag has no usage guidance.
268
questions
64
votes
1
answer
4k
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 ...
- 33.2k
48
votes
4
answers
5k
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\...
- 33.2k
36
votes
1
answer
1k
views
Errata for Fulton's "Young tableaux"
Fulton's Young tableaux is one of the best texts on the subject, one which I
often recommend and cite for reference. Unlike Fulton/Lang and
Fulton/Harris,
it is neither an early-dawn draft nor a ...
34
votes
1
answer
3k
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'...
- 33.2k
29
votes
2
answers
5k
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 ...
- 1,651
29
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 ...
- 2,527
28
votes
3
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 $...
- 16.3k
27
votes
0
answers
878
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 ...
- 271
26
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 ...
- 33.2k
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 ...
- 33.2k
24
votes
0
answers
871
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-...
- 609
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 ...
- 33.2k
21
votes
14
answers
3k
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 ...
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
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\...
- 33.2k
21
votes
1
answer
2k
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)^...
- 1,780
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 ...
- 37.2k
21
votes
1
answer
2k
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, ...
- 33.2k
20
votes
2
answers
899
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 \...
20
votes
0
answers
381
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) ...
- 33.2k
19
votes
1
answer
932
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 $\...
- 33.2k
19
votes
2
answers
560
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, ...
- 33.2k
18
votes
0
answers
376
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_\...
- 27.7k
16
votes
0
answers
452
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 ...
- 2,143
15
votes
2
answers
646
views
Do power sums determine the variables?
In my analysis research, I came across the following problem. Given $n$ positive real numbers $x_1,\dots,x_n$, consider the $n$-many power sums
$$ p_3 = x_1^3 + x_2^3 + \dots + x_n^3 , $$
$$ p_5 = ...
- 153
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 $\...
- 41.8k
15
votes
1
answer
581
views
What is the centralizer of a Young subgroup of $S_n$?
In their celebrated paper "A new approach to the representation theory of the symmetric group. II", Okounkov and Vershik prove that $Z(n-1,1)$, the centralizer of $\mathbb{C}[S_{n-1}]$ in $\...
- 482
15
votes
1
answer
406
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 ...
- 40.9k
15
votes
1
answer
449
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$ ...
- 1,440
15
votes
1
answer
2k
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 ...
- 1,211
15
votes
1
answer
712
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)^{...
- 151
14
votes
2
answers
1k
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)$.
...
14
votes
3
answers
863
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 ...
- 33.2k
14
votes
2
answers
839
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^{...
- 5,594
14
votes
1
answer
385
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 ...
- 8,559
14
votes
1
answer
394
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 ...
13
votes
4
answers
6k
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 ...
- 30k
13
votes
3
answers
613
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 ...
- 380
13
votes
1
answer
630
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
616
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
926
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 (...
- 19.4k
13
votes
0
answers
187
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 ...
- 688
12
votes
1
answer
618
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&...
- 41.8k
12
votes
1
answer
2k
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
750
views
Does this matrix norm inequality have interesting application in other areas of mathematics?
In my new paper, one of the main theorems gives an upper bound for the spectral distance of a general real symmetric matrix to diagonal matrices:
Theorem 3. Let $A=[a_{ij}]$ be a real symmetric ...
- 4,454
12
votes
0
answers
191
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 ...
12
votes
0
answers
703
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_{...
- 2,038
11
votes
2
answers
831
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 ...
- 33.2k
11
votes
1
answer
800
views
Dual of a Specht module
For a partition $\mu$ of $n$, let $S^{\mu}$ be the associated Specht module, defined over $\mathbb{Z}$. For any field $k$, we can tensor $S^{\mu}$ with $k$ to get a representation $S^{\mu}_k$ of the ...
- 113