# Two characterizations of the grid graphs

Brhane Gebremichel  School of Mathematical Sciences, University of Science and
Technology of China, 96 Jinzhai Road, Hefei, 230026, Anhui, PR China. Meng-Yue
Cao111Corresponding author. School of Mathematical Sciences, Beijing Normal
University, 19 Xinjiekouwai Street, Beijing, 100875, PR China.  Jack H. Koolen
School of Mathematical Sciences, University of Science and Technology of
China, 96 Jinzhai Road, Hefei, 230026, Anhui, PR China. CAS Wu Wen-Tsun Key
Laboratory of Mathematics, University of Science and Technology of China, 96
Jinzhai Road, Hefei, Anhui, 230026, PR China

###### Abstract

In this paper we give two characterizations of the $p\times q$-grid graphs as
co-edge-regular graphs with four distinct eigenvalues.

††2010 Mathematics Subject Classification. Primary 05C50, secondary
05E99.††E-mail addresses<EMAIL_ADDRESS>(B. Gebremichel),
<EMAIL_ADDRESS>(M.-Y. Cao<EMAIL_ADDRESS>(J.H. Koolen).

Keywords : Strongly co-edge-regular graphs, grid graphs, co-edge-regular
graphs with four distinct eigenvalues, walk-regular.

##  1 Introduction

All graphs mentioned in this paper are finite, undirected and simple. For
undefined notations, see [1] and [2]. The eigenvalues of a graph are the
eigenvalues of its adjacency matrix in this paper. Recall that a co-edge-
regular graph with parameters $(n,k,c)$ is a $k$-regular graph with $n$
vertices, such that any two distinct non-adjacent vertices have exactly $c$
common neighbours.

In this paper, we continue our study on co-edge-regular graphs with four
distinct eigenvalues. A motivation to study these graphs comes from the
lecture note [10]. In these note, Terwilliger shows that any local graph of a
thin $Q$-polynomial distance-regular graph is co-edge-regular and has at most
five distinct eigenvalues. So it is interesting to study co-edge-regular
graphs with a few distinct eigenvalues. Another motivation is as follows:
strongly regular graphs have attracted a lot of attention, see for example
[14]. On the other hand, there are only a few papers on regular graphs with
four eigenvalues, see for example [11, 12, 13, 6]. We think that connected co-
edge-regular graphs are an interesting class of graphs.

Tan, Koolen and Xia [9] gave the following conjecture.

######  Conjecture 1.1.

Let $G$ be a connected co-edge-regular graph with parameters $(n,k,c)$ having
four distinct eigenvalues. Let $m\geqslant 2$ be an integer. Then there exists
a constant $n_{m}$ such that, if $\theta_{\min}(G)\geqslant-m$ and $n\geqslant
n_{m}$ and $k<n-2-\frac{(m-1)^{2}}{4}$, then either $G$ is the $s$-clique
extension of a strongly regular graph for $2\leqslant s\leqslant m-1$ or $G$
is a $p\times q$-grid with $p>q\geqslant 2$.

The first result on co-edge-regular graphs was shown by Brouwer, Cohen and
Neumaier [1, Lemma 1.1.3]. They showed that a co-edge-regular graph with
parameters $(n,k,1)$ is strongly regular. They gave some more conditions such
that a co-edge-regular graph satisfying these conditions is strongly regular.
Hayat, Koolen and Riaz [4] showed that any co-edge-regular graph cospectral
with the $s$-clique extension of the $t\times t$-grid is the $s$-clique
extension of the $t\times t$-grid, if $t$ is much larger than $s$. Tan et al.
[9] showed that any co-edge-regular graph cospectral with the $s$-clique
extension of the triangular graph $T(t)$ is the $s$-clique extension of
$T(t)$. In this paper, we will concentrate on co-edge-regular graphs with
parameters $(n,k,2)$ having exactly four distinct eigenvalues. A $p\times
q$-grid is the line graphs of the complete bipartite graph $K_{p,q}$. In other
words it is the cartesian product of the complete graphs $K_{p}$ and $K_{q}$.
For connected co-edge-regular graphs with four distinct eigenvalues, we obtain
the following two characterizations of the $p\times p$-grid.

######  Theorem 1.2.

Let $G$ be a co-edge-regular graph with parameters $(n,k,2)$ with distinct
eigenvalues $k=\theta_{0}>\theta_{1}>\theta_{2}>\theta_{3}$. Let
$\ell:=2(\sum\limits_{i=1}^{3}\theta_{i})+\frac{\prod_{i=1}^{3}(k-\theta_{i})}{n}-2(k-2)$.

  1. (i)

If $\ell\geqslant\frac{3}{4}k$, then $G$ is a $p\times q$-grid, where
$p>q\geqslant 2$, $p+q=k+2$ and $\ell=k-2$ or the $2$-clique extension of
$C_{5}$.

  2. (ii)

If $\theta_{3}\geqslant-3$ and $k\geqslant 120$, then $G$ is a $p\times
q$-grid, where $p>q\geqslant 2$, $p+q=k+2$ and $\ell=k-2$.

Now we introduce a class of co-edge-regular graphs that gives a combinatorial
generalization of co-edge-regular graphs with exactly four distinct
eigenvalues. Let $G$ be a graph. Let $a_{xy}$ denote the number of common
neighbours of two adjacent vertices $x$ and $y$ in $G$. A _strongly co-edge-
regular graph_ $G$ with parameters $(n,k,c,\ell)$ is a co-edge-regular graph
with parameters $(n,k,c)$ such that for any two distinct non-adjacent vertices
$x$ and $z$, $\sum_{y\sim x,y\sim z}a_{xy}=\ell$ holds. Note that there are
many strongly co-edge-regular graphs, for example, the complement of a
distance-regular graph of diameter at least $2$ is strongly co-edge-regular.

A co-edge-regular graph with exactly four distinct eigenvalues is strongly co-
edge-regular and walk-regular, as we will show in Section 4.2.

We will use the concept of strongly co-edge-regular graphs to show the
following two results.

######  Theorem 1.3.

Let $G$ be a walk-regular and strongly co-edge-regular graph with parameters
$(n,k$, $2,\ell)$. If $\ell\geqslant\frac{3}{4}k$, then $G$ is a $p\times
q$-grid, where $p+q=k+2$ and $\ell=k-2$ or the $2$-clique extension of
$C_{5}$.

When we moreover assume that the smallest eigenvalue is at least $-3$, we can
remove the bound on $\ell$.

######  Theorem 1.4.

Let $G$ be a walk-regular and strongly co-edge-regular graph with parameters
$(n,k$, $2,\ell)$ with smallest eigenvalue $\theta_{\min}$ at least $-3$. If
$k\geqslant 120$, then $G$ is a $p\times q$-grid, where $p+q=k+2$ and
$\ell=k-2$.

######  Remark 1.5.

  1. (i)

The $2$-clique extension of the pentagon $C_{5}$ is a co-edge-regular graph
with parameters $(10,5,2)$ with exactly four distinct eigenvalues and smallest
eigenvalue $-\sqrt{5}$.

  2. (ii)

The $2$-clique extension of the Petersen graph is co-edge-regular with
parameters $(20,7,2)$ with exactly four distinct eigenvalues and smallest
eigenvalue $-3$.

Theorem 1.2 follows directly from Theorem 1.3 and 1.4, as a co-edge-regular
graph with four distinct eigenvalues is walk regular and strongly co-edge-
regular graph.

This paper is organized as follows. In Section 2 we give preliminaries. In
Section 3 we give some results on co-edge-regular and strongly co-edge-regular
graphs. We show Theorem 1.4 and Theorem 1.2 in Section 4.

##  2 Preliminaries

###  2.1 Graphs

A graph $G$ is an ordered pair $(V(G),E(G))$, where $V(G)$ is a finite set and
$\displaystyle E(G)\subseteq\binom{V(G)}{2}$. The set $V(G)$ (resp. $E(G)$) is
called the _vertex set_ (resp. _edge set_) of $G$. A _subgraph_ of a graph $G$
is a graph $H$ such that $V(H)\subseteq V(G)$ and $E(H)\subseteq E(X)$. If
$E(H)=\binom{V(H)}{2}\cap E(G)$, then we say $H$ is an _induced subgraph_ of
$G$. The disjoint union of the graphs $G_{1}$ and $G_{2}$ is denoted by
$G_{1}\dot{\cup}G_{2}$. If $\\{x,y\\}$ is an edge in $E$, then we say the
vertices $x,y$ are adjacent, denoted by $x\sim y$, and otherwise, we say that
$x,y$ are not adjacent, denoted by $x\not\sim y$ . The _complement_
$\overline{G}$ of a graph $G$ has the same vertex set as $G$, where distinct
vertices $x$ and $y$ are adjacent in $\overline{G}$ if and only if they are
not adjacent in $G$. The _adjacency matrix_ of $G$, denoted by $A(G)$, is a
symmetric $(0,1)$-matrix indexed by $V(G)$, such that $(A(G))_{xy}=1$ if and
only if $x\sim y$. The _eigenvalues_ of $G$ are the eigenvalues of $A(G)$. The
_spectrum_ of a graph $G$ is the list of the eigenvalues of $A(G)$ together
with their multiplicities.

Let $G$ be a graph. For a vertex $x\in V(G)$, we denote by $N_{G}(x)$ the set
of the neighbours of $x$ in $G$, and call the subgraph induced on $N_{G}(x)$
the _local graph_ of $x$ in $G$. We denote by $N_{G}(x,y)$ the set of common
neighbours of $x,y$ in $G$. We write $a_{xy}$ for the cardinality of
$N_{G}(x,y)$, if $x,y$ are adjacent. A graph $G$ is called bipartite if its
vertex set can be partitioned into two parts $V_{1}$ and $V_{2}$ such that
every edge has one end in $V_{1}$ and one in $V_{2}$. If every vertex in
$V_{1}$ is adjacent to all vertices in $V_{2}$, then we say $G$ is a complete
bipartite graph, and also denoted by $K_{|V_{1}|,|V_{2}|}$. A graph is
complete, if every pair of distinct vertices is adjacent. We call a subgraph
is a _clique_ , if it is isomorphic to a complete graph. We say a clique with
$s$ vertices an $s$-clique. The cardinality of a maximum clique in a graph $G$
is called the _clique number_ of $G$, and is denoted by $\omega(G)$. A graph
$G$ is called _$k$ -regular_ if every vertex in $G$ has $k$ neighbours.

######  Definition 2.1.

Let $G$ be a $k$-regular graph on $n$ vertices that is neither complete nor
empty. Then $G$ is said to be

  1. (i)

_co-edge-regular_ with parameters $(n,k,c)$, if any pair of distinct non-
adjacent vertices have $c$ common neighbours.

  2. (ii)

_strongly regular_ with parameters $(n,k,a,c)$, if any two adjacent vertices
have $a$ common neighbours and any pair of distinct non-adjacent vertices have
$c$ common neighbours.

  3. (iii)

_walk-regular_ , if for all nonnegative integers $r$, all the diagonal entries
of $A^{r}$ are the same, where $A$ is the adjacency matrix of $G$.

For a positive integer $s$, the _$s$ -clique extension_ of a graph $G$ is the
graph $\tilde{G}$ obtained from $G$ by replacing each vertex $x\in V(G)$ by a
clique $\tilde{X}$ with s vertices, such that $\tilde{x}\sim\tilde{y}$ (for
$\tilde{x}\in\tilde{X},\tilde{y}\in\tilde{Y}$) in $\tilde{G}$ if and only if
$x\sim y$ in $G$. If $\tilde{G}$ is the $s$-clique extension of $G$, then
$\tilde{G}$ has adjacency matrix
$\mathbf{J}_{s}\otimes(A(G)+\mathbf{I}_{n})-\mathbf{I}_{sn}$, where
$\mathbf{I}$ is the identity matrix and $\mathbf{J}$ is the all-ones matrix.
If $G$ has spectrum
$\\{\theta_{0}^{m_{0}},\theta_{1}^{m_{1}},\ldots,\theta_{t}^{m_{t}}\\}$, then
the spectrum of $\tilde{G}$ is

$\\{(s(\theta_{0}+1)-1)^{m_{0}},(s(\theta_{1}+1)-1)^{m_{1}},\ldots,(s(\theta_{t}+1)-1)^{m_{t}},(-1)^{(s-1)(m_{0}+m_{1}+\cdots+m_{t})}\\}.$

###  2.2 Interlacing

If $M$ (resp. $N$) is a real symmetric $m\times m$ (resp. $n\times n$) matrix,
let $\eta_{1}(M)\geqslant\eta_{2}(M)\geqslant\cdots\geqslant\eta_{m}(M)$
(resp. $\eta_{1}(N)\geqslant\eta_{2}(N)\geqslant\cdots\geqslant\eta_{n}(N)$)
denote the eigenvalues of $M$ (resp. $N$) in nonincreasing order. Assume
$m\leqslant n$. We say that the eigenvalues of $M$ _interlace_ the eigenvalues
of $N$, if $\eta_{n-m+i}(N)\leqslant\eta_{i}(M)\leqslant\eta_{i}(N)$ for each
$i=1,\ldots,m$. The following result is a special case of interlacing.

######  Lemma 2.2 (cf.[3, Theorem 9.1.1]).

Let $B$ be a real symmetric $n\times n$ matrix and $C$ a principal submatrix
of $B$ of order $m$, where $m<n$. Then the eigenvalues of $C$ interlace the
eigenvalues of $B$.

As an easy consequence of Lemma 2.2, we have the following proposition.

######  Proposition 2.3.

Let $G$ be a graph and $H$ a proper induced subgraph of $G$. Denote by
$\theta_{\min}(G)$ (resp. $\theta_{\min}(H)$) the smallest eigenvalue of $G$
(resp. $H$). Then $\theta_{\min}(G)\leqslant\theta_{\min}(H)$.

Let $G=(V,E)$ be a graph and $\pi:=\\{V_{1},\ldots,V_{r}\\}$ be a partition of
$V$. We say $\pi$ is an _equitable partition_ with respect to $G$ if the
number of neighbours in $V_{j}$ of a vertex $u$ in $V_{i}$ is a constant
$q_{ij}$, independent of $u$. For an equitable partition $\pi$ with respect to
$G$, the quotient matrix $Q$ of $G$ with respect to $\pi$ is defined as
$Q=(q_{ij})_{1\leqslant i,j\leqslant r}$.

######  Lemma 2.4 (cf.[3, Theorem 9.3.3]).

Let $G$ be a graph. If $\pi$ is an equitable partition of $G$ and $Q$ is the
quotient matrix with respect to $\pi$ of $G$, then every eigenvalue of $Q$ is
an eigenvalue of $G$.

For a graph $G$, let $C(G)$ be the _cone_ of $G$, that is, $C(G)$ is obtained
by adding a vertex to $G$ and joining it to all vertices of $G$.

######  Lemma 2.5.

Let $G$ be a graph with smallest eigenvalue at least $-3$. Then none of the
following graphs is an induced subgraph of $G$.

  1. (i)

Connected bipartite graphs with order at least $11$ and containing an induced
$K_{1,9}$;

  2. (ii)

Graphs $C(2K_{s}\dot{\cup}tK_{1})$, where $(s+2)(t-3)>12$;

  3. (iii)

Graphs $C(2K_{15}\dot{\cup}K_{3}\dot{\cup}2K_{1})$,
$C(2K_{21}\dot{\cup}K_{11}\dot{\cup}K_{1})$, $C(C(2K_{13})\dot{\cup}K_{13})$,
$C(C(3K_{5}))$.

######  Proof.

Let $G$ be a graph with smallest eigenvalue at least $-3$.

$(\mathrm{i})$ Let $B$ be a connected bipartite graph with order $n\geqslant
11$. Assume that $B$ contains an induced $K_{1,9}$. Denote by
$\theta_{\max}(B)$ the largest eigenvalue and $\theta_{\min}(B)$ the smallest
eigenvalue of $B$. By the Perron-Frobenius Theorem [1, Theorem 3.1.1], we have
$\theta_{\max}(B)>3$, as the largest eigenvalue of $K_{1,9}$ is $3$. Since $B$
is a bipartite graph, we obtain $\theta_{\min}(B)=-\theta_{\max}(B)<-3$. It
follows by Lemma 2.2 that $G$ does not contain $B$ as an induced subgraph.

$(\mathrm{ii})$ Assume that $G$ contains $C(2K_{s}\dot{\cup}tK_{1})$, say $H$,
as an induced subgraph for some integers $s,t$. By Lemma 2.2, we have the
smallest eigenvalue of $H$ is at least $-3$. Let $u$ be the vertex of valency
$2s+t$ in $H$. Let $V_{1}$ be the set of vertices of valency $s$ in $H$ and
$V_{2}=V(H)-\\{u\\}-V_{1}$. Consider a partition
$\pi=\\{\\{u\\},V_{1},V_{2}\\}$ of $H$. The partition $\pi$ is equitable with
quotient matrix $Q$:

$\displaystyle Q=\begin{pmatrix}0&2s&t\\\ 1&s-1&0\\\ 1&0&0\end{pmatrix}.$

Note that $\det(Q+3\mathbf{I})=-(s+2)(t-3)+12$. By Lemma 2.4, we see that the
smallest eigenvalue of $Q$ is at least $-3$. Hence, we have
$(s+2)(t-3)\leqslant 12$, as $\det(Q+3\mathbf{I})\geqslant 0$. This shows $G$
does not contain $C(2K_{s}\dot{\cup}tK_{1})$ as an induced subgraph for
$(s+2)(t-3)>12$.

$(\mathrm{iii})$ By using a similar method as in the proof for
$(\mathrm{ii})$, we obtain $(\mathrm{iii})$. ∎

###  2.3 Strongly regular graphs

A strongly regular graph $G$ with at least $2$ vertices is called _primitive_
if both $G$ and its complement are connected. Note that, if $G$ is primitive
strongly regular with parameters $(n,k,a,c)$, then $0<c<k$. A _conference
graph_ is a strongly regular graph with parameters $(4c+1,2c,c-1,c)$, where
$c$ is a positive integer.

######  Lemma 2.6 (cf.[8, Lemma 1.2]).

Let $G$ be a strongly regular graph with parameters $(n,k,a,c)$ and
eigenvalues $k>\theta_{1}>\theta_{2}$. Then $G$ is a conference graph or both
$\theta_{1},\theta_{2}$ are integers.

######  Lemma 2.7 (cf.[3, Sections 10.2 and 10.3]).

Let $G$ be a strongly regular graph with parameters $(n,k,a,c)$, where $k>c$.
Then $G$ has exactly three distinct eigenvalues $k>\theta>\tau$ satisfying

$\displaystyle\theta$ $\displaystyle=\frac{(a-c)+\sqrt{(a-c)^{2}+4(k-c)}}{2},$
$\displaystyle\tau$ $\displaystyle=\frac{(a-c)-\sqrt{(a-c)^{2}+4(k-c)}}{2}.$

Moreover, $m_{\tau}-m_{\theta}=\frac{2k+(n-1)(a-c)}{\sqrt{(a-c)^{2}+4(k-c)}}$,
where $m_{\theta}$ and $m_{\tau}$ are the respective multiplicities of
$\theta,\tau$.

######  Lemma 2.8 (cf.[8, Theorem 4.7]).

Let $G$ be a strongly regular graph with parameters $(n,k,a,c)$ and
eigenvalues $k>\theta_{1}>\theta_{2}$, where $\theta_{2}<-1$ is an integer. If
$c\notin\\{\theta_{2}(\theta_{2}+1),\theta_{2}^{2}\\}$, then

$\theta_{1}\leqslant\frac{\theta_{2}(\theta_{2}+1)(c+1)}{2}-1.$

######  Lemma 2.9 (cf.[1, Corollary 3.12.3 and Theorem 3.12.4]).

Let $G$ be a connected regular graph with smallest eigenvalue $\theta_{\min}$.

  1. (i)

If $\theta_{\min}>-2$, then $G$ is a clique or an odd cycle.

  2. (ii)

If $G$ is a strongly regular graph and $\theta_{\min}=-2$, then $G$ is a
triangle graph $T(n)$ ($n\geqslant 5$), a square grid $n\times n$ ($n\geqslant
3$), a complete multipartite graph $K_{n\times 2}$ ($n\geqslant 2$), or one of
the graphs of Petersen, Clebsch, Schläfli, Shrikhande, or Chang.

Table 1 below states the parameters of $K_{n},C_{5}$ and all the graphs in
Lemma 2.9 (ii).

Graph | Parameters
---|---
$K_{n}$ | $(n,n-1,n-2,0)$
the pentagon $C_{5}$ | $(5,2,0,1)$
$T(n)$ ($n\geqslant 5$) | $(\frac{n(n-1)}{2},2n-4,n-2,4)$
$n\times n$-grid ($n\geqslant 3$) | $(n^{2},2n-2,n-2,2)$
$K_{n\times 2}$ ($n\geqslant 2$) | $(2n,2(n-1),2(n-2),2(n-1))$
the Petersen graph | $(10,3,0,1)$
the Clebsch graph | $(16,10,6,6)$
the Schläfli graph | $(27,16,10,8)$
the Shrikhande graph | $(16,6,2,2)$
the Chang graphs | $(28,12,6,4)$
Table 1: Parameters of $K_{n},C_{5}$ and strongly regular graphs with smallest
eigenvalue $-2$

###  2.4 Terwilliger graphs

A _Terwilliger graph_ is a non-complete graph $G$ such that, for any two
vertices $x,y$ at distance $2$, the subgraph induced by $N_{G}(x,y)$ forms a
clique of size $c$ (for some fixed $c\geqslant 0$).

######  Lemma 2.10 (cf.[1, Proposition 1.16.2]).

Let $G$ be a connected co-edge-regular Terwilliger graph. Then $G$ is the
$s$-clique extension of a strongly regular graph, where $s$ is a positive
integer.

######  Proposition 2.11 (cf.[7, Proposition 6 (1) and (2)]).

  1. (i)

Let $G$ be a connected non-complete strongly regular with parameters
$(n,k,a,1)$. If $k<7(a+1)$, then $G$ is either the pentagon or the Petersen
graph.

  2. (ii)

Let $G$ be a connected non-complete strongly regular Terwilliger graph with
$n$ vertices and valency $k$. If $k\leqslant 7a$, then $G$ is either the
pentagon or the Petersen graph.

######  Lemma 2.12.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,2,\ell)$. If
$\ell\geqslant\frac{2}{7}k$, then $G$ contains an induced quadrangle or $G$ is
the $2$-clique extension of the pentagon or the Petersen graph.

######  Proof.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,2,\ell)$
which does not contain induced quadrangles. Then $G$ is a Terwilliger graph of
diameter $2$ and hence $G$ is the $s$-clique extension of a non-complete
strongly regular graph $H$ for some integer $s$, by Lemma 2.10.

If $s=1$, then $G$ is a strongly regular Terwilliger graph with parameters
$(n,k,a,2)$ and $\ell=2a$. As $\ell\geqslant\frac{2}{7}k$ we have $k\leqslant
7a$. Thus, by Proposition 2.11 $(ii)$ , we see that no such graph exists.

If $s=2$, then $G$ is the $2$-clique extension of a strongly regular graph $H$
with parameters $(n_{H},k_{H},a_{H},1)$. It is not hard to see that

$n_{H}=\frac{n}{2},\text{ }k_{H}=\frac{k-1}{2},\text{ and
}a_{H}=\frac{\ell-4}{4}.$

As $\ell\geqslant\frac{2}{7}k$, we have $k_{H}<7(a_{H}+1)$ and hence $H$ is
the pentagon or the Petersen graph, by Proposition 2.11$(i)$. This completes
the proof of the lemma.

∎

##  3 Co-edge-regular graphs and strongly co-edge-regular graphs

In this section, we state some results for co-edge-regular graphs and strongly
co-edge-regular graphs.

######  Lemma 3.1.

Let $G$ be a walk-regular and co-edge-regular graph with parameters $(n,k,c)$.
Let $x$ be a vertex of $G$ and $a_{xy}$ the number of common neighbours of
$x,y$ for $y\in N_{G}(x)$. Then $\sum\limits_{y\sim x}a_{xy}$ and
$\sum\limits_{y\sim x}a_{xy}^{2}$ only depend on the spectrum of $G$.

######  Proof.

Let $G$ be a walk-regular graph and co-edge-regular graph with parameters
$(n,k,c)$. Let $A$ be the adjacency matrix of $G$. As $G$ is walk-regular, for
any vertex $x$, the numbers $(A^{3})_{xx}$ and $(A^{4})_{xx}$ only depend on
the spectrum of $G$.

As $\sum\limits_{y\sim x}a_{xy}=(A^{3})_{xx}$, we see that $\sum\limits_{y\sim
x}a_{xy}$ only depends on the spectrum of $G$ for any vertex $x$ of $G$.

Note that

$(A^{4})_{xx}=k^{2}+\sum\limits_{y\sim x}a^{2}_{xy}+(n-k-1)c^{2},$

as $G$ is co-edge-regular with parameters $(n,k,c)$. Hence,
$\sum\limits_{y\sim x}a_{xy}^{2}$ only depends on the spectrum of $G$ for any
vertex $x$ of $G$, as $\sum\limits_{y\sim x}a_{xy}$ only depends on the
spectrum of $G$.

∎

######  Lemma 3.2.

Let $G$ be a walk-regular and co-edge-regular graph. If there exists a vertex
$x\in V(G)$ such that $a_{xy}=a_{xy^{\prime}}$ for all $y,y^{\prime}\in
N_{G}(x)$, then $G$ is strongly regular.

######  Proof.

Let $G$ be a walk-regular and co-edge-regular graph. Let $x$ be a vertex in
$G$, such that $a_{xy}=a$ for all $y\in N_{G}(x)$, where $a$ is a constant.
Let $u$ be a vertex in $G$. We now show that $a_{uv}=a$ for all $v\in
N_{G}(u)$. Note that, $\sum\limits_{v\sim u}a_{uv}=\sum\limits_{y\sim
x}a_{xy}$ and $\sum\limits_{v\sim u}a_{uv}^{2}=\sum\limits_{y\sim
x}a_{xy}^{2}$, by Lemma 3.1. Hence,

$\begin{array}[]{rl}\sum\limits_{v\sim u}(a_{uv}-a)^{2}&=\sum\limits_{v\sim
u}a_{uv}^{2}-2a\sum\limits_{v\sim u}a_{uv}+a^{2}\\\ &=\sum\limits_{y\sim
x}a_{xy}^{2}-2a\sum\limits_{y\sim x}a_{xy}+a^{2}\\\ &=\sum\limits_{y\sim
x}(a_{xy}-a)^{2}=0.\end{array}$

This shows the lemma. ∎

######  Lemma 3.3.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,2,\ell)$.
Let $x$ be a vertex in $G$ and let $W:=\\{w\mid x\sim
w,a_{xw}\geqslant\frac{k}{2}\\}$. If $W\neq\emptyset$, then $W$ induces a
clique in $G$.

######  Proof.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,c,\ell)$,
where $c=2$. Let $x$ be a vertex in $G$. Let $W:=\\{w\mid x\sim
w,a_{xw}\geqslant\frac{k}{2}\\}$. The lemma is clear when $|W|=1$. Now we
assume $|W|\geqslant 2$. Take $w_{1},w_{2}$ in $W$. Suppose that $w_{1},w_{2}$
are not adjacent. Note that $\\{w_{1},w_{2}\\}\cup N_{G}(x,w_{1})\cup
N_{G}(x,w_{2})\subseteq N_{G}(x)$. Then,

$|N_{G}(x,w_{1})\cap N_{G}(x,w_{2})|\geqslant
2+a_{xw_{1}}+a_{xw_{2}}-k\geqslant 2.$

This means $w_{1}$ and $w_{2}$ have at least $3$ common neighbours in $G$, as
$\\{x\\}\cup(N_{G}(x,w_{1})\cap N_{G}(x,w_{2}))\subseteq N_{G}(w_{1},w_{2})$.
This is a contradiction, as $c=2$. This shows the lemma. ∎

The following theorem shows that a strongly co-edge-regular graph with large
clique number has large $\ell$.

######  Theorem 3.4.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,2,\ell)$ and
clique number $\omega$. If $\omega>\frac{\ell+4}{2}$, then $\ell=k-2$.

######  Proof.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,c,\ell)$ and
clique number $\omega$, where $c=2$ and $\omega>\frac{\ell+4}{2}$. Let $x$ be
a vertex in a maximum clique in $G$. Denote by $\Delta(x)$ the local graph of
$x$ in $G$. Assume $C$ is a maximum clique in $\Delta(x)$ with order
$\omega^{\prime}=\omega-1>\frac{\ell+2}{2}$. Define $R:=N_{G}(x)-C$ and
$r:=|R|$.

######  Claim 3.5.

There is no edge between $C$ and $R$.

Proof of Claim 3.5. Assume there exists $u\in C$ and $v\in R$ such that $u\sim
v$. There exists a vertex $u^{\prime}\in C$ with $u\neq u^{\prime}$ such that
$u^{\prime}\not\sim v$, as $C$ is a maximum clique.

$x$$u^{\prime}$$u$$v$

Note that

$\ell=a_{u^{\prime}x}+a_{u^{\prime}u}\geqslant
2(\omega^{\prime}-1)>2(\frac{\ell+2}{2}-1)=\ell,$

as $|C|=\omega^{\prime}>\frac{\ell+2}{2}$. This is a contradiction, which
shows Claim 3.5. ∎

Let $u$ be a vertex in $C$. Define

$W(u):=\\{w\mid w\sim u,w\not\sim x\\}.$

By Claim 3.5, we obtain $|W(u)|=k-1-(\omega^{\prime}-1)=k-\omega^{\prime}=r$.
Note that every vertex in $W(u)$ has exactly one neighbour in $C$, as $\ell-
a_{xu}=\ell-(\omega^{\prime}-1)<\ell-\frac{\ell}{2}<\frac{\ell}{2}<\omega^{\prime}-1$.
Then every vertex in $W(u)$ has exactly one neighbour in $R$, as $c=2$. By
Claim 3.5, the vertex $v$ has no neighbours in $C$ for $v\in R$. Hence, $v$
has one neighbour in $W(u)$. So, $a_{xv}=\ell-a_{xu}<\frac{\ell}{2}$ for $v\in
R$. It follows that any two distinct vertices in $R$ have no common neighbours
outside $N_{G}(x)\cup\\{x\\}$.

######  Claim 3.6.

The set $R$ forms a clique in $G$.

Proof of Claim 3.6. Suppose that $v_{1}\neq v_{2}\in R$ are not adjacent. As
$a_{xv_{1}}=a_{xv_{2}}=\ell-a_{xu}<\frac{\ell}{2}$ and $c=2$, we obtain
$v_{1}$ and $v_{2}$ have a common neighbour $v_{3}$ in $N_{G}(x)$. By Claim
3.5, the vertex $v_{3}$ is in $R$.

$x$$v_{1}$$v_{3}$$v_{2}$

As $a_{xv_{1}}=a_{xv_{3}}=\ell-a_{xu}<\frac{\ell}{2}$, the vertices $v_{1}$
and $v_{3}$ have no common neighbours outside $N_{G}(x)-\\{x\\}$. Hence,
$a_{v_{1}v_{3}}\leqslant r-2+1<\frac{\ell}{2}$. It follows that

$\ell=a_{v_{1}x}+a_{v_{1}v_{3}}<\frac{\ell}{2}+\frac{\ell}{2}=\ell,$

which is a contradiction. This shows Claim 3.6. ∎

Let $u$ be a vertex in $C$. Note that
$a_{xu}=\omega^{\prime}-1>\frac{\ell}{2}$, by Claim 3.5. Then there exists a
vertex $v$ in $R$, such that $a_{xv}+a_{xu}=\ell$. By Claims 3.5 and 3.6, we
have $a_{xv}=k-\omega^{\prime}-1$. Hence, $\ell=k-2$. This finishes the proof
of Theorem 3.4. ∎

##  4 Main results

###  4.1 Strongly co-edge-regular graphs with large $\ell$

In this subsection, we show that a walk-regular and strongly co-edge-regular
graph with parameters $(n,k,2,\ell)$ is a $p\times q$-grid, where $p+q=k+2$ or
the $2$-clique extension of pentagon, if $\ell\geqslant\frac{3}{4}k$.
Moreover, we show that there does not exist a strongly co-edge-regular graph
with parameters $(n,k,2,\ell)$ and smallest eigenvalue at least $-3$,
satisfying $k\geqslant 120$ and $\ell<\frac{3}{4}k$.

First we consider the case where $G$ is a walk-regular and strongly co-edge-
regular graph with $\ell=k-2$.

######  Theorem 4.1.

Let $G$ be a walk-regular and strongly co-edge-regular graph with parameters
$(n,k$, $2,k-2)$. If $G$ contains an induced quadrangle, then $G$ is
isomorphic to the Shrikhande graph or a $p\times q$-grid, where $p+q=k+2$.

######  Proof.

Let $G$ be a walk-regular and strongly co-edge-regular graph with parameters
$(n,k,c,\ell)$, such that $\ell=k-2$ and $c=2$. Assume that $G$ contains an
induced quadrangle, say $x\sim u\sim y\sim v\sim x$. Assume further, the
number of common neighbours of $x,u$ and $x,v$ satisfy $s=a_{xu}\geqslant
a_{xv}=t$. As $c=2$, we have $N_{G}(x,u)\cap N_{G}(x,v)=\emptyset$ and
$s+t=a_{xu}+a_{xv}=\ell=k-2$. Note that $a_{yu}=\ell-a_{xu}=\ell-s=t$ and
$a_{yv}=\ell-a_{xv}=\ell-t=s$.

######  Claim 4.2.

The number $a_{xw}\in\\{s,t\\}$ for any $w\in N_{G}(x)$.

Proof of Claim 4.2. Let $w_{1}$ be a vertex in $N_{G}(x)-\\{u,v\\}$. By
$a_{xu}+a_{xv}=\ell=k-2$, we have $w_{1}$ is adjacent to $u$ or $v$. Without
loss of generality, we may assume $w_{1}\sim u$. As $c=2$, we have
$w_{1}\not\sim y$. Then there exists a vertex $w_{2}\in
N_{G}(w_{1},y)-\\{u\\}$. By $a_{yu}+a_{yv}=\ell=k-2$, we have $w_{2}$ is
adjacent to $u$ or $v$. Note that $w_{2}$ is not adjacent to $x$, as $c=2$. So
we find

$a_{xw_{1}}=\left\\{\begin{array}[]{rl}\ell-a_{xu}=t,&\text{if $w_{2}\sim
u$},\\\ \ell-a_{xv}=s,&\text{if $w_{2}\sim v$}.\end{array}\right.$

This shows the claim. ∎

Now we consider the following two cases.

Case 1. $s=t$.

In this case, by Lemma 3.2, we have $G$ is a strongly regular graph with
parameters $(n,k,\frac{k-2}{2},2)$. Then by Lemma 2.7, the three distinct
eigenvalues of $G$ are $k,\frac{k-2}{2}$ and $-2$. Hence, $G$ is isomorphic to
the Shrikhande graph or the $(s+2)\times(s+2)$-grid, by Lemma 2.9.

Case 2. $s>t$.

Let $w$ be a vertex in $N_{G}(x,v)$. By $c=2$, we obtain $w\not\sim u$ and $w$
has at most one neighbour in $N_{G}(x,u)$ for all $w\in N_{G}(x,v)$, and
similarly, for all $w^{\prime}\in N_{G}(x,u)$, we have $w^{\prime}\not\sim v$
and $w^{\prime}$ has at most one neighbour in $N_{G}(x,v)$. Then there exists
at least one vertex $z\in N_{G}(x,u)$ such that $z$ has no neighbours in
$N_{G}(x,v)$, as $a_{xu}=s>t=a_{xv}$. Note that $z\not\sim v$. There exists a
vertex $z_{1}$ such that $N_{G}(z,v)=\\{x,z_{1}\\}$. Note, $z_{1}$ is not
adjacent to $x$, as $z$ has no neighbour in $N_{G}(x,v)$. Hence, $a_{xz}=\ell-
a_{xv}=s$, which implies that $z$ is adjacent to all vertices in
$N_{G}(x,u)-\\{z\\}$. Therefore, any two distinct vertices in
$N_{G}(x,u)-\\{z\\}$ have at least three common neighbours, namely, $x,u,z$.
By $c=2$, we obtain that the subgraph induced on $\\{u\\}\cup N_{G}(x,u)$ is a
clique with valency $s$. It follows that there are no edges between
$N_{G}(x,u)$ and $N_{G}(x,v)$. We find $a_{xw}\leqslant
1+|N_{G}(x,v)-\\{w\\}|\leqslant a_{xv}=t$ for all $w\in N_{G}(x,v)$. By Claim
4.2, we have $a_{xw}=t$ for $w\in N_{G}(x,v)$. This shows that the subgraph
induced on $\\{v\\}\cup N_{G}(x,v)$ is a clique with valency $t$. Hence, the
local graph of $x$ in $G$ is isomorphic to $K_{s+1}\dot{\cup}K_{t+1}$.

Let $u^{\prime}$ (resp. $v^{\prime}$) be a vertex in $N_{G}(x,u)$ (resp.
$N_{G}(x,v)$), and $x,y^{\prime}$ be the common neighbours of
$u^{\prime},v^{\prime}$. Then the subgraph induced on
$\\{x,u^{\prime},y^{\prime},v^{\prime}\\}$ is a quadrangle. Hence, every
neighbour of $x$ lies on a quadrangle. It follows that every vertex in $G$
lies on a quadrangle. This shows that the local graph of any vertex of $G$ is
isomorphic to $K_{s+1}\dot{\cup}K_{t+1}$. This shows that $G$ is a
$(s+2)\times(t+2)$-grid.

This completes the proof of the theorem. ∎

######  Theorem 4.3.

There does not exist a strongly co-edge-regular graph with parameters
$(n,k,2,\ell)$ which contains an induced quadrangle and satisfies
$\frac{3k}{4}\leqslant\ell\leqslant k-3$.

######  Proof.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,c,\ell)$,
such that $\frac{3k}{4}\leqslant\ell=k-d$ and $c=2$, where
$\frac{k}{4}\geqslant d\geqslant 3$ is an integer. Assume that $G$ contains an
induced quadrangle, say $x\sim u\sim y\sim v\sim x$. Without loss of
generality, we may assume that $a_{xu}\geqslant a_{xv}$. Define

$\begin{array}[]{rl}U:=&N_{G}(x,u)\cup\\{u\\},\\\
V:=&N_{G}(x,v)\cup\\{v\\},\\\ W:=&N_{G}(x)-(U\cup V),\\\ Z:=&\cup_{w\in
W}N_{G}(w,y).\end{array}$

Note that $|W|=k-2-\ell=d-2$, as $\ell=k-d$. As $c=2$, the set $W\cap
N_{G}(y)$ is empty and every vertex in $W$ has two neighbours in $Z$.

######  Claim 4.4.

If $\ell>2(d-1)$, then for every $w\in W$, $a_{xw}=a_{xv}$ holds, and for all
$u^{\prime}\in U$ we have $w\not\sim u^{\prime}$.

Proof of Claim 4.4. Assume that $\ell>2(d-1)$. Note that, for $w\in W$, we
have $a_{xw}\leqslant k-(\ell+2)-1+2=d-1$, as $x,w,u$ (resp. $x,w,v$) have at
most one common neighbour. Then for $z\in Z$, the vertex $z$ has exactly one
neighbour in $W$ as $\ell>2(d-1)$. Hence, $|Z|=2|W|=2(d-2)$. Since $z\not\sim
x$ and $a_{xv}+a_{xw}\leqslant\frac{\ell}{2}+d-1<\ell$, we obtain $z\not\sim
v$ for $z\in Z$. As

$\begin{array}[]{rcl}k&=&|W|+2+a_{xu}+a_{xv}=|W|+2+a_{yu}+a_{yv},\\\
|Z|&=&2|W|=2(d-2)\end{array}$

and for all $z\in Z$ $z\not\sim v$, we find $|N_{G}(y,u)\cap Z|\geqslant d-2$.

For $w\in W$, the vertices $u$ and $w$ have at most one common neighbour in
$Z$, as $c=2$ and $x$ is a common neighbour of $u$ and $w$. Thus,
$|N_{G}(y,u)\cap Z|=|W|=d-2$ and $w,u$ have exactly one common neighbour in
$Z$ for $w\in W$. It follows that $a_{xw}=\ell-a_{xu}=a_{xv}$ for $w\in W$.
Moreover, the vertices $w$ and $u^{\prime}$ are non-adjacent for
$u^{\prime}\in U$ and $w\in W$. This finishes the proof of Claim 4.4. ∎

As $\ell\geqslant\frac{3k}{4}$ and $d\leqslant\frac{k}{4}$, we have
$\ell\geqslant 3d>2(d-1)$. Fix $w\in W$. Then $w$ and $v$ have at most one
neighbour in $V$, as $c=2$. This means that $a_{xv}=a_{xw}\leqslant|W|=d-2$,
by Claim 4.4. It follows that $a_{xu}=\ell-
a_{xv}\geqslant\ell-(d-2)>\frac{3k}{4}-\frac{k}{4}=\frac{k}{2}$. By Lemma 3.3,
the set $U^{\prime}=\\{u^{\prime}\sim x\mid a_{u^{\prime}x}=a_{ux}\\}$ is a
clique. In particular, $U^{\prime}\subseteq U$ holds. Let
$Z^{\prime}:=\\{z^{\prime}\neq x\mid z^{\prime}\not\sim x,z^{\prime}\sim
w\\}$. We find $|Z^{\prime}|\geqslant k-a_{xw}\geqslant k-d+2.$ As
$z^{\prime}\in Z^{\prime}$ has exactly one neighbour in $U^{\prime}$ and
$u^{\prime}\in U^{\prime}$ has at most one neighbour in $Z^{\prime}$, we find
that $|U|\geqslant|U^{\prime}|\geqslant|Z^{\prime}|\geqslant k-d+2.$ On the
other hand

$|U|\leqslant k-a_{xv}-1-|W|\leqslant k-1-d+2=k-d+1,$

which is a contradiction. This finishes the proof of the theorem. ∎

Note that Theorem 1.3 immediately follows from Lemma 2.12, Theorem 4.1 and
Theorem 4.3. Now we show that, if $G$ is a strongly co-edge-regular graph with
parameters $(n,k,2,\ell)$ and smallest eigenvalue at least $-3$, then $G$ is a
$t\times s$-grid or $k$ is small.

######  Theorem 4.5.

There is no strongly co-edge-regular graph with smallest eigenvalue
$\theta_{\min}$ and parameters $(n,k,2,\ell)$ satisfying
$\theta_{\min}\geqslant-3$, $k\geqslant 120$ and $\ell<\frac{3k}{4}$.

######  Proof.

Let $G$ be a strongly co-edge-regular graph with parameters $(n,k,2,\ell)$,
satisfying $k\geqslant 120$ and $\theta_{\min}\geqslant-3$. Let $x$ be a
vertex in $G$. Consider $\Delta(x)$, the local graph of $x$ in $G$. Let
$\\{z_{1},\ldots,z_{t}\\}$ be a maximum independent set in $\Delta(x)$. Define

$\begin{array}[]{rl}C_{i}:=&\\{w\mid w\sim x,\ w\sim z_{i},\ w\not\sim z_{j},\
j\neq i\\}\cup\\{z_{i}\\},\ i=1,\ldots,t,\\\
R:=&N_{G}(x)-\cup_{i=1}^{t}C_{i}.\end{array}$

Then $C_{i}$ forms a clique for $i=1,\ldots,t$, as $\\{z_{1},\ldots,z_{t}\\}$
is a maximum independent set. Let $c_{i}:=|C_{i}|$ for $i=1,\ldots,t$ and
$r=|R|$. Without loss of generality, we may assume
$c_{1}\geqslant\cdots\geqslant c_{t}$. Note that every vertex in $R$ has at
least two neighbours in $\\{z_{1},\ldots,z_{t}\\}$. Then
$r\leqslant\binom{t}{2}$, as $c=2$.

######  Claim 4.6.

There exists at most one edge between $C_{i}$ and $C_{j}$ for $1\leqslant
i\neq j\leqslant t$.

Proof of Claim 4.6. Note that every vertex in $C_{i}$ has at most one
neighbour in $C_{j}$ and vice versa, as $c=2$. Suppose there are two disjoint
edges between $C_{i}$ and $C_{j}$. Then $\Delta(x)$ contains an induced
quadrangle. This is impossible, as $c=2$. This shows Claim 4.6. ∎

######  Claim 4.7.

We have $t=3$.

Proof of Claim 4.7. First, we show that $t\leqslant 8$ holds. Let $v$ be a
vertex in $G$, such that $v\sim z_{1}$ and $v\not\sim x$. Then the subgraph of
$G$ induced on $\\{x,v,z_{1},\ldots,z_{t}\\}$ is bipartite. As
$\theta_{\min}\geqslant-3$, we obtain $t\leqslant 8$, by Lemma 2.5
($\mathrm{i}$). By Claim 4.6, there exist at least $c_{2}-1$ vertices in
$C_{2}$ which have no neighbours in $C_{1}$. Note that by Theorem 3.4, we have
$c_{1}\leqslant\frac{\ell+2}{2}<\frac{3k+8}{8}$, as $\ell<\frac{3k}{4}<k-2$.

Hence, we obtain

$\begin{array}[]{rl}c_{2}&\geqslant\frac{k-c_{1}-r}{t-1}\\\
&>\frac{5k-8-4t(t-1)}{8(t-1)}\\\ &\geqslant\frac{5\times
120-8-4t(t-1)}{8(t-1)}\\\ &\geqslant\left\\{\begin{array}[]{rl}6.5,&\text{if
}t=8,\\\ 8.8,&\text{if }t=7,\\\ 11.8,&\text{if }t=6,\\\ 16,&\text{if }t=5,\\\
22.6,&\text{if }t=4,\end{array}\right.\end{array}$ (1)

as $k\geqslant 120$.

Now we show that $t\leqslant 5$. Assume that $t\geqslant 6$. There exists at
most one edge between $C_{1}$ and $C_{2}$, by Claim 4.6. It follows that
$C(2K_{6}\dot{\cup}6K_{1})$, $C(2K_{8}\dot{\cup}5K_{1})$ or
$C(2K_{11}\dot{\cup}4K_{1})$ is a subgraph of $G$ induced on a subset of
$C_{1}\cup C_{2}\cup\\{x,z_{3},\ldots,z_{t}\\}$ for $t=8,7$ and $6$,
respectively. This is a contradiction, by Lemma 2.5 ($\mathrm{ii}$).

For $4\leqslant t\leqslant 5$, we have

$\begin{array}[]{rl}c_{3}&\geqslant\frac{k-c_{1}-c_{2}-r}{t-2}\\\
&>\frac{k-8-2t(t-1)}{4(t-2)}\\\ &\geqslant\frac{120-8-2t(t-1)}{4(t-2)}\\\
&=\left\\{\begin{array}[]{rl}6,&\text{if }t=5,\\\ 11,&\text{if
}t=4,\end{array}\right.\end{array}$ (2)

as $c_{2}\leqslant c_{1}<\frac{3k+8}{8}$ and $k\geqslant 120$.

There exists at most one edge between $C_{i}$ and $C_{j}$ for $1\leqslant
i\neq j\leqslant 3$, by Claim 4.6. It follows from (1) and (2) that

$\begin{array}[]{ll}c_{1}\geqslant c_{2}\geqslant 17\text{ and }c_{3}\geqslant
7,&\text{ if }t=5,\text{ and}\\\ c_{1}\geqslant c_{2}\geqslant 23\text{ and
}c_{3}\geqslant 12,&\text{ if }t=4.\end{array}$

This shows that $C(2K_{15}\dot{\cup}K_{7}\dot{\cup}2K_{1})$ or
$C(2K_{21}\dot{\cup}K_{12}\dot{\cup}K_{1})$ is an induced subgraph of $G$, and
this is a contradiction, by Lemma 2.5 ($\mathrm{iii}$). This finishes the
proof of Claim 4.7. ∎

######  Claim 4.8.

The local graph of $x$ in $G$, $\Delta(x)$, is isomorphic to
$3K_{\frac{k}{3}}$.

Proof of Claim 4.8. We have $N_{G}(x)=C_{1}\cup C_{2}\cup C_{3}\cup R$, by
Claim 4.7. Now we consider two cases, namely, $R=\emptyset$ and
$R\neq\emptyset$.

First, we assume that $R=\emptyset$. As $c=2$, we obtain
$\ell=a_{xz_{i}}+a_{xz_{j}}=(c_{i}-1)+(c_{j}-1)=c_{i}+c_{j}-2$ for $1\leqslant
i<j\leqslant 3$. Hence, $c_{1}=c_{2}=c_{3}=\frac{k}{3}$ and
$\ell=2\times\frac{k-3}{3}=\frac{2k-6}{3}$. Let $v$ be a vertex in
$\Delta(x)$. Then $a_{xv}\geqslant\frac{k-3}{3}$. By Claim 4.6, we have
$a_{xv}\leqslant(c_{1}-1)+2=\frac{k+3}{3}<k-1$, as $k\geqslant 120$. This
means $v$ has a neighbour $z$ outside $\\{x\\}\cup N_{G}(x)$.

Let $u,v$ be the two common neighbours of vertices $x$ and $z$. Then

$\frac{2k-6}{3}=\ell=a_{xu}+a_{xv}\geqslant\frac{k-3}{3}+\frac{k-3}{3}=\frac{2k-6}{3}.$

This means that $a_{xv}=\frac{k-3}{3}$, and there exist no edges between
$C_{i}$ and $C_{j}$ for $1\leqslant i,j\leqslant 3$. Therefore,
$\Delta(x)\cong 3K_{\frac{k}{3}}$.

Now assume that $R\neq\emptyset$. Let $w$ be a vertex in $R$. As $c=2$, note
that $w$ either has at most one neighbour in $C_{i}$ or is adjacent to all
vertices in $C_{i}$ for each $i=1,2,3$. By Theorem 3.4, we have
$c_{1}+c_{2}\leqslant\frac{\ell+2}{2}+\frac{\ell+2}{2}=\ell+2$. Then

$c_{3}=k-(c_{1}+c_{2}+r)\geqslant
k-(\ell+2+\binom{t}{2})>k-\frac{3k}{4}-5=\frac{k}{4}-5\geqslant 25,$

as $t=3$, $\ell<\frac{3k}{4}$ and $k\geqslant 120$. As there is at most one
edge between $C_{i}$ and $C_{j}$, we see that there exists clique
$C_{i}^{\prime}\subseteq C_{i}$ of order $c_{i}-1$ such that the induced
subgraph on $V(C_{1}^{\prime})\cup V(C_{2}^{\prime})\cup V(C_{3}^{\prime})$ is
$K_{c_{1}-1}\dot{\cup}K_{c_{2}-1}\dot{\cup}K_{c_{3}-1}$. Note
$c_{1}-1\geqslant c_{2}-1\geqslant c_{3}-1\geqslant 24$. If $w$ has at most
one neighbour in each $C_{i}$ for $i=1,2,3$, then we can find $3$ vertices
$w_{1}^{\prime}\in C_{1}^{\prime}$, $w_{2}^{\prime}\in C_{2}^{\prime}$ and
$w_{3}^{\prime}\in C_{3}^{\prime}$, such that $w_{i}^{\prime}\not\sim
w_{j}^{\prime}$ for $i\neq j$ and $w_{i}^{\prime}\not\sim w$ for all
$i=1,2,3$. So we are back to the case $t\geqslant 4$. If $w$ is adjacent to
all vertices of $C_{1}\dot{\cup}C_{2}\dot{\cup}C_{3}$, then we see that
$\Delta(x)$ contains an induced $C(3K_{5})$. This is a contradiction with
Lemma 2.5 ($\mathrm{iii}$). In similar fashion, we obtain that there exists an
induced $K_{13}\cup C(2K_{13})$ in $\Delta(x)$, if $w$ is adjacent to all
vertices of $C_{i}\dot{\cup}C_{j}$ for some $i,j$ satisfying $1\leqslant
i<j\leqslant 3$. Hence, $w$ is adjacent to all vertices of $C_{i}$ for exactly
one $i\in\\{1,2,3\\}$. Take $z_{i}^{\prime}\in C_{i}-\\{z_{i}\\}$ such that
$z_{i}^{\prime}$ has no neighbours in $C_{j}$ for $i,j\in\\{1,2,3\\}$ such
that $i\neq j$. Then each vertex in
$\Delta(x)-\\{z_{1}^{\prime},z_{2}^{\prime},z_{3}^{\prime}\\}$ has exactly one
of $\\{z_{1}^{\prime},z_{2}^{\prime},z_{3}^{\prime}\\}$ as its neighbour.
Hence, we are back to the case $R=\emptyset$. This finishes the proof of Claim
4.8. ∎

Since $\Delta(x)\cong 3K_{\frac{k}{3}}$ for $x\in V(G)$, we obtain that $G$ is
strongly regular with parameters $(\frac{k^{2}+3k+3}{3}$,
$k,\frac{k-3}{3},2)$. Assume $G$ has eigenvalues $k>\theta>\tau$ with
respective multiplicities $1,m_{\theta},m_{\tau}$. By Lemma 2.7, we have

$m_{\tau}-m_{\theta}=\frac{2k+(\frac{k^{2}+3k+3}{3}-1)(\frac{k-3}{3}-2)}{\sqrt{(\frac{k-3}{3}-2)^{2}+4(k-2)}}.$

Note that $m_{\tau}-m_{\theta}$ is an integer, as $k\geqslant 120$. It follows
that $(\frac{k-3}{3}-2)^{2}+4(k-2)=\frac{k^{2}+18k+9}{9}$ must be a perfect
square. This implies $k=0$, which is a contradiction.

This finishes the proof of Theorem 4.5. ∎

Now, we are ready to prove Theorem 1.4.

Proof of Theorem 1.4. Let $G$ be a walk-regular and strongly co-edge-regular
graph with parameters $(n,k,2,\ell)$, such that $k\geqslant 120$. Assume that
$\theta_{\min}\geqslant-3$. By Theorem 4.5 we see that no graph exists for
$l<\frac{3}{4}k$. For $l\geq\frac{3}{4}k$, G is a $p\times q$-grid, where
$p+q=k+2$ and $l=k-2$ by Theorem 1.3, as $k\geq 120$. This completes the proof
of this theorem.

###  4.2 Co-edge-regular graphs with four eigenvalues

In this subsection we study co-edge-regular graphs with four eigenvalues. We
start with the following lemma.

######  Lemma 4.9.

Let $G$ be a connected regular graph with $n$ vertices and valency $k$. If $G$
has exactly four distinct eigenvalues
$\\{\theta_{0}=k,\theta_{1},\theta_{2},\theta_{3}\\}$, then $G$ is walk-
regular. If moreover $G$ is co-edge-regular with parameters $(n,k,c)$, then
$G$ is strongly co-edge-regular with parameters $(n,k,c,\ell)$ where
$\ell=(\sum\limits_{i=1}^{3}\theta_{i})c+\frac{\prod_{i=1}^{3}(k-\theta_{i})}{n}-(k-c)c.$

######  Proof.

Let $G$ be a connected regular graph with $n$ vertices and valency $k$ having
exactly four distinct eigenvalues
$\\{\theta_{0}=k,\theta_{1},\theta_{2},\theta_{3}\\}$. Then the adjacency
matrix $A$ of $G$ satisfies the following equation (see [5]):

$\displaystyle A^{3}-(\sum\limits_{i=1}^{3}\theta_{i})A^{2}+(\sum_{1\leq
i<j\leq
3}\theta_{i}\theta_{j})A-\theta_{1}\theta_{2}\theta_{3}I=\frac{\prod_{i=1}^{3}(k-\theta_{i})}{n}J.$
(3)

This implies that $G$ is walk-regular, as was shown by Van Dam [11]. Now
assume that $G$ is also co-edge-regular with parameters $(n,k,c)$. Let $x,y$
be two vertices at distance 2. Then Equation (3) gives us

$(A^{3})_{xy}=(\sum\limits_{i=1}^{3}\theta_{i})c+\frac{\prod_{i=1}^{3}(k-\theta_{i})}{n}.$

This implies

$\sum_{z}a_{xz}+(k-c)c=(\sum\limits_{i=1}^{3}\theta_{i})c+\frac{\prod_{i=1}^{3}(k-\theta_{i})}{n},$

where the first sum is taken over all common neighbours $z$ of $x$ and $y$. It
follows that $G$ is strongly co-edge-regular with parameters $(n,k,c,\ell)$
where
$\ell=(\sum\limits_{i=1}^{3}\theta_{i})c+\frac{\prod_{i=1}^{3}(k-\theta_{i})}{n}-(k-c)c.$
This shows the lemma. ∎

As an immediate consequence of Theorems 1.3 and 1.4 and Lemma 4.9, we obtain
Theorem 1.2.

## Acknowledgments

We would like to thank the referees for their detailed comments. Their
comments significantly improved the paper.

Brhane Gebremichel is supported by a Chinese Scholarship Council at University
of Science and Technology of China.

We greatly thank professor Min Xu supporting M.-Y. Cao to visit University of
Science and Technology of China.

J.H. Koolen is partially supported by the National Natural Science Foundation
of China (No. 12071454), Anhui Initiative in Quantum Information Technologies
(No. AHY150000), and the project ”Analysis and Geometry on Bundles” of
Ministry of Science and Technology of the People’s Republic of China.

## References

  * [1] A. E. Brouwer, A. M. Cohen, and A. Neumaier.  Distance-Regular Graphs.  Springer-Verlag, Berlin Heidelberg, 1989.
  * [2] A. E. Brouwer and W. H. Haemers.  Spectra of Graphs.  Springer, New York, 2012.
  * [3] C. Godsil and G. Royle.  Algebraic Graph Theory.  Springer-Verlag, Berlin, 2001.
  * [4] S. Hayat, J. H. Koolen, and M. Riaz.  A spectral characterization of the s-clique extension of the square grid graphs.  European J. Combin., 76:104–116, 2019.
  * [5] A. J. Hoffman.  On the polynomial of a graph.  Amer. Math. Monthly, 70:30–36, 1963.
  * [6] X. Huang and Q. Huang.  On regular graphs with four distinct eigenvalues.  Linear Algebra Appl., 512:219–233, 2017.
  * [7] J. H. Koolen and J. Park.  Distance-regular graphs with $a_{1}$ or $c_{2}$ at least half the valency.  J. Combin. Theory Ser. A, 119(3):546–555, 2012.
  * [8] A. Neumaier.  Strongly regular graphs with smallest eigenvalue $-m$.  Arch. Math., 33:392–400, 1979.
  * [9] Y.-Y. Tan, J. H. Koolen, and Z.-J. Xia.  A spectral characterization of the $s$-clique extension of the triangular graphs.  Discuss. Math. Graph Theory, 40:663–676, 2020.
  * [10] P. Terwilliger.  Algebraic graph theory, lecture notes, unpublished.  https://icu-hsuzuki.github.io/lecturenote/, visited: 12-5-2021.
  * [11] E. R. van Dam.  Regular graphs with four eigenvalues.  Linear Algebra Appl., 226-228:139–162, 1995.
  * [12] E. R. van Dam.  Three-class association schemes.  J. Algebraic Combin., 10:69–107, 1999.
  * [13] E. R. van Dam and E. Spence.  Small regular graphs with four eigenvalues.  Discrete Math., 189(1–3):233–257, 1998.
  * [14] J. H. van Lint and A. E. Brouwer.  Strongly regular graphs and partial geometries.  D. M. Jackson, S. A. Vanstone (Eds.), Enumeration and Design, Academic Press Inc., pages 85–122, 1984.


# Minimum directed information:
A design principle for compliant robots

Kevin Haninger Corresponding email<EMAIL_ADDRESS>Author
affiliated with the Fraunhofer Institut für Produktionsanlagen und
Konstruktionstechnik (IPK).

###### Abstract

A robot’s dynamics – especially the degree and location of compliance – can
significantly affect performance and control complexity. Passive dynamics can
be designed with good regions of attraction or limit cycles for a specific
task, but achieving flexibility on a range of tasks requires co-design of
control. This paper takes an information perspective: the robot dynamics
should reduce the amount of information required for a controller to achieve a
threshold of performance in a range of tasks. Towards this goal, an iterative
method is proposed to minimize the directed information from state to control
on discrete-time nonlinear systems. iLQG is used to find a controller and
value of information, then the design parameters of the dynamics (e.g.
stiffness of end-effector or joint) are optimized to reduce directed
information while maintaining a minimum bound on performance. The approach is
validated in simulation, on a two-mass system in contact with an uncertain
wall position and a high-DOF door opening task, and shown to improve noise
robustness and reduce time variance of control gains.

##  1 Introduction

Robotic tasks in semi-structured environments, such as contact-rich
manipulation and human-robot interaction, are partially observed and the robot
must respond appropriately to the current environment state. In physical
tasks, this can be realized with intrinsic dynamics or active control, and the
environment state either directly affects the robot dynamics, or is inferred
and informs the control policy.

Such tasks are often viewed from the impedance control framework [1], where
the desired response to external forces or velocities is explicitly designed
and realized through control. To adapt to a new task, the impedance can be
changed by optimizing the impedance control parameters [2, 3, 4], or impedance
control can be used with other higher-level control, where it can improve
reinforcement learning efficiency [5] and robustness [6]. However, the
rendered impedance depends heavily on the intrinsic robot dynamics (e.g.
stiffness of end-effector/joints, reflected motor inertia), especially in
dynamic events like collision, which have frequency content beyond the control
bandwidth [7].

So what design objectives should be applied to the intrinsic robot dynamics?
Often, a low impedance is desired, which is a design goal in haptic devices
[8], human-robot interaction [9], soft robotics [10], and soft actuators [11].
However, reducing the intrinsic impedance comes with design trade-offs.
Classically, a lower stiffness reduces motion control bandwidth and accuracy
[12]. The modelling and motion control of soft robots remains challenging,
even with data-driven approaches [13]. Additionally, compliance reduces the
proprioceptive information flow - the ability to infer environment state or
contact dynamics from robot position and force signals: intrinsic stiffness
affects torque sensing accuracy [14] and the ability to infer contact
conditions [15].

A possible solution to this trade-off is variable impedance actuators, which
can adapt their physical dynamics, e.g. the DLR David [16], but they currently
present prohibitive cost and complexity.

The intrinsic dynamics (i.e. dynamics without control) are important, and for
certain tasks they are sufficient – passive devices are established for
locomotion [17] and peg-in-hole assembly [18]. These systems are classically
understood from a dynamics perspective; that their dynamics achieve stable
limit cycles and good convergence properties. However, as illustrated in
Figure 1, purely passive devices do not have the adaptability which defines
modern robotics.

An alternative approach to the design of intrinsic dynamics is morphological
computation [19], which use information theoretic metrics to characterize the
degree of influence between environment/robot [20], predictability [21],
empowerment of a system [22], or the influence of an external system [23].
While information-theoretic approaches can scale to more complex systems
described by data, they often do not include a sense of performance
(objective/cost/reward function), thus limiting their applicability to design.
The selection of minimal sensors to meet performance requirements has been
considered on networked control systems [24], but not the co-design of
dynamics and sensing.

Figure 1: Range of capabilities of different hardware systems, and the degree
to which their capabilities arise from passive dynamics or active control.

This paper adopts an information-limited control approach, and proposes that
good intrinsic dynamics reduce the amount of information required by the
controller to achieve a certain performance in a range of tasks. In the
limiting case of no online information required, the system is informationally
passive, and can be operated open-loop (i.e. pure trajectory planning) [25,
26]. We propose that if only a small amount of information is required for
control, suitable controllers may tolerate noise better or be more easily
found by exploration.

Existing results on linear systems are illustrative: the information rate
required for a controller to stabilize a discrete-time linear system is
$\sum\lambda_{i}^{+}$ bits/sample, where $\lambda^{+}_{i}$ are the unstable
eigenvalues where $|\lambda_{i}|>1$ – the more unstable, the more information
required [27]. Recent results have provided bounds on information rates
required for linear time-varying systems with quadratic costs (i.e. LQG
systems) [26]. These rates are measured with directed information [25], also
known as transfer entropy [23], which has also been used to find bounds on the
bits/sample required for control [28].

Here, an iterative method is proposed for finding intrinsic dynamic parameters
which reduce the required directed information, as seen in Figure 2. About an
initial trajectory, iLQG is used to find control, nominal performance, and the
value of information [29, 30]. Parameters of the intrinsic dynamics are then
updated to reduce the directed information while maintaining a bound on
performance. The approach is validated in simulation, a two-mass system which
makes contact with an uncertain environment position and a high-DOF door
opening task, and shown to reduce sensitivity to environment noise.

Figure 2: Proposed algorithm for minimizing directed information while
maintaining a performance bound $D$. The result is optimized dynamics
parameters $\phi$, such as end-effector or joint stiffness, link geometry, or
center of compliance.

###  1.1 Notation

Denote a matrix determinant $|\cdot|$ and transpose $\cdot^{\prime}$. Time
series are denoted $y^{t}=[y_{0},\dots,y_{t}]$. A random variable is typeset
$\mathrm{y}$ which takes values/samples $y$. Expectation is denoted
$\mathbb{E}$, independence with $\perp$, and
$\mathrm{y}\sim\mathcal{N}(\mu,\Sigma)$ denotes that $\mathrm{y}$ is
distributed normally with mean $\mu$, covariance $\Sigma$.

##  2 Information and Performance

###  2.1 Directed Information

Denote robot design variables as $\phi\in\Phi$, which may affect dynamics
and/or sensing (e.g. end-effector compliance, joint stiffness, geometry of
linkages). Let the robot and environment state at time step $t$ be
$x_{t}\in\mathbb{R}^{n}$ with control input $u_{t}\in\mathbb{R}^{m}$. The
directional influence of the state trajectory distribution of length $T$,
$\mathrm{x}^{T}$, on control trajectory $\mathrm{u}^{T}$ can be characterized
by directed information [25]

$\displaystyle\mathrm{DI}(\mathrm{x}^{T}\rightarrow\mathrm{u}^{T})\triangleq\sum_{t=0}^{T}\mathrm{I}\left(\mathrm{x}^{t};\mathrm{u}_{t}|\mathrm{u}^{t-1}\right),$
(1)

where conditional mutual information is

$\mathrm{I}(\mathrm{x}^{t};\mathrm{u}_{t}|\mathrm{u}^{t\mathtt{-}1})\triangleq\\\
\int
p(x^{t},u^{t})\log\frac{p\left(x^{t},u_{t}|u^{t\mathtt{-}1}\right)}{p\left(x^{t}|u^{t\mathtt{-}1}\right)p\left(u_{t}|u^{t\mathtt{-}1}\right)}dx^{t}u^{t}.$
(2)

As mutual information is non-negative and zero when the arguments are
independent, $\mathrm{DI}(\mathrm{x}^{T}\rightarrow\mathrm{u}^{T})$ is zero if
and only if $\mathrm{u}_{t}$ is independent of $\mathrm{x}^{t}$, conditioned
on $\mathrm{u}^{t-1}$, for all time. This occurs, for example, when there is
no feedback and the system is operating in open-loop [25]. Reducing (1) means
the control input is (in summation) more weakly related with the state. We
propose that if acceptable performance can be reached with lower (1), the
control is simpler: more controller noise can be tolerated, and the state need
not be so accurately estimated.

###  2.2 Dynamics and Performance

To formalize performance, consider the nonlinear coupled robot/environment
dynamics as

$\displaystyle\mathrm{x}_{t+1}$
$\displaystyle=f\left(\mathrm{x}_{t},\mathrm{u}_{t}\right)+\mathrm{w}_{t}$ (3)
$\displaystyle\mathrm{y}_{t}$
$\displaystyle=g\left(\mathrm{x}_{t}\right)+\mathrm{v}_{t}$

where process and measurement noise are independently distributed as
$\mathrm{w}_{t}\sim\mathcal{N}(0,W_{t})$,
$\mathrm{v}_{t}\sim\mathcal{N}(0,V_{t})$, and the initial state as
$\mathrm{x}_{0}\sim\mathcal{N}(0,X_{0})$.

Take a performance metric and objective of

$\displaystyle J(\mathrm{x}^{T},\mathrm{u}^{T})$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}\ell_{t}(\mathrm{x}_{t},\mathrm{u}_{t})+\ell_{T}(\mathrm{x}_{T})\right]$
(4) $\displaystyle J(\mathrm{x}^{T},\mathrm{u}^{T})$ $\displaystyle\leq D,$
(5)

respectively, for some given performance threshold $D$. The bound (5) captures
that many robotic task outcomes are binary – success/failure – and the
performance need not be optimal but rather meet some threshold for success.

###  2.3 Problem Statement

Note that $\mathrm{DI}(x^{T}\rightarrow u^{T})$ depends on the control policy,
which may not be known at design time. By Theorem 5 of [31], when
$\mathrm{v}_{t}\perp\mathrm{w}_{t}$ and
$(\mathrm{v}_{t},\mathrm{w}_{t})\perp\mathrm{x}_{0}$, and the control policy
$\pi$ is deterministic given past observations $u_{t}=\pi(y^{t})$,

$\displaystyle\mathrm{DI}(\mathrm{x}^{T}\rightarrow\mathrm{u}^{T})\leq\mathrm{DI}(\mathrm{x}^{T}\rightarrow\mathrm{y}^{T}).$
(6)

$\mathrm{DI}(\mathrm{x}^{T}\rightarrow\mathrm{y}^{T})$ can be evaluated from
dynamics and observation models alone, and will thus be used here. When the
control policy is not deterministic, e.g. for exploration in reinforcement
learning, additive control noise can considered with system noise
$\mathrm{w}_{t}$.

Let $J^{i}$ denote a performance metric of task $i$ and $D^{i}$ the
corresponding minimum required performance which must be met by a control
policy $u_{t}=\pi^{i}(y^{t})$. Then

$\displaystyle\phi=$
$\displaystyle\arg\min_{\phi\in\Phi}\mathrm{DI}_{\phi}(\mathrm{x}^{T}\rightarrow\mathrm{y}^{T})$
(7)
$\displaystyle\,\,\mathrm{s.t.}\,\,\exists\pi^{i},\,\,J^{i}_{\phi}(\mathrm{x}^{T},\pi^{i}(\mathrm{y}^{T}))\leq
D^{i}\,\,\forall i\in I.$

When the cost function of a performance metric $\ell_{t}$ is quadratic in
state and dynamics are linear time-invariant (LTI) with Gaussian i.i.d. noise
(i.e. LQG), the minimum information rate required for the controller to meet
performance $D$ is $R\leq\mathrm{DI}(\mathrm{x}^{T}\rightarrow\mathrm{u}^{T})$
[32]; where $R$ is an average number of bits/sample provided to the
controller. Closed-form bounds on $R(D)$ have also been developed for LTI
systems [28].

For linear time-varying systems, the selection of ‘virtual sensor’ parameters
and noise covariance to solve (7) can be formulated as a semidefinite program
[26]. The problem at hand is slightly different – here, sensing is not freely
chosen, but determined by design parameters, and these design parameters may
also affect the dynamics. Furthermore; most problems of interest in robotics
are nonlinear. Thus, here (7) will be approached with gradients and barrier
functions, to be introduced in the following two sections.

##  3 Iterative Linearization

In the style of the iLQG algorithm [30], we consider approximations to (7)
based on local linearization about a previous trajectory. The iLQG is here
extended to the partially observed case (i.e. iLQG + EKF), which allows
approximation to the value of information.

Given a trajectory $x^{T},u^{T}$, consider state and control perturbations
$\delta_{x}^{T}$, $\delta_{u}^{T}$, which approximate dynamics (3) as

$\displaystyle\mathrm{x}_{t+1}$ $\displaystyle\approx
f(x_{t},u_{t})+A_{t}\delta_{x,t}+B_{t}\delta_{u,t}+\mathrm{w}_{t}$ (8)
$\displaystyle\mathrm{y}_{t}$ $\displaystyle\approx
g(x_{t})+C_{t}\delta_{x,t}+\mathrm{v}_{t}$

where $A_{t}=\frac{\partial f}{\partial x}$, $B_{t}=\frac{\partial f}{\partial
u}$, $C_{t}=\frac{\partial g}{\partial x}$ and all derivatives are evaluated
at $x_{t},u_{t}$.

###  3.1 Estimation and Directed Information

Considering the directed information of the trajectory deviations,
$\mathrm{DI}(\mathrm{\delta}_{x}^{T}\rightarrow\mathrm{y}^{T})$ can be written
largely following results for linear time-varying systems [26],

$\displaystyle\mathrm{I}(\mathrm{\delta}_{x}^{t};\mathrm{y}_{t}|\mathrm{y}^{t-1})$
$\displaystyle=\mathrm{H}(\mathrm{\delta}_{x}^{t}|\mathrm{y}^{t-1})-\mathrm{H}(\mathrm{\delta}_{x}^{t}|\mathrm{y}^{t})$
$\displaystyle=\mathrm{H}(\mathrm{\delta}_{x,t}|y^{t-1})-\mathrm{H}(\mathrm{\delta}_{x,t}|y^{t})$
(9)

with differential entropy $\mathrm{H}(\mathrm{x})\triangleq-\int p(x)\ln
p(x)dx$, where (9) follows from the chain rule of entropy, conditional
independence, and cancellation of terms [33].

Denoting belief $p(\delta_{x,t}|y^{t})=\mathcal{N}(\mu_{t},\Sigma_{t})$,
standard extended Kalman filter equations give

$\Sigma_{t+1}=((A_{t}\Sigma_{t}A_{t}^{\prime}+W_{t})^{-1}+C_{t+1}^{\prime}V_{t+1}^{-1}C_{t+1})^{-1}$
(10)

where $\Sigma_{0}=(X_{0}^{-1}+C_{0}^{\prime}V_{0}^{-1}C_{0})^{-1}$. The
directed information can then be written as [26]

$\displaystyle\mathrm{DI}(\mathrm{\delta}_{x}^{T}\rightarrow\mathrm{y}^{T})$
$\displaystyle=\sum_{t=0}^{T}\frac{1}{2}\log|A_{t}\Sigma_{t}A_{t}^{\prime}+W_{t}|-\frac{1}{2}\log|\Sigma_{t}|$
(11a)
$\displaystyle=\sum_{t=0}^{T}\frac{1}{2}\log|\Sigma_{t}^{\texttt{-}1}+A_{t}^{\prime}W_{t}^{\texttt{-}1}A_{t}|-\frac{1}{2}\log|W_{t}|.$
(11b)

###  3.2 Partially Observed iLQG

To consider the performance constraint in (7), we extend the iLQG derivation
in [30] with additive noise and partial observations according to (8). Recall
optimal cost to go,

$\displaystyle
J_{t}^{*}\left(\mathrm{x}_{t}\right)=\min_{u_{t}}\mathbb{E}\left[\ell_{t}\left(\mathrm{x}_{t},u_{t}\right)+J_{t+1}^{*}\left(\mathrm{x}_{t+1}\right)|\mathrm{y}^{t}\right]$
(12)

where $J_{T}^{*}(\mathrm{x}_{T})=\mathbb{E}\,\ell_{T}(\mathrm{x}_{T})$.
Approximating the argument of (12) about perturbed state and input of
$\tilde{\mathrm{x}}_{t}=\mathrm{x}_{t}+\delta_{x,t}$,
$\tilde{u}=u_{t}+\delta_{u,t}$ and supressing subscript $t$ where unambiguous:

$\displaystyle\ell_{t}\left(\tilde{\mathrm{x}},\tilde{u}\right)$
$\displaystyle\approx\ell_{t}\left(\mathrm{x},u\right)\texttt{+}\ell_{x}\delta_{x}\texttt{+}\ell_{u}\delta_{u}\texttt{+}\delta_{x}^{{}^{\prime}}\ell_{xu}\delta_{u}\texttt{+}\frac{1}{2}\delta_{x}^{{}^{\prime}}\ell_{xx}\delta_{x}$
$\displaystyle J_{t+1}^{*}\left(\mathrm{x}_{t+1}\right)$ $\displaystyle\approx
J_{t+1}^{*}\left(f\left(\mathrm{x}_{t},u_{t}\right)\right)+\mathbb{E}\left[J_{x}^{+}\delta_{x+}+\frac{1}{2}\delta_{x+}^{{}^{\prime}}J_{xx}^{+}\delta_{x+}\right]$

where $\delta_{x+}=A_{t}\delta_{x,t}+B_{t}\delta_{u,t}+\mathrm{w}_{t}$,
$J_{x}^{+}=\frac{dJ_{t+1}^{*}}{d\mathrm{x}_{t+1}}$,
$J_{xx}^{+}=\frac{d^{2}J_{t+1}^{*}}{d\mathrm{x}^{2}_{t+1}}$, and
$\ell_{x}=\frac{\partial\ell_{t}}{\partial x_{t}}$. This then gives a change
in the argument to (12) of

$\approx\mathbb{E}\left[Q_{x}\delta_{x}+Q_{u}\delta_{u}+\frac{1}{2}\delta_{x}^{\prime}Q_{xx}\delta_{x}+\right.\\\
\left.\delta_{x}^{\prime}Q_{ux}^{\prime}\delta_{u}+\frac{1}{2}\delta_{u}^{\prime}Q_{uu}\delta_{u}|\mathrm{y}^{t}\right]+\frac{1}{2}\mathrm{Tr}(J_{xx}^{+}W_{t})$
(13)

where $Q_{x}=\ell_{x}+J_{x}^{+}A_{t}$, $Q_{u}=\ell_{u}+J_{x}^{+}B_{t}$,
$Q_{xx}=\ell_{xx}+A^{\prime}_{t}J_{xx}^{+}A_{t}$,
$Q_{uu}=\ell_{uu}+B_{t}^{\prime}J_{xx}^{+}B_{t}$,
$Q_{ux}=\ell_{ux}+B^{\prime}_{t}J_{xx}^{+}A_{t}$.

If $p(\delta_{x}|\mathrm{y}^{t})=\mathcal{N}(\mu_{t},\Sigma_{t})$, (13) is
minimized by

$\delta u^{*}=-Q_{uu}^{-1}\left(Q_{u}+Q_{ux}\mu_{t}\right)=k_{t}+K_{t}\mu_{t}$
(14)

which gives

$J_{t}^{*}\left(\tilde{x}_{t}\right)\approx\ell_{t}(x,u)+J_{t+1}^{*}(f(x_{t},u_{t}))+\Delta
J_{t}+J_{x}\mu_{t}+\mu_{t}^{\prime}J_{xx}\mu_{t}\\\
+\frac{1}{2}\mathrm{Tr}(\Xi_{t}\Sigma_{t})+\frac{1}{2}\mathrm{Tr}(J_{xx}^{+}W_{t})$
(15)

where $\Delta J_{t}=k^{\prime}Q_{uu}k+k^{\prime}Q_{uu}$,
$J_{x}=Q_{x}+K^{\prime}Q_{uu}k+K^{\prime}Q_{u}+Q_{ux}^{\prime}k$,
$J_{xx}=Q_{xx}+K^{\prime}Q_{uu}K+K^{\prime}Q_{ux}+Q_{ux}^{\prime}K$, and
$\Xi_{t}=Q_{xu}Q_{uu}^{-1}Q_{ux}$. Note that
$\Xi_{t}=K_{t}^{\prime}(\ell_{uu}+B_{t}^{\prime}J_{xx}^{+}B_{t})K_{t}$, and
$\mathrm{Tr}(\Xi_{t}\Sigma_{t})$ is the new cost introduced by belief
uncertainty (i.e. the value of information).

###  3.3 Differences with respect to fully-observed iLQG

In comparison the standard iLQG, there are two additional terms in (15)
arising from process noise covariance $W_{t}$ and belief uncertainty
$\Sigma_{t}$.

One important additional distinction is that the state is not known, so the
point to linearize the dynamics about is also uncertain. We adopt the
heuristic of maintaining a moving average for reference trajectories
$\overline{x}^{T}$ and $\overline{u}^{T}$. For a new trajectory, the maximum
likelihood state estimate $\mu^{T}$ is used as
$\overline{x}^{T}\leftarrow\alpha\mu^{T}+(1-\alpha)\overline{x}^{T}$ and
$\overline{u}^{T}\leftarrow\alpha u^{T}+(1-\alpha)\overline{u}^{T}$ for some
$\alpha\in[0,1]$.

Furthermore, the cost of an individual trajectory is not deterministic, making
the use of cost reduction to schedule regularization [30] or as a terminating
condition more difficult.

##  4 Optimizing information

To avoid higher-order tensors or vectorization, consider a single element of
the design parameters $\phi_{i}\in\mathbb{R}$ which affects both the
observations $g_{\phi}\left(x_{t}\right)$ and/or the dynamics
$f_{\phi}\left(x,u\right)$. Changing this parameter can affect the directed
information $\mathrm{DI}\left(\mathrm{x}^{T}\rightarrow\mathrm{y}^{T}\right)$,
the belief covariance $\Sigma_{t}$, and performance $J^{*}_{t}$. This section
optimizes (7) by gradient descent, including the constraint via barrier
methods.

###  4.1 Objective

Let precision matrix $\Gamma_{t}=\Sigma_{t}^{-1}$ and denote
$\nabla_{i}\Gamma_{t}=\frac{\partial\Gamma_{t}}{\partial\phi_{i}}$ ,
$\nabla_{i}A_{t}=\frac{\partial^{2}f}{\partial
x\partial\phi_{i}}|_{x_{t},u_{t}}$ and
$\nabla_{i}C_{t}=\frac{\partial^{2}f}{\partial
u\partial\phi_{i}}|_{x_{t},u_{t}}$. Calculating the gradient of the terms in
the objective in the form of (11a):

$\frac{\partial}{\partial\phi_{i}}\mathrm{DI}(\delta_{x}^{T}\rightarrow
y^{T})=\\\
\sum_{t=0}^{T}\frac{1}{2}\mathrm{Tr}\left(\left(A_{t}^{\prime}\Sigma_{t}A_{t}+W_{t}\right)^{-1}\Upsilon_{t,i}\right)+\frac{1}{2}\mathrm{Tr}\left(\nabla_{i}\Gamma_{t}\Sigma_{t}\right)$
(16)

where
$\Upsilon_{t,i}=\nabla_{i}A_{t}^{\prime}\Sigma_{t}A_{t}+A_{t}^{\prime}\Sigma_{t}\nabla_{i}\Gamma_{t}\Sigma_{t}A_{t}+A_{t}^{\prime}\Sigma_{t}\nabla_{i}A_{t}$.

This is found by standard matrix relations [34], including
$\frac{d\Sigma_{t}}{d\phi_{i}}=\Sigma_{t}\nabla_{i}\Gamma_{t}\Sigma_{t}$.
Calculating the gradient via (11b) was found to be less numerically stable.

$\nabla_{i}\Gamma_{t}$ can be calculated recursively as

$\nabla_{i}\Gamma_{t+1}=N_{0}-N_{1}+N^{\prime}\nabla_{i}\Gamma_{t}N$ (17)

where
$N_{0}=\nabla_{i}C_{t}^{\prime}V_{t}^{-1}C_{t}+C_{t}^{\prime}V_{t}^{-1}\nabla_{i}C_{t}$,
$N_{1}=\Psi_{t}\left(\nabla_{i}A_{t}\Sigma_{t}A_{t}^{\prime}+A_{t}\Sigma_{t}\nabla_{i}A_{t}^{\prime}\right)\Psi_{t}$,
$N=\Psi_{t}A_{t}\Sigma_{t}$, and
$\Psi_{t}=\left(A_{t}\Sigma_{t}A_{t}^{\prime}+W_{t}\right)^{-1}$. Recursive
expressions such as (17) may not be stable. For a simplified stability
analysis, consider time-invariant system matrices and derivatives, where a
sufficient condition for the convergence of the sequence, i.e.
$\nabla\Gamma_{t+1}=\nabla\Gamma_{t}$, is if all eigenvalues of $N$ are stable
$|\lambda_{j}(N)|<1\forall j$, arising from the existence condition for the
discrete-time Lyapunov equation [35].

###  4.2 Performance constraint

The performance constraint can then be incorporated by barrier methods, where

$\displaystyle\phi^{*}=\arg\min$
$\displaystyle\,\,\mathrm{DI}\left(\phi\right)\,\,\mathrm{s.t.}\,\,J_{0}^{*}(\phi)\leq
D$ $\displaystyle\approx\arg\min$
$\displaystyle\,\,\mathrm{DI}\left(\phi\right)-\beta\log\left(D-J_{0}^{*}(\phi)\right)$

where $\beta>0$ is a scalar weight for the barrier penalty. The gradient of
the barrier can be found as

$\displaystyle\frac{\partial}{\partial\phi_{i}}\left[-\beta\log\left(D-J_{0}^{*}\right)\right]$
$\displaystyle=-\frac{\beta}{D-J_{0}^{*}}\frac{\partial
J_{0}^{*}}{\partial\phi_{i}}.$

We simplify by considering only the impact of $\phi$ on belief covariance
$\Sigma_{t}$, leaving the impact of $\phi$ on dynamics to be handled with the
control optimization in the iLQR, giving

$\displaystyle\frac{\partial J_{0}^{*}}{\partial\phi_{i}}$
$\displaystyle\approx\sum_{t=1}^{T}\mathrm{Tr}\left(\Xi_{t}\Sigma_{t}\frac{d\Gamma_{t}}{d\phi_{i}}\Sigma_{t}\right)$
(18)

Recall $\Xi_{t}$ is the value of information from (15).

###  4.3 Gradient Descent

Simple gradient descent is used to update $\phi$ as

$\displaystyle\phi$
$\displaystyle\leftarrow\phi+h\left(\frac{\partial}{\partial\phi}\mathrm{DI}-\frac{\beta}{D-J_{0}^{*}}\frac{\partial
J_{0}^{*}}{\partial\phi}\right)$ (19) $\displaystyle h$
$\displaystyle=\mathrm{tanh}(D-J_{0}^{*}+\gamma)$ (20)

where gradients are given in (16) and (18), $J_{0}^{*}$ is taken from the iLQG
solution, small positive constant $\gamma$, and the step size $h$ reduces as
the cost barrier is approached.

##  5 Validation

To validate the approach, an implementation111Implementation available at
https://github.com/khaninger/info_min is built based on the DRAKE robotics
library [36]. Two example systems are tested: a two-mass system with rigid
contact, and a simplified door-opening task with a high-DOF robot. Optimizing
compliance is shown to improve noise robustness and reduce the time variance
in iLQR gains, which has been proposed as a metric for control complexity
[37].

(a)

(b)

Figure 3: In (a), a two mass system in contact (in free-space when
$x^{2}<x^{w}$, $K_{2}=0$). In (b), a door opening simulation, robot EE is
coupled with a diagonal stiffness to door handle.

(a)  Total cost and directed information (bits)

---
(b) Trace of optimization over DI (top) and total cost (bottom)

Figure 4: The parameter space and traces of the optimization

###  5.1 Two-mass with contact

A standard two-mass system is taken with inertia, damping, and stiffness of
$M_{i}$, $B_{i}$, and $K_{i}$ for $i=1,2$, and positions of $x^{1},x^{2}$. A
rigid wall is added at $\mathrm{x}^{w}$, where $\mathrm{x}^{w}\sim p(x^{w})$
varies between trajectory rollouts, but is fixed within the task. This system
emulates a flexible-joint robot with joint-torque sensing coming in contact
with a rigid environment of uncertain location. The stiffness $K_{1}$ is the
joint stiffness, and $K_{2}$ the effective stiffness of end-effector and
environment in series. The bounds $K_{1}\in[50,600]$ (N/m) and
$K_{2}\in[100,600]$ (N/m) will be applied, with fixed parameters
$M_{\cdot}=0.8,0.4$ Kg and $B_{\cdot}=60,35$ Ns/m, for 1, 2, respectively.

(a) iLQG result, $K_{1}=500N/m$, $K_{2}=500N/m$

(b) iLQG result, $K_{1}=123N/m$, $K_{2}=240N/m$

Figure 5: Plots of true state, mean and covariance of corresponding belief,
for initial and optimized gains. Uncertainty in the state estimate is
increased; but acceptable performance is maintained. Figure 6: iLQG total cost
(mean and covariance over 20 trajectories) as noise is increased in (top)
environment ($x_{w}$ position) and control (additive Gaussian noise). The
optimized stiffness has better noise robustness than the high-stiffness
system.

The measurements are position and force
$y_{t}=[x^{1};K_{1}(x^{2}-x^{1})]+v_{t}$ where
$v_{t}\sim\mathcal{N}(0,\mathtt{diag}(1e-3,1e-2)])$. The dynamics are
standard, with the caveat that when $x^{2}<x^{w}$, $K_{2}$ is effectively $0$.
Process noise has covariance
$W=\mathtt{diag}(1e\mathtt{-}7,5e\mathtt{-}3,1e\mathtt{-}7,1e\mathtt{-}2,0)$
and initial state covariance is $X0=10^{-3}\mathtt{diag}(1,1,1,1,0.1)$ with
state of $[x^{1},\dot{x}^{1},x^{2},\dot{x}^{2},x^{w}]$. The objective is to
achieve a small positive contact force $f^{o}$ with the environment (which is
a basic requirement for contact tasks),

$\ell_{t}=\|(K_{2}(x^{2}-x^{w})_{+})-f^{o}\|+0.1\|\dot{x}^{1}\|+0.1\|\dot{x}^{2}s\|+10^{-4}\|\tau_{m}\|$

where $(x)_{+}$ is $\frac{1}{2}(\sqrt{(}x^{2}+\gamma^{2})+x)$, the
differentiable approximation to $\max(0,x)$ from [30]. Here, $f_{0}=10$,
$\gamma=0.1$, and the barrier weight $\beta=1e4$.

(a) Low stiffness $k_{1:3}=[1,1,1]1e4$

(b) Optimized stiffness $k_{1:3}=[9.8,9.3,7.9]e5$

(c) High stiffness $k_{1:3}=[1,1,1]1e6$

Figure 7: Optimization of the stiffness coupling robot to door reduces the
temporal variability of the feedback gains compared with the stiff system,
reducing directed information by almost 1/3 with only a $6\%$ penalty in total
cost, relative to high-stiffness gains.

First, iLQG was performed over a grid of $K_{1}$ and $K_{2}$, and the directed
information of the converged controller estimated. The total cost and DI can
be seen in Figure 4a. The total cost decreases as $K_{1}$ or $K_{2}$
increases, and reducing $K_{1}$ reduces the directed information.

The stiffnesses $\phi={K_{1},K_{2}}$ can be optimized according to (19), where
a number of initial $\phi$ can be seen on contour plots of directed
information 4b and performance 4b, where $D=250$. The barrier method succeeds
in increasing $K_{2}$ from lower initial values, but the trajectories do not
converge to a single point as the barrier gradient is almost parallel to the
DI graddient. A trace of the system response with initial stiffnesses
$K_{1}=500$, $K_{2}=500$ can be compared with the optimized stiffneses
$K_{1}=123$, $K_{2}=240$ is shown in Figure 5a and 5b, respectively.

The noise robustness of several $\phi$ was compared: how the total cost of
iLQG varies as either (1) environment or (2) control noise increases, where
environment noise is the covariance of normally distributed $x_{w}$ and the
control noise is additive Gaussian. The high stiffness system is more
sensitive to all noise. The optimized gains show better environment noise
robustness, even compared with the low-stiffness system. However, the
optimized gains have slightly more control noise sensitivity than the low
stiffnesses. This suggests that optimizing to reduce required information
allows the system to better tolerate environment noise.

###  5.2 Manipulator opening door

To investigate the scalability of the algorithm, it is then applied to a
simulation of the KUKA iiwa manipulator in a door opening/closing task. The
robot and door handle are coupled via a diagonal stiffness matrix
$K_{e}=\mathtt{diag}[k_{1},k_{2},k_{3},k_{4},k_{5},k_{6}]$ to simulate the
compliance of a gripper. Torsional stiffnesses are fixed at $k_{4:6}=50$
Nm/rad, and linear stiffnesses $\phi=k_{1:3}$ are optimized. The robot
positions and velocities are observed, joint-space torque control is used, and
the cost function is

$\ell_{t}=\|\theta-\theta_{0}\|+0.05\|\dot{q}\|+0.1\|\tau_{m}\|$

where $\theta$ is the angle of the door, and $\dot{q}$, $\tau_{m}$ the joint
velocities and torque of the robot. This objective function aims to move the
door to the position $\theta_{0}$, while reducing the velocity and motor
torque along the way.

Due to space limitations, interested readers are referred to the public code
for parameter values used and the calculation of the required derivatives. A
very low-stiffness $k_{1:3}=[1,1,1]1e4$ (N/m) and high-stiffness
$k_{1:3}=[1,1,1]1e6$ coupling are compared with the optimized stiffnesses
where $k_{1:3}=[9.8,9.3,7.9]e5$. A video is available at
https://youtu.be/Mp5HAMRCdAg and the resulting state and control trajectories
are seen in Figure 7. The iLQR feedback gains and feedforward trajectory vary
more over time when the stiffness is higher, providing better performance from
higher directed information. The optimized gains respect the performance limit
of $D=300$ while reducing DI. Similar trends occur in a door closing task, as
seen in the attached video.

##  6 Conclusion

This paper proposed a new principle for the design of intrinsic dynamics: to
reduce the information required for control, operationalized by iLQG where
gradients of the linearized dynamics and value of information reduce the
directed information while maintaining performance. The feasibility and
stability of the algorithm was validated on a two-mass model; and a higher-DOF
example used to demonstrate the scalability. Optimizing compliance was shown
to reduce the time variation in control gains and the environment noise
sensitivity.

## Acknowledgements

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 820689 — SHERLOCK.
The author would also like to thank Raul Vicete-Garcia, Manuel Baum, and the
reviewers for conversations which contributed to the paper development.

## References

  * [1] Neville Hogan  “Impedance Control: An Approach to Manipulation”  In _American Control Conference, 1984_ IEEE, 1984, pp. 304–313  URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4788393
  * [2] Fotios Dimeas and Nikos Aspragathos  “Reinforcement Learning of Variable Admittance Control for Human-Robot Co-Manipulation”  In _Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference On_ IEEE, 2015, pp. 1011–1016
  * [3] Pietro Balatti et al.  “A Self-Tuning Impedance Controller for Autonomous Robotic Manipulation”  In _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 5885–5891  DOI: 10.1109/IROS.2018.8593860
  * [4] Jianlan Luo et al.  “Reinforcement Learning on Variable Impedance Controller for High-Precision Robotic Assembly”, 2019  arXiv:1903.01066
  * [5] Roberto Martín-Martín et al.  “Variable Impedance Control in End-Effector Space: An Action Space for Reinforcement Learning in Contact-Rich Tasks”, 2019  arXiv: http://arxiv.org/abs/1906.08880
  * [6] Miroslav Bogdanovic, Majid Khadiv and Ludovic Righetti  “Learning Variable Impedance Control for Contact Sensitive Tasks”, 2019  arXiv: http://arxiv.org/abs/1907.07500
  * [7] Sami Haddadin, Alin Albu-Schäffer, Oliver Eiberger and Gerd Hirzinger  “New Insights Concerning Intrinsic Joint Elasticity for Safety”  In _Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference On_ IEEE, 2010, pp. 2181–2187  URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5652037
  * [8] Thomas H. Massie and J. Salisbury  “The Phantom Haptic Interface: A Device for Probing Virtual Objects”  In _Proceedings of the ASME Winter Annual Meeting, Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems_ 55 Chicago, IL, 1994, pp. 295–300  URL: https://dac.etsii.urjc.es/docencia/RVA/06-07/Massie00_The%20PHANTOM%20Haptic%20Interface_A%20Device%20for%20Probing%20Virtual_building1.pdf
  * [9] Pascal D. Labrecque et al.  “uMan: A Low-Impedance Manipulator for Human–Robot Cooperation Based on Underactuated Redundancy”  In _IEEE/ASME Transactions on Mechatronics_ 22.3 IEEE, 2017, pp. 1401–1411
  * [10] A. Albu-Schaffer et al.  “Soft Robotics”  In _IEEE Robotics Automation Magazine_ 15.3, 2008, pp. 20–30  DOI: 10.1109/MRA.2008.927979
  * [11] G.A. Pratt and M.M. Williamson  “Series Elastic Actuators”  In _1995 IEEE/RSJ International Conference on Intelligent Robots and Systems 95. ’Human Robot Interaction and Cooperative Robots’, Proceedings_ 1, 1995, pp. 399–406 vol.1  DOI: 10.1109/IROS.1995.525827
  * [12] A. Bicchi and G. Tonietti  “Fast and ”Soft-Arm” Tactics”  In _IEEE Robotics & Automation Magazine_ 11.2, 2004, pp. 22–33  DOI: 10.1109/MRA.2004.1310939
  * [13] Thomas Beckers and Sandra Hirche  “Keep Soft Robots Soft – a Data-Driven Based Trade-off between Feed-Forward and Feedback Control”, 2019  arXiv: http://arxiv.org/abs/1906.10489
  * [14] N. Kashiri, J. Malzahn and N.. Tsagarakis  “On the Sensor Design of Torque Controlled Actuators: A Comparison Study of Strain Gauge and Encoder-Based Principles”  In _IEEE Robotics and Automation Letters_ 2.2, 2017, pp. 1186–1194  DOI: 10.1109/LRA.2017.2662744
  * [15] Kevin Haninger and Dragoljub Surdilovic  “Multimodal Environment Dynamics for Interactive Robots: Towards Fault Detection and Task Representation”  In _Proc. IEEE/RSJ Intl Conf on Intelligent Robots and Systems (IROS)_ , 2018, pp. 6932–6937
  * [16] Markus Grebenstein et al.  “The Hand of the DLR Hand Arm System: Designed for Interaction”  In _The International Journal of Robotics Research_ 31.13 SAGE Publications Sage UK: London, England, 2012, pp. 1531–1555
  * [17] Tad McGeer  “Passive Dynamic Walking”  In _I. J. Robotic Res._ 9.2 Citeseer, 1990, pp. 62–82
  * [18] Paul C. Watson  “Remote Center Compliance System”  Google Patents, 1978
  * [19] Vincent C. Müller and Matej Hoffmann  “What Is Morphological Computation? On How the Body Contributes to Cognition and Control”  In _Artificial Life_ 23.1 MIT Press, 2017, pp. 1–24  DOI: 10.1162/ARTL˙a˙00219
  * [20] Keyan Ghazi-Zahedi et al.  “Morphological Computation: The Good, the Bad, and the Ugly”  In _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ IEEE, 2017, pp. 464–469
  * [21] William Bialek, Ilya Nemenman and Naftali Tishby  “Predictability, Complexity and Learning”, 2001  arXiv: http://arxiv.org/abs/physics/0007070
  * [22] A.S. Klyubin, D. Polani and C.L. Nehaniv  “Empowerment: A Universal Agent-Centric Measure of Control”  In _2005 IEEE Congress on Evolutionary Computation_ 1, 2005, pp. 128–135 Vol.1  DOI: 10.1109/CEC.2005.1554676
  * [23] Paul L. Williams and Randall D. Beer  “Generalized Measures of Information Transfer”, 2011  arXiv: http://arxiv.org/abs/1102.1507
  * [24] Vasileios Tzoumas, Luca Carlone, George J. Pappas and Ali Jadbabaie  “LQG Control and Sensing Co-Design”  In _IEEE Transactions on Automatic Control_ , 2020, pp. 1–1  DOI: 10.1109/TAC.2020.2997661
  * [25] James Massey  “Causality, Feedback and Directed Information”  In _Proc. Int. Symp. Inf. Theory Applic.(ISITA-90)_ Citeseer, 1990, pp. 303–305
  * [26] Takashi Tanaka, Peyman Mohajerin Esfahani and Sanjoy K. Mitter  “LQG Control with Minimum Directed Information: Semidefinite Programming Approach”  In _IEEE Transactions on Automatic Control_ 63.1, 2017, pp. 37–52
  * [27] Sekhar Tatikonda and Sanjoy Mitter  “Control under Communication Constraints”  In _IEEE Transactions on automatic control_ 49.7 IEEE, 2004, pp. 1056–1068
  * [28] Victoria Kostina and Babak Hassibi  “Rate-Cost Tradeoffs in Control”  In _IEEE Transactions on Automatic Control_ 64.11 IEEE, 2019, pp. 4525–4540
  * [29] E. Todorov and Weiwei Li  “A Generalized Iterative LQG Method for Locally-Optimal Feedback Control of Constrained Nonlinear Stochastic Systems”  In _Proceedings of the 2005, American Control Conference, 2005._ , 2005, pp. 300–306 vol. 1  DOI: 10.1109/ACC.2005.1469949
  * [30] Y. Tassa, T. Erez and E. Todorov  “Synthesis and Stabilization of Complex Behaviors through Online Trajectory Optimization”  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2012, pp. 4906–4913  DOI: 10.1109/IROS.2012.6386025
  * [31] Milan S. Derpich, Eduardo I. Silva and Jan Østergaard  “Fundamental Inequalities and Identities Involving Mutual and Directed Informations in Closed-Loop Systems”, 2013  arXiv: http://arxiv.org/abs/1301.6427
  * [32] Takashi Tanaka et al.  “Rate of Prefix-Free Codes in LQG Control Systems”  In _2016 IEEE International Symposium on Information Theory (ISIT)_ IEEE, 2016, pp. 2399–2403
  * [33] Thomas M. Cover  “Elements of Information Theory”  John Wiley & Sons, 1999
  * [34] Kaare Brandt Petersen and Michael Syskind Pedersen  “The Matrix Cookbook”  In _Technical University of Denmark_ 7, 2008, pp. 15  URL: http://www.cim.mcgill.ca/~dudek/417/Papers/matrixOperations.pdf
  * [35] John M. Davis, Ian A. Gravagne, Robert J. Marks and Alice A. Ramos  “Algebraic and Dynamic Lyapunov Equations on Time Scales”  In _2010 42nd Southeastern Symposium on System Theory (SSST)_ IEEE, 2010, pp. 329–334
  * [36] R. Tedrake  “Drake: Model-Based Design and Verification for Robotics”, 2019
  * [37] Elmar A. Rückert and Gerhard Neumann  “Stochastic Optimal Control Methods for Investigating the Power of Morphological Computation”  In _Artificial Life_ 19.1 MIT Press, 2013, pp. 115–131