Math Graduate Student Seminar

Independent sets and proper colorings are central objects in graph theory. They can be viewed through the lens of graph homomorphisms, which are vertex maps preserving edge relations. The following general question has been studied: fix a host graph G, and vary a graph H within a specified class (e.g., d-regular graphs). Which H minimizes or maximizes the normalized number of homomorphisms from H to G?

We present two results giving an extremal graph in each direction when G is "antiferromagnetic", covering both cases of independent sets and proper colorings. The maximization proof uses Lorentzian polynomials, a log-concavity framework in algebraic combinatorics. The minimization result comes from an AI-assisted search that suggested a proof blueprint, which we then completed and verified in full detail.

Based on joint work with Jaeseong Oh and Joonkyung Lee, and with Joonkyung Lee.