Insights into Graph Colorings, Chromatic Polynomials, and Conjectures in Discrete Geometry

Slide Note

Delve into the fascinating world of graph colorings, chromatic polynomials, and notable conjectures in discrete geometry. Explore the impact of June Huh in bringing Hodge theory to combinatorics and his proof of various mathematical conjectures. Uncover the significance of the four-color theorem, contraction-deletion relation, and the Read's 1968 conjecture. Witness the transformation of conjectures into theorems and the algebraic revelations in graph theory by distinguished mathematicians.

alexeide Follow

Uploaded on Sep 13, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

The Work of June Huh Gil Kalai Einstein Institute of Mathematics Hebrew University of Jerusalem and Efi Arazi School of Computer Science Reichman University Itai Benjamini

June Huh June Huh the short citation the short citation June Huh is awarded the Fields Medal 2022 for bringing the ideas of Hodge theory to combinatorics, the proof of the Dowling Wilson conjecture for geometric lattices, the proof of the Heron Rota Welsh conjecture for matroids, the development of the theory of Lorentzian polynomials, and the proof of the strong Mason conjecture.

Graph colorings A proper coloring of a graph ? is a coloring of the vertices of ? such that every two adjacent vertices are colored with different colors. The four-color theorem (conjectured by Guthrie 1852, proved by Appel and Haken 1976): Every planar graph can be properly colored with 4 colors.

Chromatic polynomials Let G be a graph ??(?) is the number of proper colorings of ? with ? colors. ??(?) is called the chromatic polynomial of the graph ?. Contraction-deletion relation: ??? + ??/?? = ??\e(?) George Birkhoff (1912), Hassler Whitney, William Tutte, Tutte polynomials, and Tutte-Grothendieck invariants; Stanley (1973): ??( 1) is the number of acyclic orientations of ?

Reads 1968 conjecture Theorem (conjectured by Read 1968, proved by June Huh 2009): Suppose that ??? = ???? ?? 1?? 1+ + 1??0 Then the sequence ?0,?1, ,?? is unimodal.

June Huhs proof In his proof June Huh related the coefficients of the chromatic polynomial to the Milnor numbers of a complex hyperplane arrangement associated with the graph ?. I first heard about Huh s startling proof of the Read conjecture from a 2011 paper by Ji Matou ek who regarded this result, among a few other results, as the beginning of a new algebraic era in discrete geometry. To me, 2010 looks as annus mirabilis, a miraculous year, in several areas of my mathematical interests.

The Heron-Rota-Welsh conjecture (1970) Let ??? = ???? ?? 1?? 1+ + 1??0 be the characteristic polynomial of a matroid M, then the the sequence ?0,?1, ,?? is log- concave: ?? 2 ?? 1??+1 This conjecture is now a theorem: For representable matroids over zero characteristic (Huh 2009) For representable matroids over arbitrary characteristic (Huh and Katz 2010 ) The full conjecture (Adiprasito, Huh and Katz 2015)

What is a matroid? Matroids are abstract mathematical objects that extend the notion of sets of points in vector space. (Hassler Whitney, 1935; Takeo Nakasawa ). Let ? = {?1,?2, ,??} be a set of points in some vector space V over a field F. We can consider The set of linearly independent subsets of X The set of bases of X (a base is a maximal independent set) The set of flats of X (A flat is a subset that is closed under linear combination) The rank function that associates to a subset Y of X the dimension of the vector space spanned by Y. Matroids can be defined by the abstract properties of any of these notions. Matroids also give an abstraction of the notion of graphs. Characteristic polynomials of matroids extend the notion of chromatic polynomials of graphs.

Examples of Matroids Matroid theory is a triumph in the pursuit of both abstraction and concrete simple examples Important examples of matroids. From left to right: The Fano matroid, the V mos matroid, and the non-Pappus matroid. The points of the Fano plane violate the Gallai Sylvester theorem, hence, it is not representable over the reals. As a matter of fact, the Fano matroid is representable over a field if and only the characteristic of is 2. The V mos matroid is not algebraic. Pappus ancient theorem implies that the non-Pappus matroid is not representable over any field. Bernt Lindstr m proved that it is algebraic. Picture credit: Wikipedia and the matroid union blog.

Hodge Theory Homology of algebraic varieties satisfy (PD) Poincar duality (HL) The Hard Lefschetz theorem (HR) Hodge-Riemann relations These three properties are referred to as the standard conjectures. Combinatorial applications of the hard Lefschetz theorem were pioneered by Stanley in 1980 and were later refined and studied by many.

Log concavity for arbitrary characteristics (Huh and Katz) The proof by Huh and Katz for the case of an arbitrary characteristic relied on classical Hodge theory applied to the wonderful compactification defined by Corrado de Concini and Claudio Procesi for complements of hyperplane arrangements.

Homology for varieties that do not exist A starting point in the Adiprasito-Huh-Katz argument: The original definition of De Concini and Procesi of the wonderful compactification applied to realizable matroids, but in 2004 Feichtner and Yuzvinsky defined a commutative ring associated to an arbitrary matroid that specializes to the cohomology ring of a wonderful compactification in the realizable case. Main problem: Prove the standard conjectures for these objects. The proof is a tour de force. The argument is inductive, and AHK showed that the Hodge-Riemann inequality is preserved under a certain operation of flips .

Points and lines Given a set A of n points in d-space that linearly span the space and let ?? be the number of k-dimensional linear subspaces determined by A. Then (1) ?1 ?? 1Motzkin (1951) (2) There is a bijection ? from the set of 1-dimensional spaces to the set of d-1 dimensional spaces that ? ? ?. Greene (1970) The case d=3 simply asserts that (1) A set of n points in the plane not all on the same line determines at least n lines. de Bruijn- Erd s (1948) (2) There is a one-to-one map from every point p to a line containing P.

The Dowling-Wilson conjecture 1975 Theorem (Huh and Wang 2017): Given a set A of n points in d-space that linearly span the space and let ?? be the number of k-dimensional linear subspaces determined by A. Then (1) ?? ?? ? (2) There is a bijection ? from the set of ?-flats of A to the set of (d-k)- flats such that ? ? ?. Theorem (Braden, Huh, Matherne, Proudfoot, and Wang 2020): The same result applies to arbitrary matroids!

The strong (and ultra strong) Mason Conjecture 1972 Let ? be a matroid and let ?? denote the number of independent sets of ? of size ?. The Mason Conjecture ?? 2 1 +1 2 ?? 1 ??+1 The strong Mason Conjecture ?? ??? 1 ??+1 2 1 +1 1 The Ultra Strong Mason conjecture ?? 1 + ? ??? 1 ??+1 ? All these conjectures are now proved for general matroids. Lenz (representable case based in HK); Adiprasito. Huh, Katz (general case) Huh, Schr ter, and Wang; Br nd n and Huh, Anari, Liu, Oveis Gharan, and Vinzant

Applications and connections Remarkable applications of the Adiprasito, Huh, Katz theorem to the theory of algorithms were recently achieved Theorem (Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant 2018 conjectured by Milena Mihail and Umesh Vazirani ~ 1990): The random walk on the graph of matroid bases is rapidly mixing.