34
$\begingroup$

[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 combinatorics.]

In 1999 R. Stanley wrote a very nice survey on open problems in algebraic combinatorics, with a specific focus on positivity, called "Positivity problems and conjectures in algebraic combinatorics", available online here. It includes 25 specific open problems, as well as a lot of discussion/context.

Question: 20 years later, which problems from Stanley's list have been resolved?

On his website he has a page with updates from 2004, but still, even 2004 was 15 years ago.

$\endgroup$
5

1 Answer 1

37
$\begingroup$

I'm posting a community wiki answer to compile all the known information about the status of all the problems.

Problem 1 (The Generalized Lower Bound Theorem/g-theorem for Gorenstein* complexes): In December 2018, Adiprasito posted a preprint (see also this summary) announcing a proof of the g-theorem for homology spheres that are also homology manifolds, which are the same thing as Gorenstein* complexes.

Problem 2 (The GLBT for toric h-vectors of polytopes/Gorenstein* lattices): Karu established the GLBT for toric h-vectors of arbitrary convex polytopes. It would seem the extension to Gorenstein* lattices remains open though, and is discussed in this paper of Billera and Nevo.

Problems 3 and 3' (Kalai's $3^d$ conjecture for $f$-vectors of centrally symmetric polytopes): It would seem this is still open (see Wikipedia). Some stronger versions of the conjecture were disproved by Sanyal-Werner-Ziegler. The latest discussion I can find is in Freij-Henze-Schmitt-Ziegler.

Problem 4 (The Charney-Davis conjecture on $h$-vectors of flag spheres): This seems wide-open still. In dimensions $\leq 3$ it has been proved by Davis and Okun. The most significant progress for arbitrary dimensions is work of Gal in which he defines the $\gamma$-vector of a flag complex as the "right" analog of the $g$-vector for flag complexes, and conjectures that the $\gamma$-vector of a flag generalized homology sphere is nonnegative. This would in particular imply the Charney-Davis conjecture (which is essentially the statement that a particular coefficient in the $\gamma$-vector is nonnegative). See this nice survey of Zheng.

Problem 5 (A generalization of the decomposition of acyclic complexes to "$k$-fold" acyclic complexes): This conjecture of Stanley was resolved in the negative by Doolittle and Goeckner.

Problem 6 (Are Cohen-Macaulay complexes partitionable?): This conjecture of Stanley and Garsia was resolved in the negative by Duval–Goeckner–Klivans–Martin.

Problem 7 (Positivity of the cd-index of a Gorenstein* poset): This was proved by Karu.

Problem 8 (Positivity of cubical $h$-vectors of Cohen-Macaulay cubical complexes): I believe that this is still open. The one significant result I can find is that Athanasiadis has proved that for a Cohen-Macaulay cubical complex of dimension $d$ (or more generally a Cohen-Macaulay cubical poset) we have $h^{(c)}_{d-1}\geq 0$ (that $h^{(c)}_{d}\geq 0$ is easy).

Problem 9 (Combinatorial interpretation of plethysm coefficients): Still wide-open in general but solved in many special cases. The maximal and minimal constituents of an arbitrary plethysm were found by Paget and Wildon; this article has a survey of the main results known in 2016. Some relations between plethysm coefficients, generalizing results of Brion, Bruns–Conca–Varbaro, Ikenmeyer, and Paget–Wildon, are in this preprint. Foulkes' Conjecture is the special case that $h_m \circ h_n - h_n \circ h_m$ is Schur positive when $m \ge n$: it is known when $m \le 5$ (Cheung–Ikenmeyer–Mkrtchyan) and when $m$ is large compared to $n$ (Brion).

Problem 10 (Combinatorial interpretation of Kroenecker coefficients): Still wide-open in general. But some special cases are known, such as when some of the partitions are hooks or two-rowed shapes (see Blasiak and Liu and its references).

Problem 11 (Combinatorial interpretation of Schubert polynomial structure constants): Still wide-open in general. But some special cases are known, such as some cases of "Schur times Schubert" (see Mészáros–Panova–Postnikov).

Problem 12 (Combinatorial interpretation of row sums of the character table of the symmetric group): Still open in general. Some special cases are discussed by Baker and Early in "Character Polynomials and Row Sums of the Symmetric Group", see here, and Sundaram in "The conjugacy action of $S_n$ and modules induced from centralisers", see here.

Problem 13 (The Macdonald positivity conjecture): This was resolved by Haiman, using advanced machinery from algebraic geometry like the Hilbert scheme of points. A combinatorial interpretation of the $(q,t)$-Kostka polynomials remains elusive in general, but there are some partial results (see e.g. this paper of Assaf).

Problem 14 (LLT polynomials- combinatorial proof of symmetry, and Schur positivity): The Schur positivity of LLT polynomials was proved by Grojnowski and Haiman in an unpublished manuscript from 2006. I imagine a combinatorial proof of the symmetry of these polynomials remains open.

Problem 15 (Positivity of the coefficients of Kazhdan-Lusztig polynomials for arbitrary Coxeter groups): This was resolved by the work of Elias and Williamson on Soergel bimodules.

Problem 16 (Combinatorial interpretation of the coefficients of Kazhdan-Lusztig polynomials for Weyl groups/affine Weyl groups): ???

Problems 17, 17', 18 (Total positivity and Schur positivity of monomial immanants): These are apparently open (for instance, Stanley notes that an affirmative answer to Problem 17 would imply one for Problem 21), but some special cases are addressed in the work of Clearman–Shelton–Skandera.

Problem 19 (Positivity/symmetry/unimodality of monomial characters of Hecke algebra evaluated on Kazhdan-Lusztig basis elements): According to Clearman–Hyatt–Shelton–Skandera, this is still open (or at least was in 2016).

Problems 20 and 20' (The Stanley-Neggers conjecture about real rootedness of poset descent polynomials): Counterexamples to these conjectures were first found by Brändén and Stembridge. (As explained in the survey by Stanley, Problem 20' about chain polynomials is equivalent to Problem 20 and hence also has a negative answer.)

Problem 21 (The Stanley-Stembridge conjecture about e-positivity of chromatic symmetric functions of (3+1)-free posets): This is currently a hot topic, and still open, although many special cases are known as documented here. The most significant advances on the problem are a result of Guay-Paquet which reduces the conjecture to the case of (3+1)- and (2+2)-free posets, i.e., unit interval orders; as well as work of Shareshian and Wachs, Brosnan and Chow, and Guay-Paquet, which connects the conjecture to the cohomology of Hessenberg varieties.

Problems 22 (Gasharov's conjecture about s-positivity of chromatic symmetric functions of claw-free graphs): ???

Problem 23 (Real-rootedness of stable set polynomials of claw-free graphs): This was proved by Chudnovsky and Seymour.

Problem 24 (The Monotone Column Permanent Conjecture): Solved by Brändén–Haglund–Visontai–Wagner using the theory of real stable polynomials.

Problem 25 (Unimodality/log concavity of (a) coefficients of characteristic polynomial of graph/matroid, (b) number of size $i$ independent sets of graph/matroid, (c) rank sizes of a geometric lattice): For graphs, (the absolute value of) the coefficients of the chromatic polynomial were shown to be log-concave by Huh; this was extended to realizable matroids by Huh–Katz; and then to all matroids by Adiprasito–Huh–Katz. The result for the characteristic polynomial actually implies the result for independent sets, as observed by Lenz using a result of Brylawski. The unimodality of the rank sizes of a geometric lattice (i.e., the so-called "Whitney numbers of the second kind") is apparently a harder question and remains open: see section 5.10 of this survey of Baker. But ``half'' of the conjecture has been proved (i.e., that the rank sizes increase up to halfway), in the case of realizable matroids by Huh–Wang, and in the case of arbitrary matroids in this preprint of Braden–Huh–Matherne–Proudfoot–Wang.

$\endgroup$
14
  • 10
    $\begingroup$ I took the liberty of converting all the raw URLs to hyperlinks, which I think makes the text much more readable. $\endgroup$ Dec 31, 2019 at 18:04
  • 10
    $\begingroup$ Problem 23 on the zeros of stable set polynomials of clawfree graphs was solved by Chudnovsky and Seymour at web.math.princeton.edu/~mchudnov/roots.pdf. $\endgroup$ Jan 2, 2020 at 3:41
  • 2
    $\begingroup$ Gorenstein* simplicial complexes are the same as homology spheres that are also homology manifolds, which are discussed in the paper; I just stuck to the more classical notation (which is admittedly more of a mouthful, but also self-explanatory). Here is also a simpler overview over the proof $\endgroup$ Jan 6, 2020 at 15:58
  • 2
    $\begingroup$ Sami Assaf has been working on a combinatorial solution of Problem 13 for some time. Judging from her introduction in arxiv.org/abs/1703.07457 it looks like this has only been established thus far in special cases. (Her earlier claim to combinatorially resolve Problems 13, 14 in arxiv.org/abs/1005.3759 unfortunately had some gaps.) $\endgroup$
    – Terry Tao
    Jan 8, 2020 at 15:45
  • 1
    $\begingroup$ @RichardStanley Yes, that is also the notation I used in the paper, it is better. To summarize, given a field F: Gorenstein* (over F) = A homology manifold that has the homology of a sphere (over F). Thanks $\endgroup$ May 10, 2020 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.