# What are the most important open problems in algebraic combinatorics? [closed]

I have seen the paper of Stanley http://math.mit.edu/~rstan/pubs/pubfiles/116.pdf but it is quite old and many of the problems are solved. I would like to know the two or three biggest open problems in algebraic combinatorics.

-

## closed as off-topic by Bill Johnson, Chris Godsil, Felipe Voloch, Vidit Nanda, Ben Webster♦Apr 24 '13 at 3:13

This question does not appear to be about research level mathematics within the scope defined in the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

algebraic combinatorics is a wide subject (Stanley naturally, only treats problems from "his" area) and what really is "biggest" is a very subjective question. –  Dima Pasechnik Apr 22 '13 at 13:30
in any case, this should be made community wiki... –  Suvrit Apr 22 '13 at 17:06
I'll just note, this question is not blatantly offensive; I just accidentally clicked the wrong reason to close. I can unilaterally reopen and recluse if people think the reason listed matters (it doesn't). –  Ben Webster Apr 24 '13 at 3:14

One basic problem is to give a combinatorial formula (or "Littlewood-Richardson rule") for the Schubert structure constants. There is a basis $\{ X_w \}$ of the polynomial ring $\mathbb{Z}[x_1,x_2,\dots]$ in countably many variables that is indexed by $w \in S_{\infty}$, where $S_{\infty}$ is the group of permutations of $\mathbb{N} = \{1,2,\dots\}$ that fix all but finitely many numbers. Given $u, v \in S_{\infty}$, one can expand the product $X_u X_v$ in this basis:

$$X_u X_v = \sum_{w \in S_{\infty}} c_{u,v}^w X_w.$$

A priori, one only knows that $c_{u,v}^w \in \mathbb{Z}$, but it is known for geometric reasons that in fact $c_{u,v}^w \geq 0$ for all $u,v,w \in S_{\infty}$. The problem is to find a positive formula for $c_{u,v}^w$; loosely speaking, the goal is to find a set of objects that is counted by $c_{u,v}^w$.

The problem is intimately tied up with the geometry of the (complete) flag varieties, just as the Littlewood-Richardson rule is connected to the geometry of the Grassmannians.

Also, everything can be formulated for polynomials in finitely many variables indexed by a finite symmetric group $S_n$, but in that case the statement is really about a quotient of a polynomial ring. There is also a generalization to Weyl groups of other types if work with a quotient of a polynomial ring (the Borel presentation of the cohomology of a flag variety).

Edit: I'm pretty sure this problem is mentioned in Stanley, but it is worth emphasizing that it is still open and that there is a lot of beautiful combinatorics related to it. Recently, progress on the two-step flag variety version of the problem was made due to conjectures of Allen Knutson and Ravi Vakil. Izzet Coskun proved A Littlewood-Richardson rule for two-step flag varieties using the notion of Mondrian tableaux. Anders Buch has conjectured a rule for three-step flag varieties.

-

One of the oldest standing open problems in algebraic combinatorics is Foulkes' conjecture; for some history and nice reformulations of the problem, see

On Foulkes' conjecture

by William F. Doran IV in Journal of Pure and Applied Algebra (August 1998), 130 (1), pg. 85-98.

-