# On claw-free Toeplitz graphs††thanks: This work was supported by the
National Research Foundation of Korea (NRF) grant funded by the Korea
government (MSIP) (2016R1A5A1008055, NRF-2019R1A2C1007518, and
NRF-2017R1E1A1A03070489).

Gi-Sang Cheona,b, Bumtle Kanga, Suh-Ryung Kima,c, Seyed Ahmad Mojallald,
and Homoon Ryua,c
aApplied Algebra and Optimization Research Center, Sungkyunkwan University,
Suwon 16419, Rep. of Korea
bDepartment of Mathematics, Sungkyunkwan University, Suwon 16419, Rep. of
Korea
cDepartment of Mathematics Education, Seoul National University,
Seoul 08826, Rep. of Korea
dDepartment of Mathematics and Statistics, University of Regina, Regina,
Saskatchewan, S4S0A2, Canada

###### Abstract

This paper was initiated by the observation that chordal Toeplitz graphs
$T_{n}\langle t_{1},\ldots,t_{k}\rangle$ with $n>t_{k-1}+t_{k}$ are claw-free.
A Toeplitz graph with $n$ vertices is a simple graph whose adjacency matrix is
an $n\times n$ $(0,1)$-symmetric Toeplitz matrix with zero diagonal and a claw
in a graph means a star $K_{1,3}$ as an induced subgraph. We find an
interesting family of claw-free Toeplitz graphs so called ‘cocoonery’ and show
that if $n>t_{k-1}+t_{k}$, then this family becomes exactly the family of
claw-free Toeplitz graphs. We also completely characterize a claw-free
Toeplitz graph $T_{n}\langle t_{1},\ldots,t_{k}\rangle$ for $k=2$ and $k=3$.
We go further to study Toeplitz graphs which happen to be line graphs.

Key Words: Toeplitz graphs, Claw-free graphs, Line graphs, Cocoonery, Chordal
Graphs
2020 Mathematics Subject Classification: 05C75, 05C76

##  1 Introduction

An $n\times n$ matrix $T=(t_{i,j})_{1\leq i,j\leq n}$ is called a Toeplitz
matrix if $t_{i,j}=t_{i+1,j+1}$ for each $1\leq i,j\leq n-1$. Toeplitz
matrices are precisely those matrices that are constant along all diagonals
parallel to the main diagonal. Toeplitz matrices occur in a large variety of
areas in pure and applied mathematics, see [2, 8, 11] for example.

A simple graph is called a Toeplitz graph if its adjacency matrix is a
$(0,1)$-symmetric Toeplitz matrix with zero diagonal. Thus the first row of
the adjacency matrix determines a unique Toeplitz graph. In this vein, we
denote a Toeplitz graph with $n$ vertices by $T_{n}\langle
t_{1},\ldots,t_{k}\rangle$ if the $1$’s in the first row of its adjacency
matrix are placed at positions $1+t_{1}$, …, $1+t_{k}$ with $1\leq
t_{1}<\ldots<t_{k}<n$. In addition, we label the vertices of the Toeplitz
graph with $1,\ldots,n$ so that the $i$th row of its adjacency matrix
corresponds to the vertex labeled $i$. For the vertex set $V=\mathbb{N}$ and
$k<\infty$, infinite Toeplitz graphs $T_{\infty}\langle
t_{1},\ldots,t_{k}\rangle$ are defined as the same way. We simply mention that
both types may be studied as special subgraphs of integer distance graphs [1,
12, 13].

Toeplitz graphs have been first investigated with respect to hamiltonicity by
van Dal et al. in 1996. [19] (see also [9, 14, 15]). Since then some
properties of Toeplitz graphs have been studied by several authors. Indeed,
bipartite Toeplitz graphs have been fully characterized in terms of bases and
circuits by Euler et al. [3, 5]. Colouring aspects are especially treated in
[10, 13, 17]. Planar Toeplitz graphs have been also fully characterized by
Euler [4, 6] providing, in particular, a complete description of the class of
3-colourable such graphs. Very recently, Mojallal et al. [16] studied
structures of Toepolitz graphs and obtained the following interesting result.

A chordal graph is a simple graph with no chordless cycle of length at least
$4$ as an induced subgraph. A graph is an interval graph if it captures the
intersection relation for some set of intervals on the real line. A clique is
a complete subgraph or a subset of vertices of an undirected graph such that
every two distinct vertices in the clique are adjacent. The clique number
$\omega(G)$ of a graph $G$ is the maximum number of vertices among the cliques
of $G$.

######  Lemma 1.1 ([16]).

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$. If $n\geq t_{k-1}+t_{k}$, then
the following statements are equivalent.

  * (i)

$G$ is interval;

  * (ii)

$G$ is chordal;

  * (iii)

$t_{i}=it_{1}$ for all $i\in[k]$;

  * (iv)

$\omega(G)=k+1$.

By the way, a Toeplitz graph satisfying the condition (iii) of Lemma 1.1 has a
noteworthy structure described as follows.

######  Proposition 1.2 ([16]).

For positive integers $k,t$, let $G=T_{n}\langle t,2t,\ldots,kt\rangle$. Then
$G$ has $t$ components. In particular, if $H_{1},\ldots,H_{t}$ are the
components of $G$, then $H_{i}$ is isomorphic to the graph
$T_{\lfloor(n-i)/t\rfloor+1}\langle 1,2,\ldots,k\rangle$ and the vertex set of
$H_{i}$ is $\\{i+st\;|\;s=0,1,\ldots,\lfloor(n-i)/t\rfloor\\}$ for each
$i\in[t]$.

This proposition tells us that each component of $T_{n}\langle
t,2t,\ldots,kt\rangle$ is a lump of consecutive cliques of size $k+1$ sharing
$k$ vertices. Based on this observation, we call a Toeplitz graph
$T_{n}\langle t,2t,\ldots,kt\rangle$ an $(n,k,t)$-cocoonery. We say that a
graph is a cocoonery if it is an $(n,k,t)$-cocoonery for some positive
integers $n,k,t$ with $n>kt$.

$1$$6$$21$$11$$16$$26$$2$$7$$22$$12$$17$$27$$4$$9$$24$$14$$19$$29$$3$$8$$23$$13$$18$$28$$5$$10$$25$$15$$20$$30$
Figure 1: A cocoonery $T_{30}\langle 5,10,15\rangle$

A claw of a graph means the complete bipartite graph $K_{1,3}$ as an induced
subgraph. In this paper, we denote a $K_{1,3}$ with center $a$ and leaves
$b,c,d$ by $(a;b,c,d)$. By the definition of Toeplitz graph, if there is a
$K_{1,3}$ (resp. claw) $(a;b,c,d)$ in $T_{n}\langle
t_{1},\ldots,t_{k}\rangle$, then $((n+1)-a;(n+1)-b,(n+1)-c,(n+1)-d)$ is also a
$K_{1,3}$ (resp. claw). In this vein, we may consider only $K_{1,3}$
satisfying the following:

  * ($\star$)

at least two of $b,c,d$ are greater than $a$ for $(a;b,c,d)$.

In section 2, we show that a Toeplitz graph $T_{n}\langle
t_{1},\ldots,t_{k}\rangle$ being a cocoonery is logically equivalent to its
being claw-free if $n>t_{k-1}+t_{k}$. (Corollary 2.4 and Theorem 2.5) By doing
so, we are able to add one more equivalent statement to Lemma 1.1. (Theorem
2.6) Then we go ahead to give an equivalent condition for a Toeplitz graph
being claw-free in a more general case. (Theorem 2.8) In Section 3, we
characterize a claw-free Toeplitz graph $T_{n}\langle t_{1},t_{2}\rangle$
(Theorem 3.4) and a claw-free Toeplitz graph $T_{n}\langle
t_{1},t_{2},t_{3}\rangle$ (Theorem 3.5). We also classify claw-free Toeplitz
graphs $T_{n}\langle t_{1},t_{2},t_{3}\rangle$ which are not cocooneries
(Theorem 3.6).

A claw-free graph was initially studied as a generalization of the line graph
of a graph $H$, which represents the adjacencies between edges of $H$. More
precisely, the line graph $G$ of a graph $H$ has the edge set of $H$ as its
vertex set and two vertices are adjacent in $G$ if and only if their
corresponding edges are adjacent in $H$. In section 4, we show that there are
infinitely many Toeplitz graphs among line graphs by characterizing an
$(n,k,t)$-cocoonery that happens to be a line graph (Theorem 4.3). On the
other hand, we show that, for $n\geq 3$, a Toeplitz graph $G=T_{n}\langle
t_{1},\ldots,t_{k}\rangle$ with $n>t_{k}+t_{k-1}$ cannot be a line graph
(Corollary 4.5).

Throughout the paper, let $T_{n}\langle t_{1},\ldots,t_{k}\rangle$ be a
Toeplitz graph with $n$ vertices and let $[n]$ denote the $n$-set
$\\{1,\ldots,n\\}$. The complete graph, the cycle graph and the path graph
with $n$ vertices are denoted by $K_{n}$, $C_{n}$ and $P_{n}$, respectively.

##  2 Equivalence conditions for a Toeplitz graph being claw-free

The section begins with the following question:

######  Question 2.1.

Which Toeplitz graphs $T_{n}\langle t_{1},\ldots,t_{k}\rangle$ are claw-free?

Let $G$ be a Toeplitz graph with $n$ vertices. If $G=T_{n}\langle
t_{1}\rangle$ then $G$ is the union of paths by Proposition 1.2, which is
claw-free. Accordingly, we only consider Toeplitz graphs $T_{n}\langle
t_{1},\ldots,t_{k}\rangle$ for $k\geq 2$.

######  Lemma 2.2.

Let $B$ be a nonempty subset of positive integers which is bounded above and
is closed under difference of distinct elements. Then $B=\\{d,2d,\ldots,kd\\}$
for some positive integers $d$ and $k$.

###### Proof.

By the Well-Ordering Principle, there is a minimum element $d$ in $B$. Suppose
there is an element $a$ distinct from $d$ in $B$. Then $a=qd+r$ for some
integers $q$ and $r$, $0\leq r<d$. Now $a-d\in B$ by the hypothesis. Then
$(a-d)-d\in B$. We continue in this way to have $a-qd=r\in B$ unless $r=0$.
Thus, by the minimality of $d$, $r=0$. Thus every element in $B$ is a multiple
of $d$. Since $B$ is bounded above, there is a maximum element $b$ in $B$.
Then $b=kd$ for some positive integer $k$. Now $b-d=(k-1)d\in B$ by the
hypothesis. Then $(b-d)-d=(k-2)d\in B$. We continue in this way to have
$B=\\{d,2d,\ldots,kd\\}$. ∎

######  Theorem 2.3.

Suppose that $T_{n}\langle t_{1},\ldots,t_{k}\rangle$ is claw-free with
$n>t_{k}+t_{\ell}$ for some $1\leq\ell<k$. Then $t_{i}=it_{1}$ for any $1\leq
i\leq\ell$.

###### Proof.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$. Take two distinct positive
integers $i,j\leq\ell$ and consider $(1+t_{k};1,1+t_{k}+t_{i},1+t_{k}+t_{j})$,
a $K_{1,3}$ in $G$. Since $(1+t_{k}+t_{i})-1>t_{k}$ and
$(1+t_{k}+t_{j})-1>t_{k}$, the vertex $1$ is not adjacent to $1+t_{k}+t_{i}$
and $1+t_{k}+t_{j}$. Thus, $1+t_{k}+t_{i}$ and $1+t_{k}+t_{j}$ are adjacent
since $G$ is claw-free. Therefore $|t_{i}-t_{j}|\in\\{t_{1},\ldots,t_{k}\\}$.
Since $|t_{i}-t_{j}|<t_{\ell}$, $|t_{i}-t_{j}|\in\\{t_{1},\ldots,t_{\ell}\\}$.
Since we have chosen $i,j$ arbitrarily as long as $i,j\leq\ell$,
$\\{t_{1},\ldots,t_{\ell}\\}$ is closed under difference of two distinct
elements. Thus, by Lemma 2.2, $t_{i}=it_{1}$ for any $1\leq i\leq\ell$. ∎

######  Corollary 2.4.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$ be claw-free. If
$n>t_{k-1}+t_{k}$ then $G$ is a cocoonery.

###### Proof.

By Theorem 2.3, $t_{i}=it_{1}$ for each $i\in\\{1,\ldots,k-1\\}$. Consider
$(1+t_{k};1,1+t_{k}-t_{1},1+t_{k-1}+t_{k})$. Since $G$ is claw-free and
$t_{k-1}+t_{k}>t_{k}$, one of $t_{k}-t_{1}$ and $t_{1}+t_{k-1}$ belongs to
$\\{t_{1},\ldots,t_{k}\\}$. If $t_{k}-t_{1}\in\\{t_{1},\ldots,t_{k}\\}$, then
$t_{k}-t_{1}=t_{k-1}$ since $t_{i}=it_{1}$ for each $i\in\\{1,\ldots,k-1\\}$.
If $t_{1}+t_{k-1}\in\\{t_{1},\ldots,t_{k}\\}$, then $t_{k}=t_{1}+t_{k-1}$
since $t_{1}+t_{k-1}>t_{k-1}$. Therefore $t_{k}=kt_{1}$ in each case and so
$G$ is a cocoonery. ∎

The following result states that every cocoonery is claw-free. In addition,
its converse is true if the number of vertices is sufficiently large.

######  Theorem 2.5.

A cocoonery is claw-free.

###### Proof.

Let $G$ be a cocoonery. Then $G=T_{n}\langle t,\ldots,kt\rangle$ for some
positive integers $t$ and $k\geq 2$. To reach a contradiction, suppose that
$G$ contains a claw $(j;i_{1},i_{2},i_{3})$. By $(\star)$, we may assume that
$i_{2}>i_{1}>j$. Then $i_{2}=j+rt$ and $i_{1}=j+st$ for some $1\leq s<r\leq
k$, so $i_{2}-i_{1}=(r-s)t$. Since $1\leq r-s\leq k-1$, $i_{1}$ and $i_{2}$
are adjacent and we reach a contradiction. Thus $G$ is claw-free. ∎

Corollary 2.4 and Theorem 2.5 generalize Theorem 1.1 as follows:

######  Theorem 2.6.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$. If $n>t_{k-1}+t_{k}$, then the
following statements are equivalent.

  * (i)

$G$ is claw-free;

  * (ii)

$G$ is interval;

  * (iii)

$G$ is chordal;

  * (iv)

$G$ is a cocoonery;

  * (v)

$\omega(G)=k+1$.

Theorem 2.6 gives a meaningful characterization for a claw-free Toeplitz
graphs. However, this equivalent relation does not hold without the
restriction on $n$. The following theorem shows that the lower bound on $n$ is
tight.

For convenience, a new family of Toeplitz graphs obtained from cocooneries
needs to be termed. Given an $(n,k,t)$-cocoonery $G=T_{n}\langle
t,2t,\ldots,kt\rangle$, if $H$ is the Toeplitz graph obtained from $G$ by
replacing $kt$ with $(k+1)t$, then we call $H$ the mutation of $G$.

######  Lemma 2.7.

The mutation of an $(n,k,t)$-cocoonery is claw-free if $n\leq 2kt$.

###### Proof.

Let $G$ be the mutation of an $(n,k,t)$-cocoonery. Then $G=T_{n}\langle
t,\ldots,(k-1)t,(k+1)t\rangle$. Let $B=\\{t,\ldots,(k-1)t,(k+1)t\\}$. To reach
a contradiction, suppose that $G$ has a claw $(u;x,y,z)$. By $(\star)$, we may
assume $u<y<z$. Then $\\{y-u,z-u\\}\subset B$. Since $z-y=(z-u)-(y-u)$,
$z-y\notin B$ only if $z-u=(k+1)t$ and $y-u=t$. If $u<x$, then $0<x-u<y-u$ and
$x-u\in B$, which is impossible. Suppose that $u>x$. Then $u-x\in B$. If
$u-x\geq(k-1)t$, then $z-x=(z-u)+(u-x)\geq 2kt$, which is impossible since
$n\leq 2kt$. Thus $u-x<(k-1)t$. Since $y-x=(y-u)+(u-x)$, $y-x$ is a multiple
of $t$ in $\\{t,\ldots,(k-1)t\\}$ and we reach a contradiction. Hence $G$ is
claw-free. ∎

######  Theorem 2.8.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$ with $k\geq 4$. Suppose that
$t_{k-1}+t_{k}=n$. Then $G$ is claw-free if and only if $G$ is a cocoonery or
the mutation of a cocoonery.

###### Proof.

The ‘if’ part immediately follows from Theorem 2.5 and Lemma 2.7.

We show the ‘only if’ part. Since $G$ is claw-free and
$t_{k-2}+t_{k}<t_{k-1}+t_{k}=n$,

$t_{j}=jt_{1}\ \ \mbox{for each}\ \ 1\leq j\leq k-2$ (1)

by Theorem 2.3.

We first consider $(1+t_{k-2};1,1+t_{k-2}+t_{1},1+t_{k-2}+t_{k-1})$. Since $G$
is claw-free, one of $t_{k-2}+t_{1}$, $t_{k-1}-t_{1}$, or $t_{k-2}+t_{k-1}$
belongs to $B:=\\{t_{1},\ldots,t_{k}\\}$.

If $t_{k-1}-t_{1}\in B$, then $t_{k-1}-t_{1}=t_{k-2}$ and so
$t_{k-1}=(k-1)t_{1}$ by (1). Assume $t_{k-2}+t_{1}\in B$. Then $t_{k-2}+t_{1}$
equals either $t_{k-1}$ or $t_{k}$. If $t_{k-2}+t_{1}=t_{k}$, then
$t_{k-1}+t_{1}$ and $t_{k-1}+t_{1}$ do not belong to $B$, so
$(1+t_{k-1};1,1+t_{k-1}+t_{1},1+2t_{k-1})$ is a claw and we reach a
contradiction. Therefore $t_{k-2}+t_{1}=t_{k-1}$ and so $t_{k-1}=(k-1)t_{1}$
by (1). Now we suppose that $t_{k-2}+t_{k-1}\in B$. Then
$t_{k-2}+t_{k-1}=t_{k}$. Consider $(1+t_{k-1};1,1+2t_{k-1},1+t_{k-1}-t_{1})$.
Since $k\geq 4$, $t_{k-2}\neq t_{1}$ and so $t_{k-1}+t_{1}\notin B$. In
addition, $2t_{k-1}\notin B$ by the assumption. Therefore $t_{k-1}-t_{1}\in
B$, so $t_{k-1}=(k-1)t_{1}$ by (1).

Now we consider $(1+t_{k};1,1+t_{k}-t_{2},1+t_{k}+t_{k-2})$. Obviously, $1$
and $t_{k}+t_{k-2}+1$ are not adjacent. Then one of $t_{k}-t_{2}$ or
$t_{k-2}+t_{2}$ belongs to $B$. If $t_{k-2}+t_{2}$ belongs to $B$, then
$t_{k}=kt_{1}$ since $t_{j}=jt_{1}$ for each $1\leq j\leq k-1$. Thus $G$ is a
cocoonery. Suppose that $t_{k}-t_{2}$ belongs to $B$. Since $t_{j}=jt_{1}$ for
each $1\leq j\leq k-1$, $t_{k}-t_{2}=t_{k-2}$ or $t_{k}-t_{2}=t_{k-1}$. Then
$G$ is a cocoonery in the former and $G$ is the mutation of a cocoonery in the
latter. ∎

Consider the mutation $H$ of an $(n,k,t)$-cocoonery for $k\geq 4$. Then
$H=T_{n}\langle t,2t,\ldots,(k-1)t,(k+1)t\rangle$. Since $(k-1)t+(k+1)t=2kt$,
$n$ is even if $n=(k-1)t+(k+1)t$. Therefore we have the following corollary.

######  Corollary 2.9.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$ with $k\geq 4$. Suppose that
$n=t_{k}+t_{k-1}$ is an odd integer. Then $G$ is claw-free if and only if $G$
is a cocoonery.

We have completely characterized claw-free Toeplitz graphs $T_{n}\langle
t_{1},\ldots,t_{k}\rangle$ for $n\geq t_{k}+t_{k-1}$ until now. It is natural
to ask which Toeplitz graphs are claw-free for $t_{k}+1\leq n<t_{k}+t_{k-1}$.
To answer this question, we approach from two directions. One is to consider a
relatively small $k$ and the other is to consider a relatively small $n$. In
the rest of this section, we take the second approach while we concentrate on
the first approach in Section 3. We start with $n=t_{k}+1$. Each of
$T_{t_{i}+1}\langle t_{1},\ldots,t_{i}\rangle$ is an induced subgraph of
$T_{t_{k}+1}\langle t_{1},\ldots,t_{k}\rangle$ since $t_{i}+1\leq t_{i+1}$ for
$i=1,2,\ldots,k-1$. Therefore, if $T_{t_{k}+1}\langle
t_{1},\ldots,t_{k}\rangle$ is claw-free, then $T_{t_{i}+1}\langle
t_{1},\ldots,t_{i}\rangle$ is claw-free for each $i=1,2,\ldots,k-1$, and if
$T_{t_{j}+1}\langle t_{1},\ldots,t_{j}\rangle$ is not claw-free for some
positive integer $j$, then $T_{t_{k}+1}\langle t_{1},\ldots,t_{k}\rangle$ is
not claw-free for each integer $k\geq j$. The following example shows that for
the Fibonacci sequence $\\{t_{i}\\}_{i=1}^{\infty}$, even if
$T_{t_{k}+1}\langle t_{1},\ldots,t_{k}\rangle$ is not claw-free for $k\geq 6$,
it is claw-free for $k\leq 5$.

######  Example 2.10.

Let $G_{k}=T_{F_{k}+1}\langle F_{1},\ldots,F_{k}\rangle$ for the Fibonacci
sequence $\\{F_{i}\\}_{i=1}^{\infty}$ with $F_{1}=1$, $F_{2}=2$. Then
$G_{5}=T_{9}\langle 1,2,3,5,8\rangle$ and $G_{6}=T_{14}\langle
1,2,3,5,8,13\rangle$. It is easy to check that $(3;1,5,11)$ is a claw of
$G_{6}$. Thus $G_{k}$ is not claw-free for $k\geq 6$.

Now we show that $G_{5}$ is claw-free. To reach a contradiction, suppose that
$G_{5}$ contains a claw $(v_{1};v_{2},v_{3},v_{4})$ with $v_{2}<v_{3}<v_{4}$.
By $(\star)$, we may assume that $v_{1}<v_{3}<v_{4}$. By the definition of
Toeplitz graph, $|v_{2}-v_{1}|$, $v_{3}-v_{1}$, and $v_{4}-v_{1}$ are
Fibonacci numbers.

First, we suppose $v_{1}<v_{2}$. Then
$\\{v_{2}-v_{1},v_{3}-v_{1},v_{4}-v_{1}\\}\subset\\{1,2,3,5,8\\}$. Since
$(v_{i}-v_{1})-(v_{j}-v_{1})=v_{i}-v_{j}$ for $2\leq j<i\leq 4$,
$(v_{1};v_{2},v_{3},v_{4})$ is not a claw if two of
$v_{2}-v_{1},v_{3}-v_{1},v_{4}-v_{1}$ are consecutive Fibonacci numbers. Thus
$\\{v_{2}-v_{1},v_{3}-v_{1},v_{4}-v_{1}\\}=\\{1,3,8\\}$. Then $v_{4}-v_{1}=8$,
$v_{3}-v_{1}=3$, and $v_{2}-v_{1}=1$. However, $v_{3}-v_{2}=2$ in this case,
so $v_{2}$ and $v_{3}$ are adjacent and we reach a contradiction.

Now we suppose $v_{1}>v_{2}$. Then
$\\{v_{1}-v_{2},v_{3}-v_{1},v_{4}-v_{1}\\}\subset\\{1,2,3,5,8\\}$. Note that
$v_{4}-v_{2}=(v_{4}-v_{1})+(v_{1}-v_{2})$ and
$v_{3}-v_{2}=(v_{3}-v_{1})+(v_{1}-v_{2})$. Since $G_{5}$ has $9$ vertices,
$v_{3}-v_{2}<v_{4}-v_{2}\leq 8$ and so
$\\{v_{1}-v_{2},v_{3}-v_{1},v_{4}-v_{1}\\}\subset\\{1,2,3,5\\}$. Since
$(v_{4}-v_{1})-(v_{3}-v_{1})=v_{4}-v_{3}$ and
$v_{4}-v_{3}\notin\\{1,2,3,5\\}$, $v_{4}-v_{1}=5$ and $v_{3}-v_{1}=1$. Then,
since $(v_{4}-v_{1})+(v_{1}-v_{2})=v_{4}-v_{2}\leq 8$, $v_{1}-v_{2}\leq 3$.
However, if $v_{1}-v_{2}$ is $1$ or $2$, then $v_{3}-v_{2}$ is $2$ or $3$, and
if $v_{1}-v_{2}=3$, then $v_{4}-v_{2}=8$. Consequently, we have reached a
contradiction. Thus $G_{5}$ is claw-free and so $G_{1},\ldots,G_{5}$ are claw-
free.

In the following, we give a characterization for an infinite sequence
$\\{t_{i}\\}_{i=1}^{\infty}$ for which $T_{t_{k}+1}\langle
t_{1},\ldots,t_{k}\rangle$ is claw-free for any positive integer $k$. We need
the following lemma.

######  Lemma 2.11.

Suppose that $T_{n}\langle t_{1},\ldots,t_{k}\rangle$ is claw-free. For a
given integer $1\leq\ell<k$, if there is some positive integer $\ell\leq j<k$
such that $t_{j+1}-t_{j}>t_{\ell}$, then $t_{i}=it_{1}$ for any $1\leq
i\leq\ell$.

###### Proof.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$ and $H=T_{t_{j+1}}\langle
t_{1},\ldots,t_{j}\rangle$. Then $H$ is an induced subgraph of $G$, so $H$ is
also claw-free. If $j>\ell$, then, by Theorem 2.3, $t_{i}=it_{1}$ for any
$1\leq i\leq\ell$. If $j=\ell$, then, by Corollary 2.4, since
$t_{\ell+1}>2t_{\ell}$, $t_{i}=it_{1}$ for any $1\leq i\leq\ell$. ∎

######  Theorem 2.12.

Suppose that $T_{t_{n}+1}\langle t_{1},\ldots,t_{n}\rangle$ is claw-free for
any positive integer $n$. Then the sequence $\\{t_{n}\\}^{\infty}_{n=1}$ is
bounded above by some arithmetic sequence with a common difference $t_{\ell}$
for some positive integer $\ell$.

###### Proof.

If $\\{t_{n}\\}$ is an arithmetic sequence, then it is bounded above by
itself. Now, suppose that $\\{t_{n}\\}$ is not arithmetic. Then there is some
positive integer $i$ such that $t_{i}\neq it_{1}$. Let $\ell$ be the smallest
integer such that $t_{\ell}\neq\ell t_{1}$. If $t_{j+1}-t_{j}>t_{\ell}$ for
some $j\geq\ell$, then $t_{\ell}=\ell t_{1}$ by Theorem 2.11, which is a
contradiction. Thus $t_{j+1}-t_{j}\leq t_{\ell}$ for any $j\geq\ell$.
Therefore $t_{n}\leq(n-\ell+1)t_{\ell}$ for $n\geq\ell$. Take an arithmetic
sequence $\\{a_{n}\\}$ with $a_{n}=nt_{\ell}$. If $n>\ell$, then
$t_{n}\leq(n-\ell+1)t_{\ell}<nt_{\ell}=a_{n}$. If $n=\ell$, then
$t_{\ell}<\ell t_{\ell}=a_{\ell}$. If $n<\ell$, then
$t_{n}=nt_{1}<nt_{\ell}=a_{n}$. Hence, $\\{t_{n}\\}$ is bounded above by
arithmetic sequence $\\{a_{n}\\}$. ∎

##  3 Claw-free Toeplitz graphs $T_{n}\langle t_{1},t_{2}\rangle$ and
$T_{n}\langle t_{1},t_{2},t_{3}\rangle$

In Section 2, we suggested two approaches to answer the question which
Toeplitz graphs are claw-free for $t_{k}+1\leq n<t_{k}+t_{k-1}$. One is to
consider a relatively small $k$ and the other is to consider a relatively
small $n$. In this section, we take the first approach to characterize claw-
free Toeplitz graphs $T_{n}\langle t_{1},t_{2}\rangle$ and $T_{n}\langle
t_{1},t_{2},t_{3}\rangle$.

We begin with the following lemma, which generalizes Proposition 1.2.

######  Lemma 3.1 ([18]).

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$ with
$\gcd(t_{1},\ldots,t_{k})=d$. Suppose that $r$ is an integer such that
$r\equiv n\pmod{d}$ with $1\leq r\leq d$. Then each of
$G^{d}_{1},\ldots,G^{d}_{r}$ is isomorphic to $T_{\lceil n/d\rceil}\langle
t_{1}/d,\ldots,t_{k}/d\rangle$ and each of $G^{d}_{r+1},\ldots,G^{d}_{d}$ is
isomorphic to $T_{\lfloor n/d\rfloor}\langle t_{1}/d,\ldots,t_{k}/d\rangle$.
Moreover, there is no edge joining a vertex in $G^{d}_{i}$ and a vertex in
$G^{d}_{j}$ if $i\neq j$.

A hole is a chordless cycle of length at least $4$ as an induced subgraph.

######  Lemma 3.2 ([16]).

Let $G=T_{n}\langle t_{1},t_{2}\rangle$ with $n\geq t_{1}+t_{2}$. If
$t_{2}\neq 2t_{1}$, then $G$ has a hole of length
$(t_{1}+t_{2})/\gcd(t_{1},t_{2})$.

The following result describes a useful structure of the Toeplitz graph
$T_{n}\langle t_{1},t_{2}\rangle$ with $n=t_{1}+t_{2}$.

######  Theorem 3.3.

Let $G=T_{n}\langle t_{1},t_{2}\rangle$. If $n=t_{1}+t_{2}$ and
$d=gcd(t_{1},t_{2})$ then $G$ is isomorphic to the disjoint union of $d$
copies of the holes of order $n/d$, i.e.

$G\cong d\,C_{n/d}.$

###### Proof.

Since $n=t_{1}+t_{2}$, $n$ is multiple of $d$. Then, by Lemma 3.1, $G\cong
d\,T_{n/d}\langle t_{1}/d,t_{2}/d\rangle$. Now, $T_{n/d}\langle
t_{1}/d,t_{2}/d\rangle\cong C_{n/d}$ by Lemma 3.2 and this completes the
proof.∎

A claw-free Toeplitz graph $T_{n}\langle t_{1},t_{2}\rangle$ is characterized
as follows.

######  Theorem 3.4.

A Toeplitz graph $T_{n}\langle t_{1},t_{2}\rangle$ is claw-free if and only if
$n\leq t_{1}+t_{2}$ or $t_{2}=2t_{1}$.

###### Proof.

If $n>t_{1}+t_{2}$, then $t_{2}=2t_{1}$ by Corollary 2.4 and so the ‘only if’
part is valid.

To show the ‘if” part, let $n\leq t_{1}+t_{2}$ or $t_{2}=2t_{1}$. If
$n=t_{1}+t_{2}$, by Theorem 3.3, $G$ is isomorphic to union of $d$ cycles of
same size where $d={\rm gcd}(t_{1},t_{2})$. Consequently, for $n<t_{1}+t_{2}$,
the graph $G$ is isomorphic to union of isolated vertices, paths and probably
$a$ cycles, where $0\leq a\leq d-1$. Thus the degree of any vertex in $G$ is
not greater than $2$, which implies $G$ is claw-free. If $t_{2}=2t_{1}$, then
$G$ is claw-free from Proposition 1.2. Hence the proof is complete. ∎

Next, we will characterize a claw-free $T_{n}\langle
t_{1},t_{2},t_{3}\rangle$. We begin with the following theorem.

######  Theorem 3.5.

A Toeplitz graph $G:=T_{t_{3}+1}\langle t_{1},t_{2},t_{3}\rangle$ is claw-free
if and only if $t_{1}+t_{2}=t_{3}$ or $t_{2}=2t_{1}$ or $t_{3}=2t_{1}$.

###### Proof.

To show the ‘only if’ part, suppose that $G$ is claw-free and
$t_{1}+t_{2}<t_{3}$. Since $1+t_{1}+t_{2}<1+t_{3}$,
$H_{1}:=(1+t_{1};1,1+2t_{1},1+t_{1}+t_{2})$ is a subgraph of $G$. Since
$t_{2}<t_{1}+t_{2}<t_{3}$, $1$ and $1+t_{1}+t_{2}$ are not adjacent. Therefore
$1$ and $1+2t_{1}$ are adjacent or $1+2t_{1}$ and $1+t_{1}+t_{2}$ are
adjacent. Since $t_{1}<2t_{1}<t_{1}+t_{2}<t_{3}$, $t_{2}=2t_{1}$ in the
former. In addition, since $t_{2}-t_{1}<t_{2}$, we have $t_{2}-t_{1}=t_{1}$,
i.e. $t_{2}=2t_{1}$ in the latter.

Assume that $t_{1}+t_{2}>t_{3}$. Let $H_{2}=(1;1+t_{1},1+t_{2},1+t_{3})$.
Since $t_{3}-t_{2}<t_{1}$, $1+t_{2}$ and $1+t_{3}$ are not adjacent. Therefore
$1+t_{1}$ and $1+t_{2}$ are adjacent or $1+t_{1}$ and $1+t_{3}$ are adjacent.
Since $t_{2}-t_{1}<t_{2}$, we have $t_{2}-t_{1}=t_{1}$, i.e. $t_{2}=2t_{1}$ in
the former. In addition, since $t_{3}-t_{1}<t_{2}$, we have
$t_{3}-t_{1}=t_{1}$, i.e. $t_{3}=2t_{1}$ in the latter. Thus we have shown the
‘only if’ part.

To show the ‘if’ part, suppose that $t_{1}+t_{2}=t_{3}$ or $t_{2}=2t_{1}$ or
$t_{3}=2t_{1}$. To the contrary, suppose that $G$ has a claw
$(v_{1};v_{2},v_{3},v_{4})$ with $v_{2}<v_{3}<v_{4}$. By $(\star)$, we may
assume $v_{1}<v_{3}<v_{4}$. Then
$\\{|v_{2}-v_{1}|,v_{3}-v_{1},v_{4}-v_{1}\\}\subset\\{t_{1},t_{2},t_{3}\\}$.
Suppose that $v_{4}-v_{1}=t_{3}$. Then $v_{4}=t_{3}+1$ and $v_{1}=1$ and so
$v_{1}<v_{2}$. Since $v_{2}-v_{1}<v_{3}-v_{1}$, we have $v_{2}=t_{1}+1$ and
$v_{3}=t_{2}+1$. If $t_{1}+t_{2}=t_{3}$, then $v_{4}-v_{2}=t_{2}$ and so
$v_{2}$ and $v_{4}$ are adjacent. If $t_{2}=2t_{1}$, then $v_{3}-v_{2}=t_{1}$
and so $v_{2}$ and $v_{3}$ are adjacent. If $t_{3}=2t_{1}$, then
$v_{4}-v_{2}=t_{1}$ and so $v_{2}$ and $v_{4}$ are adjacent. Thus
$(v_{1};v_{2},v_{3},v_{4})$ is not a claw in every case and we reach a
contradiction.

Now we suppose that $v_{4}-v_{1}\neq t_{3}$. Since $v_{3}-v_{1}<v_{4}-v_{1}$,
$v_{3}-v_{1}=t_{1}$ and $v_{4}-v_{1}=t_{2}$. Since $v_{2}-v_{1}<v_{3}-v_{1}$,
$v_{2}<v_{1}$ and so $v_{1}-v_{2}\in\\{t_{1},t_{2},t_{3}\\}$. If
$t_{2}=2t_{1}$, then $v_{4}-v_{3}=(v_{4}-v_{1})-(v_{3}-v_{1})=t_{1}$, which is
a contradiction. Thus $t_{1}+t_{2}=t_{3}$ or $t_{3}=2t_{1}$. Note that

$v_{4}-v_{2}=(v_{4}-v_{1})-(v_{2}-v_{1})=t_{2}-(v_{2}-v_{1})$

and

$v_{3}-v_{2}=(v_{3}-v_{1})-(v_{2}-v_{1})=t_{1}-(v_{2}-v_{1}).$

If $v_{1}-v_{2}=t_{3}$, then
$v_{4}-v_{2}=(v_{4}-v_{1})+(v_{1}-v_{2})=t_{2}+t_{3}>t_{3}+1$ and we reach a
contradiction. Therefore $v_{1}-v_{2}\in\\{t_{1},t_{2}\\}$. Thus
$(v_{4}-v_{2},v_{3}-v_{2})$ is either $(t_{1}+t_{2},2t_{1})$ or
$(2t_{2},t_{1}+t_{2})$. If $t_{1}+t_{2}=t_{3}$, then either $v_{4}-v_{2}$ or
$v_{3}-v_{2}$ is $t_{3}$, which is a contradiction. If $t_{3}=2t_{1}$, then
either $2t_{1}<t_{1}+t_{2}=v_{4}-v_{2}\leq t_{3}$ or
$2t_{1}<2t_{2}=v_{4}-v_{2}\leq t_{3}$, which is impossible. ∎

######  Theorem 3.6.

Let $G:=T_{n}\langle t_{1},t_{2},t_{3}\rangle$ be a Toeplitz graph which is
not a cocoonery. Then $G$ is claw-free if and only if $n\leq t_{2}+t_{3}$ and
one of the following holds:

  * (i)

$t_{1}+t_{2}=t_{3}$;

  * (ii)

$t_{2}=2t_{1}$ and either $t_{3}=4t_{1}$ or $n\leq\frac{t_{2}}{2}+t_{3}$;

  * (iii)

$t_{3}=2t_{1}$ and $n\leq\min\\{2t_{2},3t_{3}/{2}\\}$.

###### Proof.

We first show the ‘only if’ part. Suppose that $G$ is claw-free. Since $G$ is
not a cocoonery,

$n\leq t_{2}+t_{3}$ (2)

by Theorem 2.6 and

$t_{2}\neq 2t_{1}\quad\mbox{or}\quad t_{3}\neq 3t_{1}.$ (3)

To the contrary, suppose that none of (i), (ii), and (iii) holds. Assume that
none of $t_{1}+t_{2}=t_{3}$, $t_{2}=2t_{1}$, and $t_{3}=2t_{1}$ holds. Then
$T_{t_{3}+1}\langle t_{1},t_{2},t_{3}\rangle$ has a claw by Theorem 3.5. For
each $n\geq t_{3}+1$, $T_{t_{3}+1}\langle t_{1},t_{2},t_{3}\rangle$ is an
induced subgraph of $T_{n}\langle t_{1},t_{2},t_{3}\rangle$ and so
$T_{n}\langle t_{1},t_{2},t_{3}\rangle$ has a claw. Therefore one of
$t_{1}+t_{2}=t_{3}$, $t_{2}=2t_{1}$, and $t_{3}=2t_{1}$ is true.

Suppose that $t_{2}=2t_{1}$, $t_{3}\neq 2t_{2}$, and $n>t_{1}+t_{3}$. Then
$(1+t_{1};1,1+t_{1}+t_{2},1+t_{1}+t_{3})$ is a claw. To see why, suppose that
$1$ and $1+t_{1}+t_{2}$ are adjacent. Then $t_{1}+t_{2}=t_{3}$ and
$t_{3}=3t_{1}$, which contradicts (3). Suppose that $1+t_{1}+t_{2}$ and
$1+t_{1}+t_{3}$ are adjacent. Since $t_{3}\neq 2t_{2}$, $t_{3}-t_{2}=t_{1}$.
Then $t_{3}=3t_{1}$, which contradicts (3).

Suppose that $t_{3}=2t_{1}$ and $n>\min\\{t_{1}+t_{3},2t_{2}\\}$. Suppose that
$t_{1}+t_{3}\leq 2t_{2}$. Then $(1+t_{1};1,1+t_{1}+t_{2},1+t_{1}+t_{3})$ is a
claw. To see why, suppose that $1$ and $1+t_{1}+t_{2}$ are adjacent. Then
$t_{1}+t_{2}=t_{3}=2t_{1}$ and $t_{2}=t_{1}$, which is a contradiction. In
addition, since $t_{3}-t_{2}<t_{3}-t_{1}=t_{1}$, $1+t_{1}+t_{2}$ and
$1+t_{1}+t_{3}$ are not adjacent. Suppose that $t_{1}+t_{3}>2t_{2}$. Note that
$2t_{2}>t_{1}+t_{2}>2t_{1}=t_{3}$. In addition, if $t_{2}-t_{1}=t_{1}$, then
$t_{2}=2t_{1}=t_{3}$, which is impossible.

Now we show the ‘if’ part. For $i,j\in\\{t_{3}+1,\ldots,2t_{3}\\}$,
$T_{i}\langle t_{1},t_{2},t_{3}\rangle$ is an induced subgraph of
$T_{j}\langle t_{1},t_{2},t_{3}\rangle$ if $i<j$. Thus it suffices to show
that the following graphs are claw-free:

  * •

$G_{1}:=T_{t_{2}+t_{3}}\langle t_{1},t_{2},t_{3}\rangle$ with
$t_{1}+t_{2}=t_{3}$;

  * •

$G_{2}:=T_{t_{2}+t_{3}}\langle t_{1},t_{2},t_{3}\rangle$ with $t_{2}=2t_{1}$
and $t_{3}=4t_{1}$;

  * •

$G_{3}:=T_{t_{2}/2+t_{3}}\langle t_{1},t_{2},t_{3}\rangle$ with $t_{2}=2t_{1}$
and $t_{3}\neq 4t_{1}$;

  * •

$G_{4}:=T_{3t_{3}/2}\langle t_{1},t_{2},t_{3}\rangle$ with $t_{3}=2t_{1}$ and
$3t_{3}/2\leq 2t_{2}$;

  * •

$G_{5}:=T_{2t_{2}}\langle t_{1},t_{2},t_{3}\rangle$ with $t_{3}=2t_{1}$ and
$3t_{3}/2>2t_{2}$.

We note that if a Toeplitz graph has a claw, then the graph has a claw
containing the vertex $1$. First we suppose that one of $G_{1}$, $G_{2}$,
$G_{3}$, $G_{4}$, $G_{5}$ has a claw with the center $1$. Then it is
$(1;1+t_{1},1+t_{2},1+t_{3})$. However, we may check that $1+t_{2}$ and
$1+t_{3}$ are adjacent in $G_{1}$, $1+t_{1}$ and $1+t_{2}$ are adjacent in
$G_{2}$ and $G_{3}$, and $1+t_{1}$ and $1+t_{3}$ are adjacent in $G_{4}$ and
$G_{5}$. Thus none of $G_{1}$, $G_{2}$, $G_{3}$ has a claw with the center
$1$. We suppose that the graph $G_{i}$ has a claw $H_{i}$ with a pendent
vertex $1$ for each $i=1,2,\ldots,5$.

Suppose that the center of $H_{1}$ is $1+t_{1}$. Then the other possible
pendent vertices of $H_{1}$ are $1+2t_{1}$, $1+t_{1}+t_{2}$, and
$1+t_{1}+t_{3}$. Since $t_{1}+t_{2}=t_{3}$, $1$ and $1+t_{1}+t_{2}$ are
adjacent. In addition, since $t_{3}-t_{1}=t_{2}$, $1+2t_{1}$ and
$1+t_{1}+t_{3}$ are adjacent. Therefore the center of $H_{1}$ is not
$1+t_{1}$. Suppose that the center of $H_{1}$ is $1+t_{2}$. Then the other
possible pendent vertices of $H_{1}$ are $1+t_{2}-t_{1}$, $1+t_{2}+t_{1}$,
$1+2t_{2}$. Then $1$ and $1+t_{2}+t_{1}$ are adjacent. In addition, since
$t_{2}+t_{1}=t_{3}$, $1+t_{2}-t_{1}$ and $1+2t_{2}$ are adjacent. Thus the
center of $H_{1}$ is not $1+t_{2}$. Suppose that the center of $1+t_{3}$. Then
the other possible pendent vertices of $H_{1}$ are $1+t_{3}-t_{1}$,
$1+t_{3}-t_{2}$, $1+t_{3}+t_{1}$. Since $t_{3}-t_{1}=t_{2}$ and
$t_{3}-t_{2}=t_{1}$, $1$ is adjacent to $1+t_{3}-t_{1}$ and $1+t_{3}-t_{2}$.
Therefore the center of $H_{1}$ is not $1+t_{3}$. Thus we reach a
contradiction and so $G_{1}$ is claw-free.

Suppose that the center of $H_{2}$ is $1+t_{1}$. Then the other possible
pendent vertices of $H_{2}$ are $1+2t_{1}$, $1+t_{1}+t_{2}$. Since
$t_{2}=2t_{1}$, $1$ and $1+2t_{1}$ are adjacent. Therefore the center of
$H_{2}$ is not $1+t_{1}$. Suppose that the center of $H_{2}$ is $1+t_{2}$.
Then the other possible pendent vertices of $H_{2}$ are $1+t_{2}-t_{1}$,
$1+t_{2}+t_{1}$, $1+2t_{2}$. Then $1$ and $1+t_{2}-t_{1}$ are adjacent. In
addition, $1+t_{2}+t_{1}$ and $1+2t_{2}$ are adjacent. Thus the center of
$H_{2}$ is not $1+t_{2}$. Suppose that the center of $1+t_{3}$. Then the other
possible pendent vertices of $H_{1}$ are $1+t_{3}-t_{1}$, $1+t_{3}-t_{2}$.
However, $1+t_{3}-t_{1}$ and $1+t_{3}-t_{2}$ are adjacent. Therefore the
center of $H_{1}$ is not $1+t_{3}$. Thus we reach a contradiction and so
$G_{2}$ is claw-free.

Suppose that the center of $H_{3}$ is $1+t_{1}$. Then the other possible
pendent vertices of $H_{3}$ are $1+2t_{1}$, $1+t_{1}+t_{2}$, and
$1+t_{1}+t_{3}$. Since $t_{2}=2t_{1}$, $1$ and $1+2t_{1}$ are adjacent. In
addition, since $t_{3}-t_{2}=t_{2}$ and so $1+t_{1}+t_{2}$ and $1+t_{1}+t_{3}$
are adjacent. Therefore the center of $H_{3}$ is not $1+t_{1}$. Suppose that
the center of $H_{3}$ is $1+t_{2}$. Then the other possible pendent vertices
of $H_{3}$ are $1+t_{2}-t_{1}$, $1+t_{2}+t_{1}$, $1+2t_{2}$. Then $1$ and
$1+t_{2}-t_{1}$ are adjacent. In addition, $1+t_{2}+t_{1}$ and $1+2t_{2}$ are
adjacent. Thus the center of $H_{3}$ is not $1+t_{2}$. Suppose that the center
of $1+t_{3}$. Then the other possible pendent vertices of $H_{3}$ are
$1+t_{3}-t_{1}$, $1+t_{3}-t_{2}$, and $1+t_{3}+t_{1}$. However, $1$ and
$1+t_{3}-t_{2}$ are adjacent. In addition, $1+t_{3}-t_{1}$ and $1+t_{3}+t_{1}$
are adjacent. Therefore the center of $H_{3}$ is not $1+t_{3}$. Thus we reach
a contradiction and so $G_{3}$ is claw-free.

Suppose that the center of $H_{4}$ is $1+t_{1}$. Then the other possible
pendent vertices of $H_{4}$ are $1+2t_{1}$, $1+t_{1}+t_{2}$. However, $1$ and
$1+2t_{1}$ are adjacent. Therefore the center of $H_{4}$ is not $1+t_{1}$.
Suppose that the center of $H_{4}$ is $1+t_{2}$. Then the other possible
pendent vertices of $H_{4}$ are $1+t_{2}-t_{1}$, $1+t_{2}+t_{1}$. Then
$1+t_{2}-t_{1}$ and $1+t_{2}+t_{1}$ are adjacent. Therefore the center of
$H_{4}$ is not $1+t_{2}$. Suppose that the center of $1+t_{3}$. Then the other
possible pendent vertices of $H_{4}$ are $1+t_{3}-t_{1}$, $1+t_{3}-t_{2}$.
However, $1$ and $1+t_{3}-t_{1}$ are adjacent. Therefore the center of $H_{4}$
is not $1+t_{3}$. Thus we reach a contradiction and so $G_{4}$ is claw-free.

Suppose that the center of $H_{5}$ is $1+t_{1}$. Then the other possible
pendent vertices of $H_{5}$ are $1+2t_{1}$, $1+t_{1}+t_{2}$. However, $1$ and
$1+2t_{1}$ are adjacent. Therefore the center of $H_{5}$ is not $1+t_{1}$.
Suppose that the center of $H_{5}$ is $1+t_{2}$. Then the other possible
pendent vertices of $H_{5}$ are $1+t_{2}-t_{1}$, $1+t_{2}+t_{1}$. Then
$1+t_{2}-t_{1}$ and $1+t_{2}+t_{1}$ are adjacent. Therefore the center of
$H_{5}$ is not $1+t_{2}$. Suppose that the center of $1+t_{3}$. Then the other
possible pendent vertices of $H_{5}$ are $1+t_{3}-t_{1}$, $1+t_{3}-t_{2}$.
However, $1$ and $1+t_{3}-t_{1}$ are adjacent. Therefore the center of $H_{5}$
is not $1+t_{3}$. Thus we reach a contradiction and so $G_{5}$ is claw-free. ∎

######  Theorem 3.7.

Let $G=T_{n}\langle t_{1},t_{2},t_{3}\rangle$ of order $n=2t_{3}-i$ for
$i=1,2,3$. Then $G$ is claw-free if and only if $G$ is one of the following
graphs:

  * (i)

$T_{6t_{1}-1}\langle t_{1},2t_{1},3t_{1}\rangle$, $T_{6t_{1}-2}\langle
t_{1},2t_{1},3t_{1}\rangle$, $T_{6t_{1}-3}\langle t_{1},2t_{1},3t_{1}\rangle$;

  * (ii)

$T_{2t_{3}-1}\langle 1,t_{3}-1,t_{3}\rangle$, $T_{2t_{3}-2}\langle
1,t_{3}-1,t_{3}\rangle$, $T_{2t_{3}-3}\langle 1,t_{3}-1,t_{3}\rangle$,
$T_{2t_{3}-2}\langle 2,t_{3}-2,t_{3}\rangle$, $T_{2t_{3}-3}\langle
2,t_{3}-2,t_{3}\rangle$, $T_{2t_{3}-3}\langle 3,t_{3}-3,t_{3}\rangle$;

  * (iii)

$T_{7}\langle 2,4,5\rangle$, $T_{6}\langle 1,2,4\rangle$, $T_{5}\langle
1,2,4\rangle$;

  * (iv)

$T_{6}\langle 2,3,4\rangle$, $T_{5}\langle 2,3,4\rangle$, $T_{9}\langle
3,5,6\rangle$.

###### Proof.

Let $n=2t_{3}-i$ for $i=1,2,3$. If $G$ is a cocoonery, then $G$ is claw-free.
Therefore the cocooneries $T_{6t_{1}-1}\langle t_{1},2t_{1},3t_{1}\rangle$,
$T_{6t_{1}-2}\langle t_{1},2t_{1},3t_{1}\rangle$, and $T_{6t_{1}-3}\langle
t_{1},2t_{1},3t_{1}\rangle$ with $2t_{3}-i$ vertices for $i=1,2,3$ are claw-
free. Suppose that $G$ is claw-free and is not a cocoonery. Then, by Theorem
3.6, one of (i), (ii), and (iii) of Theorem 3.6 holds.

Case 1. Theorem 3.6(i) holds. Then $t_{3}+1\leq 2t_{3}-i\leq t_{2}+t_{3}$, so
$t_{2}\geq t_{3}-i$. Since $t_{1}+t_{2}=t_{3}$, $t_{1}\leq i$. Therefore, in
this case, the following are claw-free: $T_{2t_{3}-1}\langle
1,t_{3}-1,t_{3}\rangle$; $T_{2t_{3}-2}\langle 1,t_{3}-1,t_{3}\rangle$;
$T_{2t_{3}-3}\langle 1,t_{3}-1,t_{3}\rangle$; $T_{2t_{3}-2}\langle
2,t_{3}-2,t_{3}\rangle$; $T_{2t_{3}-3}\langle 2,t_{3}-2,t_{3}\rangle$;
$T_{2t_{3}-3}\langle 3,t_{3}-3,t_{3}\rangle$.

Case 2. Theorem 3.6(ii) holds. Then $t_{2}=2t_{1}$, and either $t_{3}\neq
2t_{2}$ and $t_{3}+1\leq 2t_{3}-i\leq{t_{2}}/{2}+t_{3}$ or $t_{3}=2t_{2}$ and
$t_{3}+1\leq 2t_{3}-i\leq t_{2}+t_{3}$.

Assume the former. Then $2t_{3}-i\leq t_{1}+t_{3}$. Since $t_{1}\leq
t_{2}-1\leq t_{3}-2$, we have $2t_{3}-i\leq t_{1}+t_{3}\leq 2t_{3}-2$. Thus
$i=2$ or $i=3$. Suppose $i=2$. Then $t_{1}=t_{3}-2$ and $t_{2}=t_{3}-1$. Since
$t_{2}=2t_{1}$, we have $t_{1}=1$, $t_{2}=2$ and $t_{3}=3$ which is impossible
as it induces a cocoonery. Thus $i=3$. Then $t_{1}=t_{3}-2$ or $t_{3}-3$. If
$t_{1}=t_{3}-2$, then $t_{1}=1$, $t_{2}=2$ and $t_{3}=3$, which is impossible,
for the same reason as above. Thus $t_{1}=t_{3}-3$. Then $t_{2}=t_{3}-1$ or
$t_{2}=t_{3}-2$. Suppose $t_{2}=t_{3}-1$. Then, since $t_{2}=2t_{1}$, we have
$t_{1}=2,t_{2}=4$ and $t_{3}=5$. Therefore $T_{7}\langle 2,4,5\rangle$ is
claw-free. Suppose $t_{2}=t_{3}-2$. Then, since $t_{2}=2t_{1}$, we have
$t_{1}=1,t_{2}=2$ and $t_{3}=4$, which contradicts the fact that $t_{3}\neq
2t_{2}$.

Assume the latter. Then $t_{2}$ and $t_{3}$ are both even, so $t_{2}\leq
t_{3}-2$. Thus $2t_{3}-i\leq t_{2}+t_{3}\leq 2t_{3}-2$. Therefore $i=2$ or
$i=3$. If $i=2$, then $t_{2}=t_{3}-2$. Suppose $i=3$. Then $2t_{3}-3\leq
t_{2}+t_{3}$. Since $t_{2}$ and $t_{3}$ are both even, $2t_{3}-2\leq
t_{2}+t_{3}$ and so $2t_{3}-2\leq t_{2}+t_{3}\leq 2t_{3}-2$. Thus
$t_{2}=t_{3}-2$. Since $t_{3}=2t_{2}$ and $t_{2}=2t_{1}$, we have
$t_{1}=1,t_{2}=2$ and $t_{3}=4$. Therefore $T_{6}\langle 1,2,4\rangle$ and
$T_{5}\langle 1,2,4\rangle$ are claw-free.

Case 3. Theorem 3.6(iii) holds. Then $t_{3}=2t_{1}$ and
$2t_{3}-i\leq\min\\{2t_{2},3t_{3}/2\\}$. Since $t_{1}\leq t_{2}-1\leq
t_{3}-2$, we have

$2t_{3}-i\leq\min\\{2t_{2},3t_{3}/2\\}\leq 3t_{3}/2=t_{1}+t_{3}\leq 2t_{3}-2.$

Thus $i=2$ or $i=3$. Suppose $i=2$. Then $t_{1}=t_{3}-2$ and $t_{2}=t_{3}-1$.
Since $t_{3}=2t_{1}$, we have $t_{1}=2$, $t_{2}=3$, and $t_{3}=4$. Therefore
$T_{6}\langle 2,3,4\rangle$ is claw-free. Now suppose $i=3$. Then
$t_{1}=t_{3}-2$ or $t_{3}-3$. If $t_{1}=t_{3}-2$, then we have $t_{1}=2$,
$t_{2}=3$, and $t_{3}=4$ and so $T_{5}\langle 2,3,4\rangle$ is claw-free.
Suppose $t_{1}=t_{3}-3$. Then $t_{2}=t_{3}-1$ or $t_{3}-2$. If
$t_{2}=t_{3}-2$, then

$2t_{3}-3\leq\min\\{2t_{2},3t_{3}/2\\}\leq 2t_{2}=2t_{3}-4,$

which is a contradiction. Thus $t_{2}=t_{3}-1$. Since $t_{3}=2t_{1}$, we have
$t_{1}=3,t_{2}=5$, and $t_{3}=6$. Therefore $T_{9}\langle 3,5,6\rangle$ is
claw-free. ∎

##  4 On Toeplitz graphs which are line graphs

Recall that the line graph $L(H)$ of a graph $H$ is the graph whose vertex set
is in one-to-one correspondence with the set of edges of $H$, where two
vertices of $L(H)$ are adjacent if and only if the corresponding edges in $H$
have a vertex in common. Equivalently, a graph $G$ is a line graph if it is
isomorphic to the line graph $L(H)$ of some graph $H$. In this case, we write
$G=L(H)$ [7].

In this section, we study the Toeplitz graphs which are line graphs. In the
case $k=1$, by Proposition 1.2 we have

$T_{n}\langle
t_{1}\rangle\cong\bigcup^{t_{1}}_{i=1}P_{n_{i}}=L(\bigcup_{i=1}^{t_{1}}P_{n_{i}+1}),$

where $n_{i}=\lfloor(n-i)/t_{1}\rfloor+1$. In the following, we characterize
an $(n,k,t)$-cocoonery which is a line graph.

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. Now define
$M_{v}=\\{e\in E(G)\mid v\text{ is incident to }e\\}$. Then $M_{v}$ is a
clique in the line graph $L(G)$ of $G$.

######  Proposition 4.1.

Let $G$ be a graph. If $M$ is a clique of size at least $4$ in $L(G)$, then
there is a vertex $v$ in $G$ such that $M\subset M_{v}$.

###### Proof.

Let $M$ be a clique of size at least $4$ in $L(G)$. Take a vertex $e\in M$ in
$L(G)$ and let $u,v$ be endpoints of $e$ in $G$. Then for any vertex
$e^{\prime}\in M$ in $L(G)$, $u\in e^{\prime}$ or $v\in e^{\prime}$. Suppose,
to the contrary, there are two vertices $e_{1},e_{2}\in M$ in $L(G)$ with
$u\in e_{1}$ but $v\notin e_{1}$ and $v\in e_{2}$ but $u\notin e_{2}$. Then,
since $e_{1}$ and $e_{2}$ are adjacent in $L(G)$, there is a vertex $w\in
V(G)$ such that $e_{1}=uw$ and $e_{2}=vw$. Since $M$ has size at least $4$,
there is a vertex $e_{3}\in M$ different from $e,e_{1},e_{2}$ in $L(G)$. Then
$u\in e_{3}$ or $v\in e_{3}$. Without loss of generality, we may assume $u\in
e_{3}$. Since $e_{3}\neq e$ and $e_{3}\neq e_{1}$, $v,w\notin e_{3}$. Thus
$e_{3}\cap e_{2}=\emptyset$, which contradicts the fact that $e_{2}$ and
$e_{3}$ are adjacent in $L(G)$. Therefore $u\in e^{\prime}$ for all vertex
$e^{\prime}\in M$ or $v\in e^{\prime}$ for all vertex $e^{\prime}\in M$. ∎

######  Corollary 4.2.

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. If $M$ is a
maximal clique of size at least $4$ of the line graph of $G$, then there is a
vertex $v$ such that $M=M_{v}$.

###### Proof.

By Proposition 4.1, there is a vertex $v$ in $G$ such that $M\subset M_{v}$.
Then $M=M_{v}$ since $M$ is maximal. ∎

By the following theorem, we can obtain infinitely many line graphs which are
Toeplitz graphs.

######  Theorem 4.3.

An $(n,k,t)$-cocoonery $G$ is a line graph if and only if either (a) $k=2$ and
$2t+1\leq n\leq 5t$ or (b) $k\geq 3$ and $kt+1\leq n\leq(k+1)t$.

In particular, if $k=2$, then one of the following is true:

  * (i)

$2t+1\leq n\leq 3t$ and $G$ consists of $r$ copies of $K_{3}$ and $t-r$ copies
of $K_{2}$;

  * (ii)

$3t+1\leq n\leq 4t$ and $G$ consists of $r$ copies of
$K_{2}\vee\overline{K_{2}}$ and $t-r$ copies of $K_{3}$;

  * (iii)

$4t+1\leq n\leq 5t$ and $G$ consists of $r$ copies of $P_{4}\vee K_{1}$ and
$t-r$ copies of $K_{2}\vee\overline{K_{2}}$.

If $k\geq 3$, then $G$ is isomorphic to
$\bigcup_{i=1}^{t}K_{\lfloor(n-i)/t\rfloor+1}$.

###### Proof.

Let $G$ denote the $(n,k,t)$-cocoonery $T_{n}\langle t,2t,\ldots,kt\rangle$.
Then $n\geq kt+1$ by definition. To show the ‘only if’ part, suppose that $G$
is a line graph of some graph $H$.

Suppose $G$ is $(n,k,t)$-cocoonery for $k\geq 3$ and $n>(k+1)t$. Then

$M_{1}=\\{1,1+t,\ldots,1+kt\\}\text{ and }M_{2}=\\{1+t,1+2t,\ldots
1+(k+1)t\\}$

are maximal cliques in $G$. By Corollary 4.2, there are vertices $u,v\in V(H)$
such that $M_{1}=M_{u}$ and $M_{2}=M_{v}$. Then $u\neq v$ since $M_{1}\neq
M_{2}$. Since $1+t\in M_{1}\cap M_{2}$ and $1+2t\in M_{1}\cap M_{2}$,
$1+t=uv=1+2t$, which is a contradiction.

To reach a contradiction, suppose that $G=T_{n}\langle t,2t\rangle$ and
$n>5t$. Then each of
$T_{1}:=\\{1,1+t,1+2t\\},T_{2}:=\\{1+t,1+2t,1+3t\\},T_{3}:=\\{1+2t,1+3t,1+4t\\},T_{4}:=\\{1+3t,1+4t,1+5t\\}$
form triangle in $G$. Now the vertices of $T_{i}$ correspond to either the
edges of a triangle in $H$ or the edges of $K_{1,3}$ in $H$. Suppose both of
$T_{i}$ and $T_{i+1}$ are from triangles or from $K_{1,3}$ in $H$. Then, since
$|T_{i}\cap T_{i+1}|=2$, $T_{i}$ and $T_{i+1}$ are from the same triangle or
the same $K_{1,3}$ in $H$. Therefore $1+(i-1)t$ and $1+(i+2)t$ correspond to
the same edge in $H$ and we reach a contradiction. Thus
$T_{1},T_{2},T_{3},T_{4}$ are alternatively from a triangle or a $K_{1,3}$.
Without loss of generality, we may assume $T_{1}$ and $T_{3}$ are from a
$K_{1,3}$ and $T_{2}$ and $T_{4}$ are from a triangle. Then we assume $T_{2}$
is from triangle $abc$ in $H$ so that $1+t=ab$, $1+2t=ac$, and $1+3t=bc$. Then
$T_{1}$ is from $K_{1,3}$ with center $a$ and leaves $b,c,d$ and $T_{3}$ is
from $K_{1,3}$ with center $c$ and leaves $a,b,e$ so that $1=ad$ and
$1+4t=ce$. Therefore $T_{4}$ is from triangle $bce$ in $H$ so that $1+5t=be$.
Then $1+t=bc$ and $1+5t=be$ are adjacent in $G$, which is a contradiction.

Now we show the ‘if’ part. If $G$ is an $(n,k,t)$-cocoonery with $k\geq 3$ and
$kt+1\leq n\leq(k+1)t$, then each component of $G$ is isomorphic to
$T_{k}\langle 1,2,\ldots,k-1\rangle$ or $T_{k+1}\langle 1,2,\ldots,k\rangle$
by Proposition 1.2, which is a clique, and so $G$ is a line graph. Suppose
that $G$ is a $(n,k,t)$-cocoonery with $k=2$ and $n\leq 5t$. Then each
component of $G$ is isomorphic to $T_{2}\langle 1\rangle$ $T_{3}\langle
1,2\rangle$ or $T_{4}\langle 1,2\rangle$ or $T_{5}\langle 1,2\rangle$ by
Proposition 1.2. It suffices to show that each component of $G$ is a line
graph. First, $T_{2}\langle 1\rangle$ is the line graph of $P_{3}$ and
$T_{3}\langle 1,2\rangle$ is the line graph of a triangle. Let $H_{1}$ be a
graph with vertex set $\\{a,b,c,d\\}$ and edge set $\\{ad,ab,ac,bc\\}$. By
letting $ad\leftrightarrow 1,ab\leftrightarrow 2,ac\leftrightarrow
3,bc\leftrightarrow 4$, we have $T_{4}\langle 1,2\rangle$ as the line graph
$L(H_{1})$. Let $H_{2}$ be a graph with vertex set $\\{a,b,c,d,e\\}$ and edge
set $\\{ad,ab,ac,bc,ce\\}$. By letting $ad\leftrightarrow 1,ab\leftrightarrow
2,ac\leftrightarrow 3,bc\leftrightarrow 4,ce\leftrightarrow 5$, we have
$T_{5}\langle 1,2\rangle$ as $L(H_{2})$. Therefore each component of $G$ is a
line graph and so $G$ is a line graph. ∎

######  Example 4.4.

We consider a cocoonery $G:=T_{n}\langle t,2t\rangle$ for $n\leq 5t$. By
Proposition 1.2, $G$ has components $H_{1},\ldots,H_{t}$ where $H_{i}\cong
T_{\lfloor(n-i)/t\rfloor+1}\langle 1,2\rangle$ and the vertex set of $H_{i}$
is $\\{i+st\;|\;s=0,1,\ldots,\lfloor(n-i)/t\rfloor\\}$ for each $i\in[t]$.

If $kt+1\leq n\leq(k+1)t$, then $\lfloor(n-i)/t\rfloor=k-1$ or $k$ for each
$i\in[t]$. Thus,

  * ($\star$)

if $kt+1\leq n\leq(k+1)t$, then $G$ has a component of order $k$ or $k+1$.

Since we consider a cocoonery $T_{n}\langle t,2t\rangle$ for only $n\leq 5t$,
$H_{i}$ is isomorphic to $T_{2}\langle 1\rangle\cong K_{2}$ or $T_{3}\langle
1,2\rangle\cong K_{3}$ or $T_{4}\langle 1,2\rangle\cong
K_{2}\vee\overline{K_{2}}$ or $T_{5}\langle 1,2\rangle\cong P_{4}\vee K_{1}$.
Especially, by ($\star$),

  * •

if $2t+1\leq n\leq 3t$, $G$ has a component of order $2$ or $3$ and so $G$
consists of $r$ copies of $K_{2}$ and $t-r$ copies of $K_{3}$;

  * •

if $3t+1\leq n\leq 4t$, $G$ consists of $r$ copies of $K_{3}$ and $t-r$ copies
of $K_{2}\vee\overline{K_{2}}$;

  * •

if $4t+1\leq n\leq 5t$, $G$ consists of $r$ copies of
$K_{2}\vee\overline{K_{2}}$ and $t-r$ copies of $P_{4}\vee K_{1}$.

where $r$ is a remainder of $n$ divided by $t$ (if $n$ is divisible by $t$
then $r=t$).

The next corollary shows that a Toeplitz graph $T_{n}\langle
t_{1},\ldots,t_{k}\rangle$ with $k\geq 3$ and $n>t_{k}+t_{k-1}$ is not a line
graph.

######  Corollary 4.5.

Let $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$ with $k\geq 3$. If
$n>t_{k}+t_{k-1}$, then $G$ is not a line graph.

###### Proof.

If $G$ is not a cocoonery, then $G$ is not claw-free by Corollary 2.4 and so
$G$ is not a line graph. If $G$ is a cocoonery, then
$n>t_{k}+t_{k-1}\geq(2k-1)t>(k+1)t$ and so $G$ is not a line graph by Theorem
4.3.∎

######  Example 4.6.

There are a lot of Toeplitz graphs $T_{n}\langle t_{1},\ldots,t_{k}\rangle$
which are not a line graph with $n\leq t_{k}+t_{k-1}$. For each $k\geq 6$, the
graph $G_{k}$ defined in Example 2.10 is not claw-free, so $G_{k}$ is not a
line graph. In addition, one can see that $(3;1,5,11)$ is a claw of
$T_{n}\langle 1,2,3,5,8\rangle$ for each $n\geq 11$. Thus, for any $n\geq 11$,
$T_{n}\langle F_{1},\ldots,F_{j}\rangle$ is not a line graph as long as $j\geq
5$ and $F_{j}+1\leq n$.

We propose the following question.

######  Problem 1.

Characterize all Toeplitz graphs $G=T_{n}\langle t_{1},\ldots,t_{k}\rangle$
with $k\geq 3$ and order $1+t_{k}\leq n\leq t_{k}+t_{k-1}$ which are line
graphs.

## References

  * [1] J. Chen, G. Chang, and K. Huang.  Integral distance graphs.  J. Graph Theory, 25:287–294, 1997.
  * [2] I. Gohberg (ed.).  Toeplitz Centennial.  Birkhäuser, Boston, 1982.
  * [3] R. Euler.  Characterizing bipartite toeplitz graphs.  Theor. Comput. Sci, 263:47–58, 2001.
  * [4] R. Euler.  Coloring planar toeplitz graphs and the stable set polytope.  Discret. Math., 276:183–200, 2004.
  * [5] R. Euler, H. Le Verge, and T. Zamfirescu.  A characterization of infinite, bipartite toeplitz graphs.  In: Ku Tung-Hsin (ed.) Combinatorics and Graph Theory’95, Academia Sinica, World Scientific, Singapore, 1:119–130, 1995.
  * [6] R. Euler and T. Zamfirescu.  On planar toeplitz graphs.  Graphs and Combinatorics, 29:1311–1327, 2013.
  * [7] F. Harary.  Graph Theory.  Reading, Addison-Wesley, 1972.
  * [8] G. Heinig and K. Rost.  Algebraic methods for Toeplitz-like matrices and operators.  Birkhäuser, Boston, 1984.
  * [9] C. Heuberger.  On hamiltonian toeplitz graphs.  Discret. Math., 245:107–125, 2002.
  * [10] C. Heuberger.  On planarity and colorability of circulant graphs.  Discret. Math., 268:153–169, 2003.
  * [11] I. S. Iohvidov.  Hankel and Toeplitz matrices and forms algebraic theory.  Birkhäuser, Boston, 1982.
  * [12] A. Kemnitz and H. Kolberg.  Coloring of integer distance graphs.  Discret. Math., 191:113–123, 1998.
  * [13] A. Kemnitz and M. Marangio.  Chromatic numbers of integer distance graphs.  Discret. Math., 233:239–246, 2001.
  * [14] S. Malik and A. M. Qureshi.  Hamiltonian cycles in directed toeplitz graphs.  Ars Combin., 109:511–526, 2013.
  * [15] S. Malik and T. Zamfirescu.  Hamiltonian connectedness in directed toeplitz graphs.  Bull. Math. Soc. Sci. Math. Roum., 53.
  * [16] S. A. Mojallal, J.-H. Jung, G.-S. Cheon, S.-R. Kim, and B. Kang.  Structural characterizations of toeplitz graphs.  under review.
  * [17] S. Nicoloso and U. Pietropaoli.  On the chromatic number of toeplitz graphs.  Discret. Appl. Math., 164:286–296, 2014.
  * [18] H. Ryu, S.-R. Kim, B. Kang, and G.-S. Cheon.  Competition graphs of directed toeplitz graphs.  preprint.
  * [19] R. van. Dal, G. Tijssen, Z. Tuza, J. van der Veen, C. H. Zamfirescu, and T. Zamfirescu.  Hamiltonian properties of toeplitz graphs.  Discret. Math., 159:69–81, 1996.


# Gradient Knowledge Distillation for Pre-trained Language Models

Lean Wang1, Lei Li2, Xu Sun1,2
1School of Electronics Engineering and Computer Science, Peking University
2MOE Key Lab of Computational Linguistics, School of Computer Science, Peking
University
{lean<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Knowledge distillation (KD) is an effective framework to transfer knowledge
from a large-scale teacher to a compact yet well-performing student. Previous
KD practices for pre-trained language models mainly transfer knowledge by
aligning instance-wise outputs between the teacher and student, while
neglecting an important knowledge source, i.e., the gradient of the teacher.
The gradient characterizes how the teacher responds to changes in inputs,
which we assume is beneficial for the student to better approximate the
underlying mapping function of the teacher. Therefore, we propose _Gradient
Knowledge Distillation_ (GKD) to incorporate the gradient alignment objective
into the distillation process. Experimental results show that GKD outperforms
previous KD methods regarding student performance. Further analysis shows that
incorporating gradient knowledge makes the student behave more consistently
with the teacher, improving the interpretability greatly.111Our code is
available at https://github.com/lancopku/GKD.

##  1 Introduction

Knowledge distillation (KD) (Hinton et al., 2015; Romero et al., 2015) is a
classic framework for model compression, which trains a compact student model
by utilizing the learned knowledge in a large teacher PLM via teacher-student
prediction alignments. Various alignment strategies have been proposed, like
internal representation matching (Sun et al., 2019; Sanh et al., 2019; Jiao et
al., 2020) and attention heatmap consistency (Wang et al., 2020), and obtain
promising efficiency-performance trade-off. However, previous KD studies for
PLMs mostly align the student to the teacher model in a point-to-point manner,
neglecting an important knowledge source, i.e., the gradient of the teacher.

Viewing a model as a function mapping the input to the label space, the
gradients thus can depict the curve of the function, capturing the model
activation changes according to the input perturbation, which we assume can be
beneficial for the student model. Besides, as gradients are closely related to
interpretation, gradient alignment is likely to improve interpretation
consistency.

Motivated by this, we explore incorporating gradient alignment in knowledge
distillation. However, introducing gradient alignment to KD for PLMS is
challenging due to the following two reasons. First, the inherent discreteness
of natural language makes directly computing the deviations w.r.t. the input
sentences intractable. To remedy this, we instead align the gradient w.r.t the
input embedding, and initialize the embedding of the student with that of the
teacher and freeze it during training. Second, our theoretical analysis shows
that the commonly adopted Dropout regularization (Srivastava et al., 2014)
will disturb the gradient alignment, so we deactivate dropout while conducting
distillation. Further analysis and experiments can be found in Section 3 and
Table 1. Experiments on large-scale datasets in the GLUE benchmark (Wang et
al., 2019) demonstrate that gradient knowledge improves the student’s
performance and behavior consistency with the teacher model. Besides, our
analysis of word saliency (Ding et al., 2019) shows that the alignments on
gradients can benefit the behavior consistency in word saliency level.

Figure 1: Comparison between traditional KD and our gradient KD. Gradient KD
introduces an extra gradient alignment objective to better inform the student
of the model behavior of the teacher.

##  2 Related Work

Knowledge distillation has been widely used in computer vision (CV) (Kong et
al., 2019; Mullapudi et al., 2019), natural language process (NLP) (Sanh et
al., 2019; Chen et al., 2020) and multimodal field (Dai et al., 2022; Li et
al., 2021a). In the NLP field, knowledge distillation methods can be roughly
classified into one-stage methods and two-stage ones. One-stage methods
perform distillation at the fine-tuning stage. BiLSTM${}_{\textrm{SOFT}}$
(Tang et al., 2019) performs knowledge distillation with the teacher’s logits
on an augmented dataset, BERT-PKD (Sun et al., 2019) performs knowledge
distillation with the teacher’s logits and hidden states, and PD (Turc et al.,
2019) uses a small pre-trained masked language model as a student to enhance
the effect of distillation. Two-stage methods perform distillation at both the
pre-training stage and the fine-tuning stage. DistilBERT (Sanh et al., 2019)
and MobileBERT (Sun et al., 2020) focus on the pre-training stage, aiming to
get a task-agnostic model that can be fine-tuned or distilled on downstream
tasks. TinyBERT (Jiao et al., 2020) first distills a task-agnostic model
during pre-training and then performs task-specific distillation on an
augmented dataset to further improve performance.

Besides, in the computer vision field, aligning gradients (Srinivas and
Fleuret, 2018) or using gradients as a weighting factor (Zhu and Wang, 2021)
have been explored before. But there is little exploration for PLMs. Wu et al.
incorporates gradients via a momentum distillation method which is similar to
the momentum mechanism (Qian, 1999), but as far as we know, direct gradient
alignment has not been explored in the context of KD for PLMs.

##  3 Gradient Knowledge Distillation For PLMs

#### Backgrounds: KD for PLMs

Formally, for a classification task, we denote
$\mathcal{D}=\\{\mathbf{x}_{i},\mathbf{y}_{i}\\}_{i=1}^{N}$ as the training
dataset with $N$ instances, where $\mathbf{x}_{i}$ is the input sentence and
$\mathbf{y}_{i}$ is the label. Without loss of generality, we take BERT as the
representative of PLM model, which transforms the sentence $\mathbf{x}_{i}$ to
a contextualized representation $\mathbf{h}_{i}=\text{BERT}(\mathbf{x}_{i})$.
A softmax layer with a learnable parameter $\mathbf{W}$ is appended for
producing probability vector
$\mathbf{p}_{i}=\operatorname{softmax}(\mathbf{W}\mathbf{h}_{i})$ over the
label set. We denote $\mathbf{p}^{T}_{i}$ and $\mathbf{p}^{S}_{i}$ as the
probability vector generated by the teacher $T$ and the student $S$ for the
$i$th input, respectively. KD aims to transform the large teacher’s knowledge
into a smaller student model. Vanilla KD (Hinton et al., 2015) achieves it by
utilizing the soft targets produced by the teacher:

$\displaystyle\small\mathcal{L}_{\text{KD}}$
$\displaystyle=(1-\alpha)\mathcal{L}_{\text{CE}}+\alpha\mathcal{L}_{\text{Soft-
CE}}$ (1) $\displaystyle\mathcal{L}_{\text{Soft-CE}}$
$\displaystyle={\tau^{2}}\sum\limits_{i=1}^{N}D_{\mathrm{KL}}\left(\mathbf{p}^{T}_{i,\tau}\|\mathbf{p}^{S}_{i,\tau}\right),$
(2)

where $\mathcal{L}_{\text{CE}}$ is the cross-entropy objective for
classification tasks,
$\mathbf{p}_{i,\tau}=\operatorname{softmax}(\mathbf{W}\mathbf{h}_{i}/\tau)$,
$\alpha$ is a hyper-parameter and $\tau$ is the temperature hyper-parameter.
Further explorations introduce alignments on hidden states (Sun et al., 2019;
Sanh et al., 2019) or attention heatmap (Wang et al., 2020), and explore
dynamic learning schedule (Li et al., 2021b).

#### Improving KD with Gradient Alignments

Different from previous KD studies which consider aligning the teacher and the
student in a point-wise manner, we propose to align the change of the model
around the inputs by introducing an extra objective on gradient consistency
between the student and the teacher. In this way, the student can better
understand how the output should change when the input changes, which is
helpful for the student to behave similarly to the teacher. However, we find
that the discreteness of the text and the dropout regularization hinder the
alignment of the gradients. First, as the input sentence tokens are discrete,
it is intractable to get the derivative w.r.t the original input sentence. To
remedy this, we instead take the derivative w.r.t the input embeddings.
Besides, to make sure that the input spaces of the student and the teacher are
aligned for calculating the gradient, we initialize the student embedding with
that of the teacher, which is a commonly adopted practice in previous KD
studies (Sun et al., 2019; Jiao et al., 2020), and fix the student embedding
layer during the training. Denote $p_{m,i}^{S}$ and $p_{m,i}^{T}$ as the
maximum probability in the obtained class probability distribution from the
student and the teacher for an input sentence $\mathbf{x}_{i}$, the gradient
alignment is defined as a mean-square error objective between two normalized
deviations:

$\mathcal{L}_{\text{GKD}}=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{L_{i}}\|\frac{\frac{\partial
p_{m,i}^{S}}{\partial\mathbf{E}^{S}_{i,j}}}{\|\frac{\partial
p_{m,i}^{S}}{\partial\mathbf{E}^{S}_{i,j}}\|_{2}}-\frac{\frac{\partial
p_{m,i}^{T}}{\partial\mathbf{E}^{T}_{i,j}}}{\|\frac{\partial
p_{m,i}^{T}}{\partial\mathbf{E}^{T}_{i,j}}\|_{2}}\|_{2}^{2}\ ,$ (3)

where $L_{i}$ denotes the length of the $i$th tokenized sentence and
$\mathbf{E}_{i,j}$ denotes the input embedding vector corresponding to the
$j$th token of the $i$th sentence. As the gradient computation will take all
the weights of the model into consideration, the objective encourages the
weight updates towards making the student produce consistent gradients with
the teacher model.

Second, we find the commonly adopted Dropout (Srivastava et al., 2014) will
cause a biased gradient estimation. We provide a mathematical analysis in
Theorem 1. Without loss of generality, in Theorem 1, we derive the gradient
when inputs are applied with a dropout mask once.

###### Theorem 1

Consider a function $f$ whose input $\mathbf{x_{0}}\odot\bm{\xi}$ comes from a
dropout layer, where each component of
$\bm{\xi}\in\\{0,\frac{1}{1-\delta}\\}^{d}$ is drawn independently from a
scaled Bernoulli($1-\delta$) random variable. Suppose $f$ can be estimated by
its second-order Taylor expansion around $\mathbf{x}_{0}$, then

$\mathbf{E}_{\bm{\xi}}[\nabla f(\mathbf{x}_{0}\odot\bm{\xi})]=\nabla
f(\mathbf{x}_{0})+\frac{\delta}{1-\delta}\operatorname{diag}(\nabla^{2}f(\mathbf{x}_{0}))\mathbf{x}_{0}\
.$ (4)

As the dropout in the teacher model is deactivated, we will align $\nabla
T(\mathbf{x}_{0})$ with $\nabla
S(\mathbf{x}_{0})+\frac{\delta}{1-\delta}\operatorname{diag}(\nabla^{2}S(\mathbf{x}_{0}))\mathbf{x}_{0}$
when conducting distillation with dropout activated in the student model.
Besides, this bias accumulates when the model goes deeper and leads to more
deviated gradients for shallow layers, which is verified in Appendix B. To
remedy this, we deactivate the dropout in the student model for a consistent
gradient calculation.

With the deactivated dropout and the gradient alignment objective, our
gradient knowledge distillation (GKD) is achieved by minimizing the combined
objectives ($\alpha$ and $\beta$ are hyper-parameters):

$\mathcal{L}=(1-\alpha)\mathcal{L}_{\textrm{CE}}+\alpha\mathcal{L}_{\textrm{soft-
CE}}+\beta\mathcal{L}_{\textrm{GKD}}\ ,$ (5)

Furthermore, we apply the gradient alignment on the [CLS] vector to enhance
the effect, as [CLS] vectors are usually adopted as the sentence
representation for sentence-level prediction:

$\mathcal{L}_{\textrm{GKD-
CLS}}=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{m}\|\frac{\frac{\partial
p_{m,i}^{S}}{\partial\mathbf{h}^{s}_{i,S_{j},\textrm{CLS}}}}{\|\frac{\partial
p_{m,i}^{S}}{\partial\mathbf{h}^{s}_{i,S_{j},\textrm{CLS}}}\|_{2}}-\frac{\frac{\partial
p_{m,i}^{T}}{\partial\mathbf{h}^{T}_{i,T_{j},\textrm{CLS}}}}{\|\frac{\partial
p_{m,i}^{T}}{\partial\mathbf{h}^{T}_{i,T_{j},\textrm{CLS}}}\|_{2}}\|_{2}^{2}\
,$ (6)

where $\mathbf{h}^{t}_{i,k,\text{CLS}}$ denotes to the hidden state of the
[CLS] token for the $i$th example in the $k$th layer. The Skip layer mapping
strategy is adopted for $S_{j}$ and $T_{j}$.222For a 6-layer student, $S_{j}$
takes value $\\{1,2,3,4,5\\}$, $T_{j}$ takes value $\\{2,4,6,8,10\\}$ and
$m=5$. As the [CLS] representations in the student and the teacher can be
different, which may hinder gradient alignment, we incorporate an extra loss
to align them:

$\mathcal{L}_{\textrm{PKD}}=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{m}\|\frac{\mathbf{h}^{S}_{i,S_{j},\textrm{CLS}}}{\|\mathbf{h}^{S}_{i,S_{j},\textrm{CLS}}\|_{2}}-\frac{\mathbf{h}^{T}_{i,T_{j},\textrm{CLS}}}{\|\mathbf{h}^{T}_{i,T_{j},\textrm{CLS}}\|_{2}}\|_{2}^{2}\
.$ (7)

Therefore, the objective of the enhanced version GKD-CLS is ($\alpha$, $\beta$
and $\gamma$ are hyperparameters)

$\mathcal{L}=(1-\alpha)\mathcal{\mathcal{missing}}L_{\textrm{CE}}+\alpha\mathcal{L}_{\textrm{soft-
CE}}+\beta\mathcal{L}_{\textrm{PKD}}+\gamma(\mathcal{L}_{\textrm{GKD}}+\mathcal{L}_{\textrm{GKD-
CLS}}).$ (8)

##  4 Experiments

In this section, we compare our method with other methods from several
aspects. We mainly focus on applying our distillation method in the fine-
tuning stage due to the limited computational resources. Still, we do
experiments to combine our method with Distilbert (Sanh et al., 2019), to
demonstrate that our method can improve the performance of the models
distilled in the pre-training stage (§ 4.3).

###  4.1 Experimental Settings

#### Datasets

As fine-tuning the BERT model on small datasets like RTE (Bentivogli et al.,
2009) and MRPC (Dolan and Brockett, 2005) can be quite unstable (Zhang et al.,
2021; Mosbach et al., 2021), we select four large-scale sentiment
classification and natural language inference datasets from the GLUE benchmark
(Wang et al., 2019) for more stable evaluation, including Stanford Sentiment
Treebank (SST-2) (Socher et al., 2013), Quora Question Pairs (QQP), Multi-
Genre Natural Language Inference (MNLI) (Williams et al., 2018) and Question-
answering NLI (QNLI) (Rajpurkar et al., 2016).

#### Baselines

We compare our method with direct fine-tuning and two task-specific KD
methods. Vanilla KD (Hinton et al., 2015) aligns the logits of the student and
the teacher. BERT-PKD (Sun et al., 2019) utilizes the hidden states of the
[CLS] token as well as the logits. Besides, in the first part of Section 4.3,
we combine our method with DistilBERT (Sanh et al., 2019), which performs
distillation during pre-training.

#### Training Details

We use a 12-layer BERT-base-uncased model as the teacher, and the students
have the same architecture as the teacher but with $6$ layers. We fine-tune
the teacher on specific tasks to get the task-specific teacher. We conduct a
hyper-parameter search for the baseline methods and our method in a way
similar to Sun et al. (2019). Appendix C gives detailed experimental settings.

###  4.2 Main Results

Table 1:  Results from the GLUE evaluation server with the best scores in bold. The metric for QQP is F1 score and others are accuracy. Avg. denotes the average score over SST-2, QQP, MNLI-m, MNLI-mm and QNLI.  Model | SST-2 | QQP | MNLI-m / mm | QNLI | Avg.
---|---|---|---|---|---
BERT${}_{\text{BASE}}$ | 93.7 | 71.5 | 84.8 / 83.8 | 91.3 | 85.0
Fine-tuning | 91.0 | 69.6 | 81.3 / 79.5 | 87.3 | 81.7
Vanilla KD | 92.0 | 71.0 | 82.2 / 81.2 | 88.9 | 83.1
BERT-PKD | 91.8 | 71.0 | 82.4 / 81.8 | 89.1 | 83.2
GKD | 92.0 | 71.5 |  82.9 / 81.7 | 89.3 | 83.5
GKD-CLS | 93.0 | 71.6 | 82.6 / 81.9 | 89.5 | 83.7
w/ Dropout | 91.8 | 71.0 | 82.3 / 81.6 | 89.1 | 83.2
Table 2:  Results obtained by fine-tuning or distilling DistilBERT model on specific tasks. † denotes the results taken from Jiao et al. (2020). Detailed experimental settings can be found in Appendix C.2.  Model | SST-2 | QQP | MNLI-m/mm | QNLI | Avg.
---|---|---|---|---|---
BERT${}_{\text{BASE}}$ | 93.7 | 71.5 | 84.8 / 83.8 | 91.3 | 85.0
DistilBERT† | 92.5 | 70.1 | 82.6 / 81.3 | 88.9 | 83.1
\+ Vanilla KD | 92.8 | 70.4 | 83.1 / 81.8 | 90.0 | 83.6
\+ BERT-PKD | 92.9 | 71.3 | 83.6 / 82.8 | 90.1 | 84.1
\+ GKD-CLS | 93.7 | 71.3 |  83.7 / 82.8 | 90.2 | 84.3

Table 1 presents the test results obtained from the GLUE evaluation server. We
find that (1) Methods with gradient alignment objectives achieve the best
performance, verifying our assumption that gradient information benefits the
student model. (2) Introducing gradient alignment on [CLS] (GKD-CLS) further
boosts the performance, since [CLS] representations play a significant role in
classification. (3) De-activating dropout is important. Activating Dropout in
GKD-CLS leads to inferior results, which is consistent with our analysis
(Section 3) that dropout will bias the gradient estimation, thus harming the
performance.

###  4.3 Analysis

#### GKD Benefits DistilBERT

Recently, many knowledge distillation methods (Sanh et al., 2019; Sun et al.,
2020; Jiao et al., 2020) have explored knowledge distillation during the pre-
training stage to build a task-agnostic model or improve task-specific
performance. In these works, knowledge distillation can be performed in two
stages—the pre-training stage and fine-tuning stage. Since we lack enough
computational resources to perform knowledge distillation at the pre-training
stage, we instead utilize the $6$-layer DisilBERT model (Sanh et al., 2019),
which is already distilled at the pre-training stage, to perform further GKD
distillation at the fine-tuning stage. Here, as the input embeddings of
DistilBERT and BERT-base-uncased do not match, we only align the gradients
w.r.t. the [CLS] tokens in the gradient alignment objective of GKD-CLS and do
not fix the student input embeddings as the teacher input embedding. The
experimental results are shown in Table 2, and the detailed experimental
settings can be found in Section C.2 in Appendix. The results demonstrate that
our GKD method can be integrated into the two-stage distillation procedure and
can bring more benefits than other methods.

#### GKD Improves Output and Interpretation Consistency

Traditional metrics like accuracy cannot reflect how alike the teacher and the
student behave, which is of great significance in deployments (Xu et al.,
2021). To measure the output consistency, we adopt Label Loyalty (LL) and
Probability Loyalty (PL) following Xu et al. (2021). LL measures the
faithfulness between the student predictions and the teacher predictions. PL
measures the distance between the student predictions and the teacher
predictions at the distribution level.

Besides, we are interested in whether GKD benefits the consistency of model
interpretability, since model interpretation plays an important role in fields
like medicine and finance, and a student loyal to the teacher in
interpretation is useful. For this purpose, we propose Saliency Loyalty (SL).
Specifically, we calculate the teacher’s and the student’s word saliency
distribution using the Grad method (Ding et al., 2019), and the SL is defined
as the Pearson correlation coefficient between them.

We evaluate different methods using these metrics on SST-2 test set. Results
are shown in Table 3.333Results on MNLI can be found in Table 5 in Appendix.
We observe that incorporating gradient into KD improves the behavior
consistency regarding all the metrics, especially in SL, i.e. interpretation
consistency. We also provide a case study of the saliency scores in Figure 2,
which shows that the saliency scores can vary when all the methods predict the
same, and that our methods show the best interpretation consistency, further
verifying our motivation.

Table 3: Behavior consistency on SST-2 test set. Our GKD methods achieve the best performance on all loyalty metrics, especially on saliency loyalty.  Model | PL | LL | SL
---|---|---|---
BERT${}_{\text{BASE}}$ | 100.0 | 100.0 | 100.0
Vanilla KD | 93.7 | 93.7 | 31.2
BERT-PKD | 93.6 | 93.7 | 31.6
GKD | 93.9 | 94.3 | 49.7
GKD-CLS | 94.9 | 94.9 | 53.5

Figure 2: Saliency score visualization on SST-2 test set. Words with positive
scores are marked green while negative ones red. While all methods predict the
sentence as negative, the word saliency distributions vary. Our method
achieves the best consistency with the teacher.

##  5 Conclusion

In this paper, we propose gradient knowledge distillation (GKD) by matching
the unbiased gradient of the student to that of the teacher. As the gradient
contains higher-order information, the alignment helps the student act more
similarly to the teacher. Experiments show that GKD outperforms baseline
methods regarding distillation performance and behavior consistency. For
future work, we intend to integrate our method with different distillation
frameworks to further examine its effectiveness.

## References

  * Bentivogli et al. (2009) Luisa Bentivogli, Ido Kalman Dagan, Dang Hoa, Danilo Giampiccolo, and Bernardo Magnini. 2009.  The fifth pascal recognizing textual entailment challenge.  In _TAC Workshop_.
  * Chen et al. (2020) Yen-Chun Chen, Zhe Gan, Yu Cheng, Jingzhou Liu, and Jingjing Liu. 2020.  Distilling knowledge learned in BERT for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7893–7905, Online. Association for Computational Linguistics.
  * Dai et al. (2022) Wenliang Dai, Lu Hou, Lifeng Shang, Xin Jiang, Qun Liu, and Pascale Fung. 2022.  Enabling multimodal generation on clip via vision-language knowledge distillation.
  * Ding et al. (2019) Shuoyang Ding, Hainan Xu, and Philipp Koehn. 2019.  Saliency-driven word alignment interpretation for neural machine translation.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 1: Research Papers)_ , pages 1–12, Florence, Italy. Association for Computational Linguistics.
  * Dolan and Brockett (2005) William B. Dolan and Chris Brockett. 2005.  Automatically constructing a corpus of sentential paraphrases.  In _Proceedings of the Third International Workshop on Paraphrasing (IWP2005)_.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015.  Distilling the knowledge in a neural network.  _ArXiv preprint_ , abs/1503.02531.
  * Jiao et al. (2020) Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2020.  TinyBERT: Distilling BERT for natural language understanding.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4163–4174, Online. Association for Computational Linguistics.
  * Kong et al. (2019) Hanyang Kong, Jian Zhao, Xiaoguang Tu, Junliang Xing, Shengmei Shen, and Jiashi Feng. 2019.  Cross-resolution face recognition via prior-aided face hallucination and residual knowledge distillation.
  * Li et al. (2021a) Junnan Li, Ramprasaath R. Selvaraju, Akhilesh Deepak Gotmare, Shafiq Joty, Caiming Xiong, and Steven Hoi. 2021a.  Align before fuse: Vision and language representation learning with momentum distillation.
  * Li et al. (2021b) Lei Li, Yankai Lin, Shuhuai Ren, Peng Li, Jie Zhou, and Xu Sun. 2021b.  Dynamic knowledge distillation for pre-trained language models.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 379–389, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Mosbach et al. (2021) Marius Mosbach, Maksym Andriushchenko, and Dietrich Klakow. 2021.  On the stability of fine-tuning BERT: misconceptions, explanations, and strong baselines.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Mullapudi et al. (2019) Ravi Teja Mullapudi, Steven Chen, Keyi Zhang, Deva Ramanan, and Kayvon Fatahalian. 2019.  Online model distillation for efficient video inference.  In _2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019_ , pages 3572–3581. IEEE.
  * Qian (1999) Ning Qian. 1999.  On the momentum term in gradient descent learning algorithms.  _Neural networks : the official journal of the International Neural Network Society_ , 12 1:145–151.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392, Austin, Texas. Association for Computational Linguistics.
  * Romero et al. (2015) Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. 2015.  Fitnets: Hints for thin deep nets.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  In _NeurIPS Workshop on Energy Efficient Machine Learning and Cognitive Computing_.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 1631–1642, Seattle, Washington, USA. Association for Computational Linguistics.
  * Srinivas and Fleuret (2018) Suraj Srinivas and François Fleuret. 2018.  Knowledge transfer with jacobian matching.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 4730–4738. PMLR.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _J. Mach. Learn. Res._ , 15:1929–1958.
  * Sun et al. (2019) Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. 2019.  Patient knowledge distillation for BERT model compression.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4323–4332, Hong Kong, China. Association for Computational Linguistics.
  * Sun et al. (2020) Zhiqing Sun, Hongkun Yu, Xiaodan Song, Renjie Liu, Yiming Yang, and Denny Zhou. 2020\.  MobileBERT: a compact task-agnostic BERT for resource-limited devices.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2158–2170, Online. Association for Computational Linguistics.
  * Tang et al. (2019) Raphael Tang, Yao Lu, Linqing Liu, Lili Mou, Olga Vechtomova, and Jimmy J. Lin. 2019\.  Distilling task-specific knowledge from bert into simple neural networks.  _ArXiv_ , abs/1903.12136.
  * Turc et al. (2019) Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Well-read students learn better: The impact of student initialization on knowledge distillation.  _ArXiv preprint_ , abs/1908.08962.
  * Wang et al. (2019) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2019.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.
  * Wang et al. (2020) Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020.  Minilm: Deep self-attention distillation for task-agnostic compression of pre-trained transformers.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1112–1122, New Orleans, Louisiana. Association for Computational Linguistics.
  * Wu et al. (2021) Chuhan Wu, Fangzhao Wu, Yang Yu, Tao Qi, Yongfeng Huang, and Qi Liu. 2021.  NewsBERT: Distilling pre-trained language model for intelligent news application.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 3285–3295, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Xu et al. (2021) Canwen Xu, Wangchunshu Zhou, Tao Ge, Ke Xu, Julian McAuley, and Furu Wei. 2021.  Beyond preserved accuracy: Evaluating loyalty and robustness of BERT compression.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 10653–10659, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Zhang et al. (2021) Tianyi Zhang, Felix Wu, Arzoo Katiyar, Kilian Q. Weinberger, and Yoav Artzi. 2021\.  Revisiting few-sample BERT fine-tuning.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Zhu and Wang (2021) Yichen Zhu and Yi Wang. 2021.  Student customized knowledge distillation: Bridging the gap between student and teacher.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 5057–5066.

##  Appendix A Proof of Theorem 1

As $f$ can be estimated by its second-order Taylor expansion around
$\mathbf{x}_{0}$, we can rewrite $f$ as

$f(\mathbf{x})=f(\mathbf{x}_{0})+\nabla
f(\mathbf{x}_{0})^{T}(\mathbf{x}-\mathbf{x}_{0})+\frac{1}{2}(\mathbf{x}-\mathbf{x}_{0})^{T}\nabla^{2}f(\mathbf{x}_{0})(\mathbf{x}-\mathbf{x}_{0})\
,$ (9)

where $\nabla f\left(\mathbf{x}_{0}\right)$ is a vector and
$\nabla^{2}f(\mathbf{x}_{0})$ is a matrix.

Then, the expectation of gradient is

$\displaystyle\mathbf{E}_{\bm{\xi}}[\nabla f(\mathbf{x}_{0}\odot\bm{\xi})]$
$\displaystyle=$ $\displaystyle\nabla
f(\mathbf{x}_{0})-\nabla^{2}f(\mathbf{x}_{0})\mathbf{x}_{0}+\mathbf{E}_{\bm{\xi}}[\bm{\xi}\odot\nabla^{2}f(\mathbf{x}_{0})(\mathbf{x}_{0}\odot\bm{\xi})]$
$\displaystyle=$ $\displaystyle\nabla
f(\mathbf{x}_{0})-\nabla^{2}f(\mathbf{x}_{0})\mathbf{x}_{0}+\nabla^{2}f(\mathbf{x}_{0})\mathbf{x}_{0}+\frac{\delta}{1-\delta}\operatorname{diag}(\nabla^{2}f(\mathbf{x}_{0}))\mathbf{x}_{0}$
$\displaystyle=$ $\displaystyle\nabla
f(\mathbf{x}_{0})+\frac{\delta}{1-\delta}\operatorname{diag}(\nabla^{2}f(\mathbf{x}_{0}))\mathbf{x}_{0}\
.$ (10)

Here, to calculate the expectation, we use the fact that each component of
$\bm{\xi}\in\\{0,\frac{1}{1-\delta}\\}^{d}$ is drawn independently from a
scaled Bernoulli($1-\delta$) random variable.

##  Appendix B Dropout Biases Gradient

To further confirm Theorem 1 by experiment, we sample 1000 items from MNLI
train dataset to calculate the cosine similarity between the gradient without
dropout and the expectation of the gradient with dropout. The model we use is
trained by GKD-CLS method. Here, for each item from MNLI, we calculate the
gradient $\mathbf{v}$ 100 times (with dropout activated) and use the average
$\frac{\sum_{i=1}^{100}\mathbf{v}_{i}}{100}$ to estimate the expectation
$\mathbf{E}_{\xi}\mathbf{v}$. The result is shown in Table 4.

Table 4: Cosine similarity between the gradient without dropout and the expectation of the gradient with dropout. $\mathbf{v}$ | $\frac{\partial p_{m,i}^{s}}{\partial\mathbf{E}}$ | $\frac{\partial p_{m,i}^{s}}{\partial\mathbf{h}_{1,\textrm{CLS}}}$ | $\frac{\partial p_{m,i}^{s}}{\partial\mathbf{h}_{2,\textrm{CLS}}}$ | $\frac{\partial p_{m,i}^{s}}{\partial\mathbf{h}_{3,\textrm{CLS}}}$ | $\frac{\partial p_{m,i}^{s}}{\partial\mathbf{h}_{4,\textrm{CLS}}}$ | $\frac{\partial p_{m,i}^{s}}{\partial\mathbf{h}_{5,\textrm{CLS}}}$
---|---|---|---|---|---|---
$\frac{\mathbf{E}_{\xi}[\mathbf{v}]\cdot\mathbf{v}}{\|\mathbf{E}_{\xi}[\mathbf{v}]\|\cdot\|\mathbf{v}\|}$ | 0.84 | 0.89 | 0.90 | 0.91 | 0.91 | 0.91

##  Appendix C Experimental Settings

###  C.1 Settings for the Main Results Shown in Table 1

For hyper-parameter search, we use a strategy similar to the one proposed by
Sun et al. (2019). That is, we first search hyper-parameters $\alpha$, $\tau$
for Vanilla KD method, and then fix $\alpha$, $\tau$ to search the additional
hyper-parameters in other methods. Besides, we initialize Vanilla KD (Hinton
et al., 2015), BERT-PKD (Sun et al., 2019) and our method with the embedding
layer and first 6 hidden layers of the teacher model.

For all the tasks, we fix the training batch size as 32, the training epoch
number as 4, and the learning rate as $5\text{e-}5$.

For Vanilla KD, we perform grid search for $\alpha$ in $\\{0.2,0.5,0.7\\}$ and
$\tau$ in $\\{5,10,20\\}$ and get the best $\alpha,\tau$ on validation set.
This $\alpha$, $\tau$ will be used for BERT-PKD, GKD and GKD-CLS. Then, for
BERT-PKD, we search $\beta$ in $\\{10,100,500,1000\\}$; for our GKD method, we
search $\beta$ in $\\{0.05,0.1,0.2,0.4\\}$; for our GKD-CLS method, we fix
$\beta$ to be $500$ and search $\gamma$ in $\\{0.02,0.05,0.1,0.2\\}$.

We run all experiments on RTX 2080 Ti GPUs. One signal run of our method takes
about 1.5h / 7.5h / 7.5h / 2h for SST-2 / QQP / MNLI / QNLI on a single RTX
2080 Ti GPU and the baseline methods take roughly half the time for a single
run.

We choose the models that show the highest accuracy on validation datasets to
generate the predictions on test datasets, which are then submitted to the
official GLUE evaluation server.

###  C.2 Settings for the Analysis Results Shown in Table 2

The experimental settings for Table 2 are similar to Section C.1, except that
we use the DistilBERT model as the student rather than initializing the
student from the teacher. Besides, we only align the gradients w.r.t. the
[CLS] tokens in the gradient alignment objective of GKD-CLS since the
embeddings of DistilBERT and BERT-base-uncased do not match, and we set
$\beta$ as $1000$ in GKD-CLS to encourage the alignment of [CLS] tokens.

##  Appendix D Loyalty Results on MNLI

We also evaluate the label loyalty, probability loyalty and saliency loyalty
on the MNLI test dataset. The results are shown in Table 5.

Table 5: Results of loyalty on MNLI test dataset. Model |  PL (m / mm) |  LL (m / mm) |  SL (m / mm)
---|---|---|---
BERT${}_{\text{BASE}}$ | 100.0 / 100.0 | 100.0 / 100.0 | 100.0 / 100.0
Vanilla KD | 88.2 / 87.4 | 87.9 / 87.0 | 15.8 / 15.9
BERT-PKD | 88.6 / 87.8 | 88.7 / 87.7 | 17.1 / 16.8
GKD | 89.7 / 89.1 | 89.5 / 88.9 | 35.6 / 35.5
GKD-CLS | 89.5 / 88.9 | 89.4 / 88.7 | 28.2 / 28.0

##  Appendix E Discussion of Distillation Cost

Since our method needs to align the gradient, we need to conduct
backpropagation twice in order to calculate the gradient of the gradient
alignment objective w.r.t. the parameters, which is then used for model
parameter update. So, our method requires roughly twice the computational cost
as normal KD in the training procedure. For example, on the largest MNLI
dataset, our method needs about 7.5h to finish training on a single RTX 2080
Ti GPU while vanilla KD takes about 3.7h. However, the training overhead is
negligible as we only need to train the model once for deployments and is
totally acceptable considering the better distillation performance. And, the
inference speed of our method is the same as normal KD, since both methods use
the student of the same architecture for inference.


Periortree: An Extention of R-Tree for Periodic Boundary Conditions

Toru Niina 1

1\. Department of Biophysics, Graduate School of Science, Kyoto University,
Kyoto 606-8502, Japan

*<EMAIL_ADDRESS>
## Abstract

Searching spatial data is an important operation for scientific simulations
which are performed mostly with periodic boundary conditions. An R-Tree is a
well known tree data structure used to contain spatial objects and it is
capable of answering to spatial searching queries in an efficient way. In this
paper, a novel method to construct an R-Tree considering periodic boundary
conditions is presented. Unlike existing methods, the proposed method works
without any kind of extra objects or queries. Moreover, because this method
reduces the volume of bounding box for each node under the periodic boundary
conditions, it is expected to increase the overall efficiency. While the
extension of an R-Tree is presented in this work, this method is not only
applicable to an R-Tree but also to other data structures that use axis-
aligned bounding boxes with periodic boundary conditions. The implementation
is available on GitHub.

## Introduction

Computational simulations are essential tools for scientific research, such as
studying behaviors of complex biochemical models[1]. To perform such large
scale simulations, both huge amount of computational resources and efficient
simulation softwares are required.

In most cases, searching for objects that satisfy some geometrical conditions
is one of the most time-consuming operation in a simulation. Generally, an
efficient algorithm that search objects drastically accelerates not only the
whole simulation processes, but also the data analysis of simulation results.
Therefore, a method that efficiently processes spatial search accelerates the
whole process of simulation in scientific research.

An R-Tree is a widely used data structure representing bounding volume
hierarchies (BVH) by using an axis-aligned bounding box (AABB) for all its
entries [2]. It is capable of containing both sizeless and finite sized
objects such as points, segments, rectangles, spheres, etc. In order to
improve the efficiency, many variants of the R-Tree algorithm have been
proposed [3, 4, 5, 6].

In order to use an R-Tree with periodic boundary conditions (PBCs), currently,
there exists two methods in the literature (Figure 1) [6]. The first method is
described in Figure 1A. It enables an R-Tree to contain and search objects
considering PBCs by storing the periodic images surrounding of the primary
unit cell. However, compared to the standard R-Tree, the memory consumption is
increased $3^{D}$ times (where $D$ reprecents a dimension of a system). On the
contrary, the other method (Figure 1B) does not store any periodic image, but
it replicates the query based on the PBCs by transposing it periodically when
the query sticks out of the boundary. Although it works fine with points, it
has a limitation when working with finite-sized objects because if the query
is inside of the boundary and the objects extend beyond the unit cell, some of
them are overlooked (Figure 1C). One ad-hoc solution to overcome this
limitation is changing the criteria for replicating a query based on the size
of elements that are contained. However, this may increase the frequency in
which queries are copied and decrease the efficiency.

Here a novel method to construct and use an R-Tree with PBCs is proposed. The
main idea is to consider the PBCs when either entries are inserted or objects
are searched. By expanding an AABB and detecting intersection between AABBs
under PBCs, an R-Tree overcomes the limitation of containing finite-sized
object under PBCs (Figure 1D). Intersection and inclusion detection can be
implemented by introducing periodic transposition in the existing algorithms
with the appropriate representation of an AABB. Comparing to the other
methods, this method does not require to copy objects or queries. Moreover,
using the information of the PBCs, it has more chance to reduce the volume of
AABBs of each node. Since the spatial searching of an R-Tree is strongly
affected by the volme of each node, this feature might increase the
efficiency.

Figure 1: Methods to consider PBCs with R-Tree. (A) By copying the unit cell,
the standard R-Tree can manage objects that are associated with periodic
images. (B) By copying query, R-Tree can find objects that are beyond
boundary. (C) With the method described in B, finite sized objects are
overlooked when queries that is inside of the boundary are not copied. (D) The
method proposed in this paper. Forming AABBs according to the periodicity,
R-Tree can organize objects under periodic boundary conditions.

The codes that are used in this paper are available on GitHub
(http://github.com/ToruNiina/periortree).

## Methods

Here some operations to modify and handle rectangles under PBCs are
introduced. To construct a tree structure, Guttman’s original quadratic
algorithm is employed [2] without any modification except for expansion of an
AABB and intersection detection. The fact that this method is independent from
the core algorithm to construct an R-Tree means that it can be applied to most
of the R-Tree variants and to other spatial indexing methods that are based on
BVH and AABBs.

Since the rectangles used in an R-Tree are axis-aligned, operation in each
dimension are independent from each other. It means that it is sufficient to
show an operation for one dimension. It should be noted that AABBs only
intersect if they overlap in all the axes.

### Representation of PBCs.

Here, only cuboids are considered as the unit cell of the PBCs. It is assumed
that all the coordinates of the objects are restricted to be inside of the
unit cell. There are well-known algorithm to restrict positions to be inside
of the unit cell and to find the minimum distance between objects acoording to
the PBCs. In this paper, these algorithms are called as RestrictPosition and
RestrictVector, respectively.

### Representation of AABBs.

There are three common representations for AABBs (Figure 2) [7]. The first one
is by the minimum and maximum coordinate values in each dimension. The second
one is by the minimum point and the diameter from the corner point. The third
one is by the center point and a half of its diameter. Here, these are called
as min-max, min-widths, and center-radius representation, respectively.

Since the proposed method uses the center point of an AABB, the natural choice
is to use center-radius representation even though the center point can be
calculated by using the other representation.

Figure 2:  (A) Three popular representations of an AABB. The first one is min-
max, the second one is min-widths, and the third one is center-radius
representation. (B) Three representations in a system with PBCs. The AABBs are
colored in the same way as A.

### Expanding AABBs under PBCs.

Expanding an AABB in order to contain a new object is one of the most
important operations in an R-Tree algorithm. Because the total area covered by
the AABB of each node affects the efficiency of spatial searching, it is
needed to find a way to make it as small as possible.

The algorithm to expand an AABB needed to contain object AABB under PBCs is
shown in Algorithm 1. In this case, the size of an AABB that contains two
rectangles is determined by their radius and the minimum distance between
their center points. In this paper, this is accomplished by using
RestrictVector. On the other hand, when the contents are points, it is enough
to find the minimum distance between the center of an AABB and the
point(Algorithm 2).

Algorithm 1 expand AABB to contain another AABB

$R1\leftarrow$ AABB to be expanded

$R2\leftarrow$ rectangle to be contained

$B\leftarrow$ boundary

function ExpandAABB($R1,R2,B$)

$dc\leftarrow R2.center-R1.center$

$dc\leftarrow$ RestrictVector(dc, B)

$l1\leftarrow R1.center-R1.radius$

$u1\leftarrow R1.center+R1.radius$

$l2\leftarrow(R1.center+dc)-R2.radius$

$u2\leftarrow(R1.center+dc)+R2.radius$

$L\leftarrow\textsc{min}(l1,l2)$

$U\leftarrow\textsc{max}(u1,u2)$

$C\leftarrow(L+U)/2$

$HW\leftarrow(U-L)/2$

$C\leftarrow$ RestrictPosition(C, B)

return $\\{C,HW\\}$

end function

Algorithm 2 expand AABB to contain a point

$R\leftarrow$ AABB to be expanded

$P\leftarrow$ point to be contained

$B\leftarrow$ boundary

function ExpandAABB($R,P,B$)

$dc\leftarrow P-R.center$

$dc\leftarrow$ RestrictVector(dc, B)

$l\leftarrow R.center-R.radius$

$u\leftarrow R.center+R.radius$

$L\leftarrow\textsc{min}(l,P)$

$U\leftarrow\textsc{max}(u,P)$

$C\leftarrow(L+U)/2$

$HW\leftarrow(U-L)/2$

$C\leftarrow$ RestrictPosition(C, B)

return $\\{C,HW\\}$

end function

### Finding an object under PBCs.

To find an object in an R-Tree, it is needed to check if two AABBs intersect
each other. This can be determined by calculating the minimum distance between
the centers of the rectangles(Algorithm 3). The inclusion can be detected in
the same way (Algorithm 4). For points, the intersection and inclusion means
almost same thing because points have no size. Here, the algorithm that checks
if a point is inside of an AABB is shown in Algorithm 5.

Algorithm 3 Check if two AABB intersect each other

$R1\leftarrow$ rectangle

$R2\leftarrow$ rectangle that might intersect to R1

$B\leftarrow$ boundary

function IntersectsAABB($R1,R2,B$)

$dc\leftarrow R1.center-R2.center$

$dc\leftarrow$ RestrictVector(dc, B)

return abs(dc) $\leq(R1.radius+R2.radius)$

end function

Algorithm 4 Check if an AABB is inside of another AABB

$R1\leftarrow$ rectangle

$R2\leftarrow$ rectangle that might be inside of R1

$B\leftarrow$ boundary

function IsAABBInsideOfAABB($R1,R2,B$)

$dc\leftarrow R1.center-R2.center$

$dc\leftarrow$ RestrictVector(dc, B)

return abs(dc) $\leq(R1.radius-R2.radius)$

end function

Algorithm 5 Check if a point is inside of an AABB

$R\leftarrow$ rectangle

$P\leftarrow$ point that might be inside of R

$B\leftarrow$ boundary

function IsPointInsideOfAABB($R,P,B$)

$dc\leftarrow R.center-P$

$dc\leftarrow$ RestrictVector(dc, B)

return abs(dc) $\leq R.radius$

end function

## Results

Figure 3A shows the expansion of an AABB to contain objects by using proposed
method and Figure 3B shows that of existing method. There, the objects are
colored in black, and the AABB is colored in red. It should be noted that,
because it sticks out of the boundaries, the periodic images of the AABB are
shown separately.

Comparing Figure 3A and B, it is shown that the proposed method successfully
finds least expansion under PBCs. Because the objects are distributed
throughout the system, if the AABB was expanded independently from the PBCs,
the AABB would wrap most of the area of the system(Figure 3B).

In Figure 3C the results of a query are shown. It successfully finds objects
that are located beyond the boundaries(indicted by arrows). As in Figure 3A,
the periodic images of the query are shown separately.

Figure 3:  (A) Expansion of the AABB(red) by proposed method. It can be seen
that the AABB is expanded beyond the boundary. (B) Expansion of the AABB by
existing method. The AABB wraps almost all the area of the system because the
AABB is expanded independently from PBCs. (C) The result of querying objects
that intersect with the yellow rectangle. The objects contained in the R-Tree
are shown as small square boxes and the ones intersecting the query box are
colored in red.

## Conclusion

In this paper, a novel method for applying PBCs to R-Trees was presented. This
method considers PBCs while inserting new objects and finding objects.
Therefore, no extra objects or queries are needed to consider PBCs. Moreover,
allowing AABBs to extend beyond the boundary, it has more chance to reduce the
volume of AABBs based on the PBCs.

As described before, since this method modifies only the algorithms to expand
an AABB and to detect intersection between AABBs, it is essentially applicable
to other R-Tree variants and to any spatial indexing method that works with
AABBs.

Because the application of spatial indexing generally increase the performance
of spatiotemporal simulations, the proposed method might be useful for
scientific simulations under PBCs.

## References

  * [1] Kouichi Takahashi, Kazunari Kaizu, Bin Hu, and Masaru Tomita.  A multi-algorithm, multi-timescale method for cell simulation.  Bioinformatics, 20(4):538–546, 2004.
  * [2] Antonin Guttman.  R-Trees: A Dynamic Index Structure for Spatial Searching.  Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD ’84, pages 47–57, 1984.
  * [3] Diane Greene.  An implementation and performance analysis of spatial data access methods.  The Fifth International Conference on Data Engineering, (4871), 1989\.
  * [4] Beckmann, Norbert and Kriegel, Hans-Peter and Schneider, Ralf and Seeger, Bernhard.  The r*-tree: An efficient and robust access method for points and rectangles.  19(2):322–331, 1990.
  * [5] Scott T Leuteneggert and Mario A Lopezt.  STR : A Simple and Efficient Algorithm for R-Tree Packing.  pages 497–506, 1997.
  * [6] Ryuya Mitsuhashi, Hideyuki Kawashima, Takahiro Nishimichi, and Osamu Tatebe.  Three-Dimensional Spatial Join Count Exploiting CPU Optimized STR R-Tree.  IEEE International Conference on Big Data, pages 2938–2947, 2016\.
  * [7] Christer Ericson.  Real-Time Collision Detection.  Morgan Kaufmann Publishers, 2004.