Questions tagged [algebraic-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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\...
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 ...
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 ...
1
vote
0answers
258 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\}$....
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 ...
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 ...
8
votes
1answer
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
1answer
567 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
0answers
220 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
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 ...
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 ...
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)^...
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\...
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 $\...
9
votes
3answers
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} \...
8
votes
1answer
335 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 ...
10
votes
2answers
962 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 ...
9
votes
3answers
893 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 ...
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 ...
9
votes
1answer
316 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 ...
3
votes
0answers
383 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 ...
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 ...
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 ...
6
votes
1answer
326 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
1answer
248 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 ...
5
votes
0answers
209 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$...
4
votes
1answer
125 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
0answers
228 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 ...
2
votes
3answers
284 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 ...
9
votes
2answers
442 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 ...
5
votes
1answer
236 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
1answer
299 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 ...
4
votes
2answers
380 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
1answer
328 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
1answer
189 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 ...
1
vote
0answers
77 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
0answers
101 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-...
1
vote
1answer
241 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,\...