Research Article
BibTex RIS Cite

CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS

Year 2021, , 116 - 167, 17.07.2021
https://doi.org/10.24330/ieja.969651

Abstract

The chromatic polynomial is characterized as the unique polynomial invariant of graphs, compatible with two interacting bialgebras structures:
the first coproduct is given by partitions of vertices into two parts, the second one by a contraction-extraction process.
This gives Hopf-algebraic proofs of Rota's result on the signs of coefficients of chromatic polynomials and of Stanley's interpretation
of the values at negative integers of chromatic polynomials. We also consider chromatic symmetric functions and their noncommutative versions.

References

  • E. Abe, Hopf Algebras, Cambridge Tracts in Mathematics, vol. 74, Cambridge University Press, Cambridge-New York, 1980.
  • M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math., 142(1) (2006), 1-30.
  • M. Aguiar and S. Mahajan, Monoidal Functors, Species and Hopf Algebras, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010.
  • N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and coinvariants of the symmetric groups in noncommuting variables, Canad. J. Math., 60(2) (2008), 266-296.
  • G. Birkhoff and D. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc., 60 (1946), 355-451.
  • J.P. Bultel, A. Chouria and J.G. Luque, and O. Mallet, Word symmetric functions and the Redfield-Polya theorem, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math.Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci.,Nancy (2013), 563-574.
  • D. Calaque, K. Ebrahimi-Fard and D. Manchon, Two interacting Hopf algebras of trees: a Hopf-algebraic approach to composition and substitution of B-series, Adv. in Appl. Math., 47(2) (2011), 282-308.
  • A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys., 199(1) (1998), 203-242.
  • A. Connes and D. Kreimer, Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the maintheorem, Comm. Math. Phys., 210(1) (2000), 249-273.
  • L. Foissy, Commutative and non-commutative bialgebras of quasi-posets and applications to Ehrhart polynomials, Adv. Pure Appl. Math., 10(1) (2019), 27-63.
  • D. Gebhard and B. Sagan, A chromatic symmetric function in noncommuting variables, J. Algebraic Combin., 13(3) (2001), 227-255.
  • I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh and J.Y. Thibon, Noncommutative symmetric functions, Adv. Math., 112(2) (1995), 218-348.
  • F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.- Menlo Park, Calif.-London, 1969.
  • M. Hazewinkel, Symmetric functions, noncommutative symmetric functions and quasisymmetric functions. II, Acta Appl. Math., 85(1-3) (2005), 319-340.
  • F. Hivert, J.C. Novelli and J.Y. Thibon, Commutative combinatorial Hopf algebras, J. Algebraic Combin., 28(1) (2008), 65-95.
  • B. Humpert and J. Martin, The incidence Hopf algebra of graphs, SIAM J. Discrete Math., 26(2) (2012), 555-570.
  • C. Kassel, Quantum Groups, Graduate Texts in Mathematics, vol. 155, Springer-Verlag, New York, 1995.
  • C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177(3) (1995), 967-982.
  • D. Manchon, On bialgebras and Hopf algebras or oriented graphs, Confluentes Math., 4(1) (2012), 1240003 (10 pp).
  • D. Manchon, A review on comodule-bialgebras, The Proceedings of the 2016 Abel Symposium "Computation and Combinatorics in Dynamics, Stochastics and Control", Abel Symp., Springer, Cham, 13 (2018), 579-597.
  • J.C. Novelli and J.Y. Thibon, Polynomial realizations of some trialgebras, ,in: Formal Power Series and Algebraic Combinatorics (FPSAC), San Diego, California, 2006.
  • M. Rosas, MacMahon symmetric functions, the partition lattice, and Young subgroups, J. Combin. Theory Ser. A, 96(2) (2001), 326-340.
  • G.C. Rota, On the foundations of combinatorial theory. I. Theory of Mobius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2 (1964), 340-368.
  • W. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra, 96(3) (1994), 299-330.
  • R. Stanley, Acyclic orientations of graphs, Discrete Math., 5 (1973), 171-178.
  • R. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., 111(1) (1995), 166-194.
  • R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999.
  • M. Sweedler, Hopf Algebras. Mathematics Lecture Note Series, W. A. Benjamin, Inc., New York, 1969.
  • P. van der Laan, Operads - Hopf algebras and coloured Koszul duality, Ph.D.- thesis, Universiteit Utrecht, 2004.
Year 2021, , 116 - 167, 17.07.2021
https://doi.org/10.24330/ieja.969651

Abstract

References

  • E. Abe, Hopf Algebras, Cambridge Tracts in Mathematics, vol. 74, Cambridge University Press, Cambridge-New York, 1980.
  • M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math., 142(1) (2006), 1-30.
  • M. Aguiar and S. Mahajan, Monoidal Functors, Species and Hopf Algebras, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010.
  • N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and coinvariants of the symmetric groups in noncommuting variables, Canad. J. Math., 60(2) (2008), 266-296.
  • G. Birkhoff and D. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc., 60 (1946), 355-451.
  • J.P. Bultel, A. Chouria and J.G. Luque, and O. Mallet, Word symmetric functions and the Redfield-Polya theorem, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math.Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci.,Nancy (2013), 563-574.
  • D. Calaque, K. Ebrahimi-Fard and D. Manchon, Two interacting Hopf algebras of trees: a Hopf-algebraic approach to composition and substitution of B-series, Adv. in Appl. Math., 47(2) (2011), 282-308.
  • A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys., 199(1) (1998), 203-242.
  • A. Connes and D. Kreimer, Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the maintheorem, Comm. Math. Phys., 210(1) (2000), 249-273.
  • L. Foissy, Commutative and non-commutative bialgebras of quasi-posets and applications to Ehrhart polynomials, Adv. Pure Appl. Math., 10(1) (2019), 27-63.
  • D. Gebhard and B. Sagan, A chromatic symmetric function in noncommuting variables, J. Algebraic Combin., 13(3) (2001), 227-255.
  • I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh and J.Y. Thibon, Noncommutative symmetric functions, Adv. Math., 112(2) (1995), 218-348.
  • F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.- Menlo Park, Calif.-London, 1969.
  • M. Hazewinkel, Symmetric functions, noncommutative symmetric functions and quasisymmetric functions. II, Acta Appl. Math., 85(1-3) (2005), 319-340.
  • F. Hivert, J.C. Novelli and J.Y. Thibon, Commutative combinatorial Hopf algebras, J. Algebraic Combin., 28(1) (2008), 65-95.
  • B. Humpert and J. Martin, The incidence Hopf algebra of graphs, SIAM J. Discrete Math., 26(2) (2012), 555-570.
  • C. Kassel, Quantum Groups, Graduate Texts in Mathematics, vol. 155, Springer-Verlag, New York, 1995.
  • C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177(3) (1995), 967-982.
  • D. Manchon, On bialgebras and Hopf algebras or oriented graphs, Confluentes Math., 4(1) (2012), 1240003 (10 pp).
  • D. Manchon, A review on comodule-bialgebras, The Proceedings of the 2016 Abel Symposium "Computation and Combinatorics in Dynamics, Stochastics and Control", Abel Symp., Springer, Cham, 13 (2018), 579-597.
  • J.C. Novelli and J.Y. Thibon, Polynomial realizations of some trialgebras, ,in: Formal Power Series and Algebraic Combinatorics (FPSAC), San Diego, California, 2006.
  • M. Rosas, MacMahon symmetric functions, the partition lattice, and Young subgroups, J. Combin. Theory Ser. A, 96(2) (2001), 326-340.
  • G.C. Rota, On the foundations of combinatorial theory. I. Theory of Mobius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2 (1964), 340-368.
  • W. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra, 96(3) (1994), 299-330.
  • R. Stanley, Acyclic orientations of graphs, Discrete Math., 5 (1973), 171-178.
  • R. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., 111(1) (1995), 166-194.
  • R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999.
  • M. Sweedler, Hopf Algebras. Mathematics Lecture Note Series, W. A. Benjamin, Inc., New York, 1969.
  • P. van der Laan, Operads - Hopf algebras and coloured Koszul duality, Ph.D.- thesis, Universiteit Utrecht, 2004.
There are 29 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Articles
Authors

Loic Foıssy This is me

Publication Date July 17, 2021
Published in Issue Year 2021

Cite

APA Foıssy, L. (2021). CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS. International Electronic Journal of Algebra, 30(30), 116-167. https://doi.org/10.24330/ieja.969651
AMA Foıssy L. CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS. IEJA. July 2021;30(30):116-167. doi:10.24330/ieja.969651
Chicago Foıssy, Loic. “CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS”. International Electronic Journal of Algebra 30, no. 30 (July 2021): 116-67. https://doi.org/10.24330/ieja.969651.
EndNote Foıssy L (July 1, 2021) CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS. International Electronic Journal of Algebra 30 30 116–167.
IEEE L. Foıssy, “CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS”, IEJA, vol. 30, no. 30, pp. 116–167, 2021, doi: 10.24330/ieja.969651.
ISNAD Foıssy, Loic. “CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS”. International Electronic Journal of Algebra 30/30 (July 2021), 116-167. https://doi.org/10.24330/ieja.969651.
JAMA Foıssy L. CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS. IEJA. 2021;30:116–167.
MLA Foıssy, Loic. “CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS”. International Electronic Journal of Algebra, vol. 30, no. 30, 2021, pp. 116-67, doi:10.24330/ieja.969651.
Vancouver Foıssy L. CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS. IEJA. 2021;30(30):116-67.