Extremal Matching Energy of Random Polyomino Chains

Abstract

Polyomino graphs is one of the research objectives in statistical physics and in modeling problems of surface chemistry. A random polyomino chain is a subgraph of a polyomino graph. The matching energy is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph. In this paper, we characterize the graphs with the extremal matching energy among all random polyomino chains of a polyomino graph by the probability method.

1. Introduction

A polyomino graph [1] (also called chessboards [2] or square-cell configurations [3]) is a connected geometric graph obtained by arranging congruent regular squares of side length 1 (called a cell) in a plane such that two squares are either disjoint or have a common edge. Considerable research in statistical physics and structural chemistry has been devoted to polyomino graphs [4,5,6,7,8,9,10,11,12,13,14].

A polyomino chain $Q_n$ with n squares, which is a subgraph of a polyomino graph, can be regarded as a polyomino chain $Q_{n-1}$ with $n-1$ squares adjoining to a new terminal square by a cut edge, see Figure 1.

Let $Q_n=S_1{S}_2\cdots S_n$ be a polyomino chain with $n(\ge 2)$ squares, where $S_k$ is the kth square of $Q_n$ attached to $S_{k-1}$ by a cut edge $u_{k-1}{w}_k$, $k=2,3,\dots ,n$, where $w_k=v_1$ is a vertex of $S_k$. A vertex v is said to be ortho- and para-vertex of $S_k$ if the distance between v and $w_k$ is one and two, denoted by $o_k$ and $p_k$, respectively. Checking Figure 1, it is easy to see that $w_n=v_1$, ortho-vertices $o_n=v_2,v_3$, and para-vertex $p_n=v_4$ in $S_n$.

A polyomino chain $Q_n$ is a polyomino ortho-chain if $u_k=o_k$ for $2\le k\le n-1$, denoted by $Q_n^o$. A polyomino chain $Q_n$ is a polyomino para-chain if $u_k=o_k$ for $2\le k\le n-1$, denoted by $Q_n^p$. The polyomino or tho-chain $Q_4^o$ and polyomino para-chain $Q_4^p$ are depicted in Figure 2.

For $n\ge 3$, the terminal square can be attached to ortho- or para-vertex in two ways, which results in the local arrangements, described as $Q_{n+1}^1$ and $Q_{n+1}^2$ (see Figure 3).

A random polyomino chain $Q(n,t)$ with n squares is a polyomino chain obtained by stepwise addition of terminal squares. At each step $k(=3,4,\dots ,n)$, a random selection is made from one of the two possible constructions:

(i)

$Q_{k-1}\to Q_k^1$ with probability $t(=t_1)$,

(ii)

$Q_{k-1}\to Q_k^2$ with probability $1-t(=t_2)$,

where the probability t is a constant, irrespective to the step parameter k. In particular, the random polyomino chain $Q(n,1)$ is the polyomino ortho-chain $Q_n^o$. In addition, $Q(n,0)$ is the polyomino para-chain $Q_n^p$. For example, random polyomino chain $Q(4,1)$ is the polyomino ortho-chain $Q_4^o$, and $Q(4,0)$ is the polyomino para-chain $Q_4^p$, respectively. The two types of uniform chains are shown in Figure 2.

A k-matching in G is a set of k pairwise non-adjacent edges. The number of k-matchings in G is denoted by $m(G,k)$. Specifically, $m(G,0)=1$, $m(G,1)=m$ and $m(G,k)=0$ for $k>\frac{n}{2}$ or $k<0$. The matching polynomial of G is defined by

$$\begin{array}{c}\hfill \mu (G,x)=\sum _{k\ge 0}{(-1)}^{k}m(G,k)x^{n-2k},\end{array}$$

and its theory is well elaborated [15,16,17,18] and the references therein.

Gutman and Wagner [19] first proposed the concept of the matching energy of a graph, denoted by $ME(G)$, as

$$\begin{array}{c}\hfill ME(G)=\frac{2}{\pi }{\int }_0^{\infty }{x}^{-2}\ln \left[\sum _{k\ge 0}m(G,k)x^{2k}\right]dx.\end{array}$$

(1)

Meanwhile, they also gave another definition of matching energy of a graph. That is,

$$\begin{array}{c}\hfill ME(G)=\sum _{i=1}^n\left|{\mu }_i\right|,\end{array}$$

where ${\mu }_i$ denotes the root of matching polynomial of G.

The formula given by Gutman and Wagner [19] reveals the relation between topological resonance energy (TRE(G)) [20], graph energy (E(G)) [21] and matching energy, i.e., $TRE(G)=E(G)-ME(G)$. The matching energy has received a lot of attention from researchers in recent years (see [22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]).

For a random polyomino chain $Q(n,t)$, the matching energy is a random variable. In this paper, we shall determine the extremal graphs with respect to the matching energy for all random polyomino chains.

2. Preliminaries

Let $G=(V(G),E(G))$ be a graph with the vertex set $V(G)=\{v_1,v_2,\dots ,v_n\}$ and the edge set $E(G)=\{e_1,e_2,\dots ,e_m\}$. The graphs obtained from G by removing v or e are denoted by $G-v$ or $G-e$, respectively, where $v\in V(G)$ and $e\in E(G)$. Let $G\cup H$ be the union of two graphs G and H that have no common vertices.

Among many properties of $m(G,k)$, we mention the following results that will be used later [21].

Lemma 1.

$(i)$ If $uv$ is an edge of G, then $m(G,k)=m(G-uv,k)+m(G-u-v,k-1)$;

$(ii)$ If u is a vertex of G, then $m(G,k)=m(G-u,k)+\sum _{v\in N(u)}m(G-u-v,k-1)$, where $N(u)$ is the neighbors of u in G.

Lemma 2.

Let $G_j(j=1,2,3,4)$ be a graph. If $m(G_1,i)\ge m(G_2,i)$ and $m(G_3,i)\ge m(G_4,i)$ for $i=1,2,\dots ,k$, then $m(G_1\cup G_3,k)\ge m(G_2\cup G_4,k)$.

The quasi-order ⪰ is defined by

$$\begin{array}{c}\hfill G⪰H⟺m(G,k)\ge m(H,k)\mathrm{for}\mathrm{all}k=0,1,\dots ,\lfloor n/2\rfloor .\end{array}$$

(2)

If $G⪰H$ and there exists some k such that $m(G,k)>m(H,k)$, then we write $G\succ H$. In particular, by Equations (1) and (2), the following property can be easily obtained:

$$\begin{array}{c}\hfill G⪰H⟹ME(G)\ge ME(H)\mathrm{and}G\succ H⟹ME(G)>ME(H).\end{array}$$

(3)

This property is an important technique to determine extremal graphs with respect to the matching energy.

In order to prove the main result of this paper, we give two auxiliary graphs of $Q(n,t)$, denoted by $Q^{\prime }(n,t)$ and $Q^{\prime \prime }(n,t)$, respectively (see Figure 4). In particular, $Q^{\prime }(n,t)$(resp. $Q^{\prime \prime }(n,t)$) is denoted by $Q_n^{o^{\prime }}$ (resp. $Q_n^{p^{\prime \prime }}$) when $Q^{\prime }(n,t)$ (resp. $Q_n^{p^{\prime \prime }}$) is isomorphic to $Q_n^o$ (resp. $Q_n^p$).

3. Main Result

In this section, we will prove the following results.

Theorem 1.

Let $Q(n,t)$ be a random polyomino chain. Then,

$$ME(Q_n^p)\le ME(Q(n,t))\le ME(Q_n^o),$$

where $Q_n^p$ and $Q_n^o$ are polyomino para-chain and polyomino ortho-chain, respectively.

Before proving Theorem 1, we first prove the following lemma.

Lemma 3.

Let $Q(n,t)$ be a random polyomino chain. Then, for any $0\le k\le 2n$,

$$m(Q_n^p,k)\le m(Q(n,t),k)\le m(Q_n^o,k),$$

where $Q_n^p$ and $Q_n^o$ denote the polyomino para-chain and polyomino ortho-chain, respectively.

Proof. 

We prove this lemma by the induction on n.

By the definition of $Q(n,t)$, if $n=1,2$, then the proof is obvious. Let $n=3$. Then $Q(3,t)$ is isomorphic to $Q_3^o$ or $Q_3^p$. By Lemma 1, we obtain that

$$\begin{array}{lll}\hfill m(Q_3^o,k)& =& m(Q_2^o\cup C_4,k)+m(Q_1^{o^{\prime }}\cup P_3,k-1)\hfill \\ & =& m(Q_2^o\cup C_4,k)+m(Q_1^o\cup 2P_3,k-1)+m(2P_3\cup P_2,k-2)\hfill \end{array}$$

and

$$\begin{array}{lll}\hfill m(Q_3^p,k)& =& m(Q_2^p\cup C_4,k)+m(Q_1^{p^{″}}\cup P_3,k-1)\hfill \\ & =& m(Q_2^p\cup C_4,k)+m(Q_1^p\cup 2P_3,k-1)+m(2P_3\cup 2K_1,k-2).\hfill \end{array}$$

Checking graphs $Q_3^o$ and $Q_3^p$, we know that $Q_2^o$ and $Q_2^p$ are isomorphic. By Lemma 2, we have $m(2P_3\cup 2K_1,k-2)\le m(2P_3\cup P_2,k-2)$. Thus, $m(Q_3^p,k)\le m(Q_3^o,k)$.

Next, we assume that the lemma is true for a random polyomino chain with length less than n.

Let $Q(n,t)$ be a random polyomino chain of length n. It is clear that $m(Q_n^p,k)\le m(Q(n,t),k)\le m(Q_n^o,k)$ for $k=0,1$. If $2\le k<n$, then

$$\begin{array}{lll}\hfill m(Q_n^o,k)& =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^{o^{\prime }}\cup P_3,k-1)\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+m(Q_{n-3}^{o^{\prime }}\cup P_3\cup P_2,k-2)\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+m(Q_{n-3}^o\cup 2P_3\cup P_2,k-2)\hfill \\ & & +m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 2P_2,k-3)\hfill \\ & =& \dots \hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+m(Q_{n-3}^o\cup 2P_3\cup P_2,k-2)\hfill \\ & & +\dots +m(Q_{n-k}^o\cup 2P_3\cup (k-2)P_2,1)+m(Q_{n-k-1}^{o^{\prime }}\cup P_3\cup (k-2)P_2,0)\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+m(Q_{n-3}^o\cup 2P_3\cup P_2,k-2)\hfill \\ & & +\dots +m(Q_{n-k}^o\cup 2P_3\cup (k-2)P_2,1)+1\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+\sum _{s=0}^{k-2}m(Q_{n-2-s}^o\cup 2P_3\cup s{P}_2,k-1-s)+1,\hfill \end{array}$$

$$\begin{array}{lll}\hfill m(Q_n^p,k)& =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^{p^{″}}\cup P_3,k-1)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^{p^{″}}\cup P_3\cup 2K_1,k-2)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^p\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +m(Q_{n-4}^{p^{″}}\cup P_3\cup 4K_1,k-3)\hfill \\ & =& \dots \hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^p\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +\dots +m(Q_{n-k}^p\cup 2P_3\cup (2k-2)K_1,1)+m(Q_{n-k-1}^{p^{″}}\cup P_3(2k-4)K_1,0)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^p\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +\dots +m(Q_{n-k}^p\cup 2P_3\cup (2k-2)K_1,1)+1\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+\sum _{s=0}^{k-2}m(Q_{n-2-s}^p\cup 2P_3\cup 2s{K}_1,k-1-s)+1,\hfill \end{array}$$

and

$$\begin{array}{lll}\hfill m(Q_n,k)& =& m(Q_{n-1}\cup C_4,k)+t_{1}m(Q_{n-2}^{o^{\prime }}\cup P_3,k-1)+t_{2}m(Q_{n-2}^{p^{″}}\cup P_3,k-1)\hfill \\ & =& m(Q_{n-1}\cup C_4,k)+m(Q_{n-2}\cup 2P_3,k-1)+t_1[t_{1}m(Q_{n-3}^{o^{\prime }}\cup P_3\cup P_2,k-2)+t_{2}m(Q_{n-3}^{p^{″}}\hfill \\ & & \cup P_3\cup P_2,k-2)]+t_2[t_{1}m(Q_{n-3}^{o^{\prime }}\cup P_3\cup 2K_1,k-2)+t_{2}m(Q_{n-3}^{p^{″}}\cup P_3\cup 2K_1,k-2)]\hfill \\ & =& m(Q_{n-1}\cup C_4,k)+m(Q_{n-2}\cup 2P_3,k-1)+t_1^2[m(Q_{n-3}\cup 2P_3\cup P_2,k-2)\hfill \\ & & +t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 2P_2,k-3)+t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup 2P_2,k-3)]+t_1{t}_2[m(Q_{n-3}\cup 2P_3\hfill \\ & & \cup P_2,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup P_2\cup 2K_1,k-3)+t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup P_2\cup 2K_1,k-3)]\hfill \\ & & +t_1{t}_2[m(Q_{n-3}\cup 2P_3\cup 2K_1,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup P_2\cup 2K_1,k-3)+t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\hfill \\ & & \cup P_2\cup 2K_1,k-3)]+t_2^2[m(Q_{n-3}\cup 2P_3\cup 2K_1,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 4K_1,k-3)\hfill \\ & & +t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup 4K_1,k-3)]\hfill \\ & =& \cdots \hfill \\ & =& m(Q_{n-1}\cup C_4,k)+\sum _{s=0}^{n-2}\sum _{s_1+s_2=s}\frac{s!}{s_1!s_2!}{t}_1^{s_1}{t}_2^{s_2}m(Q_{n-2-s}\cup 2P_3\cup s_1{P}_2\cup 2s_2{K}_1,k-1-s)+1.\hfill \end{array}$$

If $n\le k\le 2n$, then

$$\begin{array}{lll}\hfill m(Q_n^o,k)& =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^{o^{\prime }}\cup P_3,k-1)\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+m(Q_{n-3}^{o^{\prime }}\cup P_3\cup P_2,k-2)\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+m(Q_{n-3}^o\cup 2P_3\cup P_2,k-2)\hfill \\ & & +m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 2P_2,k-3)\hfill \\ & =& \cdots \hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+m(Q_{n-2}^o\cup 2P_3,k-1)+\dots +m(Q_1\cup 2P_3\hfill \\ & & \cup (n-3)P_2,k-n+2)+m(2P_3\cup (n-2)P_2,k-n+1)\hfill \\ & =& m(Q_{n-1}^o\cup C_4,k)+\sum _{s=0}^{n-2}m(Q_{n-2-s}^o\cup 2P_3\cup s{P}_2,k-1-s),\hfill \end{array}$$

$$\begin{array}{lll}\hfill m(Q_n^p,k)& =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^{p^{″}}\cup P_3,k-1)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^{p^{″}}\cup P_3\cup 2K_1,k-2)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^p\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +m(Q_{n-4}^{p^{″}}\cup P_3\cup 4K_1,k-3)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^p\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +m(Q_{n-4}^p\cup 2P_3\cup 4K_1,k-3)+m(Q_{n-5}^{p^{″}}\cup P_3\cup 6K_1,k-4)\hfill \\ & =& \cdots \hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+m(Q_{n-2}^p\cup 2P_3,k-1)+m(Q_{n-3}^p\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +\dots +m(Q_1^p\cup 2P_3\cup (2n-6)K_1,k-n+2)+m(2P_3\cup (2n-4)K_1,k-n+1)\hfill \\ & =& m(Q_{n-1}^p\cup C_4,k)+\sum _{s=0}^{n-2}m(Q_{n-2-s}^p\cup 2P_3\cup 2s{K}_1,k-1-s),\hfill \end{array}$$

and

$$\begin{array}{lll}\hfill m(Q_n,k)& =& m(Q_{n-1}\cup C_4,k)+t_{1}m(Q_{n-2}^{o^{\prime }}\cup P_3,k-1)+t_{2}m(Q_{n-2}^{p^{″}}\cup P_3,k-1)\hfill \\ & =& m(Q_{n-1}\cup C_4,k)\hfill \\ & & +t_1[m(Q_{n-2}\cup 2P_3,k-1)+t_{1}m(Q_{n-3}^{o^{\prime }}\cup P_3\cup P_2,k-2)+t_{2}m(Q_{n-3}^{p^{″}}\cup P_3\cup P_2,k-2)]\hfill \\ & & +t_2[m(Q_{n-2}\cup 2P_3,k-1)+t_{1}m(Q_{n-3}^{o^{\prime }}\cup P_3\cup 2K_1,k-2)\hfill \\ & & +t_{2}m(Q_{n-3}^{p^{″}}\cup P_3\cup 2K_1,k-2)]\hfill \\ & =& m(Q_{n-1}\cup C_4,k)+m(Q_{n-2}\cup 2P_3,k-1)\hfill \\ & & +t_1^2[m(Q_{n-3}\cup 2P_3\cup P_2,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 2P_2,k-3)\hfill \\ & & +t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup 2P_2,k-3)]\hfill \\ & & +t_1{t}_2[m(Q_{n-3}\cup 2P_3\cup P_2,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup P_2\cup 2K_1,k-3)\hfill \\ & & +t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup P_2\cup 2K_1,k-3)]\hfill \\ & & +t_1{t}_2[m(Q_{n-3}\cup 2P_3\cup 2K_1,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup P_2\cup 2K_1,k-3)\hfill \\ & & +t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup P_2\cup 2K_1,k-3)]\hfill \\ & & +t_2^2[m(Q_{n-3}\cup 2P_3\cup 2K_1,k-2)+t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 4K_1,k-3)\hfill \\ & & +t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup 4K_1,k-3)]\hfill \\ & =& m(Q_{n-1}\cup C_4,k)+m(Q_{n-2}\cup 2P_3,k-1)\hfill \\ & & +t_{1}m(Q_{n-3}\cup 2P_3\cup P_2,k-2)+t_{2}m(Q_{n-3}\cup 2P_3\cup 2K_1,k-2)\hfill \\ & & +t_1^2[t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 2P_2,k-3)+t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup 2P_2,k-3)]\hfill \\ & & +2t_1{t}_2[t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup P_2\cup 2K_1,k-3)+t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup P_2\cup 2K_1,k-3)]\hfill \\ & & +t_2^2[t_{1}m(Q_{n-4}^{o^{\prime }}\cup P_3\cup 4K_1,k-3)+t_{2}m(Q_{n-4}^{p^{″}}\cup P_3\cup 4K_1,k-3)]\hfill \\ & =& \cdots \hfill \\ & =& m(Q_{n-1}\cup C_4,k)+\sum _{s=0}^{n-2}\sum _{s_1+s_2=s}\frac{s!}{s_1!s_2!}{t}_1^{s_1}{t}_2^{s_2}m(Q_{n-2-s}\cup 2P_3\cup s_1{P}_2\cup 2s_2{K}_1,k-1-s),\hfill \end{array}$$

since ${\displaystyle \sum _{s_1+s_2=s}}\frac{s!}{s_1!s_2!}{t}_1^{s_1}{t}_2^{s_2}={(t_1+t_2)}^s=1$ and $m(Q_{n-2-s}^p\cup 2P_3\cup 2s{K}_1,k-1-s)\le m(Q_{n-2-s}\cup 2P_3\cup s_1{P}_2\cup 2s_2{K}_1,k-1-s)\le m(Q_{n-2-s}^o\cup 2P_3\cup s{P}_2,k-1-s)$. By the induction hypothesis and Lemma 2, we obtain that

$$\begin{array}{l}\hfill m(Q_n^p,k)\le m(Q(n,t),k)\le m(Q_n^o,k)\mathrm{for}\mathrm{any}0\le k\le 2n.\end{array}$$

The lemma holds by induction. ☐

In what follows, we prove Theorem 1.

Proof of Theorem 1.

By Equations (2), (3) and Lemma 3, it is straightforward to show that $ME(Q_n^p)\le ME(Q(n,t))\le ME(Q_n^o)$. ☐

4. Discussion

In this paper, we investigate the matching energy of a class of subgraphs (called polyomino chains) of a polyomino graph. The graphs with the extremal matching energy among all polyomino chains are completely determined. This is also the best result for all random polyomino chains. As a derivative problem, we shall discuss which random polyomino chain has the second largest (or smallest) matching energy.