Questions tagged [algebraic-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
57
votes
1answer
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 ...
42
votes
4answers
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
1answer
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
3answers
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
2answers
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 ...
28
votes
2answers
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
2answers
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
0answers
818 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
3answers
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
0answers
838 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
6answers
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
2answers
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
14answers
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
2answers
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
1answer
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
1answer
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
0answers
351 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
1answer
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
1answer
812 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
0answers
338 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
2answers
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
2answers
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
0answers
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
2answers
582 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
2answers
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
1answer
520 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
4answers
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
3answers
628 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
2answers
750 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
1answer
361 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
1answer
272 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
1answer
314 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
1answer
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
3answers
495 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
2answers
828 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
1answer
572 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
2answers
416 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
1answer
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
0answers
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
1answer
336 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
1answer
601 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
1answer
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
0answers
186 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
2answers
760 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
1answer
596 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
1answer
845 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
0answers
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
2answers
960 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
1answer
341 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
1answer
841 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 ...

1
2 3 4 5