Content-Type: multipart/mixed; boundary="-------------1712020848331"
This is a multi-part message in MIME format.
---------------1712020848331
Content-Type: text/plain; name="17-111.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="17-111.comments"
3 pages
---------------1712020848331
Content-Type: text/plain; name="17-111.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="17-111.keywords"
regular bipartite lattice,
---------------1712020848331
Content-Type: application/x-tex; name="graph.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="graph.tex"
\documentclass{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\mathchardef\mhyphen="2D % Define a "math hyphen"
\usepackage[a4paper]{geometry}
\usepackage{microtype}
\usepackage{relsize}
\def\Z{\mathbb Z}
\def\zo/{$0\mkern2mu\mhyphen1$}%0-1
\def\Ex{E_{\times}}
\def\nn/{$n \times n$}
\def\a{\alpha}
\newtheorem{conj}{Conjecture}
\DeclareMathOperator\perm{perm}
\title{Regular Bipartite Lattices with Large Values of $\tht/C_4$}
\date{\today}
\author{Paul Federbush\\
Department of Mathematics\\
University of Michigan\\
Ann Arbor, MI, 48109-1043}
%%%% Added by T. Murayama
\usepackage{amsthm} % Needed for conj*
\newtheorem{thm}{Theorem}[section]
\newtheorem*{conj*}{Conjecture} % Defines non-numbered conjecture environment
%\numberwithin{equation}{section} % Fixes equation labels to match manuscript
\DeclareMathOperator{\Prob}{Prob}
\DeclareMathOperator{\EE}{E}
\DeclareMathOperator{\OO}{\mathcal{O}}
\DeclareMathOperator{\PP}{P}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % For double slash
%%%%
%Paper specific macros, and other things added by R. Sandberg
\usepackage{tikz}
\newcommand{\tht}{\theta_{2,2,2}}
\newcommand{\cfour}{C_4}
\begin{document}
%Title:
\maketitle
%Abstract
\begin{abstract}
The quantities $C_4$ and $\tht$ are as defined by Wanless, $C_4$ just the number of 4-loops of a graph. The construction of this paper provides a counterexample to a conjecture of Butera, Pernici, and the author about the monomer-dimer entropy, $\lambda,$ of a regular bipartite lattice.
\end{abstract}
%Body
We let $G_1 $ and $G_2$ be the graphs illustrated in Figure \ref{fig:graphs}. Then given a graph $G$, we let $C_4= C_4(G)$ be the number of subgraphs of $G$ isomorphic to $G_1,$ and $\tht(G)$ be the number of subgraphs of $G$ isomorphic to $G_2.$ This notation follows Section 2 of \cite{Wan}.
\begin{figure}
\centering
\begin{tikzpicture}
\tikzstyle{v} = [circle, minimum size=2mm,inner sep=0pt,draw]
\node[v] (n1) at (1.5,2.5) {};
\node[v] (n2) at (2.5,2.5) {};
\node[v] (n3) at (1.5,3.5) {};
\node[v] (n4) at (2.5,3.5) {};
\node (n5) at (2,1.5) {$G_1$};
\foreach \from/\to in {n1/n2,n2/n4,n4/n3,n3/n1}
\draw (\from) -- (\to);
\node[v] (n6) at (6,2) {};
\node[v] (n7) at (5,3) {};
\node[v] (n8) at (6,3) {};
\node[v] (n9) at (7,3) {};
\node[v] (n10) at (6,4) {};
\node (n11) at (6,1) {$G_2$};
\foreach \from/\to in {n6/n7,n6/n8,n6/n9,n7/n10, n8/n10,n9/n10}
\draw (\from) -- (\to);
\end{tikzpicture}
\caption{}
\label{fig:graphs}
\end{figure}
A connected infinite graph is a lattice if there is a finitely generated Abelian group of isomorphic maps on $G$ for which the set of equivalence classes of vertices is finite. Two vertices are in the same equivalence class if there is a translation (a member of the Abelian group) that carries one into the other. The lattice is i-dimensional if exactly i of a set of generators of the group are infinite order.
For a lattice the quantities $C_4$ and $\tht$ may both be infinite, but the ratio $\tht/C_4$ makes sense. Taking a sequence of finite graphs that approach the lattice in the sense of Benjamini-Schramm \cite{CAH}
the ratios $\tht/C_4$ converge to a limit we take to be the value for the lattice.
Given any number $\kappa$ we find a one dimensional regular bipartite lattice for which \begin{align} \tht/C_4 > \kappa \\ C_6 = 0.\end{align} Here $C_6$ is the number of 6-loops as $C_4$ is the number of 4-loops.
In \cite{FF} Friedland and I introduced an expansion for the monomer-dimer entropy of a regular lattice, \begin{align}
\lambda(p)=\lambda_B(p) + \sum_k d_k p^k\end{align} where $\lambda_B$ is the monomer-dimer entropy for the Bethe lattice. In \cite{BFP} Butera, Pernici and I conjectured that for a regular bipartite lattice all the $d_k\ge 0,$ see also \cite{Csi}, Section 3.
In \cite{Per} Pernici proved in the bipartite case $d_2,d_3,d_4,d_5$ were all nonnegative using a formalism of Wanless, \cite{Wan}. For $d_6$ he finds the expression \begin{align}
d_6 = \frac{5 \bar{C_4}}{d^6} + \frac{\bar{C_6}}{2d^6} - 2\frac{\bar\theta_{2,2,2}}{d^6}
\end{align}
where we have d-regularity and the bars indicate an average over the number of vertices, again as may be taken as a Benjamini-Schramm limit. We find a one dimensional regular bipartite lattice for each $\kappa$ such that $$\tht/C_4 > \kappa$$ and also $$C_6=0.$$ Thus there are bipartite regular lattices for which $d_6 < 0.$ Pernici erred in stating otherwise.
We start the construction of our lattice with a `root unit graph', a finite graph. To this we apply a number of 2-lifts to end with a `full unit graph'. The full unit graphs are attached head to tail to yield the one dimensional lattice. We use 2-lifts similarly to as in Section 4 of \cite{Cs2}, derived from \cite{8}.
\vspace{.2 in}
\noindent\underline{The Root Unit Graph}
\vspace{.1 in}
This graph has black vertices: \begin{align*} c_i, &\quad i=1,\ldots,d\end{align*} and white vertices: \begin{align*} t,b,l,r & \\ f_i,&\quad i=1,\ldots,d-3 \end{align*}
The edges are: \begin{align*}
(t,c_i)& \quad i=1,\ldots, d \\
(b,c_i)& \quad i=1,\ldots, d \\
(c_i,f_j)& \quad i=1,\ldots, d\quad j=1,\ldots,d-3 \\
(l,c_1)& \\
(r,c_i)& \quad i=2,\ldots, d \\
\end{align*}
It has a subgraph, the `root central subgraph'. The root central subgraph has black vertices: \begin{align*}
c_i,& \quad i=1,\ldots,d
\end{align*} and white vertices: $$t,b$$ Its edges are:
\begin{align*}
(t,c_i)&\quad i=1,\ldots, d \\
(b,c_i)&\quad i=1,\ldots, d \\
\end{align*}
The quantities $\tht$ and $C_4$ for the root central subgraph are easily computed to be
\begin{align}
C_4 &= \frac{d(d-1)}{2} \\
\tht &= \frac{d(d-1)(d-2)}{6}
\end{align}
Exploitation of the root central subgraph is the key idea in this paper.
\vspace{.2 in}
\noindent\underline{Thank Heaven for 2-lifts}
\vspace{.1 in}
The full unit graph is constructed from the root unit graph through a sequence of $s$ 2-lifts. Each edge in the full unit graph projects in a natural sense onto an edge of the root unit graph. $2^s$ edges of the full unit graph project onto each edge of the root unit graph (likewise $2^s$ vertices project onto each vertex). The edges that project onto edges of the root central subgraph have all been chosen parallel, none crossed (this is also in a natural sense). Thus there are $2^s$ disjoint subgraphs of the full unit graph isomorphic to the root central subgraph.
The sequence of 2-lifts are chosen so that for the full unit graph there are no 6-loops, and 4-loops only in the $2^s$ subgraphs isomorphic to the root central subgraph.
The lattice is constructed by taking an infinite chain of the full unit graphs and connecting the ith full unit graph to the (i+1)st full unit graph by identifying each of the $2^s$ vertices that project onto vertex r of the ith graph with one of the $2^s$ vertices that project onto $l$ of the (i+1)st (the choice of how this identification goes is natural). The lattice thus constructed will have $C_6=0$ and $\frac{\bar \theta _{2,2,2}}{\bar C_4} = \frac{g-2}{3}.$
\textbf{Acknowledgement} We would like to thank Sasha Barvinok for a lecture on 2-lifts and John Stembridge for putting up
with my continual questions.
\begin{thebibliography}{1}
\bibitem{Wan}
Wanless, I. M., \textit{Counting matchings and tree-like walks in regular
graphs,} Combinatorics, Probability and Computing \textbf{19} (2010) 463-480.
\bibitem{CAH}
Csikvari, P., Abert, M., Hubai, T., \textit{Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy,} Journal of Statistical Physics \textbf{161} (2015), 16-34.
\bibitem{FF}
Federbush, P., Friedland, S., \textit{An asymptotic expansion and recursive inequalities for the monomoer-dimer problem,} J. Stat. Phys. \textbf{143} (2011) 306-325.
\bibitem{BFP}
Butera, P., Federbush, P., Pernici, M., \textit{Higher-order expansions for the entropy of a dimer or a monomer-dimer system on d-dimensional lattices,} Phys. Rev. E \textbf{87}, 062113 (2013).
\bibitem{Csi}
Csikvari, P. \textit{Matchings in vertex-transitive bipartite graphs,} accepted to Israel Journal of Mathematics.
\bibitem{Per}
Pernici, M., \textit{$1/n$ expansion for the number of matchings on regular
graphs and monomer-dimer entropy,} J. Stat.\ Phys.\ \textbf{168} (2017) 666.
\bibitem{Cs2}
Csikvari, P., \textit{Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems,} accepted to the Journal of the European Mathematical Society.
\bibitem{8}
Linial, N., \textit{Lifts of graphs,} (talk slides on the web).
\end{thebibliography}
\end{document}
---------------1712020848331--