Ir al contenido

Documat

The Newton polytope and Lorentzian property of chromatic symmetric functions

  • Jacob P. Matherne [1] ; Alejandro H. Morales [2] ; Jesse Selover [2]
    1. [1] North Carolina State University

      North Carolina State University

      Township of Raleigh, Estados Unidos

    2. [2] University of Massachusetts System

      University of Massachusetts System

      City of Boston, Estados Unidos

  • Localización: Selecta Mathematica, New Series, ISSN 1022-1824, Vol. 30, Nº. 3, 2024, págs. 1-35
  • Idioma: inglés
  • DOI: 10.1007/s00029-024-00928-4
  • Enlaces
  • Resumen

    • Chromatic symmetric functions are well-studied symmetric functions in algebraic combinatorics that generalize the chromatic polynomial and are related to Hessenberg varieties and diagonal harmonics. Motivated by the Stanley–Stembridge conjecture, we show that the allowable coloring weights for indifference graphs of Dyck paths are the lattice points of a permutahedronPλ, and we give a formula for the dominant weight λ. Furthermore, we conjecture that such chromatic symmetric functions are Lorentzian, a property introduced by Brändén and Huh as a bridge between discrete convex analysis and concavity properties in combinatorics, and we prove this conjecture for abelian Dyck paths. We extend our results on the Newton polytope to incomparability graphs of (3 + 1)-free posets, and we give a number of conjectures and results stemming from our work, including results on the complexity of computing the coefficients and relations with the ζ map from diagonal harmonics.

  • Referencias bibliográficas
    • Abreu, A., Nigro, A.: Chromatic symmetric functions from the modular law. J. Combin. Theory Ser. A 180, 105407 (2021)
    • Adve, A., Robichaux, C., Yong, A.: An efficient algorithm for deciding vanishing of Schubert polynomial coefficients. Adv. Math. 383, 107669...
    • Adve, A., Robichaux, C., Yong, A.: Computational complexity, Newton polytopes, and Schubert polynomials. Sém. Lothar. Combin. 82B, 52 (2020)
    • Aguiar, M., Bergeron, N., Sottile, F.: Combinatorial Hopf algebras and generalized Dehn–Sommerville relations. Compos. Math. 142(1), 1–30...
    • Alexandersson, P., Sulzgruber, R.: A combinatorial expansion of vertical-strip LLT polynomials in the basis of elementary symmetric functions....
    • Alexandersson, P., Panova, G.: LLT polynomials, chromatic quasisymmetric functions and graphs with cycles. Discrete Math. 341(12), 3453–3482...
    • Anari, N., Liu, K., Gharan, S.O., Vinzant, C.: Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of...
    • Bayer, M., Goeckner, B., Hong, S.J., McAllister, T., Olsen, M., Pinckney, C., Vega, J., Yip, M.: Lattice polytopes from Schur and symmetric...
    • Beck, M., Robins, S.: Computing the continuous discretely. Undergraduate Texts in Mathematics, 2nd edn. Springer, New York (2015)
    • Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Ann. Math. (2) 14(1–4), 42–46 (1912/13)
    • Borcea, J., Brändén, P.: The Lee–Yang and Pólya–Schur programs. I. Linear operators preserving stability. Invent. Math. 177(3), 541–569 (2009)
    • Borcea, J., Brändén, P.: The Lee–Yang and Pólya–Schur programs. II. Theory of stable polynomials and applications. Commun. Pure Appl. Math....
    • Brändén, P., Huh, J.: Lorentzian polynomials. Ann. Math. (2) 192(3), 821–891 (2020)
    • Braun, B.: Unimodality problems in Ehrhart theory, Recent trends in combinatorics. IMA Vol. Math. Appl. 159, 687–711 (2016)
    • Brosnan, P., Chow, T.Y.: Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties. Adv. Math....
    • Carlsson, E., Mellit, A.: A proof of the shuffle conjecture. J. Am. Math. Soc. 31(3), 661–697 (2018)
    • Castillo, F., Cid-Ruiz, Y., Mohammadi, F., Montaño, J.: Double Schubert polynomials do have saturated Newton polytopes. Forum Math. Sigma...
    • Chandler, A., Sazdanovic, R., Stella, S., Yip, M.: On the strength of chromatic symmetric homology for graphs. Adv. Appl. Math. 150, 102559...
    • Chow, T.: Note on the Schur-expansion of XG for indifference graphs G (2015). link
    • Colmenarejo, L., Morales, A.H., Panova, G.: Chromatic symmetric functions of Dyck paths and q-rook theory. Eur. J. Combin. 107, 103595 (2023)
    • Diekert, V., Rozenberg, G.: The Book of Traces. World Scientific Publishing Co. Inc., River Edge (1995)
    • Fang, W.: Bijective proof of a conjecture on unit interval posets. DMTCS 26(2), #2 (2024)
    • Fenn, M., Sommers, E.: A transitivity result for ad-nilpotent ideals in type A. Indagat. Math. 32(6), 1175–1189 (2021)
    • Fink, A., Mészáros, K., St. Dizier, A.: Schubert polynomials as integer point transforms of generalized permutahedra. Adv. Math. 332, 465–475...
    • Foley, A.M., Hoàng, C.T., Merkel, O.D.: Classes of graphs with e-positive chromatic symmetric function. Electron. J. Combin. 26(3), 3.51 (2019)
    • Gasharov, V.: Incomparability graphs of (3+1)-free posets are s-positive. Discrete Math. 157, 211–215 (1996)
    • Gélinas, F., Segovia, A., Thomas, H.: Proof of a conjecture of Matherne, Morales, and Selover on encodings of unit interval orders. arXiv...
    • Gerstenhaber, M.: Dominance over the classical groups. Ann. Math. 2(74), 532–569 (1961)
    • Guay-Paquet, M.: A modular relation for the chromatic symmetric functions of (3 + 1)-free posets. arXiv preprint arXiv:1306.2400 (2013)
    • Guay-Paquet, M., Morales, A.H., Rowland, E.: Structure and enumeration of (3+1)-free posets. Ann. Combin. 18(4), 645–674 (2014)
    • Haglund, J., Ono, K., Wagner, D.G.: Theorems and conjectures involving rook polynomials with only real zeros. Topics in Number Theory (University...
    • Haglund, J., Wilson, A.T.: Macdonald polynomials and chromatic quasisymmetric functions. Electron. J. Combin. 27(3), #P3.37 (2020)
    • Haglund, J.: Further investigations involving rook polynomials with only real zeros. Eur. J. Combin. 21(8), 1017–1037 (2000)
    • Haglund, J.: The q,t-Catalan Numbers and the Space of Diagonal Harmonics, University Lecture Series, vol. 41. American Mathematical Society,...
    • Harada, M., Precup, M.E.: The cohomology of abelian Hessenberg varieties and the Stanley–Stembridge conjecture. Algebr. Combin. 2(6), 1059–1108...
    • Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge Mathematical Library, Cambridge University Press, Cambridge (1988). Reprint...
    • Huh, J.: Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. J. Am. Math. Soc. 25(3), 907–927 (2012)
    • Huh, J., Matherne, J.P., Mészáros, K., St. Dizier, A.: Logarithmic concavity of Schur and related polynomials. Trans. Am. Math. Soc. 375(6),...
    • Mason, J.H.: Matroids: unimodal conjectures and Motzkin’s theorem. In: Proceedings Combinatorics, Proc. Conf. Combinatorial Math., pp. 207–220....
    • Kaplansky, I., Riordan, J.: The problem of the rooks and its applications. Duke Math. J. 13(2), 259–268 (1946)
    • Lewis, J.B., Zhang, Y.X.: Enumeration of graded (3 + 1)-avoiding posets. J. Combin. Theory Ser. A 120(6), 1305–1327 (2013)
    • Macdonald, I.G.: Symmetric functions and Hall polynomials. Oxford Classic Texts in the Physical Sciences, 2nd edn. The Clarendon Press, Oxford...
    • McDonald, L.M., Moffatt, I.: On the Potts model partition function in an external field. J. Stat. Phys. 146(6), 1288–1302 (2012)
    • Monical, C., Tokcan, N., Yong, A.: Newton polytopes in algebraic combinatorics. Selecta Math. (N.S.) 25(5), 66 (2019)
    • Monical, C.: Polynomials in algebraic combinatorics, Ph.D. Thesis (2018), University of Illinois at Urbana-Champaign
    • Murota, K.: Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics....
    • Orellana, R., Scott, G.: Graphs with equal chromatic symmetric functions. Discrete Math. 320, 1–14 (2014)
    • Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 2009(6), 1026–1106 (2009)
    • Rado, R.: An inequality. J. Lond. Math. Soc. 27, 1–6 (1952)
    • Rubey, M., Stump, C., et al.: FindStat—the combinatorial statistics database. http://www.FindStat.org. Accessed 28 Feb 2024
    • Sazdanovic, R., Yip, M.: A categorification of the chromatic symmetric function. J. Combin. Theory, Ser. A 154, 218–246 (2018)
    • Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, Paths, Flows, Matchings, Chapters...
    • Shareshian, J., Wachs, M.L.: Chromatic quasisymmetric functions. Adv. Math. 295, 497–551 (2016)
    • Stanley, R.P.: Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, vol. 49, 2nd edn. Cambridge University Press,...
    • Stanley, R.P.: Enumerative combinatorics. Volume 2, Cambridge Studies in Advanced Mathematics, vol. 62. Cambridge University Press, Cambridge...
    • Stanley, R.P.: Graph colorings and related symmetric functions: ideas and applications: a description of results, interesting applications,...
    • Stanley, R.P.: Symmetric function generalization of the chromatic polynomial of a graph. Adv. Math. 111(1), 166–194 (1995)
    • Stanley, R.P.: Catalan Numbers. Cambridge University Press, New York (2015)
    • Stanley, R.P., Stembridge, J.R.: On immanants of Jacobi–Trudi matrices and permutations with restricted position. J. Combin. Theory Ser. A...
    • The Sage-Combinat community: Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, (2022)
    • Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189–201 (1979)
    • Wagner, D.G.: Multivariate stable polynomials: theory and applications. Bull. Am. Math. Soc. (N.S.) 48(1), 53–84 (2011)
    • White, D.E.: Monotonicity and unimodality of the pattern inventory. Adv. Math. 38(1), 101–108 (1980)
    • Whitney, H.: The coloring of graphs. Ann. Math. (2) 33(4), 688–718 (1932)
    • Zhang, F.: The Schur complement and its applications, Numerical Methods and Algorithms, vol. 4. Springer, New York (2005)
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno