conjectures

This is a compilation of conjectures and open questions mainly from research articles with updates on their current status. If the information or attributions are not correct please contact me.

Legend: open, settled


  • (2/24/2018) The famous Higman conjecture states that the number k(U_n(F_q)) of conjugacy classes of the group U_n(F_q) of n by n upper triangular matrices over a finite field F_q is a polynomial in q. This conjecture has been verified up to n=16 by Pak and Soffer [1]. Also, Halasi and Pálfy [2] showed that Higman's conjecture fails for other class of groups defined from partially ordered sets. The data for k(U_n(F_q)) gives nonnegative polynomials in T=q-1. Kirilov conjectured that for q=2,3 the sequence {k(U_n(F_q))} is at least the Euler numbers A_n and the Springer numbers S_n. Computations with the data in [1] suggest the following more general conjecture (Kirilov's conjecture is included when T=1, 2):
  • Conjecture: Let T=q-1 and A_n(T) be defined as the coefficients of the following exponential generating function 1/(1-sin(Tx))^(1/T). Then for an infinite family of primes such that k(U_n(F_q)) is a polynomial in q then k(U_n(F_(T+1)) - A_n(T) is a polynomial with nonnegative coefficients.


From papers

A combinatorial model for computing volumes of flow polytopes, with Carolina Benedetti, Rafael S. González D'León, Christopher R. H. Hanusa, Pamela E. Harris, Apoorva Khare, and Martha Yip, 2018, arxiv:1801.07684

    • Conjecture 6.16: The volume of the Caracol flow polytope of size n with netflow (a,b,c,c...,c) is Cat(n-2)*a^(n-2)*(a+(n-1)*b)*(a+b+(n-2)*c)^(n-3)
    • Conjecture 8.7: Product formula for the polynomial E_PS_(n+1)(x) for the Pitman-Stanley graph (see paper for explicit formula). This follows from known facts of lattice points of the Pitman-Stanley polytope (proof will be included in arxiv v.2 o the paper above)
    • Conjecture 8.8: Product formula for the polynomial E_Car_(n+1)(x) for the Caracol graph (see paper for explicit formula).


Rook theory of the finite general linear group, with Joel Brewster Lewis, 2017, arxiv:1707.08192,

    • Conjecture 6.3: Given any board B ⊆ [m] × [n], rank r, and prime power q, the q-hit number Hr(B, q) is nonnegative.
    • Question 6.5: For which permutations w do the q-hit numbers Hi(bar(Iw), q) have positive coefficients?
    • Conjecture 6.8: For the permutation v = (2n−1)(2n)(2n−3)(2n−2)· · · 3412 we have that the number of 2n by 2n invertible matrices over Fq with support in the complement of the inversions of v is in N[q].
    • Conjecture 6.9: For every 123-avoiding permutation w of size n we have that the number of n by n invertible matrices over Fq with support in the complement of the inversions of w is in N[q].


Hook formulas for skew shapes III. Multivariate and product formulas, with Igor Pak and Greta Panova, 2017, arxiv:1707.00931

    • Conjecture 5.17 Theorem (joint with C. Krattenthaler): Let λ = (2a+c) c+a (a+c) a , µ = (a+ 1)a a−11, then the number of standard Young tableaux of shape λ / µ equals a product formula (see paper for formula).
    • Conjecture 9.6: Theorem a product formula for the number standard tableaux of a 4-parameter shifted skew shape Λ(a, c, d, m) (see paper for formula).


Flow polytopes and the space of diagonal harmonics, with Ricky I. Liu and Karola Mészáros, 2016, arxiv:1610.08370, accepted Canadian Journal of Mathematics

    • Conjecture 6.1: Let G be a threshold graph with n + 1 vertices. Then the q,t Ehrhart series of the flow polytope F_G with netflow (n,-1,-1,...,-1) is a q,t positive polynomial. (verified up to n=9)
    • Conjecture 6.3: Let G be a threshold graph with n + 1 vertices. Then the difference of q,t Ehrhart series of the flow polytope F_(K_(n+1))(n,-1,...,-1) and F_G(n,-1,...,-1) is q,t positive. (verified up to n=9)
    • Conjecture 6.4: For threshold graphs G and H with n+1 vertices, H sugraph of G we have that the difference of q,t Ehrhart series of the flow polytope F_G(n,-1,...,-1) and F_H(n,-1,...,-1) is q,t positive. (verified up to n=9)


Asymptotics for the number of standard Young tableaux of skew shape, with Igor Pak and Greta Panova, 2016, arxiv:1610.07561, to appear European Journal of Combinatorics,

    • Section 13.7: For the thick ribbons (2k-1,2k-2,...,1)/(k-1,k-2,...1) the number of SYT of this skew shape equals (n/2)log n + cn + o(n) for some c<0 and n = binomial(2k,2)-binomial(k,2).


Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications, with Igor Pak and Greta Panova, 2016, arxiv:1610.04744, SIAM Journal of Discrete Math (SIDMA), Vol 31 (2017), 1953–1989.

    • Conjecture 7.9. If (θ1, . . . , θk) is a Lascoux–Pragacz decomposition of λ/µ ⊂ d × (n − d), then s_µ (x | y) · s_λ (x | y)^(k-1) = det [ s_λ\ θi#θj (x | y) ] where λ \ θi#θj denotes the partition obtained by removing from λ the outer substrip θi#θj . s_λ (x | y) denotes a factorial Schur function.
    • Conjecture 9.3: Theorem: The number of pleasant diagrams of the shape (n+2k-1,n+2k-2,...,1)/(n-1,n-2,...,1) is given by a certain determinant of Schroder numbers.
      • Proved by Byung-Hak Hwang, Jang Soo Kim, Meesue Yoo, Sun-mi Yun in arxiv:1711.02337
    • Conjecture 9.6: Theorem: determinantal formula for generating function of reverse plane partitions of skew shape (n+2k-1,n+2k-2,...,1)/(n-1,n-2,...,1). Proved independently by


Probabilistic trees with algebraic roots, with Olivier Bernardi, Electronic Journal of Combinatorics, Vol 23, No 2 (2016), arXiv:1501.01135, code

    • Conjecture 21: (see paper for details)


On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope, with Karola Mészáros and Jessica Striker, 2015, arXiv:1510.03357

    • Remark 3.9: If G is a planar directed graph then a result of Postnikov shows that the flow polytope F_G is equivalent to an order polytope. Is the Chan-Robbins-Yuen polytope, the flow polytope of a complete graph Kn, an order polytope? The answer is positive up to n=6.


Combinatorics of diagrams of permutations, with Joel Brewster Lewis, arXiv:1405.1608, Journal of Combinatorial Theory Series A, Vol 137 (2016), 273-306; supplementary code and data

    • Conjecture 4.11: For a permutation w of size n avoiding the patterns 4231, 35142, 42513, and 351624 we have that generating polynomial of pseudo Le and pseudo Gamma diagrams of w equal the Poincare polynomial q^(ell(w)) P_w(1/q). (verified up to n=7)


Structure and enumeration of (3+1)-free posets, with Mathieu Guay-Paquet and Eric Rowland, Annals of Combinatorics, Vol 18, No 4 (2014), 645-674, arXiv:1303.3652, related extended abstract FPSAC France 2013

    • Question 1: The generating functions of the number of 2+2 free posets and of the number of 3+1 free posets are not D-finite. Are they ADE?
    • Question 2: The generating function of the number of 2+2 and 3+1 free posets (counted by the Catalan numbers) is D-finite. What is the classification of the generating functions of the number of a+b free posets and (a+b, c+d) free posets?


Flow polytopes of signed graphs and the Kostant partition function, with Karola Mészáros, 2012, arXiv:1208.0140, International Mathematics Research Notices, No 3 (2015), 830-871.

    • Conjecture 7.12 (a). Theorem: The normalized volume of the type D Chan-Robbins-Yuen polytope of order n equals 2^((n-1)^2)*Cat(1)*...*Cat(n-1). Proved independently by
    • Conjecture 7.12 (b). Theorem: The normalized volume of the type C Chan-Robbins-Yuen polytope of order n equals equals 2^(n(n-1))*Cat(1)*...*Cat(n-1).


Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams, with Aaron J. Klein and Joel Brewster Lewis, Journal of Algebraic Combinatorics, Vol 39, No 2 (2014) 429-456, arxiv:1203.5804

    • Conjecture 5.1. If Rw is the Rothe diagram of a permutation w in Sn and 0 ≤ r ≤ n then the number matq(n, Rw, r)/(q − 1) of n by n rank r matrices with support in the complement of Rw divided by (q-1)^r is a polynomial in q with nonnegative integer coefficients.
      • polynomiality and positivity when w avoids 1324, 24153, 31524, and 426153. Joint work with Joel Lewis, arxiv:1405.1608,
      • polynomiality settled for all permutations, positivity is not true in general (first counterexample at n=r=10). Joint work with Joel Lewis, arxiv:1707.08192.


Matrices with restricted entries and q-analogues of permutations, with Joel Brewster Lewis, Ricky I. Liu, Greta Panova, Steven V Sam, Yan Zhang, Journal of Combinatorics, Vol 2, No 3 (2012) 355-396, arXiv:1011.4539;

    • Question 5.6. Computations suggest that the number of invertible matrices over F_q, divided by (q-1)^n, with:
      • (a) support on a skew shape yields a polynomial in q with nonnegative coefficients.
      • (b) support on complement of a skew shape, the number appears to be a polynomial.
    • Question 5.7. Previous results suggest similarities between the number of invertible matrices over F_q with support in S and support in the complement of S that is reminiscent of the classical reciprocity of rook placements and rook numbers. Does this reciprocity hold in more generality?


From phd thesis

Combinatorics of colored factorizations, flow polytopes, and matrices over finite fields, thesis, MIT 2012

    • Conjecture 2.3.8. There appears to be symmetry of colored factorizations for two or three cycles. Note: examples show there is no such symmetry for four cycles.