Hodge theory in combinatorics

DOI10.1090/BULL/1599zbMATH Open1376.05046arXiv1705.07960OpenAlexW2963507820MaRDI QIDQ4598015FDOQ4598015

Authors:

Publication date: 19 December 2017

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Abstract: George Birkhoff proved in 1912 that the number of proper colorings of a finite graph G with n colors is a polynomial in n, called the chromatic polynomial of G. Read conjectured in 1968 that for any graph G, the sequence of absolute values of coefficients of the chromatic polynomial is unimodal: it goes up, hits a peak, and then goes down. Read's conjecture was proved by June Huh in a 2012 paper making heavy use of methods from algebraic geometry. Huh's result was subsequently refined and generalized by Huh and Katz, again using substantial doses of algebraic geometry. Both papers in fact establish log-concavity of the coefficients, which is stronger than unimodality. The breakthroughs of Huh and Huh-Katz left open the more general Rota-Welsh conjecture where graphs are generalized to (not necessarily representable) matroids and the chromatic polynomial of a graph is replaced by the characteristic polynomial of a matroid. The Huh and Huh-Katz techniques are not applicable in this level of generality, since there is no underlying algebraic geometry to which to relate the problem. But in 2015 Adiprasito, Huh, and Katz announced a proof of the Rota-Welsh conjecture based on a novel approach motivated by but not making use of any results from algebraic geometry. The authors first prove that the Rota-Welsh conjecture would follow from combinatorial analogues of the Hard Lefschetz Theorem and Hodge-Riemann relations in algebraic geometry. They then implement an elaborate inductive procedure to prove the combinatorial Hard Lefschetz Theorem and Hodge-Riemann relations using purely combinatorial arguments. We will survey these developments.

Full work available at URL: https://arxiv.org/abs/1705.07960

Recommendations

• Hodge theory for combinatorial geometries
• Relations de Hodge--Riemann et combinatoire des matro\"ides (d'apr\`es K. Adiprasito, J. Huh et E. Katz)
• Rota’s Conjecture, the Missing Axiom, and Prime Cycles in Toric Varieties
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• The amazing chromatic polynomial

zbMATH Keywords

chromatic polynomialRead's conjecture

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Singularities in algebraic geometry (14B05) Hodge theory in global analysis (58A14)

Cites Work

• Lectures on Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Hodge theory of Soergel bimodules.
• Chow rings of toric varieties defined by atomic lattices
• Wonderful models of subspace arrangements
• Toric and tropical compactifications of hyperplane complements
• Mixed Lefschetz Theorems and Hodge-Riemann Bilinear Relations
• Combinatorics and topology of complements of hyperplanes
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• Shellable and Cohen-Macaulay Partially Ordered Sets
• Matroid Theory for Algebraic Geometers
• Log-concavity of characteristic polynomials and the Bergman fan of matroids
• The Broken-Circuit Complex
• On simple polytopes
• Hodge theory for combinatorial geometries
• Characteristic polynomials of subspace arrangements and finite fields
• The decomposition theorem, perverse sheaves and the topology of algebraic maps
• The Hard Lefschetz Theorem and the topology of semismall maps
• Log-concavity and strong log-concavity: a review
• The \(f\)-vector of a representable-matroid complex is log-concave
• Title not available (Why is that?)
• Hard Lefschetz theorem for simple polytopes
• Enumeration of points, lines, planes, etc.
• Tropical cycles and Chow polytopes
• A tropical approach to a generalized Hodge conjecture for positive currents
• Hodge Theory of Matroids
• Almost all matroids are nonrepresentable

Cited In (19)

• Relations de Hodge--Riemann et combinatoire des matro\"ides (d'apr\`es K. Adiprasito, J. Huh et E. Katz)
• Patchworking real algebraic hypersurfaces with asymptotically large Betti numbers
• Essence of independence: Hodge theory of matroids since June Huh
• Combinatorial Thom-Hirzebruch characteristic classes
• The Hodge theory of the Hecke category
• A path forward: tropicalization in extremal combinatorics
• Convolution of a symmetric log-concave distribution and a symmetric bimodal distribution can have any number of modes
• Divisors on matroids and their volumes
• Combinatorics and Hodge theory
• Combinatorial geometry takes the lead
• Log-concave Gorenstein sequences
• Top-heavy phenomena for transformations
• Partial symmetries of iterated plethysms
• Unimodal sequences: from Isaac Newton to June Huh
• Harmonic representatives in homology over arbitrary fields
• The works of June Huh
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• Hodge theory for combinatorial geometries
• Divisors on matroids and their volumes

This page was built for publication: Hodge theory in combinatorics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598015)