%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{14}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}


% ================================================================

\usepackage{mathtools, tikz}
\usepackage{csquotes}
\usepackage{xparse}

% ------   Miscellaneous -------
% footnotes
% \newcommand{\footremember}[2]{%
%     \footnote{#2}
%     \newcounter{#1}
%     \setcounter{#1}{\value{footnote}}%
% }
% \newcommand{\footrecall}[1]{%
%     \footnotemark[\value{#1}]%
% }

% lists
\setenumerate{label=(\arabic*)}

% else
\newcommand{\Mc}{{\normalfont\rmfamily M}} % \Mc-convexity

\makeatletter
\newcommand{\thanksmark}[1]{%
  \if@marksrequired%
    \newcounter{thanksmark}%
    \setcounter{thanksmark}{#1}%
    \texorpdfstring{$^\text{\fnsymbol{thanksmark}}$}{\fnsymbol{thanksmark}}%
  \fi%
}
\makeatother

% ------   Theorem Styles -------
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}

\theoremstyle{definition}
\newtheorem{example}[thm]{Example}
\newtheorem{definition}[thm]{Definition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{claim}[thm]{Claim}
\newtheorem{question}[thm]{Question}
\newtheorem{problem}[thm]{Problem}

% ------ Math symbols ------
% \mathbb symbols
\newcommand{\RR}{\mathbb{R}}
\newcommand{\NN}{\mathbb{N}}

% bold single characters
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\be}{\mathbf{e}}

% operators
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\supp}{supp} % support
\newcommand{\Hess}{\mathop{}\!\mathcal{H}} % Hessian
\newcommand{\vzN}{\mathop{}\!\mathcal{N}} % vector-ize? Which one is a good name?
\newcommand{\entH}{\mathop{}\!\mathbb{H}} % entropy
\let\Pr\relax
\newcommand{\Pr}{\mathop{}\!\mathbb{P}} % probability
\newcommand{\diff}{\mathop{}\!d} % differential
\newcommand{\one}{\mathbf{1}} % True-False indicator

% delimiters
\DeclarePairedDelimiter{\abs}{|}{|}

% definition equality sign
\newcommand{\defeq}{\coloneqq}
\newcommand{\eqdef}{\eqqcolon}

% others
\newcommand{\HH}{\mathcal{H}}
\newcommand{\blank}{{-}}
\newcommand{\mapsfrom}{\mathrel{\reflectbox{\ensuremath{\mapsto}}}} % reversed \mapsto

% ------ Tikz ------
\tikzset{every loop/.style={}}
\tikzset{inline vertex/.style={draw, circle, fill=black, minimum size=2pt, inner sep=0pt}}

% 1-path with a loop
\newcommand{\indepg}{\!%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \draw[looseness=15] (A) to[out=125, in=55] (A);
        \draw (A) -- (B);
    \end{tikzpicture}%
    \:\!%
}

% 2-edge path
\newcommand{\pathtwo}{%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0.1) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \draw (A) -- (B);
        \draw (A) -- (C);
    \end{tikzpicture}%
    \:\!%
}

% 3-edge path
\newcommand{\paththree}{%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \node (D) at (0,0.2) {};
        \draw (A) -- (B);
        \draw (A) -- (C);
        \draw (C) -- (D);
    \end{tikzpicture}%
    \:\!%
}

% % vertex + edge
% \newcommand{\vtxplusedge}{%
%     \begin{tikzpicture}[nodes=inline vertex]
%         \node (A) at (0,0) {};
%         \node (B) at (0.42,0) {};
%         \node (C) at (0.42,0.2) {};
%         \draw (A) -- (B);
%     \end{tikzpicture}%
%     \:\!%
% }

% two edges
\newcommand{\twoedges}{%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \node (D) at (0,0.2) {};
        \draw (A) -- (B);
        \draw (C) -- (D);
    \end{tikzpicture}%
    \:\!%
}

% triangle + pendant edge
\newcommand{\triangleaddedge}{%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \node (D) at (0,0.2) {};
        \draw (A) -- (B);
        \draw (A) -- (C);
        \draw (B) -- (C);
        \draw (C) -- (D);
    \end{tikzpicture}%
    \:\!%
}

% two loops
\newcommand{\twoloops}{\!%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \draw[looseness=15] (A) to[out=125, in=55] (A);
        \draw[looseness=15] (B) to[out=125, in=55] (B);
    \end{tikzpicture}%
    \!%
}

% loop + vertex
\newcommand{\loopplusvtx}{\!%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \draw[looseness=15] (A) to[out=125, in=55] (A);
    \end{tikzpicture}%
    \:\!%
}

% loop plus edge
\newcommand{\loopplusedge}{\!%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \draw (B) -- (C);
        \draw[looseness=15] (A) to[out=125, in=55] (A);
    \end{tikzpicture}%
    \:\!%
}

% loop plus loooped edge
\newcommand{\loopplusloopededge}{%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \draw (B) -- (C);
        \draw[looseness=15] (A) to[out=125, in=55] (A);
        \draw[looseness=15] (C) to[out=325, in=35] (C);
    \end{tikzpicture}%
}

% 2-edge path with a loop
\newcommand{\loopedpathtwo}{\!%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \draw (A) -- (C);
        \draw (B) -- (C);
        \draw[looseness=15] (A) to[out=125, in=55] (A);
    \end{tikzpicture}%
    \:\!%
}

% 2-edge path with loop -- loop -- nonloop
\newcommand{\twoloopspathtwo}{\!%
    \begin{tikzpicture}[nodes=inline vertex]
        \node (A) at (0,0) {};
        \node (B) at (0.42,0) {};
        \node (C) at (0.42,0.2) {};
        \draw (A) -- (C);
        \draw (B) -- (C);
        \draw[looseness=15] (C) to[out=325, in=35] (C);
        \draw[looseness=15] (A) to[out=125, in=55] (A);
    \end{tikzpicture}%
}

% ================================================================


\newcommand{\JScomment}[1]{{\color{blue!75!black}#1}}



%% define your title in the usual way
\title{Counting homomorphisms in antiferromagnetic graphs via Lorentzian polynomials}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{%
    Joonkyung Lee%
        \thanks{{\href{mailto:joonkyunglee@yonsei.ac.kr}{joonkyunglee@yonsei.ac.kr}, \href{mailto:jaehyeonseo@yonsei.ac.kr}{jaehyeonseo@yonsei.ac.kr}}.
        Supported by Samsung STF Grant SSTF-BA2201-02, the Yonsei University Research Fund 2023-22-0125 and the National Research Foundation of Korea (NRF) grant MSIT NRF-2022R1C1C1010300.}%
        \addressmark{1}%
    , Jaeseong Oh%
        \thanks{\href{mailto:jsoh@kias.re.kr}{jsoh@kias.re.kr}.
        Supported by KIAS Individual Grant (HP083401) and the National Research Foundation of Korea (NRF) grant MSIT NRF-2022R1C1C1010300.}%
        \addressmark{2}%
    , \and Jaehyeon Seo%
        \thanksmark{1}%
        \addressmark{1}%
}{%
    Joonkyung Lee%
        \thanks{{\href{mailto:joonkyunglee@yonsei.ac.kr}{joonkyunglee@yonsei.ac.kr}, \href{mailto:jaehyeonseo@yonsei.ac.kr}{jaehyeonseo@yonsei.ac.kr}}.
        Supported by Samsung STF Grant SSTF-BA2201-02, the Yonsei University Research Fund 2023-22-0125 and the National Research Foundation of Korea (NRF) grant MSIT NRF-2022R1C1C1010300.}%
        %
    , Jaeseong Oh%
        %
        %
    , and Jaehyeon Seo%
        \thanksmark{1}%
        %
}}

%% then use \addressmark to match authors to institutions here
\address{%
    \addressmark{1}Department of Mathematics, Yonsei University, Seoul 03722, Korea.
\\  \addressmark{2}June E Huh Center for Mathematical Challenges, Korea Institute for Advanced Study, Seoul 02455, Korea.%
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{%
    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.
    
    We obtain a number of new homomorphism inequalities for antiferromagnetic target graphs~$G$. In particular, we prove that various graphs $H$ satisfy the inequality
    \[
        |\operatorname{\mathrm{Hom}}(H,G)|^{2} \leq |\operatorname{\mathrm{Hom}}(H\times K_2,G)|
    \]
    for any antiferromagnetic $G$, where $H\times K_{2}$ denotes the tensor product of $H$ and $K_2$. As a corollary, this confirms conjectures of Zhao and of Sah, Sawhney, Stoner and Zhao for complete graphs $K_d$ and adds many more instances.
    Our method uses the emerging theory of Lorentzian polynomials due to Br\"and\'en and Huh, which may be of independent interest.
}

% %% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{graph homomorphism inequalities, Lorentzian polynomials, antiferromagnetic graphs}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
% \usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{references.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


\section{Introduction}
For graphs $G$ and $H$, a \emph{homomorphism} from $H$ to $G$ is a vertex map that preserves adjacency. There are numerous concepts in graph theory that can be rephrased in terms of homomorphisms, which include two fundamental examples: independent sets and proper vertex colourings with $q$ colours, or simply $q$-colourings.
Indeed, there is a natural bijection between independent sets of a graph \( H \) and homomorphisms from \( H \) to \( G = \indepg \). Similarly, each \( q \)-coloring of \( H \) corresponds to a homomorphism from \( H \) to \( G = K_q \), the complete graph on \( q \) vertices.

This correspondence translates extremal problems on the number of independent sets or $q$-colourings to homomorphism inequalities.
For instance, the Kahn--Zhao theorem \cite{kahn2001entropy,zhao2010number} states that the complete bipartite graph $K_{d,d}$ has the maximum number of independent sets amongst $d$-regular graphs. More precisely, if $H$ is $d$-regular, then
\[
    \hom(H,\indepg)^{1/v(H)} \leq \hom(K_{d,d},\indepg)^{1/(2d)},
\]
where $\hom(H,G)=\abs{\Hom(H,G)}$ denotes the number of homomorphisms from $H$ to $G$ and $v(H)$ is the number of vertices in $H$.
There have been a lot of exciting developments along these lines of research for the last decade or two, which touches upon information theory~\cite{friedgut2004hypergraphs} and statistical physics~\cite{davies2017independent}. For a survey on the topic, see \cite{zhao2017extremal}.
Amongst many results, one of the strongest homomorphism inequalities is the `reverse Sidorenko' inequality of Sah, Sawhney, Stoner, and Zhao~\cite{sah2020reverse}.
\begin{thm}[Theorem~1.9~in~\cite{sah2020reverse}]\label{thm:SSSZ}
    Let $H$ be a $d$-regular triangle-free graph and let $G$ be a graph possibly with loops. Then
    \begin{equation}\label{eq:reverseSidorenko}
        \hom(H,G)^{1/v(H)} \leq \hom(K_{d,d},G)^{1/(2d)}.
    \end{equation}
\end{thm}
We remark that the original statement of~\cite[Theorem~1.9]{sah2020reverse} allows distinct degrees in $H$, which generalises~\Cref{thm:SSSZ} to arbitrary triangle-free graphs. On the other hand, the triangle-freeness condition is essential in the sense that, for every $H$ that contains a triangle, there exists $G$ that breaks the inequality~\eqref{eq:reverseSidorenko}. 
In contrast, the Kahn--Zhao theorem requires no condition on $H$ while an extremely specific target graph $G=\indepg$ is chosen.
For another example, when $G=K_q$, \cite[Theorem~1.7]{sah2020reverse} generalises a series of previous results~\cite{davies2018potts,zhao2011bipartite} to give that, for any $d$-regular graph $H$,
\[
    \hom(H,K_q)^{1/v(H)}\leq \hom(K_{d,d},K_q)^{1/(2d)}.
\]
Thus, it is natural to wonder whether an extra condition on $G$ that generalises both \(G=\indepg\) and \(G=K_q\) allows us to obtain an inequality of the form~\eqref{eq:reverseSidorenko} for arbitrary $d$-regular graphs.
Sah, Sawhney, Stoner, and Zhao conjectured that $G$, as a symmetric matrix, having at most one positive eigenvalue may be the correct condition to add on.
\begin{conj}[Conjecture~1.16 in~\cite{sah2020reverse}]\label{conj:SSSZ}
    Let $H$ be a $d$-regular graph and let $G$ be a graph possibly with loops that has at most one positive eigenvalue. Then
    \[
        \hom(H,G)^{1/v(H)} \leq \hom(K_{d,d},G)^{1/(2d)}.
    \]
\end{conj}
In~\cite{sah2020reverse}, the conjecture is confirmed for the particular case of \emph{semiproper colourings}, i.e., complete graphs $G$ possibly with loops, which can be seen as a common generalisation of {\indepg} and $K_q$, albeit weaker than the conjecture itself.

Identifying a graph $G$ by its adjacency matrix naturally generalises to an arbitrary symmetric matrix with nonnegative entries, or equivalently a \emph{weighted graph}, whose edges are weighted by the corresponding entry in the symmetric matrix. Then the homomorphism count $\hom(H,G)$ is also weighted in the sense that
\[
    \hom(H,G) = \sum_{\phi\in\Hom(H,G)}\prod_{uv\in E(H)}G(\phi(u),\phi(v)),
\]
where $G(x,y)$ denotes the corresponding entry of the edge $xy\in E(G)$.
In fact, \Cref{conj:SSSZ} was already stated in terms of weighted graphs $G$  in~\cite{sah2020reverse}.

There is a good reason to consider weighted graphs with at most one positive eigenvalue as a common generalisation of {\indepg} and $K_q$.
In statistical physics, such a weighted graph is called \emph{antiferromagnetic}, a term that originates from the fundamental Ising and Potts models. In what follows, an antiferromagnetic graph always means a weighted one.

Our main result is a homomorphism inequality that compares the number of complete graphs $K_d$ and its `bipartisation' $K_{d,d}\setminus M$, the complete bipartite graph $K_{d,d}$ minus a perfect matching~$M$, in an arbitrary antiferromagnetic graph.
\begin{thm}\label{thm:main}
    Let $G$ be an antiferromagnetic graph. Then
    \begin{equation}\label{eq:main}
     \hom(K_{d},G)^{1/d}\leq \hom(K_{d,d}\setminus M,G)^{1/(2d)}.
    \end{equation}
\end{thm}
As $K_{d,d}\setminus M$ is bipartite, we have \(\hom(K_{d,d}\setminus M,G)^{1/(2d)}\leq \hom(K_{d-1,d-1},G)^{1/(2d-2)}\) by~\Cref{thm:SSSZ}. Combining this with~\eqref{eq:main} then confirms~\Cref{conj:SSSZ} for complete graphs.
Recall that, due to~\Cref{thm:SSSZ}, it is enough to prove~\Cref{conj:SSSZ} for $H$ that contains a triangle. \Cref{thm:main} is the first result that confirms~\Cref{conj:SSSZ} for graphs $H$ that contain a triangle and arbitrary antiferromagnetic graphs $G$. 

The graph $K_{d,d}\setminus M$ can also be seen as a `double cover' $K_d\times K_2$ of $K_d$, where $H\times G$ denotes the tensor product of $H$ and $G$.
In~\cite[Conjecture~2.7]{zhao2011bipartite}, Zhao conjectured that for every $d$-regular graph $H$ and every $q\geq 2$, the inequality
\begin{align}\label{eq:zhao}
    \hom(H,K_q)^2\leq \hom(H\times K_2,K_q)
\end{align}
holds. In fact, \Cref{thm:main} is a consequence of a stronger correlation inequality, which generalises \eqref{eq:zhao} for `clique-blow-ups' of bipartite graphs. We postpone the precise definition of the graph class until~\Cref{sec:AF}.
\begin{thm}\label{thm:main2}
    Let $H$ be a clique-blow-up of a bipartite graph and let $G$ be an antiferromagnetic graph. Then
    \begin{align*}
        \hom(H,G)^2 \leq \hom(H\times K_2,G).
    \end{align*}
    In particular, one can take $H=K_d$ or $H=K_{r+s}\setminus K_{r}$.
\end{thm}
%Thus,~\Cref{thm:main} also confirms the conjectured inequality for $H=K_d$ in a strong form.
%We shall also prove that~\eqref{eq:zhao} holds for a broader class of graphs $H$, which will be described in due course.

Antiferromagnetism also appears in mathematical contexts with different names and their generalisations. For example, antiferromagnetism for an $n$-vertex graph $G$ is equivalent to `hyperbolicity' of its $n\times n$ adjacency matrix $A=A_G$, i.e., $(\bx^T A\bx)(\by^T A\by)\leq (\bx^T A\by)^2$ for all $\bx,\by\in\RR^n$.
As a higher-order generalisation of this, Br\"and\'en and Huh~\cite{branden2020lorentzian} (and independently, Anari et al.~\cite{anari2021logconcave1}) developed the theory of \emph{Lorentzian polynomials}, which applies to settle several  conjectures that relate to log-concavity of combinatorial or geometric sequences. In particular, the theory explains why log-concavity appears in the mixed volumes and mixed discriminants in Euclidean spaces and, as a consequence, recovers the classical Alexandrov--Fenchel inequality~\cite[Section~7.3]{schneider2014convex}.

Our main idea in proving~\Cref{thm:main,thm:main2} is to apply this emerging theory of Lorentzian polynomials. First, we find a new class of Lorentzian polynomials given by homomorphism counts of $K_d$. We then obtain a `discrete' analogue of the Alexandrov--Fenchel inequality as a corollary, which is our key tool.
To the best of our knowledge, this is the first application of the theory of Lorentzian polynomials in extremal combinatorics, although a recent result of Matherne, Morales, and Selover~\cite{matherne2024newton} shows that some chromatic symmetric functions are Lorentzian.

This proceeding is organised as follows. In~\Cref{sec:prelim}, some standard results on graph homomorphisms and the theory of Lorentzian polynomials are introduced.
In~\Cref{sec:G_chromatic}, we obtain a new family of Lorentzian polynomials that come from homomorphism counts of $K_t$.
As a consequence, our main results,~\Cref{thm:main,thm:main2}, follow in the subsequent section. 
%In~\Cref{sec:mms}, connections to the problems in \cite{matherne2024newton} that concern with Lorentzian property of chromatic symmetric functions will be discussed.
For the expository purpose, some proofs are written in a simplified form that requires extra assumptions.


\section{Preliminaries}\label{sec:prelim}
In what follows, \(n\), \(q\), and \(t\) are positive integers.
Write \(\NN_0\defeq \{0,1,2,\dots\}\) for the set of nonnegative integers and let \([n]\defeq \{1,2,\dots,n\}\).
For a finite set \(I\), let \(\binom{I}{r}\) be the collection of its subsets of size $r$.

\medskip

\noindent\textbf{Graphs.}
A \emph{graph} has no parallel edges but may have loops with nonempty edge set. We use $v(G)$ and $e(G)$ for the number of vertices and edges of a graph $G$, respectively.
A \emph{weighted graph} \(G\) is a graph with positive edge weights on edges and zero weights on non-edges. 
We write \(G(u,v)\) for the corresponding weight on $uv$ by identifying $G$ as its adjacency matrix with corresponding weights. 
A graph without specified edge weights corresponds to a canonical \(\{0,1\}\)-weight.
The \emph{support} of a weighted graph $G$, denoted by \(\supp (G)\), is the graph \(G'\) where \(V(G')\defeq V(G)\) and \(uv\in E(G')\) if and only if \(G(u,v)>0\).
Let \(N_G(v)\) be the set of neighbours of the vertex \(v\) in \(G\).
% For \(U,W\subseteq V(G)\), write \(G[U]\) for the subgraph of \(G\) induced on \(U\) and let $G[U,W]$ be the \emph{bi-induced} graph on $U\cup W$ with edges of the form $e=uv\in E(G)$ with $u\in U$ and $v\in V$. 

To recall, a weighted graph is \emph{antiferromagnetic} if it has at most one positive eigenvalue, counting multiplicities. Recall also that an antiferromagnetic graph always refers to a weighted graph.
We say that a symmetric matrix with nonnegative entries is antiferromagnetic if the corresponding weighted graph is antiferromagnetic.
By the Cauchy interlacing theorem, 
vertex deletions, i.e., principal minors, preserve antiferromagnetism.
\begin{proposition}\label{prop:induced}
    An induced subgraph of an antiferromagnetic graph is also antiferromagnetic.
\end{proposition}

%Let \(H\) be a graph. A \emph{homomorphism} from \(H\) to \(G\) is a map \(\phi\colon V(H)\to V(G)\) which preserves the edges, i.e., \(\phi(u)\phi(v)\in E(G)\) for all \(uv\in E(H)\). Let \(\Hom(H,G)\) be the set of the homomorphisms from \(H\) to \(G\), and \(\hom(H,G)\) its size.

\medskip

\noindent\textbf{Discrete mixed volume.}
% The number of proper colourings of \(H\) with \(n\) colours is given by the chromatic polynomial \(\chi_H(n)\). 
If a graph $H$ is $q$-colourable, then the \emph{$q$-chromatic symmetric polynomial}, due to Stanley~\cite{stanley1995symmetric}, is defined by
\[
    X_H(\bx)\defeq \sum_{\phi\in\Hom(H,K_q)}
    \prod_{v\in V(H)} x_{\phi(v)}.
\]
We generalise this definition by replacing $K_q$ by an arbitrary weighted graph. Let \(G\) be an $n$-vertex weighted graph on the vertex set \([n]\) and let \(\bx = (x_1,\dots,x_n)\) be an \(n\)-tuple of variables. A \emph{\(G\)-chromatic function of \(H\)} is an $n$-variable homogeneous polynomial
\[
    h_H(\bx;G) = h_H(x_1,\dots,x_n;G) \defeq \sum_{\phi\colon V(H)\to V(G)} \prod_{uv\in E(H)} G(\phi(u),\phi(v)) \prod_{v\in V(H)} x_{\phi(v)},
\]
which has degree $v(H)$.
Note that the coefficient $\prod_{uv\in E(H)} G(\phi(u),\phi(v))$ is nonzero if and only if $\phi$ is a homomorphism from $H$ to the support of $G$.
In particular, the \(K_q\)-chromatic function of $H$ is the $q$-chromatic symmetric polynomial of $H$. We however remark that \(h_H(\bx;G)\) is \emph{not} symmetric in general.
Indeed, $h_H(x_{\sigma(1)},\dots,x_{\sigma(n)};G) = h_H(x_1,\dots,x_n;G)$ holds for an automorphism $\sigma$ of $\supp(G)$ that preserves edge weights, but this may \emph{not} be true for an arbitrary permutation \(\sigma\) on \([n]\).

The \emph{$G$-volume} of $H$ is a multilinear generalisation of the $G$-chromatic function.
Let \(V(H) = [t]\) and let \(\bx_i=(x_{i,1},\dots,x_{i,n})\), \(i=1,2,\dots,t\) be \(n\)-tuples of variables. The \(G\)-volume of \(H\) is a $t$-variable real function on $(\RR^n)^t$ defined by
\[
    V_H(\bx_1,\bx_{2},\dots,\bx_t;G) \defeq \sum_{\phi\colon V(H)\to V(G)} \prod_{uv\in E(H)} G(\phi(u),\phi(v)) \prod_{u\in V(H)} x_{u,\phi(u)}.
\]
In particular, $V_H(\bx,\bx,\dots,\bx;G)=h_H(\bx;G)$. If each $\bx_{i}$ is the indicator vector for a vertex subset $U_i\subseteq V(G)$, then $V_H(\bx_{1}, \dots,\bx_{t};G)$ counts all the homomorphisms $\phi$ that embed the vertex $i\in V(H)$ into $U_i$.
Although the $G$-volume is not symmetric in general, we are mostly interested in properties of the $G$-volume of $K_t$, which is a symmetric function.

Resembling the definition of mixed volume in Euclidean geometry, 
the identity 
\[
    h_H(\lambda_1\bx_1+\dots+\lambda_r\bx_r; G) = \sum_{(i_1,\dots,i_t)\in [r]^t} V_H(\bx_{i_1},\dots,\bx_{i_t}) \lambda_{i_1}\dotsm \lambda_{i_t}
\]
holds for \(\bx_1,\dots,\bx_r\in \RR^n\) and \(\lambda_1,\dots,\lambda_r \in\RR\).
By regarding \(\lambda_1,\dots,\lambda_r\) as variables, we see
\[
    \sum_{\sigma\in S_t} V_H(\bx_{\sigma(1)},\dots,\bx_{\sigma(t)};G) = \partial_{\lambda_1}\dotsm \partial_{\lambda_t} h_H(\lambda_1\bx_1 +\dots+ \lambda_t\bx_t; G),
\]
where \(S_t\) is the symmetric group on \([t]\). In particular, as \(V_{K_t}(\bx_1,\dots,\bx_t;G)\) is symmetric,
\begin{align}\label{eq:G-volume-Kt-pdiff-form}
    V_{K_t}(\bx_1,\dots,\bx_t;G) = \frac{1}{t!} \partial_{\lambda_1}\dotsm \partial_{\lambda_t} h_{K_t}(\lambda_1\bx_1 +\dots+ \lambda_t\bx_t; G).
\end{align}

\medskip

\noindent\textbf{Lorentzian polynomials.}
Let \(f\) be a polynomial on \(n\) variables \(x_1,\dots,x_n\). The Hessian \(\Hess f\) of $f$ is the \(n\times n\) matrix where \((\Hess f)_{i,j} = \partial_i \partial_j f\) for \(1\le i,j\le n\). The \emph{support} \(\supp f\) of \(f\) is the set of tuples \((a_1,\dots,a_n)\in \NN_0^n\) such that \(x_1^{a_1}\dotsm x_n^{a_n}\) has a nonzero coefficient in \(f\).

Following Br\"{a}nd\'{e}n and Huh~\cite{branden2020lorentzian}, Lorentzian polynomials $f$ are defined recursively by using partial derivatives $\partial_i f$ and a combinatorial property of the support of $f$, the so-called \emph{\Mc-convexity}.
A set of vectors \(S\subseteq \NN_0^n\) is \emph{\Mc-convex} if the following \emph{exchange property} holds: for any vectors \(\ba=(a_1,\dots,a_n)\) and \(\bb=(b_1,\dots,b_n)\) in \(S\), whenever \(a_i>b_i\) for some \(i\in [n]\), there is \(j\in [n]\) such that \(a_j<b_j\) and \(\ba-\be_i+\be_j\in S\). Here \(\be_i\) and \(\be_j\) are the \(i\)-th and \(j\)-th standard unit vectors in \(\NN_0^n\), respectively.
%Using the bijection  \(\vzN((i,j))\defeq \be_i+\be_j\) \(\vzN\colon [n]^2\to \{\be_i+\be_j : i,j\in [n]\}\) defined by. Then \(E\subseteq [n]^2\) is a basis of a rank-\(2\) discrete polymatroid on \([n]\) if and only if \(\vzN(E)\) is \Mc-convex. 
Roughly speaking, \Mc-convexity of $S$ defines a base of a discrete polymatroid, a multiset analogue of a matroid. We refer the reader to~\cite{herzog2002discrete} for further discussions about polymatroids.

Although there is no harm in saying that all homogeneous linear polynomials with nonnegative coefficients are Lorentzian, it only causes extra technicalities to carry on. Thus, we restrict ourselves onto those homogeneous polynomials of degree at least two. 

A homogeneous polynomial $f$ with nonnegative coefficients of degree $d\geq 2$ is said to be \emph{Lorentzian} if: 
\begin{enumerate}
    \item for $d=2$, the Hessian $\Hess f$ is antiferromagnetic;
    \item for $d>2$, each partial derivative $\partial_i f$ is Lorentzian and $\supp f$ is \Mc-convex.
\end{enumerate}

%\begin{definition}
%    For \(d\ge1\), let \(P_d\) be the set of homogeneous polynomials of degree \(d\) with nonnegative coefficients. For a polynomial in some \(P_d\), the property of being \emph{Lorentzian} is defined recursively as follows.
%    \begin{enumerate}
%        \item Every polynomial in \(P_1\) is Lorentzian.
%        \item \(f\in P_2\) is Lorentzian if \(\supp f\) is \(M\)-convex and \(\Hess f\) is antiferromagnetic.
%        \item \(f(x_1,\dots,x_n)\in P_d\) with \(d\ge3\) is Lorentzian if \(\supp f\) is \Mc-convex and \(\partial_i f\) is Lorentzian for all \(1\le i\le n\).
%\end{enumerate}
%\end{definition}

We remark that, while not stated explicitly above, a quadratic Lorentzian polynomial \(f\) also has \Mc-convex support. In other words, \(\supp (f)\) is \Mc-convex if \(\Hess f\) is antiferromagnetic. We refer to~\cite[Theorem~5.3]{choe2004homogeneous} and \cite[Theorem~3.2]{branden2007polynomials} for the proof.

An \(n\)-vertex weighted graph or its adjacency matrix, denoted by \(G\), naturally corresponds to the quadratic $n$-variable polynomial \(Q_G(\bx) \defeq \frac{1}{2} \bx^T G \bx\),
whose Hessian is exactly $G$.
%Writing \(V(G)=[n]\) for \(n=v(G)\), note \(\vzN(E(G)) = \supp(Q_G)\): this is because \(\be_i+\be_j\in \vzN(E(G))\) if and only if \((i,j)\in E(G)\), and the coefficient of \(x_ix_j\) in \(Q_G(\bx)\) is \(G(i,j)\). 
Then \(G\) is antiferromagnetic if and only if \(Q_G\) is Lorentzian. 
Let $G'=\supp(G)$ for an antiferromagnetic graph $G$. Then \(\supp(Q_{G'}) = \supp(Q_G)\) is \Mc-convex, so \(Q_{G'}\) is Lorentzian by \cite[Lemma~3.11]{branden2020lorentzian}, whence \(G'\) is also antiferromagnetic.
%Moreover, if \(G\) is an unweighted graph, \cite[Lemma~3.11]{branden2020lorentzian} states that \(Q_G\) is Lorentzian if and only if \(\supp(Q_G)\) is \Mc-convex.
%More equivalent conditions would be presented in~\Cref{thm:AFM-gph-equiv} when \(G\) is unweighted.

% \begin{proposition}\label{prop:AFM-gph-supp}
%     If a weighted graph is antiferromagnetic, then so is its support.
% \end{proposition}
%\begin{proof}
%    Let \(G\) be an antiferromagnetic graph and let \(G'\) be its support. Then \(Q_G\) is Lorentzian by~\Cref{prop:quad-poly-Lor-AFM}, so \(\supp(Q_G)\) is \Mc-convex. Thus, \(\supp(Q_{G'}) = \vzN(E(G')) = \vzN(E(G)) = \supp(Q_G)\) is \Mc-convex, whence \cite[Lemma~3.11]{branden2020lorentzian} gives that \(Q_{G'}\) is Lorentzian. Therefore \(G'\) is antiferromagnetic.
%\end{proof}

%To examine whether the $G$-chromatic function $h_H(\bx;G)$ is Lorentzian or not, it is convenient to collect some operations on $G$ that preserve the Lorentzian property.
%We start by examining how operations on a weighted graph \(G\) affect a \(G\)-chromatic function.

Let \(V(G)=\{v_1,\dots,v_n\}\) and integers \(r_1,\dots,r_n\ge1\) be given. A \emph{blow-up} of \(G\) is a weighted graph \(G'\) on the vertex set \(\{v_{i}^{(j)}:i\in [n],\, j\in [r_i]\}\) with the edge weights \(G'(v_i^{(j)},v_k^{(\ell)}) \defeq G(v_i,v_k)\) for \(i,k\in [n]\), \(j\in [r_i]\), and \(\ell\in [r_k]\). Here, the vertices \(v_i^{(1)},\dots,v_i^{(r_i)}\) can be seen as `clones' of \(v_i\). If $v_i$ is a looped vertex, its clones \(v_i^{(1)},\dots,v_i^{(r_i)}\) form a complete graph $K_{r_i}$ plus $r_i$ loops. In contrast, clones of a non-looped vertex form an independent set. 
The following lemma, which generalises~\Cref{prop:induced}, states that a nonnegative linear change of variables preserves the Lorentzian property. 
It is a direct consequence of \cite[Theorem~2.10]{branden2020lorentzian} and its proof therein, so we omit the proof.

\begin{lem}\label{lem:G-vol-Lor-preserved-by-G-blowup-indsubgp}
    Let \(G'\) be a blow-up or an induced subgraph of \(G\). Then the following holds:
    \begin{enumerate}
        \item if \(h_H(\blank;G)\) has \Mc-convex support, then so does \(h_H(\blank;G')\);
        \item if \(h_H(\blank;G)\) is Lorentzian, then so is \(h_H(\blank;G')\).
    \end{enumerate}
\end{lem}
%\begin{proof}
%    Write \(V(G)=\{v_1,\dots,v_n\}\). For each \(i\), let \(v_i^{(1)},\dots,v_i^{(r_i)}\) be the copies of \(v_i\) in \(G'\), where \(r_i\ge0\) is an integer. The case \(r_i=0\) corresponds to removing \(v_i\). For \(i\in [n]\) and \(j\in [r_i]\), let \(x_i^{(j)}\) be the variable which corresponds to \(v_i^{(j)}\). Then,
 %   \[
 %       h_H\bigl( (x_i^{(j)} : i\in [n], j\in [r_i]) ;G' \bigr)
 %       = h_H\Biggl( \sum_{j=1}^{r_1} x_1^{(j)}, \dots, \sum_{j=1}^{r_n} x_n^{(j)} ; G \Biggr).
  %  \]
  %  Now the statement follows from \cite[Theorem~2.10]{branden2020lorentzian}, which says any nonnegative linear change of variables preserves the property of being Lorentzian.
%\end{proof}


\section{Lorentzian \texorpdfstring{$G$}{G}-chromatic functions}\label{sec:G_chromatic}

Our first step in proving~\Cref{thm:main} is to show that $h_{K_t}(\bx;G)$ is Lorentzian whenever $G$ is antiferromagnetic.
\begin{thm}\label{thm:AFM-hom-Lor}
    Let \(G\) be an antiferromagnetic graph and let \(t\ge2\). Then \(h_{K_t}(\bx;G)\) is Lorentzian.
\end{thm}

By the recursive definition of Lorentzian polynomials, there are two facts to check: first, $\partial_i h_{K_t}(\bx;G)$ is Lorentzian for every $i=1,\dots,n$, where $n=v(G)$; second, the support of $h_{K_t}(\bx;G)$ is \Mc-convex.
The first is rather straightforward to verify. For the expository purpose, we prove~\Cref{thm:AFM-hom-Lor} for the particular case when $G$ is unweighted and loopless.

We use induction on \(t\), where the base case follows from \(h_{K_2}(\bx;G) = Q_G(\bx)\).
Let \(V(K_t)=\{w_1,\dots, w_t\}\) and fix \(\nu\in V(G)=[n]\).
Let $g_\nu$ be the polynomial obtained by summing all the monomials of $h_{K_t}(\bx;G)$ that contain $x_\nu$.
Since \(\nu\in V(G)\) is not looped, the pre-image $\phi^{-1}(\nu)$ of $\nu$ for a homomorphism $\phi\in \Hom(K_t,G)$ has size at most one. Thus, $g_\nu(\bx)=x_\nu \cdot \partial_\nu h_{K_{t}}(\bx;G)$. 
On the other hand,
\[
    g_\nu(\bx)
    = \sum_{i=1}^{t}
        \sum_{\substack{\phi\in\Hom(K_t,G)\\ \phi(w_i)=\nu}}
        \prod_{j=1}^t x_{\phi(w_j)}
    = x_\nu \sum_{i=1}^{t}
        \sum_{\substack{\phi\in\Hom(K_t,G)\\ \phi(w_i)=\nu}}
        \prod_{j\in [t]\setminus \{i\}} x_{\phi(w_j)}.
\]
Once we embed the vertex $w_i$ into $\nu$, the other vertices in \(V(K_t)\setminus \{w_i\}\) must map to vertices in $N_G(\nu)$ so that the $t-1$ vertices induce a copy of $K_{t-1}$ in $G[N_G(\nu)]$. That is,
with the tuple of variables $\by^{(\nu)}\defeq (x_i:i\in N_G(\nu))$,
\[
    \sum_{\substack{\phi\in\Hom(K_t,G)\\ \phi(w_i)=\nu}}
        \prod_{j\in [t]\setminus \{i\}} x_{\phi(w_j)}
    = h_{K_{t-1}}(\by^{(\nu)};G[N_G(\nu)]).
\]
Here $G[N_G(\nu)]$ is antiferromagnetic too by~\Cref{prop:induced} and thus, by the induction hypothesis, $\partial_\nu h_{K_t}(\bx;G) = t\cdot h_{K_{t-1}}(\by^{(\nu)};G[N_G(\nu)])$ is Lorentzian.

\medskip

To prove that $\supp(h_{K_t}(\bx;G))$ is \Mc-convex, we provide a structural characterisation of antiferromagnetic graphs $G$. 
%Let \(V(G)=[n]\) and write \(\bx=(x_1,\dots,x_n)\). That \(h_{K_t}(\bx;G)\) is \Mc-convex follows from the structure of \(\supp G\) in~\Cref{thm:AFM-gph-equiv}, which we omit the detail. 
%We use induction on \(t\) to show \(\partial_i h_{K_t}(\bx;G)\) is Lorentzian for all \(i\in [n]\), which does not rely on the structure of \(\supp G\) but on the symmetry of \(K_t\). Here we provide the proof when \(G\) is unweighted and loopless. 
%If \(G\) is weighted and allows loops, then \(G(\blank,\blank)\) is not simply the edge indicator, and possibly \(x_\nu\in \by^{(\nu)}\). By slightly generalising the above argument to overcome these issues, we get the following theorem.
Let \(K_q^{\circ}\) denote the complete graph on \(q\) vertices with exactly one vertex looped; recall that this corresponds to a semiproper colouring.

\begin{thm}\label{thm:AFM-gph-equiv}
    Let $G$ be a (unweighted) graph without isolated vertices. Then the following are equivalent:
    \begin{enumerate}
        \item\label{cond:(thm:AFM-gph-equiv)-G-AFM} \(G\) is antiferromagnetic;
        \item\label{cond:(thm:AFM-gph-equiv)-PG-Lor} \(Q_G\) is Lorentzian;
        \item\label{cond:(thm:AFM-gph-equiv)-E(G)-Mconv} \(\supp(Q_G)\) is \Mc-convex;
        \item\label{cond:(thm:AFM-gph-equiv)-G-str} there exist disjoint vertex sets \(V_1\) and \(V_2\) such that $V_1\cup V_2=V(G)$, $V_1$ induces a complete multipartite graph, and $V_2$ consists of looped vertices that connect to all the vertices in $G$.

        That is, \(G\) is obtained by blowing up \(K_q^\circ\) and taking its connected induced subgraph.
    \end{enumerate}
\end{thm}

\begin{proof}%[Proof of \Cref{thm:AFM-gph-equiv}]
    It was already mentioned in~\Cref{sec:prelim} that 
    \ref{cond:(thm:AFM-gph-equiv)-G-AFM},
    \ref{cond:(thm:AFM-gph-equiv)-PG-Lor},
    and \ref{cond:(thm:AFM-gph-equiv)-E(G)-Mconv} are equivalent by \cite[Lemma~3.11]{branden2020lorentzian}.
    %    \(\text{\ref{cond:(thm:AFM-gph-equiv)-G-AFM}} \iff \text{\ref{cond:(thm:AFM-gph-equiv)-PG-Lor}} \iff \text{\ref{cond:(thm:AFM-gph-equiv)-E(G)-Mconv}}\) follows from \cite[Lemma~3.11]{branden2020lorentzian}.
    
    \noindent \(\text{\ref{cond:(thm:AFM-gph-equiv)-G-AFM}}\implies \text{\ref{cond:(thm:AFM-gph-equiv)-G-str}}\). If $G$ is antiferromagnetic, then so are all its induced subgraphs by~\Cref{prop:induced}. Thus, the graphs \twoedges, \paththree, \triangleaddedge, and {\twoloops} are forbidden as an induced subgraph. It follows that non-looped vertices form a complete multipartite graph and looped vertices are pairwise adjacent.

    Suppose \(G\) has \loopplusvtx\, as an induced subgraph. As \(G\) has no isolated vertex, $G$ must have \loopplusedge, \loopedpathtwo, \loopplusloopededge, or {\twoloopspathtwo} as an induced subgraph. However, none of these are antiferromagnetic, which contradicts antiferromagnetism of $G$. Thus, each looped vertex connects to all the non-looped vertices. Together with the above paragraph, this characterises the structure of $G$ as given in \ref{cond:(thm:AFM-gph-equiv)-G-str}.
    %The proof of \(\text{\ref{cond:(thm:AFM-gph-equiv)-E(G)-Mconv}} \implies \text{\ref{cond:(thm:AFM-gph-equiv)-G-str}}\) follows from some tedious applications of the exchange property, which we omit here.
    
    \noindent \(\text{\ref{cond:(thm:AFM-gph-equiv)-G-str}}\implies\text{\ref{cond:(thm:AFM-gph-equiv)-G-AFM}}\). By direct calculation, $K_q^\circ$ is antiferromagnetic. By~\Cref{lem:G-vol-Lor-preserved-by-G-blowup-indsubgp}, so is~$G$.
    %Finally, to show \(\text{\ref{cond:(thm:AFM-gph-equiv)-G-str}} \implies \text{\ref{cond:(thm:AFM-gph-equiv)-G-AFM}}\), we start with \(h_{K_2}(\bx;G) = Q_G(\bx)\). Applying~\Cref{lem:G-vol-Lor-preserved-by-G-blowup-indsubgp} with \(H=K_2\) and using \(\text{\ref{cond:(thm:AFM-gph-equiv)-G-AFM}} \iff \text{\ref{cond:(thm:AFM-gph-equiv)-PG-Lor}}\), we see that if \(G\) is antiferromagnetic, then so is its blow-up and induced subgraph. Thus, the statement follows from \(K_q^\circ\) being antiferromagnetic.
\end{proof}

\Cref{thm:AFM-gph-equiv} can be seen as a generalisation of \cite[Corollary~5.4]{choe2004homogeneous}, which states that a loopless graph without isolated vertices is antiferromagnetic if and only if it is a complete multipartite graph. The only difference is that `apex' loops, which connect to all the vertices, may appear.

Let us briefly show \Mc-convexity of $\supp(h_{K_t}(\bx;G))$ for $G=K_q$. In this case, the support of $h_{K_t}(\bx;G)$ consists of $\{0,1\}$-vectors, each of which is the indicator of a set in $\binom{[q]}{t}$. Thus, its \Mc-convexity directly follows from the base exchange property of uniform matroids. For general $G$, some case analysis proves \Mc-convexity of $\supp(h_{K_t}(\bx;G))$. %In fact, we will see in~\Cref{sec:mms} that it is enough to analyse $\supp(h_{K_t}(\bx;K_q))$ only.
In fact, even for any $H$ other than $K_t$, it is enough to analyse $\supp(h_{H}(\bx;K_q))$ only. We omit the proof.
\begin{proposition}\label{prop:reduction}
     Let \(H\) be a connected graph on \(t\ge2\) vertices. If \(h_H(\blank;K_q)\) has \Mc-convex support for some \(q\ge 3t\), then so does \(h_H(\blank;G)\) for all antiferromagnetic graphs \(G\).
\end{proposition}
This may be potentially useful in proving \Mc-convexity of $G$-chromatic functions for arbitrary antiferromagnetic graphs $G$.%, by reducing the problem to the case of complete graphs $G=K_q$.

% \begin{proof}
%    We only provide the proof when \(G\) is unweighted and has no isolated vertices.
%    Write \(V(G)=[n]\) and \(\bx=(x_1,\dots,x_n)\). The case \(t=1\) is clear as \(h_{K_1}(\bx;G)\) is a linear polynomial which is always Lorentzian, so assume \(t\ge2\).
    
%    First, we show that \(\partial_\nu h_{K_t}(\bx;G)\) is Lorentzian for all \(\nu\in [n]\) by induction on \(t\).

%    Next, we show that \(\supp(h_{K_t}(\bx;G))\) is \Mc-convex. \Cref{prop:AFM-gph-supp} and \Cref{thm:AFM-gph-equiv} say \(\supp G\) is obtained from \(K_q^\circ\) for some \(q\ge1\) by blowing-up and taking an induced subgraph. If we show \(\supp(h_{K_t}(\blank;K_q^\circ))\) is \Mc-convex, then together with the first part of the proof, we see \(h_{K_t}(\blank;K_q^\circ)\) is Lorentzian, whence~\Cref{lem:G-vol-Lor-preserved-by-G-blowup-indsubgp} implies that \(h_{K_t}(\blank;\supp G)\) is Lorentzian, therefore \(\supp(h_{K_t}(\blank;G)) = \supp(h_{K_t}(\blank;\supp G))\) is \Mc-convex. Thus, it suffices to show \(\supp(h_{K_t}(\blank;K_q^\circ))\) is \Mc-convex.

%     Write \(V(K_q^\circ) = \{w_1,\dots,w_q\}\) where \(w_q\) is looped. Let \(\ba=(a_1,\dots,a_q)\) and \(\bb=(b_1,\dots,b_q)\) be in \(\supp(h_{K_t}(\bx;K_q^\circ))\), and \(a_i>b_i\) for some \(i\in [q]\). Note \(a_j,b_j\in\{0,1\}\) for \(j\in [q-1]\). There are three cases: if \(a_q<b_q\), then \(i\neq q\) and \(\ba-\be_i+\be_q\in \supp(h_{K_t}(\bx;K_q^\circ))\). If \(a_q=b_q\), then \(i\in [q-1]\) and \(a_1+\dots+a_{q-1} = b_1+\dots+b_{q-1}\), so there is \(j\in [q-1]\setminus\{i\}\) such that \(a_j=0<1=b_j\). If \(a_q>b_q\), then \(a_1+\dots+a_{q-1} < b_1+\dots+b_{q-1}\), so again there is such \(j\in [q-1]\). In the latter two cases, \(\ba-\be_i+\be_j\in \supp(h_{K_t}(\bx;K_q^\circ))\). Therefore \(\supp(h_{K_t}(\bx;K_q^\circ))\) is \Mc-convex, which completes the proof.
% \end{proof}

\section{Alexandrov--Fenchel-type inequalities for \texorpdfstring{$G$}{G}-volumes}\label{sec:AF}

\cite[Proposition~4.5]{branden2020lorentzian} states that one can obtain an Alexandrov--Fenchel-type inequality from any Lorentzian polynomial.

\begin{proposition}[Proposition~4.5 in {\cite{branden2020lorentzian}}]
\label{prop:Lor-AF-ineq}
    Let \(f\) be a homogeneous polynomial of degree \(d\) in \(n\) variables. Let \(F_f\colon (\RR^n)^d\to \RR\) be defined by
    \[
        F_f(v_1,\dots,v_d) \defeq \frac{1}{d!} \partial_{x_1}\dotsm \partial_{x_d} f(x_1v_1+\dots+x_dv_d).
    \]
    If \(f\) is Lorentzian, then for any \(v_1\in \RR^n\) and \(v_2,\dots,v_d\in (\RR_{\ge0})^n\),
    \[
        F_f(v_1,v_2,v_3,\dots,v_d)^2 \ge F_f(v_1,v_1,v_3,\dots,v_d) \cdot F_f(v_2,v_2,v_3,\dots,v_d).
    \]
\end{proposition}

For example, $f$ can be the volume of the Minkowski sum $x_1K_1+\cdots+x_dK_d$ of convex bodies $K_1,\dots, K_d$, a Lorentzian polynomial given in~\cite{branden2020lorentzian}. Then~\Cref{prop:Lor-AF-ineq} recovers the classical Alexandrov--Fenchel inequality for mixed volumes.

In our setting, choosing $f=h_{K_t}(\bx;G)$
gives $F_f=V_G(\ba_1,\dots,\ba_t;G)$, the $G$-volume of~$K_t$ due to~\eqref{eq:G-volume-Kt-pdiff-form}.
As $f=h_{K_t}(\bx;G)$ is Lorentzian by~\Cref{thm:AFM-hom-Lor}, \Cref{prop:Lor-AF-ineq} yields an Alexandrov--Fenchel-type inequality for the \(G\)-volume of a complete graph.  That is, for \(\ba_1,\ba_2,\dots,\ba_t\in (\RR_{\ge0})^n\),
\begin{equation}\label{eq:AF}
    V_{K_t}(\ba_1,\ba_2,\ba_3\dots,\ba_t;G)^2
    \ge V_{K_t}(\ba_1,\ba_1,\ba_3,\dots,\ba_t;G)
        \cdot V_{K_t}(\ba_2,\ba_2,\ba_3,\dots,\ba_t;G).
\end{equation}

% \begin{thm}\label{thm:G-vol-AF-ineq}
%     Let \(G\) be an $n$-vertex antiferromagnetic graph and let \(\ba_i\in (\RR_{\ge0})^n\), $1\leq i\leq t$.  Then
%     \[
%         V_{K_t}(\ba_1,\ba_2,\ba_3\dots,\ba_t;G)^2
%         \ge V_{K_t}(\ba_1,\ba_1,\ba_3,\dots,\ba_t;G)\cdot V_{K_t}(\ba_2,\ba_2,\ba_3,\dots,\ba_t;G).
%     \]
% \end{thm}
%\begin{proof}
%    This follows from~\Cref{thm:AFM-hom-Lor} and \Cref{prop:Lor-AF-ineq} together with \eqref{eq:G-volume-Kt-pdiff-form}.
%\end{proof}


Applying~\eqref{eq:AF} iteratively gives the following inequality.
\begin{corollary}\label{cor:G-vol}
    Let \(G\) be an $n$-vertex antiferromagnetic graph and let \(\ba,\bb\in (\RR_{\ge0})^n\).  Then
    \[
         V_{K_t}(\bb,\ba,\dots,\ba;G)\cdot V_{K_t}(\ba,\bb,\dots,\bb;G)
        \ge 
        V_{K_t}(\ba,\ba,\dots,\ba;G)\cdot V_{K_t}(\bb,\bb,\dots,\bb;G).
    \]
\end{corollary}

We are now ready to prove our main result of this section,
%in a careful way gives the following inequality on the \(G\)-volumes of \(K_t\) and \(K_t\times K_2\),
which implies~\Cref{thm:main} by setting \(\ba=\bb=(1,1,\dots,1)\).

\begin{thm}\label{thm:G-vol-ineq-KtxK2}
    Let \(G\) be an $n$-vertex antiferromagnetic graph and let \(t\ge2\). Write the bipartition of \(K_t\times K_2\) as \(V_1\sqcup V_2\). For \(\ba,\bb\in (\RR_{\ge0})^n\),
    \[
        V_{K_t}(\underbrace{\ba,\dots,\ba}_t; G) \cdot V_{K_t}(\underbrace{\bb,\dots,\bb}_t; G) \le V_{K_t\times K_2}(\underbrace{\ba,\dots,\ba}_t,\underbrace{\bb,\dots,\bb}_t; G),
    \]
    where in the right-hand side, \(\ba\) and \(\bb\) correspond to the vertices in \(V_1\) and \(V_2\), respectively.
\end{thm}
\begin{proof}
    We provide a simplified proof for the case when \(\ba\), \(\bb\) are \(\{0,1\}\)-valued so that they represent vertex subsets and \(G\) is an unweighted loopless graph.  
    Let \(V(G)=[n]\). For \(A\subseteq [n]\), denote by \(\one_A\in \{0,1\}^n\) the indicator vector of \(A\).
    For \(A,B\subseteq [n]\) and $1\leq \ell \leq t$, write
    \begin{gather*}
        V_{K_t}(A;t;G) \defeq V_{K_t}(\underbrace{\one_A,\dots,\one_A}_t;G),
        \quad
        V_{K_t}(A,B;\ell;G) \defeq V_{K_t}(\underbrace{\one_A,\dots,\one_A}_\ell, \underbrace{\one_B,\dots,\one_B}_{t-\ell};G), \\
        \text{and}\quad
        V_{K_t\times K_2}(A;B;G) \defeq V_{K_t\times K_2}(\underbrace{\one_A,\dots,\one_A}_t, \underbrace{\one_B,\dots,\one_B}_t;G).
    \end{gather*}
    Thus, our goal is to show that for \(A,B\subseteq [n]\),
    \[
        V_{K_t}(A;t;G) \cdot V_{K_t}(B;t;G) \le V_{K_t\times K_2}(A,B;t;G).
    \]
    We use induction on \(t\). As \(K_2\times K_2 = K_2\sqcup K_2\), the base case \(t=2\) reduces to 
    \[
        V_{K_2}(A,A;G)\cdot V_{K_2}(B,B;G)\le V_{K_2}(A,B;G)^2 = V_{K_2\times K_2}(A,A,B,B;G),
    \]
    which follows from~\Cref{cor:G-vol}. 
    Suppose \(t\ge 3\). 
    We may assume that \(K_t \times K_2\) is the bipartite graph with the bipartition \(V_1 \sqcup V_2 = ([t] \times \{1\}) \sqcup ([t] \times \{2\})\) and the edge set \(\{(i,1)(j,2) : i, j \in [t],\, i \neq j\}\).

    We compute the $G$-volume \(V_{K_t\times K_2}(A,B;t;G)\) by counting homomorphisms $\phi$ from $ K_t\times K_2$ to $G$ recursively as follows: first, choose \(\phi(t,1)=r\in A\) and \(\phi(t,2)=s\in B\); next, find a homomorphic copy of $K_{t-1}\times K_2$ such that the vertices in $A$ and $B$ are adjacent to $s$ and $r$, respectively.
    %That is,
    %choose \(\phi(i,j)\) for \((i,j)\in [t-1]\times[2]\) so that
    %\begin{enumerate}
     %   \item \(\phi(i,1)\in A\) and \(\phi(i,2)\in B\) for \(1\leq i <t\),
      %  \item \(\phi(i,1)\in N_G(s)\) and \(\phi(i,2)\in N_G(r)\) for \(1\leq i <t\), and
    %    \item there is a homomorphism \(K_{t-1}\times K_2\to G\bigl[ \phi([t-1]\times[2]) \bigr]\) where \((i,j)\mapsto \phi(i,j)\).
    %\end{enumerate}
    These two-step embeddings give us the identity
    \[
        V_{K_t\times K_2}(A;B;G)
        = \sum_{r\in A,\, s\in B} V_{K_{t-1}\times K_2}(A\cap N_G(s); B\cap N_G(r); G)
    \]
    By the induction hypothesis, it follows that
    \begin{align*}
        V_{K_t\times K_2}(A;B;G)
        &\ge \sum_{r\in A,\, s\in B} V_{K_{t-1}}(A\cap N_G(s);t-1;G) \cdot V_{K_{t-1}}(B\cap N_G(r);t-1;G)
        \\&= \sum_{s\in B} V_{K_{t-1}}(A\cap N_G(s);t-1;G) \cdot \sum_{r\in A} V_{K_{t-1}}(B\cap N_G(r);t-1;G).
    \end{align*}
    The term \(V_{K_{t-1}}(A\cap N_G(s);t-1;G)\) counts the number of labelled copies of \(K_{t-1}\) in \(N_G(s)\) whose vertices are also in \(A\). By summing this over \(s\in B\), we get the number of labelled copies of \(K_t\) whose first vertex is in \(B\) and the others are in \(A\). In other words,
    \[
        \sum_{s\in B} V_{K_{t-1}}(A\cap N_G(s);t-1;G) = V_{K_t}(A,B;t-1;G),
    \]
    and, symmetrically,
    \[
        \sum_{r\in A} V_{K_{t-1}}(B\cap N_G(r);t-1;G) = V_{K_t}(A,B;1;G).
    \]
    Therefore, together with~\Cref{cor:G-vol}, we conclude that
    \[
        V_{K_t\times K_2}(A;B;G) \ge V_{K_t}(A,B;t-1;G) \cdot V_{K_t}(A,B;1;G)
        \geq V_{K_t}(A;t;G)V_{K_t}(B;t;G).
        \qedhere
    \]
\end{proof}

Let $\HH$ be a class of graphs that includes $K_1$. An \emph{$\HH$-blow-up} $H$ of a $k$-vertex graph $F$ is obtained by replacing all $k$ vertices $v_1,\dots,v_k$ of $F$ by $H_1,\dots, H_k$ in $\HH$, respectively, and the edges of the form $v_iv_j\in E(F)$ by a complete bipartite graph $K_{s,t}$, where $s=v(H_i)$ and $t=v(H_j)$. Note that a vertex blown up by $K_1$ can be considered unchanged.
A \emph{clique-blow-up} of a graph $F$ is an $\HH$-blow-up with the set $\HH$ of all complete graphs. For instance, $K_{r+s}\setminus K_{s}$ is a clique-blow-up of $K_{1,s}$.
\Cref{thm:main2} then follows from~\Cref{thm:G-vol-ineq-KtxK2}.
\begin{proof}[Proof of~\Cref{thm:main2}]
    We give a brief sketch, again assuming $G$ is unweighted.
    Let $H$ be a clique-blow-up of a $k$-vertex bipartite graph $F$, where each vertex $v_i$ is replaced by a copy of~$K_{r_i}$. 
    Let $H_1$ and $H_2$ be vertex-disjoint copies of $H$. In $H_j$, $j=1,2$, $V_i^{(j)}$, $i=1,2,\dots,k$, denotes the vertex set of the copy of $K_{r_i}$ that replace $v_i\in V(F)$.
    
    Let $L_0=H_1\sqcup H_2$ and let $L_\ell$, $\ell=1,2,\dots,k$ be the graph obtained by replacing the copy of $K_{r_\ell}\sqcup K_{r_\ell}$ induced on $V_\ell^{(1)}\cup V_\ell^{(2)}$ in $L_{\ell-1}$ by $K_{r_1}\times K_2$, whose bipartition is again $V_\ell^{(1)}\cup V_\ell^{(2)}$. It is easy to check that $L_k$ is isomorphic to $H\times K_2$ by using bipartiteness of~$F$.
    Repeated applications of~\Cref{thm:G-vol-ineq-KtxK2} then give
    \begin{align*}
        \hom(H,G)^2 = \hom(L_0,G)\leq \hom(L_1,G)\leq\cdots\leq \hom(L_k,G) = \hom(H\times K_2,G).
    \end{align*}
     Indeed, to compare $L_\ell$ and $L_{\ell-1}$, fix all homomorphic images of $V_i^{(1)}\cup V_i^{(2)}$, $i\neq\ell$, where $L_\ell$ and $L_{\ell-1}$ induce isomorphic subgraphs, and denote by $\phi$ this partial embedding. Then there exist $A_\phi,B_\phi\subseteq V(G)$ such that finding a homomorphic copy of $K_{r_\ell}$ in $A_\phi$ and in $B_\phi$, respectively, extends $\phi$ to a homomorphic copy of $L_{\ell -1}$. In contrast, finding a homomorphic copy of $K_{r_\ell}\times K_2$ across $A_\phi\cup B_\phi$ extends $\phi$ to a homomorphic copy of $L_{\ell}$.
     Thus, $\hom(L_{\ell-1},G)\leq \hom(L_{\ell},G)$ reduces to summing the inequality 
     \begin{align*}
         V_{K_{r_\ell}}(A_\phi;r_\ell;G)V_{K_{r_\ell}}(B_\phi;r_\ell;G)\leq V_{K_{r_\ell}\times K_2}(A_\phi,B_\phi;r_\ell;G)^2
     \end{align*}
    for all partial embeddings $\phi$, which follows from~\Cref{thm:G-vol-ineq-KtxK2}.
\end{proof}

The essence of the proof of~\Cref{thm:main2} leverages on a weaker statement than the Alexandrov--Fenchel-type inequality. Namely, it only requires,
with $k=v(K)$,
\begin{align}\label{eq:cross_volume}
    V_{K}(A;k;G)V_K(B;k;G)\leq V_{K\times K_2}(A,B;k;G)^2
\end{align}
holds for any $A,B\subseteq V(G)$ to blow-up a vertex of $F$ by using a copy of $K$. 
%When $G=K_q$, $A,B\subseteq V(K_q)$ can be seen as lists of colours, so \eqref{eq:cross_volume} becomes a correlation inequality for list colourings. 

For $G=K_q$, we show that complete multipartite graphs or paths $K$ also satisfy~\eqref{eq:cross_volume}, so more graphs can be added to $\HH$ to blow up vertices of a bipartite graph $F$. We omit the proof of this result, which relies on multiple reductions and certain log-concavity between complete multipartite graph counts in $K_q$.
As a consequence, we have slightly more options to blow up a bipartite graph $F$ than~\Cref{thm:main2} offers if $G=K_q$.
\begin{thm}
    Let $\HH$ be the class of graphs that consist of all complete multipartite graphs and paths. For any $\HH$-blow-up $H$ of a bipartite graph $F$ and any $q\geq 2$,
    \begin{align*}
        \hom(H,K_q)^2 \leq \hom(H\times K_2,K_q).
    \end{align*}
\end{thm}


\printbibliography


\end{document}
