# Spectra of infinite graphs with summable weight functions

Michael Farber  School of Mathematical Sciences
Queen Mary University of London
E1 4NS London
UK<EMAIL_ADDRESS>and  Lewin Strauss  School of Mathematical Sciences
Queen Mary University of London
E1 4NS London
UK<EMAIL_ADDRESS>
###### Abstract.

In this paper we study spectra of Laplacians of infinite weighted graphs.
Instead of the assumption of local finiteness we impose the condition of
summability of the weight function. Such graphs correspond to reversible
Markov chains with countable state spaces. We adopt the concept of the Cheeger
constant to this setting and prove an analogue of the Cheeger inequality
characterising the spectral gap. We also analyse the concept of the dual
Cheeger constant originally introduced in [1], which allows estimating the top
of the spectrum. In this paper we also introduce a new combinatorial
invariant, ${\sf k}(G,m)$, which allows a complete characterisation of
bipartite graphs and measures the asymmetry of the spectrum (the Hausdorff
distance between the spectrum and its reflection at point $1\in\mathbb{R}$).
We compare ${\sf k}(G,m)$ to the Cheeger and the dual Cheeger constants.
Finally, we analyse in full detail a class of infinite complete graphs and
their spectra.

###### Key words and phrases:

Infinite weighted graph; spectrum; Laplace operator; random walk; Cheeger
contant; dual Cheeger constant

###### 1991 Mathematics Subject Classification:

05C50; 05C63; 05C48; 05C81

Both authors were partially supported by a grant from the Leverhulme Trust

Data sharing is not applicable to this article as no datasets were generated
or analysed during the current study.

##  1\. Introduction

Spectral graph theory is a well-developed field of mathematics lying at the
crossroads between combinatorics, analysis and geometry. It has multiple
applications in engineering and computer science [3]. The celebrated Cheeger
inequalities relate the geometry of a graph with the spectral properties of
the graph Laplacian [4]. The Cheeger inequalities play a crucial role in
theory of expander graphs [5], which are sequences of finite graphs with
certain asymptotic properties. The literature on spectral graph theory
contains many important results about finite and infinite graphs and their
spectral properties, see for instance [3, 7, 11].

In this paper, we consider countable weighted graphs that are not necessarily
locally finite but we impose an assumption of summability on the weights, i.e.
we require the sum of all edge weights to be finite. Such summable weighted
graphs can be thought of as representations of reversible countable Markov
chains [11].

We introduce three geometric constants and analyse their bearing on the
spectral properties of the normalised graph Laplacian of summable weighted
graphs. The Cheeger constant and the dual Cheeger constant introduced in this
paper can be compared to the invariants studied in [1]. There are several
significant differences between [1] and our approach: (a) in [1] the authors
study a Dirichlet type Laplace operator and their approach is applicable to
locally finite graphs only; (b) The Cheeger constant defined in [1] measures
bottom of the spectrum which is automatically $0$ for summable weighted graphs
studied in this paper. Our Cheeger constant measures the spectral gap rather
than bottom of the spectrum.

Our new combinatorial invariant, ${\sf k}(G,m)$, affords a complete
characterisation of bipartite graphs: it vanishes if and only if the graph is
bipartite. We also show that the new invariant ${\sf k}(G,m)$ allows
estimating the asymmetry of the spectrum (Theorem 25).

In section 3 we show several examples of graphs $G$ such that different
summable weight functions on $G$ have either vanishing or non-vanishing
spectral gap illustrating the fact that the property to have a non-vanishing
spectral gap (i.e. “expansion”) strongly depends on the weight function (and
not just on the underlying graph).

In more detail, our main results can be summarised as follows. Let $(G,m)$
denote a connected summable weighted graph, and let
$\sigma(\Delta)\subset[0,2]$ denote the spectrum of the associated Laplacian
$\Delta$. Summability implies $0\in\sigma(\Delta)$. We provide geometric
estimates for the spectral gap and top of the spectrum,

$\lambda_{gap}(\Delta)=\inf\\{\sigma(\Delta)-\\{0\\}\\}\quad\text{ and
}\quad\lambda_{top}=\sup\\{\sigma(\Delta)\\}.$

Namely, we define a Cheeger constant $h(G,m)$ and a dual Cheeger constant
$\overline{h}(G,m)$, and we prove (cf. Theorem 12)

$\displaystyle 1-\sqrt{1-h(G,m)^{2}}\,\leq\,$
$\displaystyle\lambda_{gap}(\Delta)\leq 2\cdot h(G,m),$ $\displaystyle
2\cdot\overline{h}(G,m)\,\leq\,$ $\displaystyle\lambda_{top}(\Delta)\leq
1+\sqrt{1-\big{(}1-\overline{h}(G,m)\big{)}^{2}}.$

Moreover, we define a new geometric constant ${{\sf k}}(G,m)$ and show that
the Hausdorff distance between $\sigma(\Delta)\subset[0,2]$ and its reflection
around 1 is bounded above by $2\cdot{{\sf k}}(G,m)$ (Theorem 25).

Finally, in sections 8, 9, and 10, we analyse a rich class of infinite
complete graphs whose spectra admit a particularly detailed description.

We are not in a position to survey the vast literature which pertains to
various classes of graphs, various Cheeger-type combinatorial constants,
various graph Laplacians, and various aspects of the spectra of these
Laplacians. As far as we know the results contained in our paper are new and
are not contained in any previously published articles.

We may mention [2] where the authors use the concept of intrinsic metrics and
develop a comprehensive framework for countable weighted graphs, of which our
model is a special case. The authors introduce a Cheeger-type constant
(distinct from ours) and use it to bound the bottom of the spectrum of the
graph Laplacian. Our assumption of summability implies that the bottom of the
spectrum is $0$. As another example we may mention Theorem 3.5 of [9] which
provides a lower bound of the spectral gap of a normalised Laplacian, but in
[9] the underlying graphs are implicitly assumed to be locally finite as
follows from Definition 2.2 of [9].111For any oriented edge $vw$, the ratio
$i(wv)/i(vw)$ is bounded if and only if $\mu(v)/\mu(w)$ is bounded. But $\mu$
is assumed to be summable over vertices, so the vertex $v$ can only have
finitely many adjacencies.

The authors thank Norbert Peyerimhoff for helpful advice.

##  2\. Summable weighted graphs

###  2.1. Definitions

A graph is a 1-dimensional simplicial complex. For a graph $G$, we denote by
$\operatorname{V}(G)$ and $\operatorname{E}(G)$ the sets of vertexes and
edges, respectively. We say that $G$ is countable if the vertex set
$\operatorname{V}(G)$ is either finite or countably infinite. A weight
function on $G$ is a function $m:\operatorname{E}(G)\to(0,\infty)$. A weighted
graph is a pair $(G,m)$ consisting of a graph $G$ and a weight function $m$ on
$G$.

######  Definition 1.

We shall say that a countable weighted graph $(G,m)$ is summable if the sum of
all edge weights is finite, $\sum_{e\in\operatorname{E}(G)}m(e)<\infty$.

The weight function of a summable weighted graph $(G,m)$ naturally extends to
the vertexes: we set $m(v)=\sum_{v\in e}m(e).$ In other words, the weight of a
vertex is the sum of the edge weights over all edges that are incident to it
(”weighted degree”). According to this definition, a vertex has weight $0$ iff
it is isolated.

Below we shall consider only graphs without isolated vertexes; we shall have
$m(v)>0$ for any vertex $v$. The resulting function
$m:\operatorname{V}(G)\to[0,\infty)$ defines a $\sigma$-additive measure on
$\operatorname{V}(G)$. The weight $m(S)$ of a subset
$S\subset\operatorname{V}(G)$ is defined as $\sum_{v\in S}m(v)$, the sum of
the weights of all elements of $S$. Note that

$\sum_{v\in\operatorname{V}(G)}m(v)=2\cdot\sum_{e\in\operatorname{E}(G)}m(e)<\infty.$

We shall consider the Hilbert space $L^{2}(G,m)$ of square integrable
functions $f\colon\operatorname{V}(G)\rightarrow$ with respect to $m$. The
elements $f\in L^{2}(G,m)$ satisfy $\sum_{v\in\operatorname{V}(G)}m(v)\cdot
f(v)^{2}<\infty.$ The inner product of $L^{2}(G,m)$ is given by

$\langle f,g\rangle=\sum_{v\in\operatorname{V}(G)}m(v)\cdot f(v)\cdot g(v).$

Note that any constant function is square integrable, i.e. constant functions
belong to $L^{2}(G,m)$.

The normalised Laplacian of a summable weighted graph $(G,m)$ without isolated
vertexes is defined by

(1) $\displaystyle\Delta f(v)=f(v)-\sum_{w\sim v}\frac{m(vw)}{m(v)}\cdot
f(w),\quad f\in L^{2}(G,m).$

Using the Cauchy-Schwarz inequality, one sees that the sum in (1) converges
for any $f\in L^{2}(G,m)$. More precisely, for any $f\in L^{2}(G,m)$,

(2)
$\displaystyle\sum_{w}m(vw)f(w)\leq\left[\sum_{w}m(w)\left(\frac{m(vw)}{m(w)}\right)^{2}\right]^{1/2}\cdot||f||\leq
m(v)^{1/2}\cdot||f||,$

where

$||f||^{2}=\langle f,f\rangle=\sum_{v}m(v)f(v)^{2}.$

Note the following formula:

(3) $\langle\Delta
f,f\rangle=\sum_{vw\in\operatorname{E}(G)}m(vw)\cdot\big{(}f(v)-f(w)\big{)}^{2}.$

######  Lemma 2.

For a summable weighted graph $(G,m)$, the Laplacian $\Delta\colon
L^{2}(G,m)\rightarrow L^{2}(G,m)$ is well-defined; it is self-adjoint, non-
negative, and bounded. Moreover, the spectrum $\sigma(\Delta)$ of the
Laplacian lies in $[0,2]$. Any constant function
$f:\operatorname{V}(G)\to\mathbb{R}$ satisfies $\Delta f=0$, and thus
$0\in\sigma(\Delta)$ is an eigenvalue.

###### Proof.

We have $\Delta=I-P$, where

(4) $\displaystyle P(f)(v)=m(v)^{-1}\sum_{w}m(vw)f(w).$

Clearly $P$ is self adjoint. Using (2), one sees that $||P(f)||\leq||f||$,
which implies that the spectrum of $P$ lies in $[-1,1]$. Therefore
$\sigma(\Delta)\subset[0,2]$. ∎

Clearly, if the graph $G$ is infinite not every point of the spectrum
$\sigma(\Delta)$ is an eigenvalue.

###  2.2. Spectral gap

We shall be interested in the spectral gap of $\Delta$, defined by
$\lambda_{gap}(\Delta)=\inf\\{\lambda\in\sigma(\Delta)\colon\lambda>0\\}.$ The
spectral gap can be characterised as follows:

(5)
$\lambda_{gap}=\inf\bigg{\\{}\frac{\langle\Delta{f},{f}\rangle}{\langle{f},{f}\rangle}\colon
f\in L^{2}(G,m),\ f\perp{\bf 1}\bigg{\\}},$

see [10], Chapter 13. Here ${\bf 1}\colon\operatorname{V}(G)\to\mathbb{R}$ is
the constant function equal to $1$ at all points.

######  Lemma 3.

If $(G,m)$ is a summable weighted graph such that the underlying graph $G$ is
either infinite or it is finite but not a complete graph, then
$\lambda_{gap}\leq 1$.

###### Proof.

For a couple of vertexes $a,\,b\in\operatorname{V}(G)$ define $f_{ab}\in
L^{2}(G,m)$, via $f(a)=m(b)$, $f(b)=-m(a)$ and $f(v)=0$ for
$v\notin\\{a,b\\}$. Then $f_{ab}\perp\bf 1$, and using formula (3) we find

$\frac{\langle\Delta{f_{ab}},{f_{ab}}\rangle}{\langle{f_{ab}},{f_{ab}}\rangle}=1+2\cdot\frac{m(ab)}{m(a)+m(b)}.$

If $G$ is not a complete graph we can select the vertices $a,b$ such that
$m(ab)=0$ (i.e. the edge connecting $a$ and $b$ is not in $G$); then
$\lambda_{gap}\leq 1$ by (5).

If $G$ is complete and infinite then we can choose a sequence $b_{i}$ of
vertices that satisfies $m(ab_{i})\to 0$; such sequence exists since $G$ is
summable. Then the sequence

$\frac{\langle\Delta{f_{ab_{i}}},{f_{ab_{i}}}\rangle}{\langle{f_{ab_{i}}},{f_{ab_{i}}}\rangle}$

converges to 1 implying $\lambda_{gap}\leq 1$ by (5). ∎

######  Remark 4.

There are examples of graphs with spectral gap greater than 1: for a complete
graph on $n$ vertices weighted by $m(e)=1$ for all $e\in\operatorname{E}(G)$,
the spectral gap equals $\frac{n}{n-1}>1$ (see [3], pg. 6).

###  2.3. Summable weighted graphs as reversible Markov chains

A weighted graph $(G,m)$ with summable weight function $m$ determines a Markov
chain with the state space $\operatorname{V}(G)$, where the probability of
moving from $v$ to $w$ equals

$p_{vw}=\frac{m(vw)}{m(v)}.$

As above, we assume that $G$ has no isolated vertexes. If we write
$M=\sum_{v}m(v)=2\sum_{e}m(e)$, then the function $v\mapsto\phi(v)=m(v)\cdot
M^{-1}$ is a stationary probability distribution on $\operatorname{V}(G)$. The
Markov chains arising from summable weighted graphs are reversible and
recurrent, see [11].

##  3\. The Cheeger constant of a summable weighted graph and its dependence
on the weight function

###  3.1. Definition of the Cheeger constant

The Cheeger constant is a real number between 0 and 1 that, intuitively
speaking, measures the robustness of a connected weighted graph $(G,m)$.

Let $S$ be a set of vertices in $G$. The boundary of $S$, denoted $\partial
S$, is the set of all edges in $G$ with one endpoint in $S$,

$\partial S=\\{e\in\operatorname{E}(G)\colon|e\cap S|=1\\}.$

The interior of $S$, denoted $\operatorname{I}(S)$, is the set of all edges in
$G$ with both endpoints in $S$,

$\operatorname{I}(S)=\\{e\in\operatorname{E}(G)\colon|e\cap S|=2\\}.$

We shall denote by $S^{c}$ the complement, $S^{c}=\operatorname{V}(G)-S$.
Besides, $m(S)$ stands for $\sum_{v\in S}m(v)$ and $m(\partial S)$ denotes
$\sum_{e\in\partial S}m(e)$. These entities are related via

(6) $\displaystyle m(S)=m(\partial S)+2\cdot m(\operatorname{I}(S)).$

######  Definition 5.

Let $S$ be a non-empty set of vertices in $G$.

  * (a)

The Cheeger ratio of $S$, denoted $h(S)$, is the number

$h(S)=\frac{m(\partial S)}{m(S)}.$

  * (b)

The Cheeger constant of $(G,m)$, denoted $h(G,m)$, is the number

$h(G,m)=\inf\big{\\{}h(S)\big{\\}},$

where the infimum is taken over all non-empty sets of vertices $S$ that
satisfy

(7) $m(S)\leq m({S}^{\mathsf{c}}).$

It follows from Equation (6) that $h(G,m)\in[0,1].$

We consider the Cheeger constants of some interesting weighted graphs in
Subsection 3.3.

###  3.2. Cheeger sets

A set of vertexes $S\subset\operatorname{V}(G)$ satisfying (7) is a Cheeger
set if the induced subgraph $G_{S}$ is connected. The collection of Cheeger
sets in $(G,m)$ be denoted $\operatorname{\mathcal{V}}(G,m)$.

######  Lemma 6.

The Cheeger constant $h(G,m)$ equals the infimum of the Cheeger ratios taken
over all Cheeger sets:

$h(G,m)=\inf\big{\\{}h(S)\colon S\in\operatorname{\mathcal{V}}(G,m)\big{\\}}.$

###### Proof.

Let $S\subset\operatorname{V}(G)$ be a non-empty subset that satisfies (7). We
may enumerate the connected components of the induced subgraph $G_{S}$ and
denote by $S_{i}$ the vertex set of the $i$-th component. Then for $i\not=j$,
one has $\partial S_{i}\cap\partial S_{j}=\emptyset$ and $m(\partial
S)=\sum_{i}m(\partial S_{i})$. We obtain

$h(S)=\frac{\sum_{i}m(\partial
S_{i})}{\sum_{i}m(S_{i})}\geq\inf_{i}\left\\{\frac{m(\partial
S_{i})}{m(S_{i}}\right\\}=\inf_{i}\big{\\{}h(S_{i})\big{\\}}.$

Since $S_{i}$ is a Cheeger set for all $i$, the result follows from Definition
5(b). ∎

###  3.3. Examples

The Cheeger constant of a weighted graph depends not only on the structure of
the underlying graph, but also on its weight function. In this subsection, we
we consider two structurally very different graphs and equip each of them with
two different summable weight functions. Remarkably, both graphs exhibit a
vanishing Cheeger constant in one case and a large Cheeger constant in the
other.

######  Example 7 (The infinite complete graph with weight function $m_{1}$).

Denote by $K$ the infinite complete graph with vertex set
$\operatorname{V}(K)=\mathbb{N}$. We show below that different weight
functions on $K$ can lead to vastly different Cheeger constants.

Let $(p_{i})_{i\in\mathbb{N}}$ be a sequence of positive real numbers that sum
to one, $\sum_{i\in\mathbb{N}}p_{i}=1.$ We define a weight function $m_{1}$ on
the infinite complete graph $K$ by

$m_{1}(ij)=p_{i}\cdot p_{j},\quad i,j\in\mathbb{N}.$

We have $\sum_{ij}m(ij)=1$, i.e. this weight function is summable. Besides,
$m_{1}(i)=p_{i}-p_{i}^{2}$ and therefore
$m_{1}(\mathbb{N})=1-\sum_{i}p_{i}^{2}$. Every Cheeger set
$S\in\operatorname{\mathcal{V}}(K,m_{1})$ satisfies

$\displaystyle h(S)=\frac{\sum_{i\in S}p_{i}\cdot\sum_{j\not\in
S}p_{j}}{m_{1}(S)}>\frac{m_{1}(S)\cdot
m_{1}({S}^{\mathsf{c}})}{m_{1}(S)}\geq\frac{m_{1}(\mathbb{N})}{2}.$

Therefore, for the Cheeger constant one has

$h(K,m_{1})\geq\frac{m_{1}(\mathbb{N})}{2}.$

Example 7 shows that we can equip the infinite complete graph with a summable
weight function such that the Cheeger constant of the resulting weighted graph
is relatively large. Whilst it is tempting to attribute this observation
solely to the robustness of complete graphs, the following example suggests
otherwise. In section 8 we shall describe the spectrum of the weighted graph
$(K,m_{1})$ in more detail; in particular, we shall see that the spectral gap
equals 1, cf. Proposition 35.

######  Example 8 (The infinite complete graph with weight function $m_{2}$).

Now we define a different weight function $m_{2}$ on the infinite complete
graph $K$ via

$m_{2}(ij)=\begin{cases}\frac{1}{j^{2}}&\mbox{ if }|j-i|=1,\\\
\frac{1}{j!}&\mbox{ if }|j-i|>1,\end{cases}\quad\text{where }j>i.$

The weight function $m_{2}$ is summable:

$\sum_{ij}m(ij)=\sum_{i=1}^{\infty}\bigg{(}\frac{1}{i^{2}}+\frac{i-1}{i!}\bigg{)}<\infty.$

Write $T_{n}=\\{n,n+1,\ldots\\}$. The boundary and the interior of $T_{n}$
satisfy

$\displaystyle m_{2}(\partial T_{n})$
$\displaystyle=\frac{n-1}{n!}+\frac{1}{n^{2}}+n\cdot\sum_{i=n+1}^{\infty}\frac{1}{i!},$
$\displaystyle m_{2}\big{(}\operatorname{I}(T_{n})\big{)}$
$\displaystyle=\sum_{i=n+2}^{\infty}\frac{i-n-1}{i!}+\sum_{i=n+1}^{\infty}\frac{1}{i^{2}}\geq\frac{1}{4n}.$

With regard to the third summand in the first expression, we observe

$n\cdot\sum_{i=n+1}^{\infty}\frac{1}{i!}<n\cdot\frac{1}{n!}\cdot\sum_{i=1}^{\infty}\frac{1}{(n+1)^{i}}=\frac{1}{n!}.$

It follows that, for large $n$, the boundary of $T_{n}$ satisfies
$m_{2}(\partial T_{n})<\frac{3}{n^{2}}.$ Therefore,

$\frac{m_{2}\big{(}\operatorname{I}(T_{n})\big{)}}{m_{2}(\partial
T_{n})}>\frac{n^{2}}{3}\cdot\frac{1}{4n}\to\infty.$

Since

(8) $\displaystyle
h(T_{n})^{-1}-1=2\cdot\frac{m(\operatorname{I}(T_{n})}{m(\partial T_{n}))},$

it follows that the Cheeger constant of the weighted graph $(K,m_{2})$
vanishes, $h(K,m_{2})=0.$

Examples 7 and 8 illustrate the fact that the Cheeger constant $h(K,m)$
strongly depends on the weight function $m$. Below we analyse more examples of
this kind.

######  Example 9 (The Half-Line graph with weight function $m_{3}$).

The Half-Line graph, denoted by $H$, comprises the vertex set
$\operatorname{V}(H)=\mathbb{N}$ and edges of the form $e_{i}=\\{i-1,i\\}$ for
all $i\geq 1$. We define a weight function $m_{3}$ on the $H$ via
$m_{3}(e_{i})=i^{-2}.$ The weight function $m_{3}$ is summable as the series
$\sum_{i\geq 1}i^{-2}$ converges. We show below that $h(H,m_{3})=0$.

Write $T_{n}=\\{n,n+1,\ldots\\}\subset\operatorname{V}(H)$. The boundary and
interior of $T_{n}$ satisfy

$\displaystyle m_{3}(\partial{T_{n})}=n^{-2},\quad
m_{3}\big{(}\operatorname{I}({T_{n}})\big{)}=\sum_{i=n+1}^{\infty}i^{-2}.$

Therefore,

$\frac{m_{3}\big{(}\operatorname{I}({T_{n}})\big{)}}{m_{3}(\partial{T_{n})}}=n^{2}\cdot\sum_{i=n+1}^{\infty}i^{-2}\rightarrow\infty,$

which, by (8), gives $h(T_{n})\to 0$, implying $h(H,m_{3})=0.$

######  Example 10 (The Half-Line graph with weight function $m_{4}$).

Here we define another weight function on the Half-Line graph $H$:
$m_{4}(e_{i})=r^{i},$ where $r\in(0,1).$ We show below that the Cheeger
constant $h(H,m_{4})>0$.

As before, write $T_{n}=\\{n,n+1,\ldots\\}$. For $n>0$, one has
$m_{4}(\partial T_{n})=r^{n}$ and $m_{4}(T_{n})=r^{n}\cdot\frac{1+r}{1-r}$ and
therefore $h(T_{n})=\frac{1-r}{1+r}$ is independent of $n$. Note that
inequality (7) is satisfied for any $n$ large enough. We want to show that

(9) $\displaystyle h(H,m_{4})=h(T_{n})=\frac{1-r}{1+r}.$

By Lemma 6 we need to consider subsets $S\subset\operatorname{V}(H)$ such that
the induced subgraphs $H_{S}$ are connected; in other words $S$ must be an
interval, finite or infinite. Let $S=\\{i,\ldots,j\\}$ be a finite interval.
Then

$m_{4}(\partial S)=m_{4}(\partial T_{i})+r^{j-1},\quad
m_{4}(S)=m_{4}(T_{i})-m_{4}(T_{j+1}),$

and therefore

$h(S)=\frac{m_{4}(\partial S)}{m_{4}(S)}=\frac{m_{4}(\partial
T_{i})+r^{j-1}}{m_{4}(T_{i})-m_{4}(T_{j+1})}>h(T_{i})=\frac{1-r}{1+r}.$

This proves (9).

##  4\. The dual Cheeger constant

In [1], the authors introduced a new geometric constant, which they call the
dual Cheeger constant. The dual Cheeger inequalities state that this constant
controls the top of the spectrum of the Laplacian. The construction in [1] is
restricted to locally finite weighted graphs.

The purpose of this section is to introduce the notion of a dual Cheeger
constant adopted for weighted graphs with summable weight functions.

###  4.1. Definition of the dual Cheeger constant

For all $A,B\subset\operatorname{V}(G)$, denote by $\operatorname{E}(A,B)$ the
set of all edges connecting $A$ to $B$. The symbol $m(A,B)$ will denote
$m(\operatorname{E}(A,B)).$

######  Definition 11.

For $A,B\subset\operatorname{V}(G)$ with $A\cap B=\emptyset$,
$A\not=\emptyset\not=B$, write

(10) $\displaystyle\overline{h}(A,B)=\frac{2\cdot m(A,B)}{m(A)+m(B)}.$

The dual Cheeger constant of $(G,m)$, denoted by $\overline{h}(G,m)$, is
defined as

$\overline{h}(G,m)=\sup\big{\\{}\overline{h}(A,B)\big{\\}},$

where the supremum is taken over all disjoint nonempty sets of vertices $A,B$
in $G$.

Since $m(A)\geq m(A,B)$ and $m(B)\geq m(A,B)$, we see that
$\overline{h}(A,B)\leq 1$, and therefore

$\overline{h}(G,m)\leq 1$

for any weighted graph $(G,m)$.

If the graph $G$ is bipartite and $V(G)=A\sqcup B$ is a partition of the set
of vertexes such that all the edges connect $A$ to $B$, then $m(A)=m(A,B)$ and
$m(B)=m(A,B)$, which implies $\overline{h}(A,B)=1$, and therefore

(11) $\displaystyle\overline{h}(G,m)=1$

for any bipartite $(G,m)$.

The inequality $\overline{h}(G,m)<c$ is equivalent to the statement that, for
any pair of disjoint subsets $A,B\subset\operatorname{V}(G)$, one has the
inequality

(12) $\displaystyle m(A,B)\leq c\cdot\frac{m(A)+m(B)}{2}.$

In other words, the weight of the connecting edges between any pair of
disjoint subsets $A$ and $B$ is at most $c$ times the average weight of $A$
and $B$.

In [1], the authors consider locally finite weighted graphs $(G,m)$ whose
weight function is not necessarily summable. Given an exhaustion
$\Omega_{n}\uparrow\operatorname{V}(G)$ (a filtration of connected subsets
that converges to $\operatorname{V}(G)$), they write

$\overline{h}(\Omega_{n})=\sup\bigg{\\{}\frac{2\cdot
m(A,B)}{m(A)+m(B)}\bigg{\\}},$

where the supremum is taken over all disjoint nonempty subsets
$A,B\subset\Omega_{n}$. Hence, the authors define the dual Cheeger constant to
be the following limit:
$\overline{h}(G,m)=\lim_{n\rightarrow\infty}\overline{h}(\Omega_{n}).$ As the
authors of [1] show, this limit exists and it is independent of the
exhaustion. Whilst Definition 11 does not involve any such limit, our dual
Cheeger constant is equivalent to that in [1]; the difference lies in the
underlying weighted graphs.

###  4.2. Example of a non-bipartite graph with $\overline{h}(G,m)=1$

Consider the infinite graph $L$ shown on Figure 1; its vertexes are labelled
by $v_{0},v_{1},\dots$ and $w_{1},w_{2},\dots$. The graph $L$ is not bipartite
since it has a cycle of odd order. We set the weights as follows:
$m(v_{i}w_{i})=r^{i}$ and $m(v_{i}v_{i+1})=\rho^{i}$, where $0<\rho<r<1$;
besides, $m(v_{0}w_{1})=1$.

Figure 1. Non-bipartite graph $L$.

For $i>1$ we have $m(v_{i})=\rho^{i-1}+\rho^{i}+r^{i}$ and $m(w_{i})=r^{i}$.
Therefore, taking $A_{i}=\\{v_{i}\\}$ and $B_{i}=\\{w_{i}\\}$, where $i>1$, we
have

$\overline{h}(A_{i},B_{i})=\frac{2r^{i}}{2r^{i}+\rho^{i-1}+\rho^{i}}\to 1.$

Thus, we obtain $\overline{h}(L,m)=1$.

###  4.3. The same graph $L$ with a different weight function

Consider now the following weight function $m_{1}$ on the graph $L$ of the
previous example. The function $m_{1}$ is defined similarly to $m$ with the
only difference that now $\rho=r$, where $0<r<1$. In more detail,
$m_{1}(v_{i}w_{i})=r^{i}=m(v_{i}v_{i+1})$, and $m_{1}(v_{0}w_{1})=1$. Note
that $m(w_{i})=r^{i}$ for $i>1$, and $m(v_{i})=r^{i-1}+2r^{i}$ for $i>0$.
Besides, $m(w_{1})=1+r$ and $m(v_{0})=2$.

Suppose that $A,B\subset\operatorname{V}(G)$ are disjoint sets of vertexes and
for some $i\geq 1$ one has $v_{i}\in A$ and $w_{i}\in B$. Consider the
following modifications of the pair $A,B$. Let $A_{1}=A\cup\\{w_{i}\\}$ and
$B_{1}=B-\\{w_{i}\\}$. Besides, let $A_{2}=A$ and $B_{2}=B-\\{w_{i}\\}$. Since
the vertex $w_{i}$ is connected to the vertex $v_{i}$ only, by examining
formula (10) we easily see that $\overline{h}(A_{1},B_{1})<\overline{h}(A,B)$
and $\overline{h}(A_{2},B_{2})<\overline{h}(A,B)$. Thus, since we are
interested in pairs $A,B$ giving maximum to the dual Cheeger constant (10), we
may always assume that for each vertex $v_{i}\in A$ the corresponding vertex
$w_{i}$ belongs to $B$, and vice versa.

Next, for a pair of disjoint subsets $A,B\subset\operatorname{V}(G)$, suppose
that for some $i$ one has $v_{i},v_{i+1}\in A$ and $w_{i},w_{i+1}\in B$. We
can modify the sets by swapping the points $v_{i+1}$ and $w_{i+1}$, i.e.
$A^{\prime}=A-\\{v_{i+1}\\}\cup\\{w_{i+1}\\}$ and
$B^{\prime}=B-\\{w_{i+1}\\}\cup\\{v_{i+1}\\}$. Then examining (10) we see that
$\overline{h}(A^{\prime},B^{\prime})>h(A,B)$. Thus, we may only consider pairs
of disjoint subsets $A,B$ such that no neighbouring vertexes $v_{i},v_{i+1}$
lie in the same subset $A$ or $B$.

As another remark, consider a pair of disjoint subsets
$A,B\subset\operatorname{V}(G)$ such that $v_{i}\in A$ and $w_{i}\in B$ and
modify it as follows $A^{\prime}=A\cup\\{w_{i+1}\\}$ and
$B^{\prime}=B\cup\\{v_{i+1}\\}$. Then we easily see from (10) that
$\overline{h}(A^{\prime},B^{\prime})>\overline{h}(A,B)$.

Therefore, to determine $\overline{h}(G,m)$ we need to consider only pairs of
subsets $A,B$ where $A$ contains all points $v_{i}$ with $i=k+2\ell$, where
$\ell\geq 0$, and all points $w_{i}$ with $i=k+2\ell+1$, where $\ell\geq 0$;
the set $B$ is defined similarly with the letters $v$ and $w$ interchanged.
Here $k$ is a fixed integer $k\geq 1$. One finds that the dual Cheeger ratio
$\overline{h}(A,B)=\frac{4r}{3r+1}$ does not depend on $k$.

In the case $k=0$ we have to consider the slightly modified sets
$A=\\{v_{0},v_{1},w_{2},v_{3},\dots\\}$ and $B=\\{w_{1},v_{2},w_{3},\dots\\}$.
Computing the dual Cheeger ratio (10) gives $\overline{h}(A,B)=r$. Since
$r<\frac{4r}{3r+1}$ we conclude that $\overline{h}(G,m)=\frac{4r}{3r+1}<1$.

These two examples illustrate the possibility that the dual Cheeger constant
can be maximal and equal 1 for one weight function and be smaller than 1 for
another weight function.

##  5\. The Cheeger and dual Cheeger inequalities

In this section, we we show that the Cheeger constant and the dual Cheeger
constant control the spectral gap and the top of the spectrum of the
Laplacian, respectively. In particular, we prove the Cheeger inequalties and
the dual Cheeger inequalities for countable weighted graphs with summable
weight function. These inequalities give estimates on the spectral gap
$\lambda_{gap}(\Delta)=\inf\\{\lambda>0,\,\lambda\in\sigma(\Delta)\\}$ and the
top of the spectrum
$\lambda_{top}(\Delta)=\sup\\{\lambda\in\sigma(\Delta)\\}$.

######  Theorem 12 (Cheeger and dual Cheeger inequalities).

For any weighted graph $(G,m)$ with summable weight function one has

(13) $\displaystyle 1-\sqrt{1-h(G,m)^{2}}\,\leq\,$
$\displaystyle\lambda_{gap}(\Delta)\,\leq\,2\cdot h(G,m),$ (14) $\displaystyle
2\cdot\overline{h}(G,m)\,\leq\,$
$\displaystyle\lambda_{top}(\Delta)\,\leq\,1+\sqrt{1-\big{(}1-\overline{h}(G,m)\big{)}^{2}}.$

###### Proof.

For a subset $S\subset\operatorname{V}(G)$ satisfying $m(S)\leq
m(S^{\mathsf{c}})$ define the function $f_{S}\in L^{2}(G,m)$ such that
$f_{S}(v)=m(S)^{-1}$ for $v\in S$ and $f_{S}(v)=-m(S^{\mathsf{c}})^{-1}$ for
$v\in S^{c}$. Since $f_{S}\perp{\bf 1}$, we may apply (5) to get

$\displaystyle\lambda_{gap}(\Delta)$ $\displaystyle\leq\frac{\langle\Delta
f_{S},f_{S}\rangle}{\langle f_{S},f_{S}\rangle}=m(\partial
S)\cdot\big{(}\frac{1}{m(S)}+\frac{1}{m(S^{\mathsf{c}})}\big{)}\leq 2\cdot
h(S).$

Since this is true for all nonempty $S\subset\operatorname{V}(G)$ satisfying
(7), we obtain the right inequality in (13).

To prove the left inequality in (14), for a pair
$A,B\subset\operatorname{V}(G)$ of nonempty disjoint subsets define the
function $f_{A,B}\in L^{2}(G,m)$ as follows: (a) $f_{A,B}(v)=1$ for $v\in A$,
(b) $f_{A,B}(v)=-1$ for $v\in B$ and (c) $f_{A,B}(v)=0$ for
$v\in\operatorname{V}(G)-(A\cup B)$. Using the characterisation of
$\lambda_{top}(\Delta)$ in terms of Rayleigh quotients, we have

$\displaystyle\lambda_{top}(\Delta)$
$\displaystyle\geq\frac{\langle\Delta{f_{A,B}},{f_{A,B}}\rangle}{\langle{f_{A,B}},{f_{A,B}}\rangle}=2\cdot\overline{h}(A,B)+h(A\cup
B)\geq 2\cdot\overline{h}(A,B).$

Since this is true for all nonempty, disjoint subsets
$A,B\subset\operatorname{V}(G)$, the left inequality in (14) follows.

To continue with the proof of Theorem 12 we shall need to prepare certain
tools. The proof will be completed after Lemma 15.

######  Lemma 13 (Co-area formulae).

For a function $f\colon\operatorname{V}(G)\to$ and for $t\in$ we shall denote
$P_{t}(f)=\\{v\in\operatorname{V}(G);f(v)>t\\}$. Then for every $f\in
L^{2}(G,m)$ one has

  * (a)

$\displaystyle\;\;\int_{0}^{\infty}m\big{(}P_{t}(f^{2})\big{)}dt=\sum_{v\in\operatorname{V}(G)}m(v)\cdot
f(v)^{2},$

  * (b)

$\displaystyle\int_{0}^{\infty}m\big{(}\partial
P_{t}(f^{2})\big{)}dt=\sum_{uv\in\operatorname{E}(G)}m(uv)\cdot|f^{2}(u)-f^{2}(v)|.$

###### Proof.

The superlevel sets of $f^{2}$ satisfy $v\in
P_{t}(f^{2})\iff\mathbbm{1}_{(t,\infty)}\big{(}f^{2}(v)\big{)}=1.$ Therefore,

$\displaystyle{}\int_{0}^{\infty}m\big{(}P_{t}(f^{2})\big{)}dt=\int_{0}^{\infty}\sum_{v\in\operatorname{V}(G)}m(v)\cdot\mathbbm{1}_{(t,\infty)}\big{(}f^{2}(v)\big{)}dt$
$\displaystyle=\sum_{v\in\operatorname{V}(G)}m(v)\cdot\int_{0}^{\infty}\mathbbm{1}_{(t,\infty)}\big{(}f^{2}(v)\big{)}dt=\sum_{v\in\operatorname{V}(G)}m(v)\cdot
f^{2}(v).$

For any two vertices $u$ and $v$, define
$I_{uv}=\Big{[}\min\big{\\{}f^{2}(u),f^{2}(v)\big{\\}},\max\big{\\{}f^{2}(u),f^{2}(v)\big{\\}}\Big{)}$.
Then,

$\displaystyle\int_{0}^{\infty}m\big{(}\partial
P_{t}(f^{2})\big{)}dt=\int_{0}^{\infty}\sum_{uv\in\operatorname{E}(G)}m(uv)\cdot\mathbbm{1}_{I_{uv}}(t)dt$
$\displaystyle=\sum_{uv\in\operatorname{E}(G)}m(uv)\cdot\int_{0}^{\infty}\mathbbm{1}_{I_{uv}}(t)dt=\sum_{uv\in\operatorname{E}(G)}m(uv)\cdot|g^{2}(u)-g^{2}(v)|.$

∎

Consider the operator $Q=2I-\Delta\colon L^{2}(G,m)\to L^{2}(G,m)$. We have
$\lambda\in\sigma(\Delta)$ if and only if $2-\lambda\in\sigma(Q)$. Therefore,
$2-\lambda_{top}(\Delta)$ equals the bottom of the spectrum of $Q$, i.e.

(15) $\displaystyle 2-\lambda_{top}(\Delta)=\inf\left\\{\frac{\langle
Qf,f\rangle}{\langle f,f\rangle};f\not=0\right\\}$

A straightforward computation shows that for $f\in L^{2}(G,m)$, one has

(16) $\displaystyle\langle
Qf,f\rangle=\sum_{vw\in\operatorname{E}(G)}m(vw)\cdot(f(v)+f(w))^{2}.$

######  Lemma 14.

For any function $f\in L^{2}(G,m)$, $f\not\equiv 0$, one has the inequalities

(17) $\displaystyle
1-\sqrt{1-h(f)^{2}}\leq\frac{\langle\Delta{f},{f}\rangle}{\langle{f},{f}\rangle}\leq
1+\sqrt{1-h(f)^{2}}.$

where the number $h(f)\geq 0$ is defined as the infimum of the Cheeger ratios
$h(S)=m(\partial S)m(S)^{-1}$ taken over all nonempty subsets
$S\subset\\{v;f(v)\neq 0\\}$.

###### Proof.

Consider the expressions $A=\langle Qf,f\rangle\cdot\langle\Delta f,f\rangle$
and $B=\langle Qf,f\rangle\cdot\langle f,f\rangle.$ From (3), (16) and the
Cauchy-Schwarz inequality we obtain

$\displaystyle A^{1/2}$
$\displaystyle=\Big{(}\sum_{vw\in\operatorname{E}(G)}m(vw)\cdot\big{(}f(v)+f(w)\big{)}^{2}\Big{)}^{1/2}\cdot\Big{(}\sum_{vw\in\operatorname{E}(G)}m(vw)\cdot\big{(}f(v)-f(w)\big{)}^{2}\Big{)}^{1/2}$
$\displaystyle\geq\sum_{vw\in\operatorname{E}(G)}m(vw)\cdot|f(v)^{2}-f(w)^{2}|=\int_{0}^{\infty}m\big{(}\partial
P_{t}(f^{2})\big{)}dt$ $\displaystyle=\int_{0}^{t^{*}}\frac{m\big{(}\partial
P_{t}(f^{2})\big{)}}{m\big{(}P_{t}(f^{2})\big{)}}\cdot
m\big{(}P_{t}(f^{2})\big{)}dt$ $\displaystyle\geq
h(f^{2})\cdot\int_{0}^{\infty}m(P_{t}(f^{2}))dt=h(f)\cdot\langle f,f\rangle.$

The two bottom lines use Lemma 13; the finite or infinite value $t^{*}$ is
defined by $t^{*}=\sup\\{f^{2}\\};$ it is introduced in order to avoid
division by 0. Thus we have $A\geq h(f)^{2}\cdot||f||^{4}$. We also have
$B=\Big{(}2-\frac{\langle\Delta f,f\rangle}{\langle
f,f\rangle}\Big{)}\cdot||f||^{4}$. Dividing we obtain that the quotient
$\frac{\langle\Delta{f},{f}\rangle}{\langle{f},{f}\rangle}=AB^{-1}$ satisfies
the inequality

$AB^{-1}\geq\frac{h(f)^{2}}{2-AB^{-1}}.$

Solving this quadratic inequality for $AB^{-1}$ gives (17). ∎

Next, we observe that for any nonzero $g\in L^{2}(G,m)$ one can find a real
number $\tau=\tau(g)$ such that

(18) $\displaystyle
m(g^{-1}(-\infty,\tau))\,\leq\,m(\operatorname{V}(G))/2\quad\mbox{and}\quad
m(g^{-1}(\tau,\infty))\,\leq\,m(\operatorname{V}(G))/2.$

Indeed, it is easy to see that one can take
$\tau=\sup\\{t;\,m(g^{-1}(-\infty,t))<m(\operatorname{V}(G))/2\\}$.

Define the functions $g_{+},g_{-}\in L^{2}(G,m)$ by

$g_{+}(v)=\max\\{g(v)-\tau(g),0\\}\quad\mbox{and}\quad
g_{-}(v)=\max\\{\tau(g)-g(v),0\\}.$

Then

(19) $\displaystyle g=g_{+}-g_{-}+\tau,\quad\quad g_{+}g_{-}=0,$

and $h(G,m)\leq\min\\{h(g_{+}),h(g_{-})\\}$ because of (18). If
$g\perp\mathbf{1}$ then $\langle g,g\rangle$ can be estimates as follows:

$\displaystyle\langle g,g\rangle$ $\displaystyle=$ $\displaystyle\sum
m(v)g(v)^{2}\,\leq\,\sum m(v)(g(v)-\tau)^{2}=\sum
m(v)(g_{+}(v)^{2}+g_{-}(v)^{2})$ $\displaystyle=$ $\displaystyle\langle
g_{+},g_{+}\rangle+\langle g_{-},g_{-}\rangle.$

Besides,

(21) $\displaystyle\langle\Delta g,g\rangle$ $\displaystyle=$
$\displaystyle\sum m(vw)(g(u)-g(v))^{2}$ $\displaystyle\geq$
$\displaystyle\sum
m(uv)((g_{+}(u)-g_{+}(v))^{2}+(g_{-}(u)-g_{-}(v))^{2})=\langle\Delta
g_{+},g_{+}\rangle+\langle\Delta g_{-},g_{-}\rangle$

Indeed, if the vertexes $u,v$ are such that $g(v)<\tau<g(u)$ then

$\displaystyle(g(u)-g(v))^{2}$ $\displaystyle=$
$\displaystyle(g_{+}(u)-g_{-}(v))^{2}\,\geq\,g_{+}(u)^{2}+g_{-}(v)^{2}$
$\displaystyle=$
$\displaystyle(g_{+}(u)-g_{+}(v))^{2}+(g_{-}(u)-g_{-}(v))^{2}.$

Thus, for $g\perp\mathbf{1}$, using (5) and (21) we obtain

$\displaystyle\frac{\langle\Delta g,g\rangle}{\langle g,g\rangle}$
$\displaystyle\geq$ $\displaystyle\min\\{\frac{\langle\Delta
g_{+},g_{+}\rangle}{\langle g_{+},g_{+}\rangle},\frac{\langle\Delta
g_{-},g_{-}\rangle}{\langle g_{-},g_{-}\rangle}\\}$ $\displaystyle\geq$
$\displaystyle\min\\{1-\sqrt{1-h(g_{+})^{2}},\,1-\sqrt{1-h(g_{-})^{2}}\\}\,\geq\,1-\sqrt{1-h(G,m)^{2}}.$

This proves the left inequality in (13).

Finally, we prove the right inequality (14), i.e. the upper bound for the
$\lambda_{top}$. We shall use the idea of [1] and adopt their arguments to our
situation.

Given a nonzero function $f\in L^{2}(G,m)$ we consider the auxiliary weighted
graph $(G_{f},m_{f})$ which is constructed as follows. For each vertex
$v\in\operatorname{V}(G)$ with $f(v)\not=0$ we create an additional vertex
$v^{\prime}$ and the vertex set of the new graph $G_{f}$ equals
$\operatorname{V}(G_{f})=\operatorname{V}(G)\cup\\{v^{\prime};\,v\in\operatorname{V}(G),f(v)\not=0\\}.$

Next, we describe the set of edges of $G_{f}$. We remove every edge
$vw\in\operatorname{E}(G)$ with $f(v)f(w)>0$ and replace it with the edges
$vw^{\prime}$ and $v^{\prime}w$ of $\operatorname{E}(G_{f})$. All edges $vw$
of $G$ satisfying $f(v)f(w)\leq 0$ are included into $E(G_{f})$.

The weight function $m_{f}$ on $G_{f}$ is defined as follows: firstly,
$m_{f}(v^{\prime}w)=m_{f}(vw^{\prime})=m(vw)$ and, secondly, for every edge
$vw\in\operatorname{E}(G)$ with $f(v)f(w)\leq 0$ we set $m_{f}(vw)=m(vw).$

Note that the weights of vertexes $v\in\operatorname{V}(G)$ remain unchanged:
$m_{f}(v)=m(v)$. Besides, the weights of the new vertexes $v^{\prime}$ satisfy
$m_{f}(v^{\prime})\leq m(v)$.

Consider the function $f^{\prime}\in L^{2}(G_{f},m_{f})$ defined by
$f^{\prime}(v^{\prime})=0$ and $f^{\prime}(v)=|f(v)|$ for
$v\in\operatorname{V}(G)$.

######  Lemma 15.

One has

(22) $\displaystyle\frac{\langle Qf,f\rangle}{\langle
f,f\rangle}\geq\frac{\langle\Delta f^{\prime},f^{\prime}\rangle_{f}}{\langle
f^{\prime},f^{\prime}\rangle_{f}},$

where $\langle\cdot,\cdot\rangle_{f}$ denotes the scalar product in
$L^{2}(G_{f},m_{f})$.

###### Proof.

Firstly, $\langle
f,f\rangle=\sum_{v\in\operatorname{V}(G)}m(v)f(v)^{2}=\sum_{v\in\operatorname{V}(G_{f})}m_{f}(v)f^{\prime}(v)^{2}=\langle
f^{\prime},f^{\prime}\rangle_{f}.$ Next we show

(23) $\displaystyle\langle Qf,f\rangle\geq\langle\Delta
f^{\prime},f^{\prime}\rangle_{f}.$

If $vw$ is an edge in $G$ with $f(v)f(w)>0$, then

$\displaystyle m(vw)(f(v)+f(w))^{2}$ $\displaystyle\geq$ $\displaystyle
m(vw)(f(v)^{2}+f(w)^{2})=m_{f}(vw^{\prime})f^{\prime}(v)^{2}+m_{f}(v^{\prime}w)f^{\prime}(w)^{2}$
$\displaystyle=$ $\displaystyle
m_{f}(vw^{\prime})(f^{\prime}(v)-f^{\prime}(w^{\prime}))^{2}+m_{f}(v^{\prime}w)(f^{\prime}(v^{\prime})-f^{\prime}(w))^{2}.$

Besides, for an edge $vw\in\operatorname{E}(G)$ with $f(v)f(w)\leq 0$ one has

$m(vw)(f(v)+f(w))^{2}=m_{f}(vw)(f^{\prime}(v)-f^{\prime}(w))^{2}.$

Incorporating the above information into (3) and (16) we obtain (23) and hence
(22). ∎

We intend to use the left inequality in (17) applied to $f^{\prime}$ viewed as
an element of $L^{2}(G_{f},m_{f})$. The number $h_{f}(f^{\prime})$ is defined
as the infimum of the ratios $h_{f}(S)=m_{f}(\partial S)m_{f}(S)^{-1}$, where
$S$ runs over subsets of the support of $f^{\prime}$. In our case the support
of $f^{\prime}$ lies in $\operatorname{V}(G)\subset\operatorname{V}(G_{f})$
and can be represented as the disjoint union ${\sf supp}(f)_{+}\sqcup{\sf
supp}(f)_{-}$, where ${\sf supp}(f)_{+}$ is the set of all vertexes
$v\in\operatorname{V}(G)$ where $f$ is positive and ${\sf supp}(f)_{-}$ is the
set of all vertexes $v\in\operatorname{V}(G)$ with $f(v)<0$. Thus, any subset
$S\subset{\sf supp}(f)$ is the disjoint union $S=S_{+}\sqcup S_{-}$ where
$S_{\pm}=S\cap{\sf supp}(f)_{\pm}$. In the graph $G_{f}$ there are no edges
internal to $S_{+}$ and there are no edges internal to $S_{-}$. Thus, we
obtain

$m_{f}(S)=m(S)=m_{f}(\partial_{f}S)+2m(S_{+},S_{-}).$

Therefore, we see that

$h_{f}(S)=\frac{m_{f}(S)-2m(S_{+},S_{-})}{m_{f}(S)}=1-\frac{2m(S_{+},S_{-})}{m(S_{+})+m(S_{-})}=1-\overline{h}(S_{+},S_{-}).$

Taking the infimum over $S\subset{\sf supp}f$ we obtain the inequality

(24) $\displaystyle h_{f}(f^{\prime})\geq 1-\overline{h}(G,m).$

Now we can obtain the desired upper bound for
$\lambda_{top}=\lambda_{top}(\Delta)$. We have

$\displaystyle 2-\lambda_{top}=\inf_{f\not=0}\frac{\langle
Qf,f\rangle}{\langle f,f\rangle}\geq\inf_{f\not=0}\frac{\langle\Delta
f^{\prime},f^{\prime}\rangle_{f}}{\langle
f^{\prime},f^{\prime}\rangle_{f}}\geq 1-\sqrt{1-h_{f}(f^{\prime})^{2}}\geq
1-\sqrt{1-(1-\overline{h}(G,m))^{2}}.$

This completes the proof of Theorem 12. ∎

######  Remark 16.

Theorem 13.4 from the book [7] is a corollary of the left part of the first
inequality of Theorem 12.

##  6\. A new combinatorial invariant

In this section we introduce a new combinatorial invariant of countable graphs
with summable weight functions. We show that this invariant is a measure of
spectral asymmetry. We describe relations between the new invariant and the
Cheeger and the dual Cheeger constants.

###  6.1. Definition

Let $G$ be a connected countable graph and let
$m:\operatorname{E}(G)\to(0,\infty)$ be a summable weight function. For any
vertex $v\in\operatorname{V}(G)$ and any subset $S\subset\operatorname{V}(G)$
we write

(25) $\displaystyle m_{S}(v)=\sum_{w\in S}m(vw)\quad\mbox{and}\quad
p_{S}(v)=\frac{m_{S}(v)}{m(v)}.$

If we think of the underlying weighted graph as a Markov chain, then
$p_{S}(v)$ is the probability that the particle starting at $v$ ends up in $S$
in one step. If $A\sqcup B=\operatorname{V}(G)$ is a partition of the vertex
set with $A\not=\emptyset\not=B$, then

$p_{A}(v)+p_{B}(v)=1\quad\mbox{for any}\quad v\in\operatorname{V}(G).$

######  Definition 17.

For a partition $A\sqcup B=\operatorname{V}(G)$ of the vertex set we define

(26) $\displaystyle{\sf k}(A,B)=\max\\{\sup_{v\in A}p_{A}(v),\sup_{w\in
B}p_{B}(w)\\}.$

Finally, we associate the following constant ${\sf k}(G,m)$ to the weighted
graph:

(27) $\displaystyle{\sf k}(G,m)=\inf{\sf k}(A,B);$

the infimum is taken over all partitions $A\sqcup B=\operatorname{V}(G)$.

The inequality ${\sf k}(G,m)>c$ means that for any partition $A\sqcup
B=\operatorname{V}(G)$ there exists either $v\in A$ or $w\in B$ such that one
of the inequalities $p_{A}(v)>c$ or $p_{B}(w)>c$ holds. The constant ${\sf
k}(G,m)$ is the supremum of the numbers $c$ for which this graph property
holds.

###  6.2. Characterisation of bipartite graphs

######  Theorem 18.

One has ${\sf k}(G,m)\geq 0$ for any weighted graph $(G,m)$. Moreover, ${\sf
k}(G,m)=0$ if and only if the graph $G$ is bipartite.

###### Proof.

The inequality ${\sf k}(G,m)\geq 0$ is obvious from the definition.

If $G$ is bipartite and $\operatorname{V}(G)=A\sqcup B$ is a partition such
that every edge goes from $A$ to $B$, then $p_{A}(v)=0$ for $v\in A$ and
$p_{B}(w)=0$ for $w\in B$ implying ${\sf k}(A,B)=0$ and therefore ${\sf
k}(G,m)=0$.

Let $(G,m)$ be a summable weighted graph with $k(G,m)=0$. Let $A_{n}\sqcup
B_{n}=\operatorname{V}(G)$ be a sequence of partitions with ${\sf
k}(A_{n},B_{n})\to 0$. Suppose that it is not bipartite. Then $G$ admits a
cycle $C$ of odd length. For each edge $vw$ of the cycle $C$ consider the
quantity

(28) $\displaystyle
a(vw)=\min\left\\{\frac{m(vw)}{m(v)},\frac{m(vw)}{m(w)}\right\\}>0$

and choose $n$ so large that

(29) $\displaystyle a(vw)>{\sf k}(A_{n},B_{n})\quad\mbox{for any edge $vw$ of
$C$.}$

Using the definition of ${\sf k}(A_{n},B_{n})$ we see that every edge $vw$ of
$C$ connects a vertex of $A_{n}$ with a vertex of $B_{n}$. Indeed, if $v,w\in
A_{n}$ then ${\sf k}(A_{n},B_{n})\geq
p_{A_{n}}(v)\geq\frac{m(vw)}{m(v)}=a(vw)$ contradicting (29). This leads to
contradiction with the fact that the cycle $C$ has odd length. ∎

######  Remark 19.

Recall that the equality $\overline{h}(G,m)=1$ only partially characterises
the class of bipartite graphs, see (11) and Example 4.2. In contrast, by
Theorem 18, the equality ${\sf k}(G,m)=0$ gives a complete characterisation.

######  Example 20.

Let $G$ be a complete graph on $n+1$ vertexes. We equip $G$ with the counting
weight function, i.e. $m(vw)=1$ for every edge. If $A\sqcup
B=\operatorname{V}(G)$ is a partition with $|A|\leq|B|$ then

${\sf
k}(A,B)=\max\left\\{\frac{|A|-1}{n},\frac{|B|-1}{n}\right\\}=\frac{|B|-1}{n}$

and we obtain

$\displaystyle{\sf k}(G,m)=n^{-1}\cdot\lceil\frac{n-1}{2}\rceil.$

Thus, ${\sf k}(G,m)=1/2-1/(2n)$ for $n$ odd and ${\sf k}(G,n)=1/2$ for $n$
even.

######  Example 21.

Let $C_{n}$ be the cycle of order $n$ with the counting weight function $m$,
i.e. the weight of each edge equals 1. Then ${\sf k}(C_{n},m)=0$ for $n$ even
(since then $C_{n}$ is bipartite) and ${\sf k}(C_{n})=1/2$ for $n$ odd.
Indeed, for $n$ odd, for any partition $A\sqcup B$ of the vertex set one of
the sets $A$ or $B$ must contain two adjacent vertexes and therefore one of
the numbers $p_{A}(v)$ or $p_{B}(w)$ is $\geq 1/2.$

It is obvious that ${\sf k}(G,m)\leq 1$. In all examples known to us we have
${\sf k}(G,m)\leq 1/2$, but we do not know if this inequality is true in
general.

###  6.3. Relation with the dual Cheeger constant

Next we describe inequalities relating the new invariant ${\sf k}(G,m)$ with
$\overline{h}(G,m)$. We shall frequently use the inequlity

(30)
$\displaystyle\min\\{\frac{a}{c},\frac{b}{d}\\}\,\leq\,\frac{a+b}{c+d}\,\leq\,\max\\{\frac{a}{c},\frac{b}{d}\\},$

where $a,b,c,d>0$.

For a subset of vertexes $A\subset\operatorname{V}(G)$ we shall denote

$R_{A}=\frac{2\cdot m(A,A)}{m(A)}.$

######  Lemma 22.

For any partition $A\sqcup B=\operatorname{V}(G)$ of the set of vertexes of a
summable weighted graph $(G,m)$ one has

(31) $\displaystyle\min\\{R_{A},R_{B}\\}\leq
1-\overline{h}(A,B)\leq\max\\{R_{A},R_{B}\\}\leq{\sf k}(A,B).$

###### Proof.

Since $m(A)=2m(A,A)+m(A,B)$ we have

$1-\overline{h}(A,B)=2\cdot\frac{m(A,A)+m(B,B)}{m(A)+m(B)}$

and using (30) we obtain the left and the central inequalities in (31). The
right inequality in (31) follows from $R_{A}\leq\sup_{v\in A}\\{p_{A}(v)\\}$
and $R_{B}\leq\sup_{w\in B}\\{p_{B}(w)\\},$ which are consequences of (30) as
well. ∎

Next we state a relationship between ${\sf k}(G,m)$ and the dual Cheeger
constant.

######  Corollary 23.

For any summable weighted graph $(G,m)$ one has

(32) $\displaystyle\overline{h}(G,m)+{\sf k}(G,m)\geq 1.$

###### Proof.

The statement follows by taking infimum of the both sides of (31). ∎

Below is a relation between the quantities $R_{A}$ and $R_{B}$ and the Cheeger
constant:

######  Lemma 24.

The Cheeger constant $h(G,m)$ of a summable weighted graph $(G,m)$ equals

(33) $\displaystyle 1-\sup_{A,B}\min\\{R_{A},R_{B}\\},$

where the supremum is taken with respect to all nonempty
$A,B\subset\operatorname{V}(G)$ that partition $\operatorname{V}(G)$.

###### Proof.

We may write

$R_{A}=\frac{2\cdot m(A,A)}{m(A)}=\frac{m(A)-m(\partial A)}{m(A)}=1-h(A)$

and similarly $R_{B}=1-h(B)$. Thus,

$h(G,m)=\inf_{A,B}\max\\{h(A),h(B)\\}=\inf_{A,B}\max\\{1-R_{A},1-R_{B}\\}=1-\sup_{A,B}\min\\{R_{A},R_{B}\\}.$

∎

##  7\. Measure of asymmetry of the spectrum

Recall that for a pair of non-empty subsets $X$ and $Y$ of a metric space,
their Hausdorff distance $d_{H}(X,Y)$ is defined as

${\displaystyle d_{\mathrm{H}}(X,Y)=\max\left\\{\,\sup_{x\in
X}d(x,Y),\,\sup_{y\in Y}d(X,y)\,\right\\},\\!}$

Equivalently,

$d_{\mathrm{H}}(X,Y)=\inf\\{\epsilon\geq 0;X\subset
Y_{\epsilon}\,\,\mbox{and}\,\,Y\subset X_{\epsilon}\\}$

where ${\displaystyle X_{\epsilon}=\bigcup_{x\in X}\\{z\in M\,;\
d(z,x)\leq\epsilon\\}}.$

In this section we consider a summable weighted graph $(G,m)$ and the spectrum
$\sigma(\Delta)\subset[0,2]$ of its Laplacian $\Delta:L^{2}(G,m)\to
L^{2}(G,m)$, see (1) and Lemma 2. The main result of this section, Theorem 25,
describes the asymmetry of the spectrum $\sigma(\Delta)$ in terms of the
invariant ${\sf k}(G,m)$ introduced in the previous section.

######  Theorem 25.

Let $\mathcal{R}:[0,2]\to[0,2]$ denote the reflection $\mathcal{R}(x)=2-x$.
The Hausdorff distance between the spectrum of the Laplacian $\sigma(\Delta)$
and its reflection $\mathcal{R}(\sigma(\Delta))$ is at most $2\cdot{\sf
k}(G,m)$, i.e.

(34) $\displaystyle
d_{\mathrm{H}}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))\leq 2\cdot{\sf
k}(G,m).$

The following simple observation will be useful.

######  Lemma 26.

For any subset $X\subset[0,2]$, the Hausdorff distance
$d_{\mathrm{H}}(X,\mathcal{R}(X))$ equals
$\inf\\{\epsilon>0;\mathcal{R}(X)\subset X_{\epsilon}\\}$.

###### Proof.

Since $\mathcal{R}$ is an involution and an isometry, the relation
$\mathcal{R}(X)\subset X_{\epsilon}$ implies

$X=\mathcal{R}(\mathcal{R}(X))\subset\mathcal{R}(X_{\epsilon})=\mathcal{R}(X)_{\epsilon}.$

The statement now follows from the definition of the Hausdorff distance. ∎

The proof of Theorem 25 is completed by the end of this section.

Recall that the Laplacian $\Delta\colon L^{2}(G,m)\to L^{2}(G,m)$ equals $I-P$
where $I$ is the identity operator and $P\colon L^{2}(G,m)\to L^{2}(G,m)$ is
given by formula (4).

Let $\psi\colon\operatorname{V}(G)\rightarrow$ be a function satisfying
$\psi^{2}\equiv 1$. Consider the associated partition of the vertex set
$A\sqcup B=\operatorname{V}(G)$ where $A=\psi^{-1}(1)$ and $B=\psi^{-1}(-1)$.
We obtain the decomposition of $L^{2}(G,m)$ into the direct sum of two Hilbert
spaces

(35) $\displaystyle L^{2}(G,m)\,=\,L^{2}(A,m)\oplus L^{2}(B,m).$

Here $L^{2}(A,m)\subset L^{2}(G,m)$ is the space of functions $f\in
L^{2}(G,m)$ with ${\sf supp}(f)\subset A$ and similarly for $L^{2}(B,m)$.
Denote by

$\pi_{A},\pi_{B}:L^{2}(G,m)\to L^{2}(G,m)$

the projections

$\pi_{A}(f)|_{A}=f|_{A},\quad\pi_{A}(f)|_{B}=0,$

and similarly for $\pi_{B}$. Clearly, the operators $\pi_{A},\pi_{B}$ are
self-adjoint. Write

$T_{\psi}=\pi_{A}-\pi_{B}\quad\mbox{and}\quad P_{\psi}=P_{A}+P_{B},$

viewed as operators $L^{2}(G,m)\to L^{2}(G,m)$, where

$P_{A}=\pi_{A}P\pi_{A}:L^{2}(A,m)\to L^{2}(A,m)\quad\mbox{and}\quad
P_{B}=\pi_{B}P\pi_{B}:L^{2}(B,m)\to L^{2}(B,m).$

The operators $P_{A}$ and $P_{B}$ are self-adjoint since they are compositions
of self-adjoint operators.

######  Lemma 27.

One has

$T_{\psi}^{-1}\Delta T_{\psi}=2\cdot I-\Delta-2\cdot P_{\psi}$

and therefore

(36) $\displaystyle\sigma(\Delta)=\sigma(2\cdot I-\Delta-2\cdot P_{\psi}).$

###### Proof.

Since $T_{\psi}^{-1}=T_{\psi}$ one has

$\displaystyle T_{\psi}^{-1}\Delta T_{\psi}$ $\displaystyle=$
$\displaystyle(\pi_{A}-\pi_{B})(I-P)(\pi_{A}-\pi_{B})$ $\displaystyle=$
$\displaystyle I-(\pi_{A}-\pi_{B})P(\pi_{A}-\pi_{B})$ $\displaystyle=$
$\displaystyle I+\pi_{A}P\pi_{B}+\pi_{B}P\pi_{A}-P_{A}-P_{B}$ $\displaystyle=$
$\displaystyle I+P-2\cdot(P_{A}+P_{B})$ $\displaystyle=$ $\displaystyle 2\cdot
I-\Delta-2\cdot P_{\psi}.$

This proves the first claim of the Lemma. The second claim follows as well
using the fact that the spectrum is invariant under conjugation. ∎

Next we show that the norm of the operator $P_{\psi}$ can be estimated using
the combinatorial invariant ${\sf k}(A,B)$, which is introduced in §6.

######  Lemma 28.

Let $(G,m)$ be a summable weighted graph. Let
$\psi\colon\operatorname{V}(G)\rightarrow$ be a function satisfying
$\psi^{2}\equiv 1$ and let $A\sqcup B=\operatorname{V}(G)$ be the associated
partition of the vertex set $\operatorname{V}(G)$, where $\psi|_{A}\equiv 1$
and $\psi|_{B}\equiv-1$. Then one has

(37) $\displaystyle||P_{\psi}||\leq{\sf k}(A,B).$

###### Proof.

Since $P_{\psi}$ is self-adjoint, its norm $||P_{\psi}||$ equals the supremum
of

$\frac{|\langle P_{\psi}f,f\rangle|}{\langle f,f\rangle}$

taken over all nonzero $f\in L^{2}(G,m)$, see [8], §9.2. By construction,
$P_{\psi}$ is the direct sum of the operators $P_{A}$ and $P_{B}$ and we show
below that

(38) $\displaystyle||P_{A}||\leq\sup_{v\in
A}\\{p_{A}(v)\\}\quad\mbox{and}\quad||P_{B}||\leq\sup_{v\in B}\\{p_{B}(v)\\},$

where for $v\in A$ the quantity $p_{A}(v)$ is defined as $m(v)^{-1}\sum_{w\in
A}m(vw)$ and similarly for $p_{B}(v)$. Clearly, due to the definition of ${\sf
k}(A,B)$, (38) implies (37) and thus we only need to prove the inequality
(38).

For $f\in L^{2}(A,m)$ we have $(P_{A}f)(v)=m(v)^{-1}\cdot\sum_{w\in
A}m(vw)f(w)$ and therefore

$\displaystyle\langle P_{A}f,f\rangle$ $\displaystyle=$
$\displaystyle\sum_{v,w\in A}m(vw)f(v)f(w)$ $\displaystyle\leq$ $\displaystyle
1/2\cdot\sum_{v,w\in A}m(vw)[f(v)^{2}+f(w)^{2}]=\sum_{v,w\in A}m(vw)f(v)^{2}$
$\displaystyle=$ $\displaystyle\sum_{v\in A}m(v)\cdot\left[\sum_{w\in
A}\frac{m(vw)}{m(v)}\right]f(v)^{2}=\sum_{v\in A}m(v)\cdot p_{A}(v)\cdot
f(v)^{2}$ $\displaystyle\leq$ $\displaystyle\sup_{v\in
A}\,\\{p_{A}(v)\\}\cdot||f||^{2}.$

This gives the left inequality (38); the right one follows similarly. ∎

Lemma 28 implies:

######  Corollary 29.

One has

$\inf_{\psi}\big{\\{}||P_{\psi}||\big{\\}}\leq{\sf k}(G,m),$

where the infimum is taken over all functions
$\psi\colon\operatorname{V}(G)\rightarrow$ satisfying $\psi^{2}\equiv 1$.

###### Proof of Theorem 25.

Using (36) together with an obvious equality
$\sigma(2I-\Delta))=\sigma(\mathcal{R}(\Delta))=\mathcal{R}(\sigma(\Delta))$
and Theorem 4.10 from [6] we have

$\displaystyle
d_{\mathrm{H}}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))=d_{\mathrm{H}}(\sigma(2I-\Delta-2\cdot
P_{\psi}),\sigma(2I-\Delta))\leq 2\cdot||P_{\psi}||.$

The LHS of this inequality is independent of $\psi$. Taking infimum with
respect to $\psi$ and applying Corollary 29 we arrive at (34). ∎

##  8\. The spectrum of the infinite complete graph

We start with the following general remark about summable weighted graphs.

######  Lemma 30.

Let $(G,m)$ be a summable weight graph. Consider the random walk operator
$P\colon L^{2}(G,m)\to L^{2}(G,m)$, where

$(Pf)(v)=\sum_{w}\frac{m(vw)}{m(v)}\cdot f(w).$

Then $P$ is a Hilbert-Schmidt operator if and only if

(39) $\displaystyle\sum_{v,w}\frac{m(vw)^{2}}{m(v)m(w)}<\infty.$

###### Proof.

Let $g_{v}\in L^{2}(G,m)$ be the function taking the value $m(v)^{-1/2}$ at
point $v$ and vanishing at all other points. Clearly, the system

$\\{g_{v};v\in\operatorname{V}(G)\\}$

is an orthonormal basis. The matrix coefficients of the operator $P$ in this
basis are

$\langle
Pg_{w},g_{v}\rangle=\sum_{a\in\operatorname{V}(G)}m(a)(Pg_{w})(a)g_{v}(a)=\frac{m(vw)}{\sqrt{m(v)m(w)}}.$

Thus, condition (39) is equivalent to the well-known criterion for Hilbert-
Schmidt operators. ∎

######  Example 31.

Consider again the weighted graph $(G,m)$ of Example 7, i.e. $G$ is the
infinite complete graph with vertex set $\mathbb{N}$ and with the weights

$m(ij)=p_{i}p_{j}\quad\mbox{where }\quad p_{1}\geq p_{2}\geq
p_{3}\geq\dots,\quad\sum_{i\geq 1}p_{i}=1.$

The weights of vertexes are $m(i)=p_{i}q_{i}$, where $q_{i}=1-p_{i}$.
Condition (39) requires in this case convergence of the series

$\sum_{i\not=j}\frac{(p_{i}p_{j})^{2}}{p_{i}q_{i}p_{j}q_{j}}\leq\sum_{i,j}\frac{p_{i}p_{j}}{q_{i}q_{j}}=\left(\sum_{i}p_{i}q_{i}^{-1}\right)^{2}<q_{1}^{-2}.$

We see that in this example the random walk operator $P$ is Hilbert-Schmidt
and hence compact.

######  Corollary 32.

The spectrum of the Laplacian $\Delta=I-P:L^{2}(G,m)\to L^{2}(G,m)$ of the
infinite complete graph $(G,m)$ consists of an infinite sequence of
eigenvalues converging to $1\in[0,2]$ and the point $1$ is the only point of
the spectrum which is not an eigenvalue.

Below we analyse further the infinite complete graph and give a more detailed
information about its spectrum.

The random walk operator $P$ is given by

$(Pf)(i)=\sum_{j\not=i}\frac{p_{j}}{q_{j}}f(j)=\sum_{j}\frac{p_{j}}{q_{j}}f(j)-\frac{p_{i}}{q_{i}}f(i).$

Consider the eigenvalue equation $Pf_{\lambda}=\lambda f_{\lambda}$, i.e.

(40)
$\displaystyle\sum_{j}\frac{p_{j}}{q_{j}}f_{\lambda}(j)=(p_{i}q_{i}^{-1}+\lambda)f_{\lambda}(i)$

for any $i\in\mathbb{N}$. Therefore, for any $i\geq 1$ one has

$(p_{i}q_{i}^{-1}+\lambda)f_{\lambda}(i)=(p_{1}q_{1}^{-1}+\lambda)f_{\lambda}(1).$

Without loss of generality we may assume that
$(p_{1}q_{1}^{-1}+\lambda)f_{\lambda}(1)=1$. We obtain an infinite increasing
sequence of numbers

$\alpha_{1}\leq\alpha_{2}\leq\dots<0,\quad\alpha_{i}\to
0,\quad\mbox{where}\quad\alpha_{i}=-p_{i}q_{i}^{-1},$

and the eigenfunction $f_{\lambda}$ satisfies

$f_{\lambda}(i)=(\lambda-\alpha_{i})^{-1},\quad i\geq 1.$

The equation (40) becomes

(41) $\displaystyle\sum_{j=1}^{\infty}\frac{\alpha_{j}}{\alpha_{j}-\lambda}=1$

and the condition $f_{\lambda}\in L^{2}(G,m)$ can be expressed as
$\sum_{i=1}^{\infty}p_{i}q_{i}(\alpha_{j}-\lambda)^{-2}\ <\ \infty.$ Since
$q_{1}\leq q_{i}<1$, the latter condition is equivalent to

(42) $\displaystyle\sum_{j=1}^{\infty}p_{j}(\lambda-\alpha_{j})^{-2}\ <\
\infty.$

Corollary 33 summarises the above arguments.

######  Corollary 33.

A number $\lambda\in[0,2]$ is an eigenvalue of the random walk operator $P$
for the infinite complete graph if and only if the equation (41) and
inequality (42) are satisfied.

We shall see later that the condition (42) is automatically satistfied.

As an example, consider $\lambda=1$. One has
$\frac{\alpha_{j}}{\alpha_{j}-1}=p_{j}$ and hence equation (41) is satisfied.
Besides, $\frac{p_{j}}{(1-\alpha_{j})^{2}}=p_{j}q_{j}^{2}$ and (42) follows
from $\sum_{j}p_{j}=1$ and $q_{j}<1$. Thus, $\lambda=1$ is an eigenvalue.

The next lemma describes the whole spectrum of $P$.

######  Lemma 34.

Assume that all numbers $p_{i}$ are pairwise distinct, i.e.
$p_{1}>p_{2}>p_{3}>\dots$. The random walk operator $P\colon L^{2}(G,m)\to
L^{2}(G,m)$ has a unique positive eigenvalue $1$ and negative eigenvalues
$\lambda_{1}<\lambda_{2}<\dots<0$ satisfying

$\alpha_{i}<\lambda_{i}<\alpha_{i+1},\quad i=1,2,\dots.$

Additionally, $0$ belongs to the spectrum (as an accumulation point) and is
the only point of the spectrum which is not an eigenvalue.

###### Proof.

Consider the function

(43) $\displaystyle
F(\lambda)=\sum_{j=1}^{\infty}\frac{\alpha_{j}}{\alpha_{j}-\lambda},\quad\quad\lambda\in\Omega=-\\{0,\alpha_{1},\alpha_{2},\dots\\}.$

First, we verify that the series (43) converges for all $\lambda\in\Omega$.
Indeed, if $\lambda>0$ then $\lambda-\alpha_{j}>\lambda$ for all $j\geq 1$ and

$\sum_{j\geq
1}\frac{\alpha_{j}}{\alpha_{j}-\lambda}\,<\,\lambda^{-1}\sum_{j\geq
1}(-\alpha_{j})\,<\,\lambda^{-1}.$

Consider now the case when $\lambda\in(\alpha_{i},\alpha_{i+1})$. Then for
$j\geq i+2$ one has $\alpha_{j}-\lambda\,>\,\alpha_{i+2}-\alpha_{i+1}$ and
therefore

$\sum_{j\geq
i+2}\frac{\alpha_{j}}{\alpha_{j}-\lambda}\,\leq\,(\alpha_{i+2}-\alpha_{i+1})^{-1}\cdot\sum_{j\geq
i+2}(-\alpha_{j})\ <\ \infty.$

For $\epsilon>0$, let $\Omega_{\epsilon}$ denote $-\cup_{j\geq
1}B(\alpha_{j},\epsilon)$, where $B(\alpha_{j},\epsilon)$ stands for the open
ball with centre $\alpha_{j}$ and radius $\epsilon$. The arguments of the
preceding paragraph applied to the series of derivatives

(44) $\sum_{j=1}^{\infty}\frac{\alpha_{j}}{(\alpha_{j}-\lambda)^{2}}$

show that the series (44) converges uniformly on $\Omega_{\epsilon}$.

Therefore, we obtain that the function $F(\lambda)$ is differentiable and its
derivative $F^{\prime}(\lambda)$ is given by the series (44) for all
$\lambda\in\Omega$.

Each term of the series (44) is negative; this implies that $F(\lambda)$ is
monotone decreasing on every interval contained in $\Omega$. Thus, equation
(41) may have at most one solution in any such interval.

Consider the behaviour of $F(\lambda)$ on one of the intervals
$\lambda\in(\alpha_{i},\alpha_{i+1})$. It is obvious that for
$\lambda\to\alpha_{i}$ the function $F(\lambda)$ tends to $+\infty$ and for
$\lambda\to\alpha_{i+1}$ one has $F(\lambda)\to-\infty$.

There are also two infinite maximal intervals of continuity
$(-\infty,\alpha_{1})$ and $(0,\infty)$. The function $F(\lambda)$ is negative
for $\lambda\in(-\infty,\alpha_{1})$ and has limits $0$ and $-\infty$ at the
end points. Besides, $F(\lambda)$ is positive on $(0,\infty)$ and its limits
at the end points are $\infty$ and $0$. Figure 2 summarises the above
arguments.

Figure 2. The graph of the function $F(\lambda)$.

Thus we see that there is a unique solution of (41) in each interval
$(\alpha_{i},\alpha_{i+1})$; besides, there is a unique solution of (41) in
the interval $(0,\infty)$ which, as we know, is $\lambda=1$.

Finally, we note that any of the above solutions automatically satisfies (42).
Indeed, if $\lambda\in(\alpha_{i},\alpha_{i+1})$ then
$\alpha_{j}-\lambda>\alpha_{i+2}-\alpha_{i+1}$ and

$\sum_{j\geq
i+2}p_{j}(\lambda-\alpha_{j})^{-2}<(\alpha_{i+2}-\alpha_{i+1})^{-2}\cdot\sum_{j\geq
i+2}p_{j}\,<\,\infty.$

This completes the proof. ∎

We may now restate the results of this section for the Laplacian $\Delta=I-P$.

######  Proposition 35.

Consider the infinite complete graph $(G,m)$ with $V(G)=\mathbb{N}$ and
weights $m(ij)=p_{i}p_{j}$ where $p_{1}>p_{2}>\dots>0$ is a sequence with
$\sum_{i\geq 1}p_{i}=1$. The spectrum of the Laplacian $\Delta:L^{2}(G,m)\to
L^{2}(G,m)$ contains the point $1$ as an accumulation point and the other
points of the spectrum are simple eigenvalues. The point $0$ is the unique
eigenvalue in the interval $[0,1)$. The remaining eigenvalues
$\dots\,<\,\mu_{3}\,<\,\mu_{2}\,<\,\mu_{1}\,\leq\,2$ lie in $(1,2)$ and
satisfy

(45) $\displaystyle q_{i+1}^{-1}<\mu_{i}<q_{i}^{-1},\quad\mbox{where}\quad
q_{i}=1-p_{i},\quad\mbox{for}\quad i=1,2,\dots,$

hence $\mu_{i}\to 1$. More specifically, for $i=1,2,\dots,$ each eigenvalue
$\mu_{i}$ is the unique solution of the equation

(46) $\displaystyle\sum_{j=1}^{\infty}\frac{p_{j}}{q_{j}\mu-1}\,=\,-1$

lying in the interval $(q_{i+1}^{-1},q_{i}^{-1})$. The spectral gap equals $1$
and top of the spectrum $\mu_{top}=\mu_{1}$ satisfies

(47) $\displaystyle q_{2}^{-1}\,<\,\mu_{top}\,<\,q_{1}^{-1}.$

###### Proof.

Since $\Delta=I-P$ we see that the result of Proposition 35 follows from Lemma
34 by applying the affine transformation $x\mapsto 1-x$. The points of
division $\alpha_{j}$ are mapped into $1-\alpha_{j}=q_{j}^{-1}$. ∎

We can mention another form (48) of the eigenvalue equation (46) which
involves the quantities $r_{j}=q_{j}^{-1}$, where $j=1,2,\dots$

(48) $\displaystyle\sum_{j=1}^{\infty}\frac{r_{j}-1}{r_{j}-\mu}=1.$

Note that here $r_{j}>1$ and $r_{j}\to 1$. We know that equation (48) has
exactly one solution in each interval $(r_{j+1},r_{j})$ and $\mu=0$ is an
additional solution.

##  9\. Improved estimates for $\mu_{1}=\mu_{top}$

Our goal in this section is to strengthen the inequality (47) for the top
eigenvalue $\mu_{1}=\mu_{top}$. Similar method can be applied for more precise
estimates of the other eigenvalues.

Recall that the parameters of the infinite complete graph satisfy
$p_{1}>p_{2}>\dots$ and $\sum_{j}p_{j}=1$. We denote $r_{j}=(1-p_{j})^{-1}$.
We have $r_{1}>r_{2}>r_{3}>\dots>1$ and $r_{j}\to 1$. Consider the following
quadratic equation

(49)
$\displaystyle\frac{r_{1}-1}{r_{1}-\mu}+\frac{r_{2}-1}{r_{2}-\mu}\,=\,1-x,$

where $x$ is a parameter.

######  Lemma 36.

  1. (A)

For any value of the parameter $x$ the quadratic equation (49) has a unique
solution $\mu(x)$ lying in the interval $(r_{2},r_{1})$.

  2. (B)

For $x<1$, the other solution of the equation (49) lies in the interval
$(-\infty,r_{2})$; for $x>1$, the other solution of (49) lies in the interval
$(r_{1},\infty)$; for $x=1$ the equation (49) does not have solutions outside
the interval $(r_{2},r_{1})$.

  3. (C)

$\mu(x)$ is a decreasing function of $x$.

  4. (D)

The top of the spectrum $\mu_{top}=\mu_{1}$ of the Laplacian $\Delta$
satisfies

(50) $\displaystyle\mu(x_{+})<\mu_{top}<\mu(x_{-}),$

where

$x_{+}=\frac{1-p_{1}-p_{2}}{1-r_{1}}\quad\mbox{and}\quad
x_{-}=(1-p_{1}-p_{2})\cdot\frac{r_{3}}{r_{3}-r_{2}}.$

###### Proof.

The rational function
$G(\mu)=\frac{r_{1}-1}{r_{1}-\mu}+\frac{r_{2}-1}{r_{2}-\mu}$ has poles at
$\mu=r_{1}$ and $\mu=r_{2}$, and it is increasing for $\mu\in(r_{2},r_{1})$.
Its graph is shown in Figure 3.

Figure 3. The graph of the function $G(\mu)$.

We easily see that $G\colon(r_{2},r_{1})\to\mathbb{R}$ is a homeomorphism,
which implies (A). Similarly, we see that
$G\colon(-\infty,r_{2})\to(0,\infty)$ and
$G\colon(r_{1},\infty)\to(-\infty,0)$ are monotone increasing homeomorphisms;
this implies our statement (B).

To prove (C), we differentiate the equation $G(\mu(x))=1-x$ getting
$\mu^{\prime}(x)=-G^{\prime}(\mu(x))^{-1}.$ This shows that $\mu^{\prime}<0$
since $G^{\prime}>0$.

Finally, to prove (D), we note that in view of equation (48) one has
$\mu_{top}=\mu(x_{0})$ with

$x_{0}=\sum_{j\geq
3}\frac{r_{j}-1}{r_{j}-\mu},\quad\mbox{where}\quad\mu=\mu_{top}.$

We know that $r_{2}<\mu_{top}<r_{1}$ and hence

$x_{0}<\sum_{j\geq 3}\frac{r_{j}-1}{r_{j}-r_{1}}=\sum_{j\geq
3}\frac{r_{j}}{r_{j}-r_{1}}\cdot
p_{j}\leq\frac{1}{1-r_{1}}\cdot(1-p_{1}-p_{2})=x_{+}.$

Here we used the equalities $\frac{r_{j}-1}{r_{j}}=p_{j}$ and $\sum_{j\geq
1}p_{j}=1$. Similarly, we have

$x_{0}>\sum_{j\geq 3}\frac{r_{j}-1}{r_{j}-r_{2}}=\sum_{j\geq
3}\frac{r_{j}}{r_{j}-r_{2}}\cdot
p_{j}\geq\frac{r_{3}}{r_{3}-r_{2}}\cdot(1-p_{1}-p_{2})=x_{-}.$

Thus, using (C), we conclude that
$\mu(x_{+})\leq\mu_{top}=\mu(x_{0})\leq\mu(x_{-}).$ ∎

Below we shall have specific examples illustrating Lemma 36.

##  10\. Asymmetry of the spectrum and the invariant ${\sf k}(G,m)$ for the
infinite complete graph

In the section we continue studying the infinite complete graph and its
spectrum. Our goal is to examine Theorem 25 in this specific example.

First we describe the Hausdorff distance
$d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))$.

######  Lemma 37.

If $\mu_{1}\leq 3/2$ then

(51) $\displaystyle
d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))=2-\mu_{1}\,\geq\,\frac{1}{2}.$

If $\mu_{1}\geq 3/2$ then

(52)
$d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))=\frac{1}{2}-\inf_{i\geq
1}\left|\mu_{i}-\frac{3}{2}\right|\,\leq\,\frac{1}{2}.$

###### Proof.

We know that $\sigma(\Delta)=\\{0,1\\}\cup\\{\mu_{1},\mu_{2},\dots\\}$ where
$\mu_{1}>\mu_{2}>\dots>1$, $\mu_{i}\to 1$. Hence,
$\mathcal{R}(\sigma(\Delta))=\\{1,2\\}\cup\\{\bar{\mu}_{1},\bar{\mu}_{2},\dots,\\},$
where $\bar{\mu}_{i}=2-\mu_{i}$. We intend to apply Lemma 26. We have:
$\inf\\{\epsilon;\,2\in\sigma(\Delta)_{\epsilon}\\}=2-\mu_{1}$. Besides,
$\inf\\{\epsilon;\,1\in\sigma(\Delta)_{\epsilon}\\}=0$ and for $i=1,2,\dots$,
one has
$\inf\\{\epsilon;\,\bar{\mu}_{i}\in\sigma(\Delta)_{\epsilon}\\}=\min\\{2-\mu_{i},\mu_{i}-1\\}.$
This clearly implies that, for $\mu_{1}\leq 3/2$, the Hausdorff distance
$d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))$ equals $2-\mu_{1}$.
Consider now the case $\mu_{1}\geq 3/2$. By the above, the Hausdorff distance
$d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))$ in this case equals
$\sup_{i\geq 1}\\{\min\\{2-\mu_{i},\mu_{i}-1\\}\\}.$ We may write

$\min\\{2-\mu_{i},\mu_{i}-1\\}=\frac{1}{2}+\min\\{\frac{3}{2}-\mu_{i},\mu_{i}-\frac{3}{2}\\}=\frac{1}{2}-\left|\mu_{i}-\frac{3}{2}\right|.$

This implies (52). ∎

Next we consider our invariant ${\sf k}(G,m)$, see Definition 17. For a subset
$A\subset\mathbb{N}=\operatorname{V}(G)$ we set $P(A)=\sum_{i\in A}p_{i}$ and
$p_{\rm{min}}(A)=\inf_{i\in A}p_{i}$. Then for a partition $A\sqcup
B=\mathbb{N}$ one has

${\sf
k}(A,B)=\max\left\\{\frac{P(A)-p_{\rm{min}}(A)}{1-p_{\rm{min}}(A)},\frac{P(B)-p_{\rm{min}}(B)}{1-p_{\rm{min}}(B)}\right\\}.$

For an infinite set $A\subset\mathbb{N}=\operatorname{V}(G)$ clearly
$p_{\rm{min}}(A)=0$. Hence, if both sets $A,B$ are infinite, we have

${\sf k}(A,B)=\max\\{P(A),P(B)\\}\geq 1/2$

since $P(A)+P(B)=1$. Therefore, the infimum of the numbers ${\sf k}(A,B)$
taken over all partitions $A\sqcup B=\mathbb{N}$ with both sets $A,B$ infinite
equals

$\inf\\{P(A);\,A\subset\mathbb{N}\,\,\mbox{is infinite and}\,\,P(A)\geq
1/2\\}.$

Next, we consider partitions $A\sqcup B=\mathbb{N}$ with $A$ finite and hence
$B$ infinite. We shall be mainly interested in the situation when $p_{1}\geq
1/2$. In this case one may take the partition $A^{\prime}=\\{1\\}$,
$B^{\prime}=\\{2,3,\dots\\}$; then ${\sf
k}(A^{\prime},B^{\prime})=P(B^{\prime})=1-p_{1}$.

Let us show that, in fact,

${\sf k}(G,m)=1-p_{1}$

under the assumption $p_{1}\geq 1/2$. All partitions with both sets $A$ and
$B$ infinite give ${\sf k}(A,B)\geq 1/2\geq 1-p_{1}$. Consider a partition
$A\sqcup B=\mathbb{N}$ with finite $A$, $A\not=\\{1\\}$. If
$p_{\rm{min}}(A)=p_{i}$, $i>1$, then

${\sf k}(A,B)=\max\left\\{\frac{P(A)-p_{i}}{1-p_{i}},P(B)\right\\}.$

If $1\notin A$ then $1\in B$ and ${\sf k}(A,B)=P(B)\geq 1-p_{1}.$ Consider now
the remaining case: $1\in A$ and $p_{\rm{min}}(A)=p_{i}$ where $i>1$. Then
$P(B)\leq 1-p_{1}-p_{i}<1/2$ and

$\frac{P(A)-p_{i}}{1-p_{i}}\geq\frac{p_{1}}{1-p_{i}}\geq 1/2,$

and thus ${\sf k}(A,B)=\frac{P(A)-p_{i}}{1-p_{i}}\geq 1/2\geq 1-p_{1}.$ We
summarise our above arguments as follows.

######  Lemma 38.

If $p_{1}\geq 1/2$ then ${\sf k}(G,m)=1-p_{1}$.

######  Example 39.

Consider an infinite complete graph with the following parameters:
$p_{1}=0.9$, $p_{2}=0.09$, $p_{3}=0.009$; the values $p_{4},p_{5},\dots$ will
be irrelevant for our estimates below.

By Lemma 38, one has ${\sf k}(G,m)=0.1$ and applying Theorem 25 we obtain that
the spectral asymmetry satisfies

$d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))\leq 0.2.$

Next, we apply Lemma 37, which gives $\mu_{1}>3/2$, and the equality (52)
implies

$\inf_{i\geq 1}\left|\mu_{i}-\frac{3}{2}\right|\geq 0.5-0.2=0.3.$

In other words, the open interval

$(1.2,1.8)=\left(\frac{3}{2}-\frac{3}{10},\frac{3}{2}+\frac{3}{10}\right)\subset[0,2]$

contains no eigenvalues. Thus, our inequality (34) allows finding lacunas in
the spectrum.

We can also estimate the Hausdorff distance
$d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))$ using information about
the eigenvalues. We have $r_{1}=q_{1}^{-1}=10$,
$r_{2}=q_{2}^{-1}=\frac{100}{91}$ and hence $1.099<\mu_{1}<10$, by the
inequality (47), which is not informative enough. We can improve the bound
(47) using Lemma 36. We obtain $x_{+}=-\frac{0.01}{9}\approx-0.001111$, and
$x_{-}=-\frac{0.01}{\frac{0.991}{0.91}-1}\approx-0.11235$. Solving the
quaratic equation (49) we obtain $1.94747\leq\mu_{1}\leq 2.4194,$ which, of
course, should be understood as

$1.94747\leq\mu_{1}\leq 2.$

Next we estimate $\mu_{2}$ using (47). We obtain

$1.00908\approx\frac{1000}{991}=r_{3}=q_{3}^{-1}\,<\,\mu_{2}\,<\,r_{2}=q_{2}^{-1}=\frac{100}{91}\approx
1.099.$

Thus, using Lemma 37, we obtain for the Hausdorff distance

$0.00908\leq d_{H}(\sigma(\Delta),\mathcal{R}(\sigma(\Delta)))\leq 0.099.$

######  Remark 40.

It is an interesting inverse problem whether the spectrum of the infinite
complete graph determines the sequence of shape parameters
$p_{1},p_{2},\dots,$ satisfying $\sum_{i\geq 1}p_{i}=1$.

## References

  * [1] F. Bauer, B. Hua and Jürgen Jost, The dual Cheeger constant and spectra of infinite graphs,  Advances in Mathematics, 251(2014), 147 - 194.
  * [2] F. Bauer, M. Keller and R. K. Wojciechowski, Cheeger inequalities for unbounded graph Laplacians, Journal of the European Mathematical Society, 17 (2015), 259 - 271.
  * [3] F. R. K. Chung, Spectral graph theory. CBMS Regional Conference Series in Mathematics, 92. AMS, Providence, RI, 1997. xii+207 pp.
  * [4] J. Dodzuik, Difference equations, isoperimetric inequalities and transience of certain random walks, Transactions of the American Mathematical Society, 284(1984).
  * [5] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bulletin of the AMS, 43(2006), 439 - 561.
  * [6] T. Kato, PerturbationTheory for Linear Operators, Springer-Verlag 1980.
  * [7] M. Keller, D. Lenz, R. Wojciechowski, Radosław K. Graphs and discrete Dirichlet spaces. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 358. Springer, 2021.
  * [8] E. Kreyszig, Introductory functional analysis and applications, John Wiley & Sons, 1978
  * [9] S. Mokhtari-Sharghi, Cheeger inequality for infinite graphs, Geometriae Dedicata, 100(2003), 53 - 64.
  * [10] M. Reed, B. Simon, Methods of modern mathematical physics, IV, Analysis of operators, Academic Press,1978
  * [11] W. Woess, Random walks on infinite graphs and groups, Cambridge University Press, 2000.