Read's conjecture

Last updated

Read's conjecture is a conjecture, first made by Ronald Read, about the unimodality of the coefficients of chromatic polynomials in the context of graph theory. [1] [2] In 1974, S. G. Hoggar tightened this to the conjecture that the coefficients must be strongly log-concave. Hoggar's version of the conjecture is called the Read–Hoggar conjecture. [3] [4]

The Read–Hoggar conjecture had been unresolved for more than 40 years before June Huh proved it in 2009, during his PhD studies, using methods from algebraic geometry. [1] [5] [6] [7]

References

  1. 1 2 Baker, Matthew (January 2018). "Hodge theory in combinatorics". Bulletin of the American Mathematical Society. 55 (1): 57–80. arXiv: 1705.07960 . doi: 10.1090/bull/1599 . ISSN   0273-0979. S2CID   51813455.
  2. ↑ R. C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71. MR0224505 (37:104)
  3. ↑ Hoggar, S. G (1974-06-01). "Chromatic polynomials and logarithmic concavity". Journal of Combinatorial Theory . Series B. 16 (3): 248–254. doi: 10.1016/0095-8956(74)90071-9 . ISSN   0095-8956.
  4. ↑ Huh, June. "Hard Lefschetz theorem and Hodge-Riemann relations for combinatorial geometries" (PDF).
  5. ↑ "He Dropped Out to Become a Poet. Now He's Won a Fields Medal". Quanta Magazine . 5 July 2022. Retrieved 5 July 2022.
  6. ↑ Kalai, Gil (July 2022). "The Work of June Huh" (PDF). Proceedings of the International Congress of Mathematicians 2022: 1–16., pp. 2–4.
  7. ↑ Huh, June (2012). "Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs". Journal of the American Mathematical Society. 25 (3): 907–927. arXiv: 1008.4749 . doi: 10.1090/S0894-0347-2012-00731-0 .


Directed.svg

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.