# Cohen-Macaulay Weighted Chordal Graphs

Shuai Wei  University of New Mexico Department of Mathematics and Statistics,
1 University of New Mexico, MSC01 1115 Albuquerque, NM 87131 USA<EMAIL_ADDRESS>
###### Abstract.

In this paper I give a combinatorial characterization of all the Cohen-
Macaulay weighted chordal graphs. In particular, it is shown that a weighted
chordal graph is Cohen-Macaulay if and only if it is unmixed.

##  1\. Introduction

Convention. Throughout this paper, let $\mathbb{N}=\\{1,2,\dots,\\}$,
$n\in\mathbb{N}$, $\mathbb{K}$ a field, and $G=(V,E)$ a (finite simple) graph
with vertex set $V=V(G)=[n]=\\{1,\dots,n\\}$ and edge set $E=E(G)$. An edge
between vertices $i$ and $j$ is denoted $ij$.

Combinatorial commutative algebra is a branch of mathematics that uses
combinatorics and graph theory to understand certain algebraic constructions;
it also uses algebra to understand certain objects in combinatorics and graph
theory.

To the graph $G$ one associates the positive integer-valued function
$\lambda:E\to\mathbb{N}$, producing a weighted graph $G_{\lambda}$. For a
weighted graph $G_{\lambda}$ Paulsen and Sather-Wagstaff [4] introduce the
weighted edge ideal $I(G_{\lambda})\subseteq\mathbb{K}[X_{1},\dots,X_{n}]$
which is generated by all monomials $X_{i}^{\lambda(ij)}X_{j}^{\lambda(ij)}$
such that $ij\in E$. In particular, if $\lambda$ is the constant function
defined by $\lambda(ij)=1$ for $ij\in E$, then $I(G_{\lambda})=I(G)$, where
$I(G)$ is the edge ideal associated to $G$ in $\mathbb{K}[X_{1},\dots,X_{n}]$,
given by $I(G)=(X_{i}X_{j}\mid ij\in E)$.

A weighted graph $G_{\lambda}$ is called Cohen-Macaulay over $\mathbb{K}$ if
$\mathbb{K}[X_{1},\dots,X_{n}]/I(G_{\lambda})$ is a Cohen-Macaulay ring, and
is called Cohen-Macaulay if it is Cohen-Macaulay over any field. The general
problem is to classify the weighted graphs which are Cohen-Macaulay over
$\mathbb{K}$. As for unweighted graphs one cannot expect a general
classification theorem. Paulsen and Sather-Wagstaff [4] characterized all
Cohen-Macaulay weighted $K_{1}$-corona of graphs and in particular all Cohen-
Macaulay weighted trees. In this paper we classify all Cohen-Macaulay weighted
chordal graphs following the classification of all Cohen-Macaulay chordal
graphs by Herzog, Hibi, and Zheng[2]. The characterization is purely graph-
theoretical, and it turns out that for weighted chordal graphs the Cohen-
Macaulay property is independent of the field $\mathbb{K}$.

In Section 2, we recall some definitions and notations from [1], [2], and [4].
We also prove a lemma used in proving the sufficient condition for the Cohen-
Macaulay property to hold for weighted chordal graphs. In Section 3, we
classify all Cohen-Macaulay weighted chordal graphs. Theorem 3.1 gives a
sufficient condition and Theorem 3.3 says that the sufficient condition is
also a necessary condition.

##  2\. Preliminaries

In subsequent sections, let $\lambda:E\to\mathbb{N}$ be a positive integer-
valued function and $G_{\lambda}$ a weighted graph.

######  Definition 2.1.

[1] A _path_ in $G$ is a non-empty subgraph $P=(V^{\prime},E^{\prime})$ of the
form $V^{\prime}=\\{v_{0},v_{1},\dots,v_{r}\\}$ and
$E^{\prime}=\\{v_{0}v_{1},v_{1}v_{2},\dots,v_{r-1}v_{r}\\}$, where
$r\in\mathbb{N}\sqcup\\{0\\}$, we denote the path by $P=v_{0}v_{1}\cdots
v_{r}$ for simplicity and define $\mathring{P}_{0}=v_{1}\cdots v_{r}$.

######  Definition 2.2.

[1] If $G^{\prime}=(V^{\prime},E^{\prime})$ is a subgraph of $G$ and
$E^{\prime}=\\{ij\in E\mid i,j\in V^{\prime}\\}$, then $G^{\prime}$ is an
_induced subgraph_ of $G$; we say that $V^{\prime}$ _induces_ or _spans_
$G^{\prime}$ in $G$, and write $G^{\prime}=G[V^{\prime}]$. A subgraph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $G$ is a _spanning_ subgraph of $G$ if
$V^{\prime}$ spans all of $G$, i.e., if $V^{\prime}=V$.

If $U\subseteq V$, we write $G-U$ for $G[V\smallsetminus U]$.

A maximal connected subgraph of $G$ is a _component_ of $G$. If
$G_{1},\dots,G_{n}$ are components of $G$, then $G_{i}=G[V(G_{i})]$ for
$i=1,\dots,n$ and $V(G_{1}),\dots,V(G_{n})$ partition $V$.

######  Definition 2.3.

A _rooted tree_ $T$ is a tree with a special vertex $r\in V(T)$ labelled as
the ``root'' of the tree. A _rooted forest_ is a graph whose components are
rooted trees. A subgraph $G^{\prime}=(V^{\prime},E^{\prime})$ of $G$ is called
a _rooted spanning forest_ of $G$ if $G^{\prime}$ is a rooted forest and
$V^{\prime}$ spans $G$.

######  Definition 2.4.

Let $T$ be a rooted tree with root $r$. For any $v\in T\smallsetminus\\{r\\}$,
there is a unique path from $r$ to $v$, say $v_{1}\dots v_{k}$ with $v_{1}=r$
and $v_{k}=v$, we say that $v_{i}$ is a _$T$ -parent_ of $v_{i+1}$ and
$v_{i+1}$ is a _$T$ -child_ of $v_{i}$ for $i=1,\dots,k-1$.

If $\ell\in V(T)$ has no $T$-child, we say that $\ell$ is a _$T$ -leaf_,
otherwise, it is a _$T$ -inner vertex_. In particular, if $V(T)=\\{r\\}$, then
$r$ is a $T$-_leaf_ but not a $T$-inner vertex.

######  Definition 2.5.

[2] A _stable subset_ or _clique_ of the graph $G$ is a subset $F$ of $[n]$
such that $ij\in E$ for all $i,j\in F$ with $i\neq j$. We write $\Delta(G)$
for the simplicial complex on $[n]$ whose faces are the stable subsets of $G$.
A vertex of $\Delta(G)$ is _free_ if it belongs to exactly one facet of
$\Delta(G)$, otherwise it is called _nonfree_.

######  Definition 2.6.

A _chord_ in the graph $G$ refers to an edge that connects two non-adjacent
vertices within a cycle. The graph $G$ is called _chordal_ if every cycle of
length $>3$ has a chord. The weighted graph $G_{\lambda}$ is called a
_weighted chordal graph_ if the underlying graph $G$ is chordal.

######  Definition 2.7.

[4, Definition 1.4] A _weighted vertex cover_ of $G_{\lambda}$ is an ordered
pair $(V^{\prime},\delta^{\prime})$ with a subset $V^{\prime}\subseteq V$ and
a function $\delta^{\prime}:V^{\prime}\to\mathbb{N}$ such that for each edge
$ij\in E$, we have that

  1. (a)

$i\in V^{\prime}$ and $\delta^{\prime}(i)\leq\lambda(ij)$, or

  2. (b)

$j\in V^{\prime}$ and $\delta^{\prime}(j)\leq\lambda(ij)$.

The number $\delta^{\prime}(i)$ is the _weight_ of $v_{i}$.

######  Note 2.8.

If $(V^{\prime},\delta^{\prime})$ is a weighted vector cover of $G_{\lambda}$,
then $V^{\prime}$ is a vector cover of $G$ by definition.

######  Definition 2.9.

[4, Definition 1.9] Given two weighted vertex covers
$(V_{1}^{\prime},\delta_{1}^{\prime})$ and
$(V_{2}^{\prime},\delta_{2}^{\prime})$ of $G_{\lambda}$, we write
$(V_{2}^{\prime},\delta_{2}^{\prime})\leq(V_{1}^{\prime},\delta_{1}^{\prime})$
if $V_{2}^{\prime}\subseteq V_{1}^{\prime}$ and
$\delta_{2}^{\prime}\geq\delta_{1}^{\prime}|_{V_{2}^{\prime}}$. A weighted
vertex cover $(V^{\prime},\delta^{\prime})$ is _minimal_ if there does not
exist another weighted vertex cover $(V^{\prime\prime},\delta^{\prime\prime})$
such that
$(V^{\prime\prime},\delta^{\prime\prime})<(V^{\prime},\delta^{\prime})$. The
_cardinality_ of $(V^{\prime},\delta^{\prime})$ is defined to be the
cardinality of $V^{\prime}$, in symbols,
$\left\lvert(V^{\prime},\delta^{\prime})\right\rvert=\left\lvert
V^{\prime}\right\rvert$.

A weighted graph $G_{\lambda}$ is called _unmixed_ if all of the minimal
weighted vertex covers of $G_{\lambda}$ have the same cardinality, otherwise
it is called _mixed_.

For the proof of our first main theorem we need the following algebraic fact:

######  Lemma 2.10.

Let $R$ be a Noetherian ring, $S=R[X_{1},\dots,X_{n}]$,
$k\in\\{0,\dots,n-1\\}$ and
$J=(I_{1}X_{1},\dots,I_{k}X_{k},\\{X_{i}^{m_{ij}}X_{j}^{m_{ij}}\\}_{1\leq
i<j\leq n})$ an ideal of $S$, where $I_{1},\dots,I_{k}$ are ideals of $R$, no
$I_{j}$'s exists in $J$ if $k=0$, and $m_{ij}\in\mathbb{N}$ for any
$i,j\in\mathbb{N}$. Then $X=\sum_{i=1}^{n}X_{i}$ is a non-zero divisor on
$S/J$.

###### Proof.

Let $A\subseteq[n]$ be nonempty. Let $(K_{A})_{\lambda_{A}}$ be the weighted
complete graph on $A$ with the function $\lambda_{A}:E(K_{A})\to\mathbb{N}$
given by $\lambda_{A}(ij)=m_{ij}$ for $i,j\in A$ such that $1\leq i<j\leq n$.
For any weighted vertex cover $(V^{\prime},\delta^{\prime})$ of
$(K_{A})_{\lambda_{A}}$, define an ideal
$P^{A}(V^{\prime},\delta^{\prime}):=(X_{i}^{\delta^{\prime}(i)}\mid i\in
V^{\prime})$ in $\mathbb{K}[X_{j}\mid j\in A]$. Let $I((K_{A})_{\lambda_{A}})$
be the weighted edge ideal of $(K_{A})_{\lambda_{A}}$ in $\mathbb{K}[X_{j}\mid
j\in A]$. Then by [4, Theorem 3.5], we have that

$I((K_{A})_{\lambda_{A}})=\bigcap_{\min.\
(V^{\prime},\delta^{\prime})}P^{A}(V^{\prime},\delta^{\prime}),$

where the intersection is taken over all minimal weighted vertex covers of
$(K_{A})_{\lambda_{A}}$. For any $B\subseteq[n]$, let
$\mathfrak{X}_{B}=(X_{j}\mid j\in B)S$. For any $T\subseteq[k]$, set
$I_{T}=\sum_{j\in T}I_{j}$. Then

$\displaystyle J$
$\displaystyle=(I_{1}X_{1},\dots,I_{k}X_{k},I((K_{[n]})_{\lambda_{[n]}}))S$
$\displaystyle=\bigcap_{T\subseteq[k]}(I_{T},\mathfrak{X}_{[k]\smallsetminus
T})+\bigcap_{(W^{\prime},\gamma^{\prime})}P^{[n]}(W^{\prime},\gamma^{\prime})$
$\displaystyle=\bigcap_{T\subseteq[k]}\bigcap_{(W^{\prime},\gamma^{\prime})}\bigl{(}I_{T},\mathfrak{X}_{[k]\smallsetminus
T},P^{[n]}(W^{\prime},\gamma^{\prime})\bigr{)}S$
$\displaystyle=\bigcap_{T\subseteq[k]}\bigcap_{(V^{\prime},\delta^{\prime})}\bigl{(}I_{T},\mathfrak{X}_{[k]\smallsetminus
T},P^{[n]\smallsetminus([k]\smallsetminus
T)}(V^{\prime},\delta^{\prime})\bigr{)}S,$

where $(W,\gamma^{\prime})$ runs through all minimal weighted vertex covers of
$(K_{[n]})_{\lambda_{[n]}}$, and $(V^{\prime},\delta^{\prime})$ runs through
all minimal weighted vertex covers of $(K_{[n]\smallsetminus([k]\smallsetminus
T)})_{\lambda_{[n]\smallsetminus([k]\smallsetminus T)}}$. The third equality
follows from [3, Lemma 7.3.2] since $R$ is Noetherian.

To prove that $X$ is a non-zero divisor modulo $J$ it suffices to show that
$X$ is a non-zero divisor modulo each of the ideals
$(I_{T},\mathfrak{X}_{[k]\smallsetminus
T},P^{[n]\smallsetminus([k]\smallsetminus T)}(V^{\prime},\delta^{\prime}))S$.
It is equivalent to show that $X$ is a non-zero divisor on

$\frac{\mkern 1.0mu\overline{\mkern-1.0muR\mkern-1.0mu}\mkern
1.0mu[X_{1},\dots,X_{n}]}{(\mathfrak{X}_{[k]\smallsetminus
T},P^{[n]\smallsetminus([k]\smallsetminus T)}(V^{\prime},\delta^{\prime}))},$

where $\mkern 1.0mu\overline{\mkern-1.0muR\mkern-1.0mu}\mkern
1.0mu=\frac{R}{I_{T}}$. The associated prime of the primary ideal
$(\mathfrak{X}_{[k]\smallsetminus T},P^{[n]\smallsetminus([k]\smallsetminus
T)}(V^{\prime},\delta^{\prime}))$ generated by pure powers is
$(\mathfrak{X}_{[k]\smallsetminus T},\mathfrak{X}_{V^{\prime}})$ in $\mkern
1.0mu\overline{\mkern-1.0muR\mkern-1.0mu}\mkern 1.0mu[X_{1},\dots,X_{n}]$.
Since $(V^{\prime},\delta^{\prime})$ is a minimal weighted vertex cover of the
weighted complete graph $(K_{[n]\smallsetminus([k]\smallsetminus
T)})_{\lambda_{[n]\smallsetminus([k]\smallsetminus T)}}$, we have by [4,
Proposition 4.6] there exists an $\ell\in[n]\smallsetminus([k]\smallsetminus
T)$ but $\ell\not\in V^{\prime}$. Thus, $X$ is a non-zero divisor on it. ∎

The following example illustrates the decomposition in previous lemma.

######  Example 2.11.

Let $R=\mathbb{K}[Y]$ be a polynomial ring and $S=R[X_{1},X_{2},X_{3}]$.
Consider the ideal
$J=(YX_{1},YX_{2},X_{1}^{2}X_{2}^{2},X_{1}^{2}X_{3}^{2},X_{2}^{2}X_{3}^{2})S$
of $S$. Then with
$K=(X_{1}^{2}X_{2}^{2},X_{1}^{2}X_{3}^{2},X_{2}^{2}X_{3}^{2})S$,

$\displaystyle J$ $\displaystyle=(YX_{1},YX_{2})S+K$
$\displaystyle=(X_{1},X_{2})S\cap(Y,X_{2})S\cap(Y,X_{1})S\cap(Y,Y)S+K$
$\displaystyle=(X_{1},X_{2},K)S\cap(Y,X_{2},K)S\cap(Y,X_{1},K)S\cap(Y,K)S$
$\displaystyle=(X_{1},X_{2})S\cap(Y,X_{2},X_{1}^{2}X_{3}^{2})S\cap(Y,X_{1},X_{2}^{2}X_{3}^{2})S\cap(Y,K)S$
$\displaystyle=(X_{1},X_{2})S\cap(Y,K)S$
$\displaystyle=(X_{1},X_{2},K)S\cap(Y,K)S$ $\displaystyle=(YX_{1},YX_{2})S+K.$

In this paper, we will use Lemma 2.10 in the context of
$R=\mathbb{K}[X_{1},\dots,X_{n}]$. Before proving the two main theorems, let's
look at two particular examples.

######  Example 2.12.

The weighted edge ideal of the following weighted graph $G_{\lambda}$ is
mixed.

${v_{3}}$${v_{2}}$${\nu_{1}}$${\nu_{0}}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$$\scriptstyle{a}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}$$\scriptstyle{6}$

Theorem [4, Theorem 3.5] says that it suffices to find two minimal weighted
cover of $G_{\lambda}$ of different cardinality. Note that there always exists
a minimal weighted vertex cover of size $3+1-2=2$. For example,
$(V^{\prime},\delta^{\prime})=\\{\nu_{1}^{1},v_{2}^{1}\\}$ is a weighted
vertex cover of $G_{\lambda}$, and it is cardinality-minimal in the sense that
there doesn't exist any weighted vertex cover $(W^{\prime},\gamma^{\prime})$
of $G_{\lambda}$ such that
$(W^{\prime},\gamma^{\prime})\leq(V,\delta^{\prime})$ and $\left\lvert
W^{\prime}\right\rvert<\left\lvert V^{\prime}\right\rvert$. By [4, Proposition
1.12], $(V^{\prime},\delta^{\prime})$ induces a minimal weighted vertex cover
$(V^{\prime},\delta^{\prime\prime})$ for some
$\delta^{\prime\prime}\geq\delta^{\prime}$. But there exists another minimal
weighted vertex cover $\\{v_{3}^{\min\\{2,a\\}},v_{2}^{4},\nu_{1}^{6}\\}$,
whose size is 3.

######  Example 2.13.

The weighted edge ideal of the following weighted graph $G_{\lambda}$ is
mixed.

$x$$v$$w$$u$$\nu_{1}^{T}$$\nu_{1}^{S}$$\nu_{0}^{S}$$\nu_{0}^{T}$46296397

There exists a minimal weighted vertex cover of $G_{\lambda}$ of size
$6+1+1-3=5$. Note that
$(V^{\prime},\delta^{\prime}):=\\{(\nu_{1}^{S})^{6},u^{4},w^{1},(\nu_{1}^{T})^{9},v^{6},x^{1}\\}$
is a weighted vertex cover of $G_{\lambda}$ of cardinality 6, which is
cardinality-minimal. Thus $(V^{\prime},\delta^{\prime})$ induces a minimal
weighted vertex cover $(V^{\prime},\delta^{\prime\prime})$ for some
$\delta^{\prime\prime}\geq\delta^{\prime}$.

##  3\. The conditions of a weighted chordal graph to be Cohen-Macaulay

The next result gives a sufficient condition for weighted chordal graphs to be
Cohen-Macaulay.

######  Theorem 3.1.

Let $G_{\lambda}$ be a weighted chordal graph. Let $F_{1},\dots,F_{m}$ be the
facets of $\Delta(G)$ which admit a free vertex satisfying that for
$i=1,\dots,m$: there doesn't exist a rooted spanning forest $\mathfrak{F}$ of
$G[F_{i}]$ in which each component $T$ has a nonfree vertex $\nu_{1}^{T}$ as
the root such that there is a nonfree vertex $\nu_{0}^{T}$ in $V\smallsetminus
F_{i}$ with $\nu_{0}^{T}\nu_{1}^{T}\in E$ which satisfies that for any path
$\nu_{1}^{T}v_{2}\cdots v_{k}$ in $T$ with $v_{k}$ a $T$-leaf: if $k\geq 2$,
then
$\lambda(\nu_{0}^{T}\nu_{1}^{T})>\lambda(\nu_{1}^{T}v_{2})>\lambda(v_{2}v_{3})>\cdots>\lambda(v_{k-1}v_{k})$,
and which satisfies that for any component(s) $S,T$ of $\mathfrak{F}$: if $u$
is an $S$-inner vertex and $v$ is a $T$-inner vertex with $u\neq v$, then

$\lambda(uv)>\min\\{\max\\{\lambda(uw)\mid\text{$u$ is the $S$-parent of
$w$}\\},\max\\{\lambda(vx)\mid\text{$v$ is the $T$-parent of $x$}\\}\\};$

if $u$ is an $S$-inner vertex such that $u\nu_{0}^{T}\in E$, then

$\displaystyle\lambda(u\nu_{0}^{T})$
$\displaystyle>\min\\{\max\\{\lambda(uw)\mid\text{$u$ is the $S$-parent of
$w$}\\},$ $\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T}\nu_{1}^{Y})\mid\text{$Y$ is a component of
$\mathfrak{F}$ such that $\nu_{0}^{T}=\nu_{0}^{Y}$}\\}\\};$

and if $\nu_{0}^{S}\nu_{0}^{T}\in E$, then

$\displaystyle\lambda(\nu_{0}^{S}\nu_{0}^{T})$
$\displaystyle>\min\\{\max\\{\lambda(\nu_{0}^{S}\nu_{1}^{Y})\mid\text{$Y$ is a
component of $\mathfrak{F}$ such that $\nu_{0}^{S}=\nu_{0}^{Y}$}\\},$
$\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T}\nu_{1}^{Z})\mid\text{$Z$ is a component of
$\mathfrak{F}$ such that $\nu_{0}^{T}=\nu_{0}^{Z}$}\\}\\}.$

Then the following conditions are equivalent.

  1. (a)

$G_{\lambda}$ is Cohen-Macaulay;

  2. (b)

$G_{\lambda}$ is Cohen-Macaulay over $\mathbb{K}$;

  3. (c)

$G_{\lambda}$ is unmixed;

  4. (d)

$[n]$ is the disjoint union of $F_{1},\dots,F_{m}$.

###### Proof.

(a) $\Longrightarrow$ (b) is trivial.

(b) $\Longrightarrow$ (c) Since $\mathbb{K}[X_{1},\dots,X_{n}]/I(G_{\lambda})$
is Cohen-Macaulay, we have $I(G_{\lambda})$ is unmixed. So $G_{\lambda}$ is
unmixed by [4, Theorem 3.5 and Proposition 3.13].

(c) $\Longrightarrow$ (d) Since $G_{\lambda}$ unmixed, we have $G$ is unmixed
by [4, Proposition 1.14]. So (d) holds by [2, Theorem 2.1].

(d) $\Longrightarrow$ (c) Let $(V^{\prime},\delta^{\prime})$ be a minimal
weighted vertex cover of $G_{\lambda}$ with $V^{\prime}\subseteq[n]$ and
$\delta^{\prime}:V^{\prime}\to\mathbb{N}$. Then for $i=1,\dots,m$ we have
$\left\lvert V^{\prime}\cap F_{i}\right\rvert\geq\left\lvert
F_{i}\right\rvert-1$ since $F_{i}$ is a clique of $G$. Suppose for some
$i\in\\{1,\dots,m\\}$, we have $\left\lvert V^{\prime}\cap
F_{i}\right\rvert=\left\lvert F_{i}\right\rvert$, i.e., $F_{i}\subseteq
V^{\prime}$. Then $F_{i}$ contains a nonfree vertex by [4, Proposition 4.6].
Let $v\in F_{i}$. Claim. There exists a path
$\ell_{0}\ell_{1}\cdots\ell_{k-1}\ell_{k}$ in $G$ with $\ell_{0}\not\in
F_{i}$, $\ell_{1},\dots,\ell_{k-1}\in F_{i}$ and $\ell_{k}=v$ satisfying that
if $k\geq 2$, then
$\lambda(\ell_{0}\ell_{1})>\cdots>\lambda(\ell_{k-2}\ell_{k-1})>\lambda(\ell_{k-1}\ell_{k})$.

We will use an algorithm to find such a path. Since $v\in F_{i}\subseteq
V^{\prime}$, we have there exists $w_{1}\in V\smallsetminus\\{v\\}$ such that
$\delta^{\prime}(v)\leq\lambda(vw_{1})\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{<\delta^{\prime}(w_{1})}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr\tiny\upbracefill\crcr\kern
3.0pt\cr}}}\limits_{\text{if }w_{1}\in V^{\prime}}$. We then go through the
following steps:

  1. Step 1.

Initially, let $j:=1$.

  2. Step 2.

If $w_{j}\not\in F_{i}$ and $j=1$, then we have a path $w_{1}v$ in $G$ with
$w_{1}\not\in F_{j}$ and $v\in F_{i}$, so the claim is justified. If
$w_{j}\not\in F_{i}$ and $j\geq 2$, then by induction we have a path
$w_{j}w_{j-1}\cdots w_{1}v$ in $G$ with $w_{j}\not\in F_{i}$ and
$w_{j-1},\dots,w_{1},v\in F_{i}$ such that

$\delta^{\prime}(v)\leq\lambda(vw_{1})<\delta^{\prime}(w_{1})\leq\lambda(w_{1}w_{2})<\delta^{\prime}(w_{2})\leq\cdots<\delta^{\prime}(w_{j-1})\leq\lambda(w_{j-1}w_{j})\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{<\delta^{\prime}(w_{j})}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr\tiny\upbracefill\crcr\kern
3.0pt\cr}}}\limits_{\text{if }w_{j}\in V^{\prime}},$

implying that
$\lambda(w_{j}w_{j-1})>\lambda(w_{j-1}w_{j-2})>\cdots>\lambda(w_{2}w_{1})>\lambda(w_{1}v)$
and so the claim is justified. Hence in either case we jump out of the loop.

  3. Step 3.

If $w_{j}\in F_{i}$, then there exists $w_{j+1}\in V\smallsetminus\\{w_{j}\\}$
such that
$\delta^{\prime}(w_{j})\leq\lambda(w_{j}w_{j+1})\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{<\delta^{\prime}(w_{j+1})}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr\tiny\upbracefill\crcr\kern
3.0pt\cr}}}\limits_{\text{if }w_{j+1}\in V^{\prime}}$, so by induction there
exists a path $w_{j+1}w_{j}w_{j-1}\dots w_{1}v$ with $w_{j},\dots,w_{1},v\in
F_{i}$ such that

$\delta^{\prime}(v)\leq\lambda(vw_{1})<\delta^{\prime}(w_{1})\leq\lambda(w_{1}w_{2})<\delta^{\prime}(w_{2})\leq\cdots<\delta^{\prime}(w_{j})\leq\lambda(w_{j}w_{j+1})\underbrace{<\delta^{\prime}(w_{j+1})}_{\text{if
}w_{j+1}\in V^{\prime}}.$

  4. Step 4.

Re-define $j:=j+1$. If $w_{j}\not\in F_{i}$, then go back to Step 2. If
$w_{j}\in F_{i}$, then go back to Step 3.

Since $\left\lvert F_{i}\right\rvert$ is finite and $w_{j},\dots,w_{1},v\in
F_{i}$ are distinct to each other and $F_{i}$ contains a nonfree vertex, we
have after some finite loops, it will enter Step 2 and the claim will be
proved.

Let $v_{1}\in F_{i}$. Then by the claim there exists a path
$P_{1}:=\ell_{0}\ell_{1}\cdots\ell_{k-1}v_{1}$ in $G$ with $\ell_{0}\not\in
F_{i}$ and $\ell_{1},\dots,\ell_{k-1},v_{1}\in F_{i}$ satisfying that if
$k\geq 2$, then
$\lambda(\ell_{0}\ell_{1})>\cdots>\lambda(\ell_{k-2}\ell_{k-1})>\lambda(\ell_{k-1}v_{1})$.
Assume $V(\mathring{P}_{1})=F_{i}$. Then $k\geq 2$ since $F_{i}$ contains a
free vertex. So there exists a rooted spanning forest $\mathring{P}_{1}$ such
that the unique component $\mathring{P}_{1}$ has a nonfree vertex
$\nu_{1}^{\mathring{P}_{1}}:=\ell_{1}$ as the root and there is a nonfree
vertex $\nu_{0}^{\mathring{P}_{1}}:=\ell_{0}$ in $V\smallsetminus F_{i}$ with
$\ell_{0}\ell_{1}\in E$ which satisfies that for the unique path
$\ell_{1}\cdots\ell_{k-1}v_{1}$ in the tree $\mathring{P}_{1}$ with $v_{1}$ a
$\mathring{P}_{1}$-leaf if $k\geq 2$, then
$\lambda(\ell_{0}\ell_{1})>\cdots>\lambda(\ell_{k-2}\ell_{k-1})>\lambda(\ell_{k-1}v_{1})$.
Moreover, if $\ell_{\alpha}$ and $\ell_{\beta}$ are $\mathring{P}_{1}$-inner
vertices with $1\leq\alpha<\beta\leq k-1$, then since
$(V^{\prime},\delta^{\prime})$ is a weighted vertex cover of $G_{\lambda}$ and
$\ell_{\alpha},\ell_{\beta}\in V(\mathring{P}_{1})=F_{i}\subseteq V^{\prime}$,
after settting $\ell_{k}=v_{1}$ we have

$\displaystyle\lambda(\ell_{\alpha}\ell_{\beta})$
$\displaystyle\geq\min\\{\delta^{\prime}(\ell_{\alpha}),\delta^{\prime}(\ell_{\beta})\\}$
$\displaystyle>\min\left\\{\lambda(\ell_{\alpha}\ell_{\alpha+1}),\lambda(\ell_{\beta}\ell_{\beta+1})\right\\}$
$\displaystyle=\min\\{\max\\{\lambda(\ell_{\alpha}w)\mid\text{$\ell_{\alpha}$
is the $\mathring{P}_{1}$-parent of
$w$}\\},\max\\{\lambda(\ell_{\beta}x)\mid\text{$\ell_{\beta}$ is the
$\mathring{P}_{1}$-parent of $x$}\\}\\};$

and if $\ell_{\alpha}$ is an $\mathring{P}_{1}$-inner vertex such that
$u\nu_{0}^{\mathring{P}_{1}}\in E$, then $\ell_{\alpha}=\ell_{1}$, and so

$\displaystyle\lambda(\ell_{\alpha}\nu_{0}^{\mathring{P}_{1}})$
$\displaystyle=\lambda(\ell_{0}\ell_{1})$
$\displaystyle>\max\\{\lambda(\ell_{1}w)\mid\text{$\ell_{1}$ is the
$\mathring{P}_{1}$-parent of $w$}\\}$
$\displaystyle\geq\min\\{\max\\{\lambda(\ell_{\alpha}w)\mid\text{$\ell_{\alpha}$
is the $\mathring{P}_{1}$-parent of
$w$}\\},\lambda(\nu_{0}^{\mathring{P}_{1}}\nu_{1}^{\mathring{P}_{1}})\\},$

a contradiction.

On the other hand, we assume $V(\mathring{P}_{1})\subsetneq F_{i}$. We then go
through the following steps:

  1. Step 1.

Initially, let $b:=1$.

  2. Step 2.

If there exists a vertex $v\in
F_{i}\smallsetminus(V(\mathring{P}_{1})\cup\cdots\cup V(\mathring{P}_{b}))$,
then there exists a path $P_{b+1}:=h_{0}h_{1}\cdots h_{k^{\prime}-1}v$ in $G$
with $h_{0}\not\in F_{i}$ and $h_{1},\dots,h_{k^{\prime}-1},v\in F_{i}$
satisfying that if $k^{\prime}\geq 2$, then
$\lambda(h_{0}h_{1})>\cdots>\lambda(h_{k^{\prime}-2}\lambda_{k^{\prime}-1})>\lambda(h_{k^{\prime}-1}v)$.
If $V(\mathring{P}_{b+1})\cap(V(\mathring{P}_{1})\cup\cdots\cup
V(\mathring{P}_{b}))=\emptyset$, then we put $\mathring{P}_{b+1}$ into the
rooted forest formed by $\mathring{P}_{1},\dots,\mathring{P}_{b}$ while making
$\mathring{P}_{b+1}$ a rooted tree with root $h_{1}$ and making
$\mathring{P}_{b+1}$ a component of the rooted forest. Assume
$V(\mathring{P}_{b+1})\cap(V(\mathring{P}_{1})\cup\cdots\cup
V(\mathring{P}_{b}))\neq\emptyset$. Let $t=\max\\{c\geq 1\mid h_{c}\in
V(\mathring{P}_{1})\cup\cdots\cup V(\mathring{P}_{b})\\}$. Assume
$h_{t}=u_{s}\in V(\mathring{P}_{d})$ with $P_{d}:=u_{0}u_{1}\cdots u_{j}$ for
some $d\in\\{1,\dots,b\\}$ and $s\in\\{1,\dots,j\\}$. Set
$P_{b+1}^{\prime}:=u_{0}u_{1}\cdots u_{s-1}h_{t}h_{t+1}\cdots
h_{k^{\prime}-1}v$. Then $P_{b+1}^{\prime}$ is a path in $G$ with
$u_{0}\not\in F_{i}$ and
$u_{1},\dots,u_{s-1},h_{t},h_{t+1},\dots,h_{k^{\prime}-1},v\in F_{i}$. Since
$\lambda(u_{s-1}h_{t})=\lambda(u_{s-1}u_{s})\geq\delta^{\prime}(u_{s})=\delta^{\prime}(h_{t})>\lambda(h_{t}h_{t+1})$,
we have
$\lambda(u_{0}u_{1})>\cdots>\lambda(u_{s-1}h_{t})>\lambda(h_{t}h_{t+1})>\cdots>\lambda(h_{k^{\prime}-1}v)$.
Re-define $P_{b+1}:=P_{b+1}^{\prime}$, then $\mathring{P}_{b+1}$ is merged
into the component whose root is $u_{1}$, in the rooted forest formed by
$\mathring{P}_{1},\dots,\mathring{P}_{b}$.

  3. Step 3.

If $V(\mathring{P}_{1})\cup\cdots\cup V(\mathring{P}_{b+1})\subsetneq F_{i}$,
then re-define $b:=b+1$ and go back to Step 2.

  4. Step 4.

If $V(\mathring{P}_{1})\cup\cdots\cup V(\mathring{P}_{b+1})=F_{i}$, then there
exists a rooted spanning forest $\mathfrak{F}$ such that by induction each
component $T$ in $\mathfrak{F}$, which is formed by a subset of the paths
$\mathring{P}_{1},\dots,\mathring{P}_{b+1}$ say
$\mathring{P}_{i_{1}},\dots,\mathring{P}_{i_{\iota}}$, has the nonfree vertex
$\nu_{1}^{T}$ as the root, which is the first vertex of any one of the paths
$\mathring{P}_{i_{1}},\dots,\mathring{P}_{i_{\iota}}$, such that there is a
nonfree vertex $\nu_{0}^{T}$ in $V\smallsetminus F_{i}$ with
$\nu_{0}^{T}\nu_{1}^{T}\in E$, which is the first vertex of any one of the
paths $P_{i_{1}},\dots,P_{i_{\iota}}$, which satisfies that for the each path
$\nu_{1}^{T}u_{2}\cdots u_{j-1}u_{j}$ in the tree $T$ with $u_{j}$ a $T$-leaf
if $j\geq 2$, then
$\lambda(\nu_{0}^{T}\nu_{1}^{T})>\lambda(\nu_{1}^{T}u_{2})>\cdots>\lambda(u_{j-1}u_{j})$.
Moreover, for any component(s) $S,T$ of $\mathfrak{F}$, if $u$ is an $S$-inner
vertex and $v$ is a $T$-inner vertex with $u\neq v$, then since
$(V^{\prime},\delta^{\prime})$ is a weighted vertex cover of $G_{\lambda}$ and
$u,v\in(V(\mathring{P}_{1})\cup\cdots\cup
V(\mathring{P}_{b+1}))=F_{i}\subseteq V^{\prime}$, we have

$\displaystyle\lambda(uv)$
$\displaystyle\geq\min\\{\delta^{\prime}(u),\delta^{\prime}(v)\\}$
$\displaystyle>\min\\{\max_{1\leq c\leq{b+1}}\\{\lambda(uw)\mid uw\in
E(\mathring{P}_{c})\\},\max_{1\leq d\leq{b+1}}\\{\lambda(vx)\mid vx\in
E(\mathring{P}_{d})\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(uw)\mid\text{$u$ is the $S$-parent of
$w$}\\},\max\\{\lambda(vx)\mid\text{$v$ is the $T$-parent of $x$}\\}\\};$

if $u$ is an $S$-inner vertex such that $u\nu_{0}^{T}\in E$, then since
$(V^{\prime},\delta^{\prime})$ is a weighted vertex cover of $G_{\lambda}$,

$\displaystyle\lambda(u\nu_{0}^{T})$
$\displaystyle\geq\min\\{\delta^{\prime}(u)\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{,\delta^{\prime}(\nu_{0}^{T})}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr\tiny\upbracefill\crcr\kern
3.0pt\cr}}}\limits_{\text{if }\nu_{0}^{T}\in V^{\prime}}\\}$
$\displaystyle>\min\\{\max_{1\leq c\leq b+1}\\{\lambda(uw)\mid uw\in
E(\mathring{P}_{c})\\},$ $\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T}\nu_{1}^{Y})\mid\text{$Y$ is a component of
$\mathfrak{F}$ such that $\nu_{0}^{T}=\nu_{0}^{Y}$}\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(uw)\mid\text{$u$ is the $S$-parent of
$w$}\\},$ $\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T}\nu_{1}^{Y})\mid\text{$Y$ is a component of
$\mathfrak{F}$ such that $\nu_{0}^{T}=\nu_{0}^{Y}$}\\}\\};$

and if $\nu_{0}^{S}\nu_{0}^{T}\in E$, then since
$(V^{\prime},\delta^{\prime})$ is a weighted vertex cover of $G_{\lambda}$, by
symmetry we assume $\nu_{0}^{S}\in V^{\prime}$ and
$\delta^{\prime}(\nu_{0}^{S})\leq\lambda(\nu_{0}^{S}\nu_{0}^{T})$, so

$\displaystyle\lambda(\nu_{0}^{S}\nu_{0}^{T})$
$\displaystyle\geq\delta^{\prime}(\nu_{0}^{S})$
$\displaystyle>\max\\{\lambda(\nu_{0}^{S}\nu_{1}^{Y})\mid\text{$Y$ is a
component of $\mathfrak{F}$ such that $\nu_{0}^{S}=\nu_{0}^{Y}$}\\}$
$\displaystyle\geq\min\\{\max\\{\lambda(\nu_{0}^{S}\nu_{1}^{Y})\mid\text{$Y$
is a component of $\mathfrak{F}$ such that $\nu_{0}^{S}=\nu_{0}^{Y}$}\\},$
$\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T}\nu_{1}^{Z})\mid\text{$Z$ is a component of
$\mathfrak{F}$ such that $\nu_{0}^{T}=\nu_{0}^{Z}$}\\}\\},$

a contradiction.

Since $\left\lvert F_{i}\right\rvert$ is finite, after some finite loops it
will enter Step 4 and there will be a contradiction.

Thus, $\left\lvert V^{\prime}\cap F_{i}\right\rvert=\left\lvert
F_{i}\right\rvert-1$ for $i=1,\dots,m$. Since $[n]$ is the disjoint union
$[n]=\bigcup_{i=1}^{m}F_{i}$, it follows that
$\left\lvert(V^{\prime},\delta^{\prime})\right\rvert=\left\lvert
V^{\prime}\right\rvert=n-m$ and $G_{\lambda}$ is unmixed.

(c) and (d) $\Longrightarrow$ (a) We have that $G_{\lambda}$ is unmixed and
each minimal weighted vertex cover of $G_{\lambda}$ has cardinality $n-m$. Let
$S=\mathbb{K}[X_{1},\dots,X_{n}]$. Then $\dim S/I(G_{\lambda})=m$. Let
$Y_{i}=\sum_{j\in F_{i}}X_{j}$ for $i=1,\dots,m$. We will show that
$Y_{1},\dots,Y_{m}$ is a regular sequence on $S/I(G_{\lambda})$. This then
yields that $G_{\lambda}$ is Cohen-Macaulay. Let $i\in\\{2,\dots,m\\}$,
$F_{i}:=\\{i_{1},\dots,i_{\ell}\\}$ and assume that $i_{1},\dots,i_{k}$ are
the nonfree vertices of $G[F_{i}]$. Then $k\in\\{0,\dots,n-1\\}$. Let
$G^{\prime}=G[[n]\smallsetminus\\{i_{1},\dots,i_{\ell}\\}]$ and
$\lambda^{\prime}=\lambda|_{E(G^{\prime})}$. Then
$I(G_{\lambda})=(I(G^{\prime}_{\lambda^{\prime}}),J_{1}X_{i_{1}},\dots,J_{k}X_{i_{k}},J)$,
where $J_{j}=(X_{i_{j}}^{\lambda(i_{j}r)-1}X_{r}^{\lambda(i_{j}r)}\mid
i_{j}r\in E)$ for $j=1,\dots,k$, and
$J=(X_{i_{r}}^{\lambda(i_{r}i_{s})}X_{i_{s}}^{\lambda(i_{r}i_{s})}\mid 1\leq
r<s\leq\ell)$. Since $[n]$ is the disjoint union of $F_{1},\dots,F_{m}$ we
have all generators of the ideal
$(I(G^{\prime}_{\lambda^{\prime}}),Y_{1},\dots,Y_{i-1})$ belong to
$\mathbb{K}[X_{j}\mid j\in[n]\smallsetminus F_{i}]$. Thus, if we set
$R=\frac{\mathbb{K}[X_{j}\mid j\in[n]\smallsetminus
F_{i}]}{(I(G^{\prime}_{\lambda^{\prime}}),Y_{1},\dots,Y_{i-1})}$, then

$\frac{\frac{S}{I(G_{\lambda})}}{(Y_{1},\dots,Y_{i-1})\frac{S}{I(G_{\lambda})}}\cong\frac{R[X_{i_{1}},\dots,X_{i_{\ell}}]}{(I_{1}X_{i_{1}},\dots,I_{k}X_{i_{k}},\\{X_{i_{r}}^{\lambda(i_{r}i_{s})}X_{i_{s}}^{\lambda(i_{r}i_{s})}\mid
1\leq r<s\leq\ell\\})},$

where for each $j$, the ideal $I_{j}$ is the image of $J_{j}$ under the
residue class map onto $R$. Thus, Lemma 2.10 implies that $Y_{i}$ is regular
on $(S/I(G_{\lambda}))/(Y_{1},\dots,Y_{i-1})(S/I(G_{\lambda}))$. ∎

We use the following example to illustrate the previous theorem and its proof.

######  Example 3.2.

The following weighted chordal graph $G_{\lambda}$ where we only give part
weights of $\lambda$ is not Cohen-Macaulay. In the drawing, let $\nu^{\tau}$
denote an element of $(V^{\prime},\delta^{\prime})$ with $\nu\in V^{\prime}$
and $\delta^{\prime}(\nu)=\tau$.

$a^{1}$$b^{4}$$c^{1}$$d^{1}$$e^{4}$$f^{1}$$g^{6}$$h^{1}$$i^{6}$$j^{3}$$k^{1}$$l^{3}$$m^{8}$$n^{4}$$o^{1}$$p^{1}$$q^{1}$$r^{4}$$s^{5}$$t^{1}$$u^{1}$$v^{1}$$w^{1}$$x^{1}$$y^{1}$$z$5523457623533449566434584

Let $F_{1}=\\{a,\dots,l\\}$, $F_{2}=\\{m,\dots,r\\}$, $F_{3}=\\{s,\dots,x\\}$
and $F_{4}=\\{y,z\\}$. There is a rooted spanning forest $\mathfrak{F}$ of
$G[F_{1}]$ consisting of components $T_{1},\dots,T_{5}$ whose roots are
$\nu_{1}^{T_{1}}:=g,\nu_{1}^{T_{2}}:=e,\nu_{1}^{T_{3}}:=i,\nu_{1}^{T_{4}}=h,\nu_{1}^{T_{5}}=j$,
respectively.

${l}$${a}$${b}$${c}$${g}$${T_{1}}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}$
${d}$${e}$${T_{2}}$$\scriptstyle{\definecolor[named]{.}{rgb}{.75,0,.25}\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}3}$
${f}$${i}$${T_{3}}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,1,0}\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}5}$
${h}$${T_{4}}$
${k}$${j}$${T_{5}}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,0,.5}\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}2}$

Let $\nu_{0}^{T_{1}}:=m$, $\nu_{0}^{T_{2}}:=s$, $\nu_{0}^{T_{3}}:=m$,
$\nu_{0}^{T_{4}}:=n$ and $\nu_{0}^{T_{5}}:=r$. For example, for the path $gbl$
in $T_{1}$ with $l$ a $T_{1}$-leaf, we have
$\lambda(\nu_{0}^{T_{1}}\nu_{1}^{T_{1}})>\lambda(\nu_{1}^{T_{1}}b)>\lambda(bl)$
since $6>4>3$.

${l}$${a}$${b}$${c}$${g}$${m}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}$
${d}$${e}$${s}$$\scriptstyle{\definecolor[named]{.}{rgb}{.75,0,.25}\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}3}$$\scriptstyle{\definecolor[named]{.}{rgb}{.75,0,.25}\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}4}$
${f}$${i}$${m}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,1,0}\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}5}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,1,0}\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}7}$
${h}$${n}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}$
${k}$${j}$${r}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,0,.5}\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}2}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,0,.5}\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}3}$

Let $\mathcal{S}=\\{m,n,s,r\\}$, $i=3$,
$V_{2}=F_{2}\cap\mathcal{S}=\\{\nu_{0}^{T_{1}}=m=\nu_{0}^{T_{3}},\nu_{0}^{T_{4}}=n,\nu_{0}^{T_{5}}=r\\}$,
$V_{3}=F_{3}\cap S=\\{\nu_{0}^{T_{2}}=s\\}$. Let

$W=F_{2}\sqcup F_{3}\sqcup(F_{4}\smallsetminus\\{z\\})=\\{m,\dots,y\\}.$

Let $\delta:F_{1}\sqcup W\to\mathbb{N}$. The definition for $\delta$ is given
in the drawing for $G_{\lambda}$. For example, since $m\in V_{2}$,

$\displaystyle\delta(m)$ $\displaystyle=\gamma_{2}(m)$
$\displaystyle=1+\max_{j\in\\{1,2,3,4,5\\}}\\{\lambda(m\nu_{1}^{T_{j}})\mid
m=\nu_{0}^{T_{j}}\\}$
$\displaystyle=1+\max_{j\in\\{1,3,4,5\\}}\\{\lambda(m\nu_{1}^{T_{j}})\mid
m=\nu_{0}^{T_{j}}\\}$
$\displaystyle=1+\max\\{\lambda(m\nu_{1}^{T_{1}}),\lambda(m\nu_{1}^{T_{3}})\\}$
$\displaystyle=1+\max\\{\lambda(mg),\lambda(mi)\\}$
$\displaystyle=1+\max\\{6,7\\}$ $\displaystyle=8,$

For $T_{1}$-inner vertex $b$,

$\displaystyle\delta(b)$ $\displaystyle=1+\max\\{\lambda(b\alpha)\mid\text{$b$
is the $T_{1}$-parent of $\alpha$}\\}$
$\displaystyle=1+\max\\{\lambda(ba),\lambda(bl)\\}.$
$\displaystyle=1+\max\\{2,3\\}$ $\displaystyle=4.$

We have for example, for $T_{1}$-inner vertex $b$ and $T_{3}$-inner vertex
$i$,

$\displaystyle\lambda(bi)$ $\displaystyle=6$
$\displaystyle>\min\\{\max\\{2,3\\},5\\}$
$\displaystyle=\min\\{\max\\{\lambda(ba),\lambda(bl)\\},\max\\{\lambda(if)\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(b\alpha)\mid\text{$b$ is the
$T_{1}$-parent of $\alpha$}\\},$ $\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(i\beta)\mid i\text{ is the $T_{3}$-parent of $\beta$}\\}\\};$

for $T_{1}$-inner vertex $b$ and $b\nu_{0}^{T_{3}}=bm\in E$, we have

$\displaystyle\lambda(bm)$ $\displaystyle=5$
$\displaystyle>\min\\{\max\\{2,3\\},\max\\{6,7\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(ba),\lambda(bl)\\},\max\\{\lambda(mg),\lambda(mi)\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(ba),\lambda(bl)\\},\max\\{\lambda(m\nu_{1}^{T_{1}}),\lambda(m\nu_{1}^{T_{3}})\\}\\}$
$\displaystyle=\min\\{\max\\{b\alpha\mid\text{$b$ is the $T_{1}$-parent of
$\alpha$}\\},$ $\displaystyle\ \ \ \ \ \ \ \
\max_{j\in\\{1,2,3,4,5\\}}\\{\lambda(m\nu_{1}^{T_{j}})\mid
m=\nu_{0}^{T_{j}}\\}\\};$

for $ms\in E$, we have

$\displaystyle\lambda(ms)$ $\displaystyle=5$
$\displaystyle>\min\\{\max\\{6,7\\},\max\\{4\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(mg),\lambda(mi)\\},\max\\{\lambda(se)\\}\\}$
$\displaystyle=\min\\{\max\\{\lambda(m\nu_{1}^{T_{1}}),\lambda(m\nu_{1}^{T_{3}})\\},\max\\{\lambda(s\nu_{1}^{T_{2}})\\}\\}$
$\displaystyle=\min\\{\max_{j\in\\{1,2,3,4,5\\}}\\{\lambda(m\nu_{1}^{T_{j}})\mid
m=\nu_{0}^{T_{j}}\\},$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\max_{j\in\\{1,2,3,4,5\\}}\\{\lambda(s\nu_{1}^{T_{j}})\mid
s=\nu_{0}^{T_{j}}\\}\\}.$

One can check that the given weighted vertex cover $(F_{1}\sqcup
W=\\{a,\dots,y\\},\delta)$ is a weighted vertex cover of $G_{\lambda}$ but
$((F_{1}\sqcup W)\smallsetminus\\{v\\},\delta|_{(F_{1}\sqcup
W)\smallsetminus\\{v\\}})$ is not a weighted vertex cover of $G_{\lambda}$ for
any $v\in F_{1}$. Hence there exists a minimal weighted vertex cover of
$G_{\lambda}$ with cardinality $\geq 23$.

The next result says that the sufficient condition in Theorem 3.1 is also a
necessary condition.

######  Theorem 3.3.

Let $G_{\lambda}$ be a weighted chordal graph. Let $F_{1},\dots,F_{m}$ be the
facets of $\Delta(G)$ which admit a free vertex satisfying that $[n]$ is the
disjoint union of $F_{1},\dots,F_{m}$. If $G_{\lambda}$ is Cohen-Macaulay,
then $G$ and $\lambda$ satisfies the condition in Theorem 3.1.

###### Proof.

Proof by contrapositive. Without loss of generality, we assume that there
exists such a rooted spanning forest $\mathfrak{F}$ of $G[F_{1}]$ consisting
of components $T_{1},\dots,T_{k}$ in which each rooted tree $T_{i}$ has a
nonfree vertex $\nu_{1}^{T_{i}}$ as a root such that there is a nonfree vertex
$\nu_{0}^{T_{i}}$ in $V\smallsetminus F_{1}$ with
$\nu_{0}^{T_{i}}\nu_{1}^{T_{i}}\in E$ satisfying the conditions as in the
statement of the theorem. Let $\mathcal{S}$ be the minimal set containing
$\nu_{0}^{T_{1}},\dots,\nu_{0}^{T_{k}}$. Without loss of generality, we assume
$\mathcal{S}\subseteq F_{2}\sqcup\dots\sqcup F_{i}$ for some
$i\in\mathbb{N}\smallsetminus\\{1\\}$ and $F_{j}\cap\mathcal{S}\neq\emptyset$
for $j=2,\dots,i$.

For $j=2,\dots,i$, assume
$F_{j}\cap\mathcal{S}=\\{\nu_{0}^{T_{j_{1}}},\dots,\nu_{0}^{T_{j_{\ell}}}\\}=:V_{j}$
for some subset $\\{j_{1},\dots,j_{\ell}\\}\subseteq\\{1,\dots,k\\}$, and
define $\gamma_{j}:V_{j}\to\mathbb{N}$ by

$\displaystyle\gamma_{j}(\nu_{0}^{T_{j_{a}}})$
$\displaystyle=1+\max_{j^{\prime}\in\\{1,\dots,k\\}}\\{\lambda(\nu_{0}^{T_{j_{a}}}\nu_{1}^{T_{j^{\prime}}})\mid\nu_{0}^{T_{j_{a}}}=\nu_{0}^{T_{j^{\prime}}}\\}$
$\displaystyle=1+\max_{j_{a^{\prime}}\in\\{j_{1},\dots,j_{\ell}\\}}\\{\lambda(\nu_{0}^{T_{j_{a}}}\nu_{1}^{T_{j_{a^{\prime}}}})\mid\nu_{0}^{T_{j_{a}}}=\nu_{0}^{T_{j_{a^{\prime}}}}\\}.$

For $j=i+1,\dots,m$, assume that $v_{j}\in F_{j}$ is a free vertex. Let

$W:=F_{2}\sqcup\cdots\sqcup
F_{i}\sqcup(F_{i+1}\smallsetminus\\{v_{i+1}\\})\sqcup\cdots\sqcup(F_{m}\smallsetminus\\{v_{m}\\}).$

Let $\delta:F_{1}\sqcup W\to\mathbb{N}$. For $j=2,\dots,i$, set
$\delta(v)=\gamma_{j}(v)$ for any $v\in V_{j}$. Set $\delta(v)=1$ for any
$v\in W\smallsetminus(V_{2}\sqcup\cdots\sqcup V_{i})$. If
$\nu_{0}^{T_{j_{c}}}\in V_{j}$ and $\nu_{0}^{T_{j^{\prime}_{d}}}\in
V_{j^{\prime}}$ such that $\nu_{0}^{T_{j_{c}}}\nu_{0}^{T_{j^{\prime}_{d}}}\in
E$ for some $j,j^{\prime}\in\\{2,\dots,i\\}$, then by assumption,

$\displaystyle\lambda(\nu_{0}^{T_{j_{c}}}\nu_{0}^{T_{j^{\prime}_{d}}})$
$\displaystyle>\min\\{\max\\{\lambda(\nu_{0}^{T_{j_{c}}}\nu_{1}^{Y})\mid\text{$Y$
is a component of $\mathfrak{F}$ such that
$\nu_{0}^{T_{j_{c}}}=\nu_{0}^{Y}$}\\},$ $\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T_{j^{\prime}_{d}}}\nu_{1}^{Z})\mid\text{$Z$ is a
component of $\mathfrak{F}$ such that
$\nu_{0}^{T_{j^{\prime}_{d}}}=\nu_{0}^{Z}$}\\}\\}$
$\displaystyle=\min\\{\max_{j_{c^{\prime}}\in\\{j_{1},\dots,j_{\ell}\\}}\\{\lambda(\nu_{0}^{T_{j_{c}}}\nu_{1}^{T_{j_{c^{\prime}}}})\mid\nu_{0}^{T_{j_{c}}}\nu_{1}^{T_{j_{c^{\prime}}}}\\},$
$\displaystyle\ \ \ \ \ \ \ \ \
\,\max_{j^{\prime}_{d^{\prime}}\in\\{j_{1}^{\prime},\dots,j_{\ell}^{\prime}\\}}\\{\lambda(\nu_{0}^{T_{j^{\prime}_{d}}}\nu_{1}^{T_{j^{\prime}_{d^{\prime}}}})\mid\nu_{0}^{T_{j^{\prime}_{d}}}=\nu_{1}^{T_{j^{\prime}_{d^{\prime}}}}\\}\\}$
$\displaystyle=\min\\{\gamma_{j}(\nu_{0}^{T_{j_{c}}})-1,\gamma_{j^{\prime}}(\nu_{0}^{T_{j^{\prime}_{d}}})-1\\}$
$\displaystyle=\min\\{\delta(\nu_{0}^{T_{j_{c}}})-1,\delta(\nu_{0}^{T_{j^{\prime}_{d}}})-1\\},$

implying that
$\min\\{\delta(\nu_{0}^{T_{j_{c}}}),\delta(\nu_{0}^{T_{j^{\prime}_{d}}})\\}\leq\lambda(\nu_{0}^{T_{j_{c}}}\nu_{0}^{T_{j^{\prime}_{d}}})$.
So we have $(W,\delta|_{W})$ is a weighted vertex cover of
$(G-F_{1})_{\lambda|_{E(G-F_{1})}}$. For $j=1,\dots,k$ set $\delta(v)=1$ for
any $T_{j}$-leaf $v$ and set $\delta(v)=1+\max\\{\lambda(vw)\mid\text{$v$ is
the $T_{j}$-parent of $w$}\\}$ for any $T_{j}$-inner vertex $v$. Since
$\mathfrak{F}$ is a spanning forest of $G[F_{1}]$, we have defined $\delta(v)$
for all $v\in F_{1}$. If $u$ is a $T_{c}$-inner vertex and $v$ is a
$T_{d}$-inner vertex for some $c,d\in\\{1,\dots,k\\}$ with $c\neq d$. Then by
assumption,

$\displaystyle\lambda(uv)$
$\displaystyle>\min\\{\max\\{\lambda(uw)\mid\text{$u$ is the $T_{c}$-parent of
$w$}\\},\max\\{\lambda(vx)\mid\text{$v$ is the $T_{d}$-parent of $x$}\\}\\}$
$\displaystyle=\min\\{\delta(u)-1,\delta(v)-1\\}$
$\displaystyle=\min\\{\delta(u),\delta(v)\\}-1,$

implying that $\min\\{\delta(u),\delta(v)\\}\leq\lambda(uv)$. For
$j=1,\dots,k$, we have

$\displaystyle\lambda(\nu_{0}^{T_{j}}\nu_{1}^{T_{j}})$
$\displaystyle>\max\\{\lambda(\nu_{1}^{T_{j}}w)\mid\text{$\nu_{1}^{T_{j}}$ is
the $T_{j}$-parent of $w$}\\}$ $\displaystyle=\delta(\nu_{1}^{T_{j}})-1,$

implying that
$\delta(\nu_{1}^{T_{j}})\leq\lambda(\nu_{0}^{T_{j}}\nu_{1}^{T_{j}})$.
Furthermore, if $u$ is an $T_{c}$-inner vertex such that
$u\nu_{0}^{T_{j_{d}}}\in E$ for some $c\in\\{1,\dots,k\\}$ and
$j\in\\{2,\dots,i\\}$, then by assumption,

$\displaystyle\lambda(u\nu_{0}^{T_{j_{d}}})$
$\displaystyle>\min\\{\max\\{\lambda(uw)\mid\text{$u$ is the $T_{c}$-parent of
$w$}\\},$ $\displaystyle\ \ \ \ \ \ \ \ \
\,\max\\{\lambda(\nu_{0}^{T_{j_{d}}}\nu_{1}^{Y})\mid\text{$Y$ is a component
of $\mathfrak{F}$ such that $\nu_{0}^{T_{j_{d}}}=\nu_{0}^{Y}$}\\}\\}$
$\displaystyle=\min\\{\delta(u)-1,\max_{j_{d^{\prime}}\in\\{j_{1},\dots,j_{\ell}\\}}\\{\lambda(\nu_{0}^{T_{j_{d}}}\nu_{1}^{T_{j_{d^{\prime}}}})\mid\nu_{0}^{T_{j_{d}}}\nu_{1}^{T_{j_{d^{\prime}}}}\in
E\\}\\}$
$\displaystyle=\min\\{\delta(u)-1,\gamma_{j}(\nu_{0}^{T_{j_{d}}})-1\\}$
$\displaystyle=\min\\{\delta(u)-1,\delta(\nu_{0}^{T_{j_{d}}})-1\\},$

implying that
$\min\\{\delta(u),\delta(\nu_{0}^{T_{j_{d}}})\\}\leq\lambda(u\nu_{0}^{T_{j_{d}}})$.
Hence $(F_{1}\sqcup W,\delta)$ is a weighted vertex cover of $G_{\lambda}$.

For $j=1,\dots,k$, let $v\in F_{1}\smallsetminus\\{\nu_{1}^{T_{j}}\\}$ and
$p_{v}$ its $T_{j}$-parent, since $(F_{1}\sqcup W,\delta)$ is a weighted
vertex cover of $G_{\lambda}$ and

$\displaystyle\delta(p_{v})$
$\displaystyle=1+\max\\{\lambda(p_{v}w)\mid\text{$p_{v}$ is the $T_{j}$-parent
of $w$}\\}$ $\displaystyle\geq 1+\lambda(p_{v}v),$

we have $\delta(v)\leq\lambda(p_{v}v)$, hence $((F_{1}\sqcup
W)\smallsetminus\\{v\\},\delta|_{(F_{1}\sqcup W)\smallsetminus\\{v\\}})$ is no
longer a weighted vertex cover of $G_{\lambda}$. For $j=1,\dots,k$, there
exists $j^{\prime}\in\\{2,\dots,i\\}$ and
$j^{\prime}_{d}\in\\{j^{\prime}_{1},\dots,j^{\prime}_{\ell}\\}$ such that
$j^{\prime}_{d}=j$, since $(F_{1}\sqcup W,\delta)$ is a weighted vertex cover
of $G_{\lambda}$ and

$\displaystyle\delta(\nu_{0}^{T_{j}})$
$\displaystyle=\delta(\nu_{0}^{T_{j^{\prime}_{d}}})$
$\displaystyle=\gamma_{j^{\prime}}(\nu_{0}^{T_{j^{\prime}_{d}}})$
$\displaystyle=1+\max_{j^{\prime}_{d^{\prime}}\in\\{j^{\prime}_{1},\cdots,j^{\prime}_{\ell}\\}}\\{\lambda(\nu_{0}^{T_{j^{\prime}_{d}}}\nu_{1}^{T_{j^{\prime}_{d^{\prime}}}})\mid\nu_{0}^{T_{j^{\prime}_{d}}}\nu_{1}^{T_{j^{\prime}_{d^{\prime}}}}\in
E\\}$ $\displaystyle\geq
1+\lambda(\nu_{0}^{T_{j^{\prime}_{d}}}\nu_{1}^{T_{j^{\prime}_{d}}}),$

we have
$\delta(\nu_{1}^{T_{j}})=\delta(\nu_{1}^{T_{j^{\prime}_{d}}})\leq\lambda(\nu_{0}^{T_{j^{\prime}_{d}}}\nu_{1}^{T_{j^{\prime}_{d}}})$,
hence $((F_{1}\sqcup
W)\smallsetminus\\{\nu_{1}^{T_{j}}\\},\delta|_{(F_{1}\sqcup
W)\smallsetminus\\{\nu_{1}^{T_{j}}\\}})$ is not a weighted vertex cover of
$G_{\lambda}$. So $((F_{1}\sqcup W)\smallsetminus\\{v\\},\delta|_{(F_{1}\sqcup
W)\smallsetminus\\{v\\}})$ is not a weighted vertex cover of $G_{\lambda}$ for
any $v\in F_{1}$. Thus, there exists a minimal weighted vertex $(F_{1}\sqcup
W^{\prime},\delta^{\prime})$ of $G_{\lambda}$ such that $W^{\prime}\subseteq
W$ and $\delta^{\prime}\geq\delta$ by [4, Proposition 1.12]. Since
$F_{2},\dots,F_{m}$ are cliques of $G$, we have $\left\lvert
W^{\prime}\right\rvert\geq\left\lvert W\right\rvert-(i-1)$. So

$\left\lvert(F_{1}\sqcup
W^{\prime},\delta^{\prime})\right\rvert\geq\left\lvert
F_{1}\right\rvert+\left\lvert W\right\rvert-(i-1)=n-(m-i)-(i-1)=n-m+1.$

On the other hand, assume that $v_{j}\in F_{j}$ is free for $j=1,\dots,m$. Let
$U=V\smallsetminus\\{v_{1},\dots,v_{m}\\}$ and
$\delta^{\prime}:U\to\mathbb{N}$ defined by $\delta^{\prime}(v)=1$. Then
$(U,\delta^{\prime})$ is a weighted vertex cover of $G_{\lambda}$. For any
$v\in U$, we have $v\in F_{j}$ for some $j\in\\{1,\dots,m\\}$ and so
$vv_{j}\in E$, hence
$(U\smallsetminus\\{v\\},\delta^{\prime}|_{U\smallsetminus\\{v\\}})$ is not a
weighted vertex cover of $G_{\lambda}$. So there is a minimal weighted vertex
cover $(U,\delta^{\prime\prime})$ of $G_{\lambda}$ such that
$\delta^{\prime\prime}\geq\delta^{\prime}$ by [4, Proposition 1.12], but
$\left\lvert(U,\delta^{\prime\prime})\right\rvert=\left\lvert
U\right\rvert=n-m$. Therefore, $G_{\lambda}$ is mixed and so $G_{\lambda}$ is
not Cohen-Macaulay by Theorem 3.1. ∎

## Acknowledgments

I am grateful for the insightful comments and feedback provided by Keri
Sather-Wagstaff and Janet Vassilev.

## References

  * [1] Reinhard Diestel.  Graph theory, volume 173 of Graduate Texts in Mathematics.  Springer, Berlin, fifth edition, 2018.  Paperback edition of [ MR3644391].
  * [2] Jürgen Herzog, Takayuki Hibi, and Xinxian Zheng.  Cohen-Macaulay chordal graphs.  J. Combin. Theory Ser. A, 113(5):911–916, 2006.
  * [3] W. Frank Moore, Mark Rogers, and Keri Sather-Wagstaff.  Monomial ideals and their decompositions.  Universitext. Springer, Cham, 2018.
  * [4] Chelsey Paulsen and Sean Sather-Wagstaff.  Edge ideals of weighted graphs.  J. Algebra Appl., 12(5):1250223, 24, 2013.


# When to pull data from sensors for minimum Age of incorrect Information

Saad Kriouile† † Huawei Technologies, France
∗Laboratoire des Signaux et Systèmes, CentraleSupélec, Université Paris-
Saclay, France  Mohamad Assaad∗ † Huawei Technologies, France
∗Laboratoire des Signaux et Systèmes, CentraleSupélec, Université Paris-
Saclay, France

###### Abstract

The age of Information (AoI) has been introduced to capture the notion of
freshness in real-time monitoring applications. However, this metric falls
short in many scenarios, especially when quantifying the mismatch between the
current and the estimated states. To circumvent this issue, in this paper, we
adopt the age of incorrect information metric (AoII) that considers the
quantified mismatch between the source and the knowledge at the destination
while tracking the impact of freshness. We consider for that a problem where a
central entity pulls the information from remote sources that evolve according
to a Markovian Process. It selects at each time slot which sources should send
their updates. As the scheduler does not know the actual state of the remote
sources, it estimates at each time the value of AoII based on the Markovian
sources’ parameters. Its goal is to keep the time average of the AoII function
as small as possible. For that purpose, we develop a scheduling scheme based
on Whittle’s index policy. To that extent, we use the Lagrangian Relaxation
Approach and establish that the dual problem has an optimal threshold policy.
Building on that, we compute the expressions of Whittle’s indices. Finally, we
provide some numerical results to highlight the performance of our derived
policy compared to the classical AoI metric.

††This work has been done before 14 October 2022 in CentraleSupelec.

##  I Introduction

The number of connected devices has witnessed considerable growth in the last
decade due to the emergence of IoT. This remarkable proliferation of low-cost
hardware has led to the emergence of real-time monitoring services. In these
systems, the monitor needs to know the status of one or multiple processes
observed by remote sensors. To that extent, due to the channel constraint, the
monitor selects only a subset of users from which it pulls the data that
contains useful information to execute the convenient task. The sensor is only
responsible for sampling the process and transmitting the information content
to the receiver on demand.

The main goal in these applications is to implement a scheduling scheme that
keeps the monitor up to date by receiving fresh information from different
sources.

This notion of freshness is captured by the Age of Information (AoI), which is
introduced for the first time in [1]. More specifically, AoI can be viewed as
the duration which separates the generation of the last successfully received
packet’s time-stamp and the current time.

There are several works that consider this metric of AoI in different contexts
and fields, and from different perspectives [2, 3, 4, 5, 6, 7, 8, 9].
Nevertheless, even though this metric can quantify the information time lag at
the monitor, it doesn’t take into account the information content transmitted
by the sensor. Several metrics have then been proposed in the literature to
quantify the value and quality of the information [10, 11, 12, 13, 14].

In fact, AoI evolves regardless of the state of the remote source. For
instance, in some scenarios, the state of the remote source is the same as the
estimated state at the side of the monitor while AoI keeps growing. Whereas,
no penalty should be incurred as the monitor is up to date.

To meet the timeliness requirement while considering the content of the
information sent, the authors in [15] have designed a new metric dubbed Age of
incorrect information. This metric grows only if the state of the remote
sensor is different from the actual state and goes to zero otherwise. In [16],
an extension of this metric, called Age of Incorrect Information at Query
(QAoII), is proposed. This metric considers that the information is only
relevant at the times the receiver generates a query.

The AoII has been analyzed in several papers and information sampling and
scheduling schemes have been developed [15, 17, 18, 19, 20, 21]. A Markovian
source model is considered in [15, 17] under energy constraint. A threshold-
based sampling policy has been derived and proved to be the optimal policy. A
symmetric binary information source over a delay channel with feedback is
considered in [18]. The optimal information sampling policy is then derived by
dynamic programming. Furthermore, in [20, 21], the AoII metric is also
considered and the authors assume that the scheduler has perfect knowledge
about the source process at each time slot and restrict the analysis to one
transmitter-receiver pair communication. Likewise, the authors in [15, 17, 18]
consider that the transmitter is responsible for observing at each time slot
the state of the source in order to decide whether or not to send the packet.
In the context of multiple sources/sensors, if each source decides on its own
to transmit a packet, e.g. by random access techniques, collisions will occur
which will reduce the system performance, especially in the context of high
number of sensors (e.g. IoT scenario). A collision-free transmission can be
obtained if a central entity decides whether a source must sample and transmit
a packet or not. The central entity (e.g. monitor) cannot be aware of the
status of the remote sources, and hence the AoII cannot be known perfectly by
the scheduler. A prediction/estimation of the AoII must be performed, e.g. by
averaging over the different possible values of AoII. The predicted AoII will
be then used in the scheduling decision by the monitor. This problem can be
modeled as a Partially Observable Markov Decision Process (POMDP). To the best
of our knowledge, the first work that studied such a framework in the context
of AoI is [19], in which the authors consider a multiple-transmitter-one-
receiver scenario and aim to minimize the expected total average AoII by
deriving the low complex and well-performing policy, called Whittle’s index
policy, which is optimal in the many-users regime.

However, in the aforementioned work, the mismatch between the source and
monitor in the AoII metric is considered to be the indicator function. In
other words, the distance between the different states of the Markovian source
is not considered in [19], which makes it fall short in some real-life
applications. For example, in temperature monitoring, the goal of the central
entity could be to monitor the temperature variations of the system and
quickly respond to these fluctuations. Thus, the freshness of information is
not the only priority. We also need to monitor the temperature variations as
high volatility or significant temperature variation is more harmful to the
system than the smaller ones. This variation can be seen as the distance
between the actual state of the remote source and the estimated state at the
monitor’s side: The further away the actual state is from the estimated state,
the more we need to sanction the system.

For this reason, we consider in this work the AoII metric, in which the
mismatch between the source state and the monitor knowledge is modeled as the
distance between them. We tackle a realistic case in which a scheduler tracks
the states of multiple remote sources and selects at each time a subset of
them. These selected sources will transmit the information of interest while
the others remain idle. The difficulty lies in the fact that the scheduler
does not know the instantaneous state of the remote sources until it receives
their updates. Our goal will be accordingly to minimize the total expected
average AoII. For that, we apply the well-known, well-performing, and low-
complex Whittle’s index policy referred by WIP [22]. This policy has been
widely adopted in the framework of the Age of Information (one can see [23, 4,
24, 2, 25] and the references therein). Contrary to these references, we
derive the expression of the estimated/predicted AoII at the monitor side and
use it in the development of the WIP. Specifically, our contributions can be
summarized as follows: i) we consider a system where a central entity tracks
the status of remote sensors. We formulate the AoII-based scheduling problem
and show that it belongs to the family of Restles Multi-Armed Bandit (RMAB)
problems. The challenge in this case is that the monitor/scheduler does not
know the states of the sensors (i.e. the AoII exact value) and has then to
predict its value in order to perform the scheduling, ii) as the optimal
solution of this type of problem is known to be out of reach, we adopt the
Lagrangian Relaxation approach that consists of relaxing and decomposing the
problem in one-dimensional problems, iii) we establish the indexability of the
one-dimensional problem by proving that its optimal solution is threshold-
based policy, and iv) we derive the Whittle’s index policy by leveraging the
steady-state form of the one-dimensional problem under a given threshold
policy.

##  II System Model

###  II-A Network description

We consider in our paper $N$ sensors that generate and send status updates
about the process of interest to a central entity over unreliable channels.
Time is considered to be discrete and normalized to the time slot duration.
More precisely, when the monitor or the base station decides to schedule a
given sensor $i$ at time $t$, this later samples its respective process,
$X_{i}(t)$, and sends it to the monitor over an unreliable channel. If the
transmission is successful, the packet containing the information of interest
$X_{i}(t)$ will be instantaneously delivered to the monitor. Then, the monitor
keeps the information state $X_{i}(t)$ received by the sensor till the next
successful transmission. That means that the information state at the side of
the monitor denoted by $\hat{X}_{i}(t)$ is equal to $X_{i}(g_{i}(t))$ where
$g_{i}(t)$ indicates the time-stamp of the last successfully received packet
by the monitor.

As for the unreliable channel, we suppose that for user $i$, at each time slot
$t$, the probability of having successful transmission is $\rho_{i}$, and
$1-\rho_{i}$ otherwise. Consequently, the channel realizations are independent
and identically distributed (i.i.d.) over time slots that we denote
$c_{i}(t)$, i.e. $c_{i}(t)=1$ if the packet is successfully transmitted and
$c_{i}(t)=0$ otherwise.

On the other hand, regarding the nature of the process of interest $X_{i}(t)$,
we consider that for each user $i$, the process $X_{i}(t)$ evolves under
Markov chain with infinite state space as represented in Figure 1. We define
the probability of transitioning to the next state at the next time slot as
$p_{i}$. Similarly, the probability of remaining at the same state is
$1-p_{i}$. Furthermore, we consider that the distance between two consecutive
states is $d_{i}$.

Figure 1: Illustration of process $X_{i}(t)$

###  II-B Penalty function dynamics

In this paper, we study the Age of incorrect information penalty function. We
see how it is relevant and more realistic to consider the distance between the
states of the source in order to have a good performance in some scenarios
where the applications are sensitive to the gap between the estimated state
and the current state of a given process. For that purpose, we start by
reintroducing in the next section the standard metric, the age of information
metric, to emphasize its shortcomings. Then we propose our adjusted AoII
metric.

####  II-B1 Age of information penalty function

The standard metric (AoI) that captures the freshness of information for user
$i$ is:

$\delta_{AoI}(t)=t-g_{i}(t)$ (1)

where $g_{i}(t)$, as mentioned before, is the time-stamp of the last
successfully received packet by the monitor. This metric captures the lifetime
of the last update at the monitor without taking into account the information
state of the remote markovian source. Thereby, this makes it fall short in
some applications. For instance, in some scenarios, the accuracy or
performance of some applications relies heavily on information mismatch error-
sensitive actions. Having said that, a higher penalty should be paid if the
estimated source at the side of the monitor is far from the actual state of
the remote source. In other words, the penalty function should be proportional
to the distance between the estimated and the actual state.

####  II-B2 Distance-based Age of incorrect information penalty function

As was depicted in the Introduction, to capture the notion of the gap or the
mismatch between the source and the monitor while satisfying the freshness
requirement, one should adjust the AoII metric by integrating the distances
between the states of the source. To that extent, we consider this following
metric:

$\sum_{u=V_{i}(t)}^{t}[X_{i}(u)-\hat{X}_{i}(t)]d_{i}$

where $V_{i}(t)$ is the last time where
$X_{i}(V_{i}(t))=\hat{X}_{i}(V_{i}(t))$.

######  Remark 1.

Considering our system model described in II, replacing $V_{i}(t)$ by
$g_{i}(t)$ where $g_{i}(t)$ is the last successfully transmitted packet’s
time-stamp gives us the same metric.

To that extent, leveraging this remark above, we consider the following
metric:

$\sum_{u=g_{i}(t)}^{t}[X_{i}(u)-\hat{X}_{i}(t)]d_{i}$

In this paper, we consider that the monitor that plays the scheduler’s role
knows only the state of the last successively received packet. Thus, the base
station takes the expectation of AoII at each time slot. Accordingly, the
explicit expression of the AoII metric in our case is:

$\delta_{AoII}(t)=\mathbb{E}\sum_{u=g_{i}(t)}^{t}[X_{i}(u)-\hat{X}_{i}(t)]d_{i}$
(2)

In the sequel, we provide the closed-form expression of our metric in a
Partially Observable Markov Decision Process Problem.

###  II-C Metrics evolution

In this section, we describe mathematically the evolution of our metric
depending on the system parameters and the action taken. We denote by
$a_{i}(t)$ the action prescribed to user $i$ at time slot $t$ and by
$s_{i}(t)$, the age of incorrect information penalty function at time slot
$t$. According to the expression of AoII given in section II-B2, for
$g_{i}(t)\leq u\leq t$, $X_{i}(u)-\hat{X}_{i}(u)$ is a random variable that we
denote by $A_{i}(u)$ that satisfies:

######  Lemma 1.

$\displaystyle
A_{i}(u)=\left\\{\begin{array}[]{lll}u_{g_{i}}(0)&w.p&(p_{i})^{u-g_{i}(t)}\\\
u_{g_{i}}(1)&w.p&(p_{i})^{u-g_{i}(t)-1}.\binom{u-g_{i}(t)}{1}(1-p_{i})\\\
u_{g_{i}}(2)&w.p&(p_{i})^{u-g_{i}(t)-2}.\binom{u-g_{i}(t)}{2}(1-p_{i})^{2}\\\
u_{g_{i}}(3)&\cdots&\cdots\\\ \vdots&&\\\
u_{g_{i}}(k)&w.p&(p_{i})^{u-g_{i}(t)-k}.\binom{u-g_{i}(t)}{k}(1-p_{i})^{k}\\\
\vdots&&\\\ 0&w.p&(1-p_{i})^{u-g_{i}(t)}\end{array}\right.$ (11)

where $\binom{n}{k}=\frac{n!}{(n-k)!k!}$ and $u_{g_{i}}(k)=u-g_{i}(t)-k$.

###### Proof:

See appendix A. ∎

Therefore, the mean of AoII at slot $t$ equals to the mean of
$\sum_{u=g_{i}(t)}^{t}d_{i}A_{i}(u)$, i.e.

######  Lemma 2.

The mean of the AoII at slot $t$, denoted by $n_{i}(t)$ equals to:

$n_{i}(t)=\sum_{u=g_{i}(t)}^{t}d_{i}\mathbb{E}[A_{i}(u)]=d_{i}p_{i}\frac{(t-g_{i}(t)+1)(t-g_{i}(t))}{2}$

###### Proof.

See Appendix B ∎

As $n_{i}(t)$ depends only $t-g_{i}(t)$ and $i$, then, we let
$n_{i}(t)\overset{\Delta}{=}n_{i}(t-g_{i}(t))$. Therefore:

$n_{i}(j)=d_{i}p_{i}\frac{(j+1)j}{2}$ (12)

To that extent, at time slot $t+1$, if the user $i$ is scheduled and the
packet is successively transmitted, then $g_{i}(t+1)=t+1$. Accordingly, at
time slot $t+1$, AoII equals to $n_{i}(t+1-g_{i}(t+1))=n_{i}(0)$. If the user
$i$ is not scheduled or if the packet is not successively transmitted, then
$g_{i}(t+1)=g_{i}(t)$. Therefore, AoII will transit to
$n_{i}(t+1-g_{i}(t+1))=n_{i}(t-g_{i}(t)+1)$. To sum up, the evolution of AoII
can be summarized as follows:

$s_{i}(t+1)=\left\\{\begin{array}[]{ll}n_{i}(0)&ifd_{i}(t+1)=1,c_{i}(t+1)=1\\\
n_{i}(j+1)&else\end{array}\right.$ (13)

where $s_{i}(t)=n_{i}(j)$.

##  III Problem formulation

We let the vector $\boldsymbol{s}$ at time $t$ be
$\boldsymbol{s}(t)=(s_{1}(t),\ldots,s_{N}(t))$ where $s_{i}(t)$ is the penalty
function at the central entity of user $i$ with respect to AoII metric at time
slot $t$. Our aim is to find a scheduling policy that allocates per each time
slot, the available channels ($M$ channels) to a given subset of users ($M$
users, $M\leq N$) in a such way to minimize the total expected average AoII
penalty function. A scheduling policy $\phi$ is defined as a sequence of
actions $\phi=(\boldsymbol{a}^{\phi}(0),\boldsymbol{a}^{\phi}(1),\ldots)$
where
$\boldsymbol{a}^{\phi}(t)=(a_{1}^{\phi}(t),a_{2}^{\phi}(t),\ldots,a_{N}^{\phi}(t))$
is a binary vector such that $a_{i}^{\phi}(t)=1$ if the user $i$ is scheduled
at time $t$. Denoting by $\Phi$, the set of all causal scheduling policies,
then our scheduling problem can be formulated as follows:

$\displaystyle\underset{\phi\in\Phi}{\text{minimize}}$
$\displaystyle\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{\phi\in\Phi}\Big{(}\sum_{t=0}^{T-1}\sum_{i=1}^{N}s_{i}^{\phi}(t)|\boldsymbol{s}(0)\Big{)}$
(14) subject to $\displaystyle\sum_{i=1}^{N}a_{i}^{\phi}(t)\leq\alpha N\quad
t=1,2,\ldots$

where $\alpha N=M$. The problem in (14) falls into Restless Bandit framework.
RMAB problems are known to be generally difficult to solve them as they are
PSPACE-Hard [26]. To circumvent this complexity, we propose to implement a
low-complex and well-performing policy called Whittle’s index policy (WIP)
[27]. In order to get the Whittle’s index values, we need to adopt the
Lagrangian relaxation. To that extent, we introduce in the next section the
Lagrangian relaxation approach applied to our RBP problem. Then, we provide
the mathematical analysis to get the Whittle’s index policy (WIP).

##  IV Lagrangian Relaxation and Whittle’s Index

###  IV-A Relaxed problem

In order to derive the Whittle’s index scheduling policy, we adopt the
Lagrangian relaxation technique. First, it consists of relaxing the constraint
on the available resources by letting it be satisfied on average rather than
in every time slot. More specifically, we define our Relaxed Problem (RP) as
follows:

$\displaystyle\underset{\phi\in\Phi}{\text{minimize}}$
$\displaystyle\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{\phi}\Big{(}\sum_{t=0}^{T-1}\sum_{i=1}^{N}s_{i}^{\phi}(t)|\boldsymbol{s}(0)\Big{)}$
(15) subject to
$\displaystyle\lim_{T\to+\infty}\text{sup}\frac{1}{T}\mathbb{E}^{\phi}\Big{(}\sum_{t=0}^{T-1}\sum_{i=1}^{N}a_{i}^{\phi}(t)\Big{)}\leq\alpha
N$

The Lagrangian function $f(W,\phi)$ of the problem (15) is defined as:

$\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{\phi}\Big{(}\sum_{t=0}^{T-1}\sum_{i=1}^{N}s_{i}^{\phi}(t)+Wa_{i}^{\phi}(t)|\boldsymbol{s}(0)\Big{)}-W\alpha
N$ (16)

where $W\geq 0$ can be seen as a penalty for scheduling users. Thus, by
following the Lagrangian approach, our next objective is to solve the
following problem:

$\\\ \\\ \underset{\phi\in\Phi}{\text{min}}f(W,\phi)$ (17)

As the term $W\alpha N$ is independent of $\phi$, it can be eliminated from
the analysis. Baring that in mind, we present the steps to obtain the
Whittle’s index policy:

  1. 1.

We decompose the problem in (17) into $N$ one-dimensional problems that can be
solved independently (this has been shown in [28]). Accordingly, we drop the
user’s index for ease of notation, and we deal with the one-dimensional
problem:

$\displaystyle\underset{\phi\in\Phi}{\text{min}}$
$\displaystyle\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{\phi}\Big{(}\sum_{t=0}^{T-1}s^{\phi}(t)+Wa^{\phi}(t)|s(0)\Big{)}$
(18)

  2. 2.

We give the structural results on the optimal solution of the one-dimensional
problem.

  3. 3.

We establish the indexability property of Problem 18.

  4. 4.

Under indexability condition, we derive a closed-form expression of the
Whittle’s index values

  5. 5.

We define the proposed scheduling policy (WIP) for the original problem (14).

###  IV-B Structural results

The problem in (18) can be viewed as an infinite horizon average cost Markov
decision process that is defined as follows:

  * •

States: The state of the MDP at time $t$ is the penalty function $s(t)$.
According to Section II-C, $s(t)$ evolves in the state space:

$A=\\{b^{j}:j\geq 0,b^{j}=dp\frac{j(j+1)}{2}\\}$ (19)

  * •

Actions: The action at time $t$, denoted by $a(t)$, specify if the user is
scheduled (value $1$) or not (value $0$).

  * •

Transitions probabilities: The transitions probabilities between the different
states.

  * •

Cost: We let the instantaneous cost of the MDP, $C(s(t),a(t))$, be equal to
$s(t)+Wa(t)$.

The optimal policy $\phi^{*}$ of the one-dimensional problem (18) can be
obtained by solving the following Bellman equation for each state $b^{j}$:

$\displaystyle\theta+V(b^{j})=\min\big{\\{}$ $\displaystyle b^{j}+V(b^{j+1});$
$\displaystyle b^{j}+W+\rho V(b^{0})+(1-\rho)V(b^{j+1})\big{\\}}$ (20)

where $\theta$ is the optimal value of the problem, $V(b^{j})$ is the
differential cost-to-go function. Instead of resolving the equation (20), we
will limit ourselves to study the structure of the optimal scheduling policy
of (20). To that end, we adopt the relative value iteration algorithm (RVIA)
as follows:

$\displaystyle V_{t}(b^{j})=\min\big{\\{}$ $\displaystyle
b^{j}+V_{t}(b^{j+1});$ $\displaystyle b^{j}+W+\rho
V_{t}(b^{0})+(1-\rho)V_{t}(b^{j+1})\big{\\}}$ (21)

######  Theorem 1.

The optimal solution of the problem in (18) is an increasing threshold policy.
Explicitly, there exists $n$ such that when the current state $b^{j}<b^{n}$,
the prescribed action is a passive action, and when $b^{j}\geq b^{n}$, the
prescribed action is an active action.

###### Proof:

See Appendix C. ∎

###  IV-C Indexability and Whittle’s index expressions

In order to establish the indexability of the problem and find the Whittle’s
index expressions, we provide the steady-state form of the problem in (18)
under a given threshold policy $n$. Explicitly:

$\displaystyle\underset{n\in\mathbb{N}^{*}}{\text{minimize}}$
$\displaystyle\overline{s^{n}}+W\overline{a^{n}}$ (22)

where $\overline{s^{n}}$ is the average value of the penalty function with
respect to the AoII metric, and $\overline{a^{n}}$ is the average active time
under threshold policy $n$. Specifically:

$\displaystyle\overline{s^{n}}$
$\displaystyle=\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{n}\Big{(}\sum_{t=0}^{T-1}s(t)|s(0),tp(n)\Big{)}$
(23) $\displaystyle\overline{a^{n}}$
$\displaystyle=\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{n}\Big{(}\sum_{t=0}^{T-1}a(t)|s(0),tp(n)\Big{)}$
(24)

where $tp(n)$ denotes the threshold policy $n$. With the aim of computing
$\overline{s^{n}}$ and $\overline{a^{n}}$, we derive the stationary
distribution of the Discrete Time Markov Chain, DTMC that represents the
evolution of AoII under threshold policy $n$. Specifically:

######  Proposition 1.

For a given threshold $n$, the DTMC admits $u^{n}(b^{j})$ as its stationary
distribution:

$u^{n}(b^{j})=\left\\{\begin{array}[]{ll}\frac{\rho}{n\rho+1}&\text{if}\ 0\leq
j\leq n\\\ (1-\rho)^{j-n}\frac{\rho}{n\rho+1}&\text{if}\ j\geq n+1\\\
\end{array}\right.$ (25)

###### Proof:

The proof can be found in Appendix D. ∎

Leveraging the above results, we provide the closed-form expression of the
AoII under any threshold policy.

######  Proposition 2.

For a given threshold $n$, the average AoII under the threshold policy is
$\overline{s^{n}}$:

$\displaystyle\overline{s^{n}}=$ $\displaystyle
dp\frac{\rho}{n\rho+1}[\frac{1}{6}n^{3}+\frac{1}{2\rho}n^{2}+\frac{6-\rho^{2}-3\rho}{6\rho^{2}}n+\frac{1-\rho}{\rho^{3}}]$
(26)

###### Proof:

See Appendix E. ∎

######  Proposition 3.

For any given threshold $n$, the active average time is $\overline{a^{n}}$:

$\displaystyle\overline{a^{n}}=$ $\displaystyle\frac{1}{n\rho+1}$ (27)

###### Proof:

Exploiting the results in Proposition 1 and according to the expression (24),
we have:

$\overline{a^{n}}=\sum_{j=n}^{+\infty}u^{n}(j)=\frac{1}{n\rho+1}$ (28)

Hence, we obtain our desired results. ∎

To ensure the existence of the Whittle’s indices, we need first to establish
the indexability property for all users’ classes. A class is indexable if the
set of states in which the passive action is the optimal action with respect
to the optimal solution of Problem (18), increases with the Lagrangian
parameter $W$. One can see [19] for a rigorous Definition of Indexability
property as well as Whittle’s index. We note that in the sequel, we precise
the indices of users to differentiate between them.

######  Proposition 4.

For each user $i$, the one-dimensional problem is indexable.

###### Proof:

It is sufficient to show that $\overline{a_{i}^{n}}$ decreases with $n$ to
establish our desired result (see [2]). Indeed, we have that:

$\overline{a_{i}^{n+1}}-\overline{a_{i}^{n}}=-\frac{\rho}{(n\rho+1)(n\rho+\rho+1)}\leq
0$ (29)

That concludes the proof. ∎

As the indexability property has been established in the above proposition, we
can now assert the existence of the Whittle’s index. With the intention of
comparing the two metrics AoI and AoII, we provide in the following Theorem
the Whittle’s index values distinguishing between two cases: the first case
where we consider the AoI metric, and the second one where we consider the
AoII metric. For a sake of clarity, we recall that the state space of AoI for
a given user $i$ is $A_{i}^{aoi}=\\{c_{i}^{j}:c_{i}^{j}=j,j\in\mathbf{N}\\}$

######  Theorem 2.

For any user $i$, the Whittle’s index is:

  * •

AoI:

$W_{i}(c_{i}^{n})=\frac{n(n+1)\rho_{i}}{2}+n+1$ (30)

  * •

AoII:

$\displaystyle W_{i}(b_{i}^{n})=$ $\displaystyle
d_{i}p_{i}\biggl{[}\frac{1}{3}\rho_{i}n^{3}+(1+\frac{\rho_{i}}{2})n^{2}+(1+\frac{\rho_{i}}{6}+\frac{1}{\rho_{i}})n$
$\displaystyle+$ $\displaystyle\frac{1}{\rho_{i}}\biggr{]}=d_{i}p_{i}w_{i}(n)$
(31)

###### Proof.

The proof can be found in Appendix F. ∎

Based on the above proposition, we provide in the following the Whittle’s
index scheduling policy for the original problem (14).

Algorithm 1 Whittle’s index scheduling policy

1:At each time slot $t$, compute the Whittle’s index of all users in the
system using the expressions given in Proposition 2.

2:Allocating the $M$ channels to the $M$ users having the highest Whittle’s
index values at time $t+1$.

##  V Numerical Results

Our goal in this section is to compare the average empirical age of incorrect
information under the developed Whittle’s index policy WIP-AoII to the one
under the baseline policy, denoted by WIP-AoI (derived in [2]), that considers
the standard AoI metric. More precisely, we plot
$C^{\phi,N}=\frac{1}{N}\lim_{T\to+\infty}\text{sup}\>\frac{1}{T}\mathbb{E}^{\phi}\Big{(}\sum_{t=0}^{T-1}\sum_{i=1}^{N}s_{i}^{emp,\phi}(t)|\boldsymbol{s}^{emp}(0),\phi\Big{)}$
for $\phi$ equals to WIP-AoII and WIP-AoI, in function of $N$, where
$s^{emp,\phi}_{i}(\cdot)$ evolves as follows:

  * •

If $\phi_{i}(t+1)=1$: If the packet is successfully transmitted, then
$\hat{X}_{i}(t+1)=X_{i}(t+1)$. Hence the AoII will move to the state $0$. If
the packet is unsuccessfully transmitted, then the monitor maintains the last
estimated value of the process of interest, i.e.
$\hat{X}_{i}(t+1)=\hat{X}_{i}(t)$. We have $s_{i}^{emp,\phi}(t)$ evolves in
the state space $\\{\sum_{k=0}^{j}k=\frac{(j+1)j}{2}:j\in\mathbb{N}\\}$.
Therefore, if $s_{i}^{emp,\phi}(t)=\frac{j(j+1)}{2}$, the value of
$s_{i}^{emp,\phi}(t+1)$ is as follows:

$s_{i}^{emp,\phi}(t+1)=\left\\{\begin{array}[]{lll}d_{i}\frac{(j+2)(j+1)}{2}&w.p&(1-\rho_{i})p_{i}\\\
d_{i}\frac{(j+1)j}{2}&w.p&(1-\rho_{i})(1-p_{i})\\\ 0&w.p&\rho_{i}\\\
\end{array}\right.$ (32)

  * •

If $\phi_{i}(t)=0$: The monitor maintains the last estimated value of the
process of interest, i.e. $\hat{X}_{i}(t+1)=\hat{X}_{i}(t)$. Therefore, the
value of $s_{i}^{emp,\phi}(t+1)$ is as follows:

$s_{i}^{emp,\phi}(t+1)=\left\\{\begin{array}[]{lll}d_{i}\frac{(j+2)(j+1)}{2}&w.p&p_{i}\\\
d_{i}\frac{(j+1)j}{2}&w.p&1-p_{i}\\\ \end{array}\right.$ (33)

We showcase two scenarios of the network settings. In the first scenario, to
shed light on the importance of taking into account the source parameters
namely, $p_{i}$, in the derivation of Whittle’s indices, we consider that the
two classes share the same channel statistics, specifically
$\rho_{1}=\rho_{2}$, while they don’t have the same source parameters. In this
case, we compare the performance of WIP-AoII with WIP-AoI. For the second
scenario, to highlight the importance of considering the Whittle index
expressions derived through this paper precisely the function $w_{i}(.)$ in
equation (• ‣ 2), we compare our proposed solution with the weighted-baseline
policy denoted by WWIP-AoI where the expression of Whittle indices of WIP-AoI
of class $i$ are multiplied by the factor $p_{i}d_{i}$. For the first
scenario, we consider two classes with the respective parameters: i) Class 1:
$\rho_{1}=0.5$, $d_{1}=5$, $p_{1}=0.1$, and ii) Class 2: $\rho_{2}=0.5$,
$d_{2}=5$, $p_{2}=0.9$. For the second scenario, we consider the following
parameters: i) Class 1: $\rho_{1}=0.5$, $d_{1}=1$, $p_{1}=0.5$, and ii) Class
2: $\rho_{2}=0.5$, $d_{2}=100$, $p_{2}=0.5$.

Figure 2: Comparison between WIP-AoII and WIP-AoI in terms of the empirical
AoII Figure 3: Comparison between WWIP-AoII and WIP-AoI in terms of the
empirical AoII

One can observe in Figures 2 and 3 that effectively WIP-AoII gives us better
performance than WIP-AoI and WWIP-AoI in terms of minimizing the average
empirical age of incorrect information considering the distances between the
states.

##  VI Conclusion

In this paper, we considered an instance of Age of Incorrect Information that
takes into account the distances between the different states of a given
Markov process. We considered a scheduling problem of a central entity that
selects at each time slot a subset of the sensors to sample the Markovian
sources and send instantaneously their updates in such a way to minimize the
metric in question. Since the scheduler is unaware of the current state of the
source, we computed the mean of AoII at each time slot. We then developed an
efficient scheduling policy based on Whittle’s index framework. Finally, we
have provided numerical results that highlight the performance of our policy.

## References

  * [1] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _2012 Proceedings IEEE INFOCOM_. IEEE, 2012, pp. 2731–2735.
  * [2] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “On the optimality of the whittle’s index policy for minimizing the age of information,” _IEEE Transactions on Wireless Communications_ , 2020.
  * [3] Y.-P. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” _IEEE Transactions on Mobile Computing_ , 2019.
  * [4] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” _IEEE/ACM Transactions on Networking_ , vol. 26, no. 6, pp. 2637–2650, 2018\.
  * [5] A. M. Bedewy, Y. Sun, and N. B. Shroff, “The age of information in multihop networks,” _IEEE/ACM Transactions on Networking_ , vol. 27, no. 3, pp. 1248–1257, 2019.
  * [6] A. Maatouk, Y. Sun, A. Ephremides, and M. Assaad, “Status updates with priorities: Lexicographic optimality,” in _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. IEEE, 2020, pp. 1–8.
  * [7] Y. Sun, E. Uysal-Biyikoglu, and S. Kompella, “Age-optimal updates of multiple information flows,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2018, pp. 136–141.
  * [8] Y.Sun, E.Uysal-Biyikoglu, R.D.Yates, C.E.Koksal, and N.B.Shroff, “Update or wait: How to keep your data fresh,” _IEEE Transactions on Information Theory_ , vol. 63, no. 11, pp. 7492–7508, 2017.
  * [9] T. K. Oguz, E. T. Ceran, E. Uysal, and T. Girici, “Implementation and evaluation of age-aware downlink scheduling policies in push-based and pull-based communication,” _IEEE Transactions on Communications_ , vol. 24, no. 5, p. 673, 2022.
  * [10] J. Zhong, R. D. Yates, and E. Soljanin, “Two freshness metrics for local cache refresh,” in _IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1924–1928.
  * [11] O. Ayan, M. Vilgelm, M. Klugel, S. Hirche, and W. Kellerer, “Age-of-information vs. value-of-information scheduling for cellular networked control systems,” in _in Proceedings of the 10th ACM/IEEE ICCPS_ , 2019.
  * [12] G. Stamatakis and A. T. N. Pappas, “Control of status updates for energy harvesting devices that monitor processes with alarms,” in _In Proc. of IEEE Globecom Workshops (GC Wkshps)_ , 2019.
  * [13] F. C. et al., “Query age of information: Freshness in pull-based communication,” _IEEE Transactions on Communications_ , vol. 70, no. 3, pp. 1606–1622, 2022.
  * [14] E. Uysal and et al, “Semantic communications in networked systems: A data significance perspective,” _IEEE Network_ , vol. 36, no. 4, pp. 233–240, 2022.
  * [15] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 5, pp. 2215–2228, 2020.
  * [16] M. Ayik, E. T. Ceran, and E. Uysal, “Optimization of aoii and qaoii in multi-user links,” in _available on arviv, arXiv:2305.00191_ , 2023.
  * [17] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: an enabler of semantics-empowered communication,” _arXiv preprint arXiv:2012.13214_ , 2020.
  * [18] C. Kam, S. Kompella, and A. Ephremides, “Age of incorrect information for remote estimation of a binary markov source,” in _IEEE INFOCOM 2020-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2020, pp. 1–6.
  * [19] S. Kriouile and M. Assaad, “Minimizing the age of incorrect information for real-time tracking of markov remote sources,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 2978–2983.
  * [20] Y. Chen and A. Ephremides, “Minimizing age of incorrect information for unreliable channel with power constraint,” _arXiv preprint arXiv:2101.08908_ , 2021.
  * [21] ——, “Scheduling to minimize age of incorrect information with imperfect channel state information,” _Entropy_ , vol. 23, no. 12, 2021.
  * [22] M. Larranaga, M. Assaad, A. Destounis, and G. Paschos, “Asymptotically optimal pilot allocation over markovian fading channels,” _IEEE Transactions on Information Theory_ , vol. 64, no. 7, pp. 5395–5418, 2018.
  * [23] V. Tripathi and E. Modiano, “A whittle index approach to minimizing functions of age of information,” in _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2019, pp. 1160–1167.
  * [24] B. Sombabu, A. Mate, D. Manjunath, and S. Moharir, “Whittle index for aoi-aware scheduling,” in _2020 International Conference on COMmunication Systems & NETworkS (COMSNETS)_. IEEE, 2020, pp. 630–633.
  * [25] S. Kriouile, M. Assaad, and A. Maatouk, “On the global optimality of whittle’s index policy for minimizing the age of information,” _IEEE Transactions on Information Theory_ , vol. 68, no. 1, pp. 572–600, 2022.
  * [26] C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of optimal queuing network control,” _Mathematics of Operations Research_ , vol. 24, no. 2, pp. 293–305, 1999.
  * [27] R. R. Weber and G. Weiss, “On an index policy for restless bandits,” _Journal of Applied Probability_ , vol. 27, no. 3, pp. 637–648, 1990.
  * [28] S. Kriouile, M. Assaad, and M. Larranaga, “Asymptotically Optimal Delay-aware Scheduling in Queueing Systems,” _Journal of Communications and Networks_ , 2021. [Online]. Available: https://hal.archives-ouvertes.fr/hal-03437753

##  Appendix A Proof of Lemma 1

We have for $g_{i}(t)\leq u\leq t$, $A_{i}(u)=X_{i}(u)-\hat{X}_{i}(u)$. By
definition of $g_{i}(t)$, $\hat{X}_{i}(u)=X_{i}(g_{i}(t))$. Then
$\hat{X}_{i}(u)$ is a fixed constant. Whereas $X_{i}(t)$ is unknown by the
monitor. Accordingly, it is viewed as a random variable by the monitor. Baring
in mind the system dynamics showcased in Section II, $X_{i}(u)-\hat{X}_{i}(u)$
follows a binomial distribution with parameters $u-g_{i}(t)$ and $p_{i}$.
Hence, the probability that $A_{i}(u)=u-g_{i}(t)-k$ is
$(p_{i})^{u-g_{i}(t)-k}.\binom{u-g_{i}(t)}{k}(1-p_{i})^{k}$. That concludes
the proof.

##  Appendix B Proof of Lemma 2

$\displaystyle n_{i}(t)=\sum_{u=g_{i}(t)}^{t}d_{i}\mathbb{E}[A_{i}(u)]$
$\displaystyle=\sum_{u=g_{i}(t)}^{t}\sum_{k=0}^{u-g_{i}(t)}d_{i}.(u-g_{i}(t)-k)(p_{i})^{u-g_{i}(t)-k}$
$\displaystyle\ \ \ \ \ \ \ \ \ \times\binom{u-g_{i}(t)}{k}(1-p_{i})^{k}$
$\displaystyle=\sum_{u=g_{i}(t)}^{t}\sum_{k=0}^{u-g_{i}(t)}d_{i}k(p_{i})^{k}.\binom{u-g_{i}(t)}{k}(1-p_{i})^{u-g_{i}(t)-k}$

As we have, for all integer $n$ and $0\leq p\leq 1$,
$\sum_{k=0}^{n}k.p^{k}.(1-p)^{n-k}.\binom{n}{k}=np$, then:

$\displaystyle n_{i}(t)$
$\displaystyle=\sum_{u=g_{i}(t)}^{t}d_{i}p_{i}(u-g_{i}(t))$
$\displaystyle=d_{i}p_{i}\frac{(t-g_{i}(t)+1)(t-g_{i}(t))}{2}$ (35)

##  Appendix C Proof of theorem 1

We provide first an useful lemma.

######  Lemma 3.

$b^{j}$ is increasing with $j$

###### Proof:

From the expression of $b^{j}$, it is clear that this later is increasing with
$j$. ∎

Based on this lemma, we prove the following lemma.

######  Lemma 4.

$V(.)$ is increasing with $b^{j}$.

###### Proof:

We prove the present lemma by induction using the Relative value iteration
equation (21). In fact, we show that $V_{t}(\cdot)$ is increasing and we
conclude for $V(\cdot)$.
As $V_{0}(.)=0$, then the property holds for $t=0$. If $V_{t}(.)$ is
increasing with $b$, we show that for $b^{j}\leq b^{i}$,
$V_{t+1}^{0}(b^{j})\leq V_{t+1}^{0}(b^{i})$ and $V_{t+1}^{1}(b^{j})\leq
V_{t+1}^{1}(b^{i})$ where for each $k\in\mathbf{N}$:

$\displaystyle V_{t+1}^{0}(b^{k})$ $\displaystyle=b^{k}+V_{t}(b^{k+1})$ (36)
$\displaystyle V_{t+1}^{1}(b^{k})$ $\displaystyle=b^{k}+W+\rho
V_{t}(b^{0})+(1-\rho)V_{t}(b^{k+1})$ (37)

We have that:

$V_{t+1}^{0}(b^{j})-V_{t+1}^{0}(b^{i})=b^{j}-b^{i}+(V_{t}(b^{j+1})-V_{t}(b^{i+1}))$
(38)

According to Lemma 3, given that $b^{j}\leq b^{i}$, then $j\leq i$. That means
$b^{j+1}\leq b^{i+1}$. Therefore, since $V_{t}(.)$ is increasing with $b^{j}$,
we have that: $V_{t+1}^{0}(b^{j})-V_{t+1}^{0}(b^{i})\leq 0$.
As consequence, $V_{t+1}^{0}(\cdot)$ is increasing with $b^{j}$.

In the same way, we have:

$V_{t+1}^{1}(b^{j})-V_{t+1}^{1}(b^{i})=b^{j}-b^{i}+(1-\rho)(V_{t}(b^{j+1})-V_{t}(b^{i+1}))$

Hence:

$V_{t+1}^{1}(b^{j})-V_{t+1}^{1}(b^{i})\leq 0$ (39)

As consequence, $V_{t+1}^{1}(\cdot)$ is increasing with $b^{j}$.
Since $V_{t+1}(.)=\min\\{V^{0}_{t+1}(\cdot),V^{1}_{t+1}(\cdot)\\}$, then
$V_{t+1}(.)$ is increasing with $b^{j}$. Accordingly, we demonstrate by
induction that $V_{t}(.)$ is increasing for all $t$. Knowing that
$\underset{t\rightarrow+\infty}{\text{lim}}V_{t}(b^{j})=V(b^{j})$, $V(.)$ must
be also increasing with $b^{j}$. ∎

We define:

$\Delta V(b^{j})=V^{1}(b^{j})-V^{0}(b^{j})$ (40)

where
$\underset{t\rightarrow+\infty}{\text{lim}}V_{t}^{0}(b^{j})=V^{0}(b^{j})$ and
$\underset{t\rightarrow+\infty}{\text{lim}}V_{t}^{1}(b^{j})=V^{1}(b^{j})$.
Subsequently, $\Delta V(b^{j})$ equals to:

$\Delta V(b^{j})=\rho[\frac{W}{\rho}+V(b^{0})-V(b^{j+1})]$ (41)

According to Lemma 4, $V(.)$ is increasing with $b^{j+1}$. Therefore, $\Delta
V(b^{j})$ is decreasing with $b^{j}$. Hence, there exists $b^{n}$ such that
for all $b^{j}\leq b^{n}$, $\Delta V(b^{j})\geq 0$, and for all $b^{j}>b^{n}$,
$\Delta V(b^{j})<0$. Given that the optimal action for state $b^{j}$ is the
one that minimizes $\min\\{V^{0}(\cdot),V^{1}(\cdot)\\}$, then for all
$b^{j}\leq b^{n}$, the optimal decision is to stay idle since
$\min\\{V^{0}(b^{j}),V^{1}(b^{j})\\}=V^{0}(b^{j})$, and for all $b^{j}>b^{n}$,
the optimal decision is to transmit since
$\min\\{V^{0}(b^{j}),V^{1}(b^{j})\\}=V^{1}(b^{j})$. Specifically, as $b^{j}$
is increasing with $j$, there exists $n$ such that for all $j<n$, the optimal
action is passive action, and for all $j\geq n$, the optimal action is the
active one.

##  Appendix D Proof of Proposition 1

In order to demonstrate this proposition, we need to resolve the full balance
equation under threshold policy $n$ at each state $b^{j}$:

$u^{n}(b^{j})=\sum_{i=0}^{+\infty}pt^{n}(i\rightarrow j)u^{n}(b^{i})$ (42)

where $pt^{n}(i\rightarrow j)$ denotes the transitioning probability from the
state $b^{i}$ to the state $b^{j}$ under threshold policy $n$. After some
computations, we obtain the desired result.

##  Appendix E Proof of Proposition 2

Exploiting the results of Proposition 1 and by definition of
$\overline{s^{n}}$ given in (23), we have that:
$\overline{s^{n}}=\sum_{j=0}^{+\infty}b^{j}u^{n}(b^{j})$.

Therefore, using the expression of $b^{j}$ for $j\geq 0$, we have that:

$\displaystyle\overline{s^{n}}$
$\displaystyle=dp\frac{\rho}{n\rho+1}[\sum_{j=0}^{n}\frac{j(j+1)}{2}+\sum_{j=n+1}^{+\infty}\frac{j(j+1)}{2}(1-\rho)^{j-n}]$
$\displaystyle=dp\frac{\rho}{n\rho+1}[\sum_{j=0}^{n}\frac{j^{2}}{2}+\sum_{j=0}^{n}\frac{j}{2}+\sum_{j=n+1}^{+\infty}j(j+1)\frac{(1-\rho)^{j-n}}{2}]$
(43)

We have also:
$\sum_{j=0}^{n}\frac{j^{2}}{2}=\frac{1}{2}(\frac{n^{3}}{3}+\frac{n^{2}}{2}+\frac{n}{6})$
and $\sum_{j=0}^{n}\frac{j}{2}=\frac{1}{2}\frac{n(n+1)}{2}$. As for the last
term, we have that:

$\displaystyle\sum_{j=n+1}^{+\infty}j(j+1)\frac{(1-\rho)^{j-n}}{2}=\sum_{j=1}^{+\infty}(j+n)(j+1+n)\frac{(1-\rho)^{j}}{2}$
$\displaystyle=\sum_{j=1}^{+\infty}j(j+1)\frac{(1-\rho)^{j}}{2}+\frac{n^{2}}{2}\frac{1-\rho}{\rho}+\frac{n}{2}\frac{1-\rho^{2}}{\rho^{2}}$
$\displaystyle+\frac{n}{2}(1-\rho)\frac{1}{\rho^{2}}$ (44)

We have that:

$\displaystyle\sum_{j=1}^{+\infty}j(j+1)(1-\rho)^{j}$
$\displaystyle=\sum_{j=0}^{+\infty}j(j+1)(1-\rho)^{j}$
$\displaystyle=(1-\rho)\sum_{j=0}^{+\infty}\frac{\partial^{2}(1-\rho)^{j+1}}{\partial(1-\rho)^{2}}$
(45)

Leveraging that, and given that
$\sum_{j=0}^{+\infty}(1-\rho)^{j+1}=\frac{1-\rho}{\rho}$, then by deriving
twice this term with respect to $1-\rho$, we get
$\frac{1}{2}\sum_{j=1}^{+\infty}j(j+1)(1-\rho)^{j}=\frac{1-\rho}{\rho^{3}}$.
Adding all terms together, we get:

$\displaystyle\overline{s^{n}}=$ $\displaystyle
dp\frac{\rho}{n\rho+1}[\frac{1}{6}n^{3}+\frac{1}{2\rho}n^{2}+\frac{6-\rho^{2}-3\rho}{6\rho^{2}}n+\frac{1-\rho}{\rho^{3}}]$
(46)

As consequence, we get our the desired results.

##  Appendix F Proof of Theorem 2

The investigations regarding the expression of the Whittle’s index for Age of
Information metric have been already done in [2]. To that extent, in this
proof, we do the analysis only for the adapted AoII metric considered
throughout our paper. We first define the sequence $W_{i}(b_{i}^{n})$ as the
intersection points between $\overline{b_{i}^{n}}+W\overline{a_{i}^{n}}$ and
$\overline{b_{i}^{n+1}}+W\overline{a_{i}^{n+1}}$. Explicitly:

$W_{i}(b_{i}^{n})=\frac{\overline{b_{i}^{n+1}}-\overline{b_{i}^{n}}}{\overline{a_{i}^{n}}-\overline{a_{i}^{n+1}}}$
(47)

According to the results in [32, Corollary 2.1], if $W_{i}(b_{i}^{n})$ is
increasing with $b_{i}^{n}$, then the Whittle’s index for any state
$b_{i}^{n}$ is nothing but $W_{i}(b_{i}^{n})$. To that extent, we prove that
$W_{i}(b_{i}^{n})$ is increasing with $b_{i}^{n}$. However, since $b_{i}^{n}$
is increasing with $n$, it is sufficient to show that $W_{i}(b_{i}^{n})$ is
increasing with $n$ to establish the desired result.

Therefore, we first seek a closed-form expression of the intersection point
$W_{i}(b_{i}^{n})$, we obtain:

$\displaystyle
W_{i}(b_{i}^{n})=d_{i}p_{i}[\frac{1}{3}\rho_{i}n^{3}+(1+\frac{\rho_{i}}{2})n^{2}+(1+\frac{\rho_{i}}{6}+\frac{1}{\rho_{i}})n+\frac{1}{\rho_{i}}]$
(48)

From the expression above, it is clear that $W_{i}(b_{i}^{n})$ is increasing
with $b_{i}^{n}$. Therefore $W_{i}(b_{i}^{n})$ is the Whittle’s index of the
state $b_{i}^{n}$. That concludes the proof.