Questions tagged [algebraic-combinatorics]
The algebraic-combinatorics tag has no usage guidance.
45
questions
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\...
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 ...
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 ...
1
vote
0
answers
281
views
On the number of Eulerian orderings
This post is a sequel of Eulerian ordering of the integers modulo n.
Let us recall the definition of an Eulerian ordering:
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$....
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 ...
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\...
20
votes
2
answers
890
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 \...
13
votes
3
answers
608
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 ...
11
votes
1
answer
846
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 ...
8
votes
1
answer
1k
views
A remarkable sum over partitions
While studying some seemingly unrelated topological questions, I have experimentally discovered what appears (to me) to be a remarkable sum over partitions. I was wondering if anyone knows how to ...
5
votes
1
answer
601
views
Eulerian ordering of the integers modulo n
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.
An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\forall i \le n \ \forall j&...
1
vote
0
answers
223
views
Does $[H_i , G_i]$ distributive imply $[H_1 \times H_2, G_1 \times G_2]$ modular?
Let $L(G)$ be the subgroup lattice of $G$ and $[H, G]$ an interval in $L(G)$.
A lattice $(L, \wedge, \vee)$ is distributive if $a∨(b∧c) = (a∨b) ∧ (a∨c)$, $\forall a,b,c \in L $, and is modular if ...
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 ...
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
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)^...
19
votes
2
answers
559
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, ...
15
votes
1
answer
404
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 ...
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 $\...
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 ...
10
votes
3
answers
999
views
Arithmetic product of symmetric functions: why is it integral?
For every commutative ring $A$, let $\mathbf{Symm}_A$ be the ring of symmetric functions over $A$. Let $\mathbf{Symm}$ without a subscript denote $\mathbf{Symm}_{\mathbb{Z}}$.
We can define a ...
10
votes
1
answer
455
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
2
answers
1k
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
294
views
$2$-adic valuation of Schur $P$-functions in the power-sum basis
For a partition $\lambda$, let $P_\lambda$ be the Schur $P$-functions (case $t=-1$ of Hall-Littlewood symmetric functions) and let $p_\lambda=p_{\lambda_1}p_{\lambda_1}\cdots p_{\lambda_k}$ be the ...
9
votes
3
answers
1k
views
bijection between number of partitions of 2n satisfying certain conditions with number of partitions of n
Suppose $\lambda = (\lambda_1,\lambda_2,.....,\lambda_k)$ is a partition of $2n$ where $n \in \mathbb N$ satisfying the following conditions:
(1) $\lambda_{k} = 1$.
(2) $\lambda_{i} - \lambda_{i+1} \...
9
votes
2
answers
501
views
Characterization of the family of simple groups PSL(2,q) by tensor multiplicity
Let $G$ be a finite group and $(\chi_i)$ its irreducible characters. Then $\forall i,j,k, \exists!n_{i,j}^k \in \mathbb{N}_{\ge 0}$ such that $$\chi_i \chi_j = \sum_k n_{i,j}^k \chi_k.$$
Let the ...
9
votes
1
answer
356
views
Smith Normal Form of a Cayley Graph of the Symmetric Group
Let $A_n$ be the adjacency matrix of the Cayley graph $\text{Cay}(S_n,C_n)$ where $C_n \subseteq S_n$ is the conjugacy class of $n$-cycles of the symmetric group $S_n$. Since the generating set of ...
8
votes
1
answer
372
views
Motivation behind Panyushev's "constant-averages-along-orbits" conjecture
In his article "On orbits of antichains of positive roots" (European Journal of Combinatorics 30 (2009) 586–594, Dmitri Panyushev discusses an interesting self-map on the set of antichains of a finite ...
8
votes
3
answers
1k
views
Computing the lexicographic indices of integer partition
If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...
6
votes
1
answer
342
views
Is the "renormalized third comultiplication" on $\mathbf{Symm}$ integral?
Background:
For any commutative ring $R$, let $\mathbf{Symm}_R$ be the ring of symmetric functions in countably many variables $x_1$, $x_2$, $x_3$, ... over $R$. ("Symmetric functions" really means ...
6
votes
1
answer
388
views
hook-length formula: "Fibonaccized": Part II
This is a natural follow-up to my previous MO question, which I share with Brian Hopkins.
Consider the Young diagram of a partition $\lambda = (\lambda_1,\ldots,\lambda_k)$. For a square $(i,j) \in \...
5
votes
1
answer
253
views
Divisibility labeling on a boolean lattice and nonzero Euler totient
Let $B_n$ be the subset lattice of $\{1,2, \dots , n \}$, also called the boolean lattice of rank $n$.
A labeling $f: B_n \to \mathbb{N}_{\ge 1}$ is called acceptable if $\forall a,b \in B_n$:
...
5
votes
0
answers
213
views
Anti-arithmetic product of symmetric functions: (why) is it integral?
This is an analogue of MathOverflow question #138148. Indeed it is so analogous that I wrote the following by copypasting said question and making the necessary changes.
For every commutative ring $A$...
5
votes
1
answer
300
views
What is the smallest rank for a noncommutative fusion ring?
A fusion ring $\mathcal{F}$ (of rank $r$) is given by a finite set $B = \{b_1,b_2, \dots, b_r \}$ such that $b_i b_j = \sum_k n_{i,j}^k b_k$ with $n_{i,j}^k \in \mathbb{Z}_{\ge 0}$, satisfying ...
4
votes
1
answer
141
views
Why does the type-A subdivision algebra look like the Rota-Baxter algebra axiom?
Let $\mathbf{k}$ be a commutative ring, and $\beta$ an element of $\mathbf{k}$. Fix a positive integer $n$, and set $\left[n\right] = \left\{1,2,\ldots,n\right\}$.
The $n$-th type-A subdivision ...
4
votes
2
answers
463
views
About parabolic Kazhdan Lusztig polynomials
There are two types of parabolic Kazhdan Lusztig polynomials, namely, of type -1: $P_{x,w}^{I,-1}$ and of type $q$: $P_{x,w}^{I,q}$. See Kazhdan–Lusztig and R-Polynomials,
Young’s Lattice, and Dyck ...
4
votes
0
answers
245
views
Generalization of a theorem of Øystein Ore in group theory: the infinite case
This post is the infinite version of this one, and is motivated by an exchange with Carmela Musella and Maria De Falco. We are interested in relative versions of the following Ore's theorem and ...
4
votes
1
answer
368
views
Existence of a non-Eulerian atomistic lattice with this property on the Möbius function
Let $L$ be a finite lattice with least element $\hat{0}$, greatest element $\hat{1}$, and Möbius function $\mu$.
Question 1: What class of lattices the following property characterizes? $$\mu(\hat{0},...
3
votes
0
answers
386
views
Software for Combinatorial Algebra sought
I am looking for software which helps me do straightforward tasks in combinatorial algebra. Let me give an example of what I mean by a straightforward task:
I have two graded (generally ...
3
votes
1
answer
257
views
What is the relationship between Partition function and Betti numbers for nilpotent Lie algebras?
Let $p(n)$ denote the number of partitions of a positive integer $n$. It is known that $\{p(n)\}_{n>25}$ is log-concave.
Dietrich Burde said in this MathOF post that property $PF_3$ for partition ...
3
votes
3
answers
422
views
Is there a noncommutative simple fusion ring?
A fusion ring $\mathcal{F}$ is given by a finite set $B = \{b_1,b_2, \dots, b_r \}$ such that $b_i b_j = \sum_k n_{i,j}^k b_k$ with $n_{i,j}^k \in \mathbb{Z}_{\ge 0}$, satisfying axioms slightly ...
2
votes
3
answers
308
views
Constructions of $2-(v,3,3)$-designs
I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...
1
vote
1
answer
304
views
Generating function for $t$-residues of partitions using Heisenberg + $\hat{sl_t}$ representation theory
Recall that for $t\geq2$, a partition is a $t$-core if none of its hooklengths is divisible by $t$. It is known that the $t$-cores are parametrized by ${\mathbb Z}^{t-1}$. More precisely, let $(n_0,\...
1
vote
0
answers
88
views
Flag $f$-vectors of CW-complexes
Hidden away in the appendix of this nice paper by Björner and Kalai, they give a clean description of $f$-vectors that can arise from regular CW-complexes in terms of truncations of the Euler-Poincaré ...
1
vote
0
answers
109
views
Hook-content polynomial 2
Recently I have proven the following identity
\begin{align}
\sum_{\lambda\in \text{different hook of size d}} \frac{1}{d!} (-1)^{ht(\lambda)-1} \, \dim \lambda \, \prod_{\Box \in \lambda} \frac{1}{1-...