11 ***Chromatic number and polynomials***11.4 Edge-Chromatic number 12 ***Graphs and matrices***

11.5 Read’s conjecture and Matroids

For more details, refer to https://en.wikipedia.org/wiki/Chromatic_polynomial#Properties,
http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln6.htm and
http://matroidunion.org/?p=1301.

Question 11.15 (Read’s conjecture, 1968 ).

Let $P(G,x)=\sum_{i=1}^{n}a_{i}x^{i}$ . Then $|a_{0}|,\ldots,|a_{n}|$ form a log-concave sequence i.e., $|a_{i}|^{2}\geq|a_{i-1}||a_{i+1}|$ .

Verify the conjecture in the cases you can compute the coefficients such as $K_{n},C_{n},P_{n}$ et al.

This was solved recently by June Huh (in his 1st year of Ph.D.) in 2012 using ideas from algebraic geometry.

The crucial DC principle holds for more general combinatorial objects called Matroids (https://en.wikipedia.org/wiki/Matroid) and analogous to a chromatic polynomial, one can define what is called the characteristic polynomial of a matroid . The characteristic polynomial of a matroid is defined via a similar identity as in Theorem 11.6. Read’s conjecture was generalized to characteristic polynomial of matroids and known as Rota-Welsh conjecture . This was proved in 2015 by Karim Adiprasito, June Huh, and Eric Katz. An accessible exposition of these ideas can be found in the blog Matt Baker ([Baker 2015]) and a little more technical account in his survey ([Baker 2018]).

11.5 ***Read’s conjecture and Matroids***

Question 11.15 (Read’s conjecture, 1968 ).

11.5 Read’s conjecture and Matroids