BIMSA >
Research seminar in Discrete Mathematics
Counting homomorphisms in antiferromagnetic graphs via Lorentzian polynomials
Counting homomorphisms in antiferromagnetic graphs via Lorentzian polynomials
组织者
马杰
, 本杰明·苏达科夫
演讲者
Joonkyung Lee
时间
2025年11月18日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
An edge-weighted graph $G$, possibly with loops, is said to be \emph{antiferromagnetic} if it has nonnegative weights and at most one positive eigenvalue, counting multiplicities. The number of graph homomorphisms from a graph $H$ to an antiferromagnetic graph $G$ generalises various important parameters in graph theory, including the number of independent sets and proper vertex-colourings, as well as their relaxations in statistical physics.
We obtain homomorphism inequalities for various graphs $H$ and antiferromagnetic graphs~$G$ of the form
\[
\lvert\operatorname{Hom}(H,G)|^2 \leq \lvert\operatorname{Hom}(H\times K_2,G)|,
\]
where $H\times K_2$ denotes the tensor product of $H$ and $K_2$. Firstly, we show that the inequality holds for any $H$ obtained by blowing up vertices of a bipartite graph into complete graphs and any antiferromagnetic $G$. In particular, one can take $H=K_{d+1}$, which already implies a new result for the Sah--Sawhney--Stoner--Zhao conjecture on the maximum number of $d$-regular graphs in antiferromagnetic graphs. Secondly, the inequality also holds for $G=K_q$ and those $H$ obtained by blowing up vertices of a bipartite graph into complete multipartite graphs, paths or even cycles.
Both results can be seen as the first progress towards Zhao's conjecture on $q$-colourings, which states that the inequality holds for any $H$ and $G=K_q$, after his own work. Our method leverages on the emerging theory of Lorentzian polynomials due to Br\"and\'en and Huh and log-concavity of the list colourings of bipartite graphs, which may be of independent interest.
Joint work with Jaeseong Oh and Jaehyeon Seo.
We obtain homomorphism inequalities for various graphs $H$ and antiferromagnetic graphs~$G$ of the form
\[
\lvert\operatorname{Hom}(H,G)|^2 \leq \lvert\operatorname{Hom}(H\times K_2,G)|,
\]
where $H\times K_2$ denotes the tensor product of $H$ and $K_2$. Firstly, we show that the inequality holds for any $H$ obtained by blowing up vertices of a bipartite graph into complete graphs and any antiferromagnetic $G$. In particular, one can take $H=K_{d+1}$, which already implies a new result for the Sah--Sawhney--Stoner--Zhao conjecture on the maximum number of $d$-regular graphs in antiferromagnetic graphs. Secondly, the inequality also holds for $G=K_q$ and those $H$ obtained by blowing up vertices of a bipartite graph into complete multipartite graphs, paths or even cycles.
Both results can be seen as the first progress towards Zhao's conjecture on $q$-colourings, which states that the inequality holds for any $H$ and $G=K_q$, after his own work. Our method leverages on the emerging theory of Lorentzian polynomials due to Br\"and\'en and Huh and log-concavity of the list colourings of bipartite graphs, which may be of independent interest.
Joint work with Jaeseong Oh and Jaehyeon Seo.
演讲者介绍
Joonkyung Lee is an Assistant Professor of Mathematics at Yonsei University, Seoul, South Korea. He studied mathematics at KAIST and received his PhD from the University of Oxford, under the supervision of David Conlon. Before joining Yonsei, he held postdoctoral positions at the University of Oxford, Universität Hamburg, and University College London, and later served as an Assistant Professor at Hanyang University. His research lies in extremal and probabilistic combinatorics, with a focus on graph homomorphism inequalities and related problems in graph theory