# Lower General Position in Cartesian Products

Eartha Kruft Welton a,b
<EMAIL_ADDRESS>Sharif Khudairi b
<EMAIL_ADDRESS>James Tuite a
<EMAIL_ADDRESS>
###### Abstract

A subset $S$ of vertices of a graph $G$ is in _general position_ if no
shortest path in $G$ contains three vertices of $S$. The _general position
problem_ consists of finding the number of vertices in a largest general
position set of $G$, whilst the _lower general position problem_ asks for a
smallest maximal general position set. In this paper we determine the lower
general position numbers of several families of Cartesian products. We also
show that the existence of small maximal general position sets in a Cartesian
product is connected to a special type of general position set in the factors,
which we call a _terminal set_ , for which adding any vertex $u$ from outside
the set creates three vertices in a line with $u$ as an endpoint. We give a
constructive proof of the existence of terminal sets for graphs with diameter
at most three. We also present conjectures on the existence of terminal sets
for all graphs and a lower bound on the lower general position number of a
Cartesian product in terms of the lower general position numbers of its
factors.

a School of Mathematics and Statistics, Open University, Milton Keynes, UK
b School of Mathematics, University of Cardiff, UK

Keywords: general position number; universal line; Cartesian product

AMS Subj. Class. (2020): 05C12, 05C69, 05C76

##  1 Introduction

The lower general position problem originates in the puzzles of two of the
best known recreational mathematicians of modern history, Henry Dudeney and
Martin Gardner. Dudeney posed the following chessboard puzzle in [8]: how many
pawns can be placed on an $n\times n$ chessboard if we do not allow any three
pawns to lie on a common line in the plane? In Gardner’s column in Scientific
American [10], he suggested investigating the ‘worst-case scenario’ of this
problem by finding the smallest no-three-in-line configurations of pawns on
the chessboard that cannot be extended by adding another pawn.

The no-three-in-line problem was extended to the setting of graph theory in
[3, 16]. A set $S$ of vertices of a graph $G$ is in _general position_ if no
shortest path of $G$ contains more than two vertices of $S$. The _general
position number_ $\operatorname{gp}(G)$ is the cardinality of a largest
general position set of $G$. Inspired by Gardner’s suggestion, a recent paper
[7] studied the _lower position number_ $\operatorname{gp}^{-}(G)$ of a graph,
which the authors defined to be the number of vertices in a smallest maximal
general position set of $G$. The lower general position number can be seen as
representing the worst-case output of a greedy search for general position
sets.

There are several papers on the general position numbers of the Cartesian
product of graphs. The first paper to treat this problem was [11]; in this
article the lower bound
$\operatorname{gp}(G\operatorname{\,\square\,}H)\geq\operatorname{gp}(G)+\operatorname{gp}(H)-2$
is deduced and this is used to find a lower bound on the general position
number of the product of an arbitrary number of complete graphs. In [13] the
authors determine the exact values of the general position numbers of cylinder
graphs $P_{r}\operatorname{\,\square\,}C_{s}$ and strong bounds for torus
graphs $C_{r}\operatorname{\,\square\,}C_{s}$, as well as counting all maximum
general position sets in a Cartesian grid
$P_{r}\operatorname{\,\square\,}P_{s}$ and giving lower bounds for Cartesian
powers. The paper [21] discusses the case when one of the factors has a small
diameter and in [22] the general position number of the product of two trees
is determined. The latest work on this subject [14] largely resolves the
general position problem in torus graphs and gives some partial results on
hypercubes.

More recently, variants of the general position problem have been investigated
for Cartesian products; they are treated in the context of the mutual
visibility problem in [5] and [15], the edge general position problem in [17]
and the monophonic position problem in [18] (for background on the mutual
visibility and monophonic position problems, consult [6] and [20]
respectively).

In this paper we study the lower general position problem in Cartesian
products. We demonstrate that this problem is connected with a special type of
general position set in a graph, which we call a _terminal set_. In Section 2
we present a bound on the lower general position number of Cartesian products
using terminal sets and use this to derive some exact values. We also discuss
products with complete graphs and give a conjecture for a lower bound on the
lower general position number of a Cartesian product. In Section 3 we tackle
the problem of the existence of terminal sets and show that they always exist
in graphs with diameters at most three using an algorithmic proof. We also
demonstrate existence for chordal graphs and cographs and conclude with a
conjecture on the existence of terminal sets. Finally in Section 4 we derive
some exact values for the largest and smallest order of terminal position sets
in some common graph families and apply this to find the lower general
position number of the product of complete multipartite graphs.

Throughout this paper a graph $G$ will mean a simple, undirected graph, with
vertex set $V(G)$ and edge set $E(G)$. We will write $u\sim v$ if the vertices
$u,v\in V(G)$ are adjacent. The neighbourhood of $u$ is the set $N(u)=\\{v\in
V(G):u\sim v\\}$. Two vertices $u,v$ are _twins_ if they have the same
neighbourhood, i.e. $N(u)=N(v)$. A graph $H$ is a subgraph of $G$ if
$V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$; a subgraph $H$ of $G$ is
_induced_ if for any $u,v\in V(H)$ we have $u\sim v$ in $H$ if and only if
$u\sim v$ in $G$. For any subset $W\subseteq V(G)$ the subgraph of $G$ induced
by $W$ will be written $G[W]$. The _line graph_ $L(G)$ of $G$ is the graph
with vertex set equal to $E(G)$, with an edge in $L(G)$ between
$e_{1},e_{2}\in E(G)$ if and only if $e_{1}$ and $e_{2}$ are incident to a
common vertex.

A path $P_{\ell+1}$ of length $\ell$ in $G$ is a sequence
$u_{0},u_{1},\dots,u_{\ell}$ of distinct vertices of $G$ such that $u_{i}\sim
u_{i+1}$ for $0\leq i\leq\ell-1$. The distance $d(u,v)$ between two vertices
$u$ and $v$ of $G$ is the length of a shortest path from $u$ to $v$; if we
wish to specify in which graph the distance is taken we will include a
subscript, e.g. $d_{G}(u,v)$. The greatest value of $d(u,v)$ over all pairs of
vertices $u,v$ in $G$ is the _diameter_ $\operatorname{diam}(G)$ of $G$. A
cycle of length $\ell$ is a sequence $u_{0},u_{1},\dots,u_{\ell-1}$ such that
$u_{i}\sim u_{i+1}$ for $1\leq i\leq\ell-2$ and $u_{0}\sim u_{\ell-1}$. The
wheel graph $W_{n}$ is the join $C_{n-1}\vee K_{1}$, i.e. a cycle of length
$n-1$ with an added vertex that is adjacent to every vertex of the cycle. A
graph is _chordal_ if all of its induced cycles have length three
(equivalently, any cycle with length at least four has a chord). A graph is a
_cograph_ if it does not contain any induced copies of $P_{4}$.

A set $S$ of vertices of $G$ is _geodetic_ if for any vertex $u\in V(G)-S$
there exist vertices $x,y\in S$ such that $u$ lies on a shortest $x,y$-path in
$G$; the number of vertices in a smallest geodetic set of $G$ is the _geodetic
number_ of $G$ and is denoted by $\operatorname{g}(G)$. A clique or complete
graph $K_{n}$ is a graph on $n$ vertices such that every pair of distinct
vertices is adjacent. More generally, a complete multipartite graph
$K_{r_{1},r_{2},\dots,r_{t}}$ is a graph such that the vertex set can be
partitioned into independent sets $X_{1},X_{2},\dots,X_{t}$, where
$|X_{i}|=r_{i}$ for $1\leq i\leq t$, such that $u\sim v$ if and only if $u$
and $v$ lie in different parts of the partition.

The Cartesian product $G\operatorname{\,\square\,}H$ of two graphs $G$ and $H$
is defined to be the graph with vertex set $V(G)\times V(H)$ and an edge
between vertices $(u_{1},v_{1})$ and $(u_{2},v_{2})$ if and only if either i)
$u_{1}=u_{2}$ and $v_{1}\sim v_{2}$ in $H$ or ii) $u_{1}\sim u_{2}$ in $G$ and
$v_{1}=v_{2}$. For any $h\in V(H)$, the subgraph of
$G\operatorname{\,\square\,}H$ induced by $V(G)\times\\{h\\}$ is isomorphic to
$G$; we call this subgraph a _$G$ -layer_ of $G\operatorname{\,\square\,}H$
and denote it by $G^{h}$. Similarly, a $H$-layer ${}^{g}H$ is the subgraph of
$G\operatorname{\,\square\,}H$ induced by the subset $\\{g\\}\times V(H)$ of
$V(G)\times V(H)$ and is isomorphic to $H$. If $P$ is a path
$u_{0},u_{1},\dots,u_{\ell}$ in $G$, then for any $v\in V(H)$ the path
$(u_{0},v),(u_{1},v),\dots,(u_{\ell},v)$ in $G\operatorname{\,\square\,}H$
will be written $P_{v}$, with a similar notation ${}_{u}Q$ for $u\in V(G)$ and
a path $Q$ in $H$. The operation $\operatorname{\,\square\,}$ is associative
and commutative (up to isomorphism), so in Cartesian products of three or more
factors we will drop brackets. The distance between vertices
$(u,v),(u^{\prime},v^{\prime})\in V(G\operatorname{\,\square\,}H)$ is given by

$d_{G\operatorname{\,\square\,}H}((u,v),(u^{\prime},v^{\prime}))=d_{G}(u,u^{\prime})+d_{H}(v,v^{\prime}).$

We define the projection functions
$\pi_{1}:G\operatorname{\,\square\,}H\rightarrow G$ and
$\pi_{2}:G\operatorname{\,\square\,}H\rightarrow H$ by $\pi_{1}(x,y)=x$ and
$\pi_{2}(x,y)=y$ for all $(x,y)\in V(G)\times V(H)$. For a detailed discussion
of the structure of Cartesian products, see the book [12]. For other graph-
theoretical terminology not defined here, we refer the reader to [2].

##  2 Bounds and exact values

In this section we introduce the notion of _terminal set_ and its applications
to finding small general position sets in Cartesian products. It was shown in
[7] that a graph $G$ has a maximal general position set of order two, i.e.
$\operatorname{gp}^{-}(G)=2$, if and only if $G$ contains a _universal line_.
The line ${\cal L}(u,v)$ of $G$ induced by two vertices $u,v\in V(G)$ is
defined to be

$\\{w\in V(G):\ d(u,v)=d(u,w)+d(w,v)\ {\rm or}\ d(u,v)=|d(u,w)-d(w,v)|\\}.$

The line ${\cal L}(u,v)$ is _universal_ if it contains every vertex of $G$.
More generally, universal lines are of interest in the setting of metric
spaces and are connected to the Chen-Chvátal Conjecture (see [4, 19]).

The article [19] gave the following necessary and sufficient condition for the
existence of a universal line in a Cartesian product.

######  Theorem 2.1.

For two graphs $G$ and $H$, the Cartesian product
$G\operatorname{\,\square\,}H$ contains a universal line if and only if either

  1. (i)

$G$ or $H$ has a maximal general position set consisting of two adjacent
vertices, or

  2. (ii)

$\operatorname{g}(G)=2$ and $\operatorname{g}(H)=2$.

As shown in [7] and [19], any bipartite graph or any graph with a bridge
contains two adjacent vertices that form a universal line; hence any Cartesian
product $G\operatorname{\,\square\,}H$ containing such a factor $G$ or $H$
will satisfy the conditions of Theorem 2.1, implying that
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)=2$. In particular, if
either of the factors of $G\operatorname{\,\square\,}H$ is a tree or an even
cycle, the product will contain a universal line. Hence for many of the
families of Cartesian product graphs discussed in the preceding section the
lower general position number follows easily from known results; hence for
interesting problems we will have to look to more complicated families. We
will treat the case of an odd cycle factor in Corollary 2.4.

In the case i) of Theorem 2.1 that either $G$ or $H$ has a maximal general
position set consisting of a pair of adjacent vertices, note that
$G\operatorname{\,\square\,}H$ has a maximal general position set of order two
contained within a single layer. This suggests the following question: can we
always find a small maximal general position set of
$G\operatorname{\,\square\,}H$ within a single $G$\- or $H$-layer? A subset
$S$ of a $G$-layer $G^{h}$ will be in general position in
$G\operatorname{\,\square\,}H$ only if $S$ is a general position set of $G$,
so any maximal general position set of $G\operatorname{\,\square\,}H$
belonging to a single $G$-layer must be a maximal general position set of $G$.
However, that $S$ is a maximal general position set of $G$ does not
necessarily imply that $S\times\\{h\\}$ is a maximal general position set in
the product $G\operatorname{\,\square\,}H$. We now present the extra property
that a maximal general position set $S$ of $G$ must satisfy in order for a
copy $S\times\\{h\\}$ of $S$ in a $G$-layer $G^{h}$ to be a maximal general
position set of $G\operatorname{\,\square\,}H$.

######  Definition 2.2.

A _terminal set_ of a graph $G$ is a maximal general position set $S$ such
that for any vertex $u\in V(G)-S$ there is a shortest path of $G$ that
contains $u$ as an endpoint as well as at least two vertices of $S$. The
number of vertices in a largest terminal set will be denoted by
$\operatorname{tp}(G)$ and the number of vertices in a smallest terminal set
by $\operatorname{tp}^{-}(G)$. If there is no such set, then we write
$\operatorname{tp}^{-}(G)=\operatorname{tp}(G)=\infty$.

An example of a terminal position set is shown in Figure 1. As a terminal set
is a maximal general position set, we have
$\operatorname{tp}(G)\geq\operatorname{tp}^{-}(G)\geq\operatorname{gp}^{-}(G)$
for any graph $G$. Hence for any complete graph
$\operatorname{tp}(K_{n})=\operatorname{tp}^{-}(K_{n})=n$. If $S$ is a (not
necessarily maximal) general position set of $G$, then we will say that a
vertex $u\in V(G)-S$ is _terminal with respect to $S$_, or _$S$ -terminal_ for
short, if there is a shortest path with $u$ as an endpoint that contains two
vertices of $S$; we will refer to such a path as a _$(u,S)$ -bad path_.

Figure 1: The Petersen graph with a terminal position set (red). Any vertex
outside the set of red vertices is the endpoint of a shortest path containing
two red vertices.

######  Lemma 2.3.

Let $G$ and $H$ be graphs with order at least two. If $S$ is a maximal general
position set of $G$ and $h\in V(H)$, then $S\times\\{h\\}$ is a maximal
general position set of $G\operatorname{\,\square\,}H$ if and only if $S$ is a
terminal position set of $G$ (with a similar result for the factor $H$).
Hence, for any Cartesian product

$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\leq\min\\{\operatorname{tp}^{-}(G),\operatorname{tp}^{-}(H)\\}.$

###### Proof.

Firstly, suppose that $S$ is a maximal general position set of $G$, but that
there is a vertex $w\in V(G)-S$ such that there is no $(w,S)$-bad path. Then
for any vertex $h\in V(H)$ the set $S\times\\{h\\}$ is not a maximal general
position set of $G\operatorname{\,\square\,}H$, as for any $h^{\prime}\in
V(H)-\\{h\\}$ the vertex $(w,h^{\prime})$ can be added to $S\times\\{h\\}$
without violating the no-three-in-line property.

Conversely, let $S$ be a terminal set in $G$ and consider the set
$S^{\prime}=S\times\\{v\\}$ for any $v\in V(H)$. By definition, $S$ is a
maximal general position set of $G$, so $S^{\prime}$ is in general position in
$G\operatorname{\,\square\,}H$ and adding a further vertex from the layer
$G^{v}$ would create three-in-a-line. Suppose that we add a vertex
$(u^{\prime},v^{\prime})$ to $S^{\prime}$, where $v^{\prime}\neq v$. Let $P$
be a shortest $v,v^{\prime}$-path in $H$. If $u^{\prime}\not\in S$, then let
$Q$ be a $(u^{\prime},S)$-bad path, i.e. $Q$ is a shortest path with
$u^{\prime}$ as an endpoint and containing two vertices of $S$; otherwise, if
$u^{\prime}\in S$, $Q$ can be any shortest path from $u^{\prime}$ to a vertex
of $S$. Now the concatenated path ${}_{u^{\prime}}P,Q_{v}$ is a shortest path
in $G\operatorname{\,\square\,}H$ that contains three vertices of
$S^{\prime}\cup\\{(u^{\prime},v^{\prime})\\}$. Thus $S^{\prime}$ is a maximal
general position set of $G\operatorname{\,\square\,}H$ and
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\leq\operatorname{tp}^{-}(G)$
and similarly
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\leq\operatorname{tp}^{-}(H)$.
∎

This allows us to immediately settle the question of the lower general
position problem when one of the factors is a cycle or a wheel.

######  Corollary 2.4.

For any graph $H$ and any odd $r$,
$\operatorname{gp}^{-}(C_{r}\operatorname{\,\square\,}H)=3$, unless $H$ has a
universal line consisting of two adjacent vertices.

###### Proof.

By Theorem 2.1 the product $C_{r}\operatorname{\,\square\,}H$ will not have a
universal line unless $H$ has a maximal general position set consisting of two
adjacent vertices, so in all other cases
$\operatorname{gp}^{-}(C_{r}\operatorname{\,\square\,}H)\geq 3$. However a
pair of adjacent vertices in $C_{r}$, together with the corresponding
antipodal vertex, forms a terminal set in $C_{r}$, so by Lemma 2.3 we obtain
the upper bound $\operatorname{gp}^{-}(C_{r}\operatorname{\,\square\,}H)\leq
3$, establishing the result. ∎

Products with one factor a wheel graph can be dealt with in a similar fashion,
since $\operatorname{g}(W_{n})>2$ for $n\geq 6$. In this case any triangle is
a terminal set.

######  Corollary 2.5.

For $n\geq 6$, $\operatorname{gp}^{-}(W_{n}\operatorname{\,\square\,}H)=3$,
unless $H$ has a maximal general position set consisting of two adjacent
vertices.

We now show that Lemma 2.3 is tight for products
$K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}\operatorname{\,\square\,}\cdots\operatorname{\,\square\,}K_{n_{k}}$
of an arbitrary number of complete graphs (of which a rook graph
$K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}$ is a particular instance). In
the article [11] it was shown that
$\operatorname{gp}(K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}\operatorname{\,\square\,}\cdots\operatorname{\,\square\,}K_{n_{k}})\geq
n_{1}+n_{2}+\dots+n_{k}-k$.

######  Theorem 2.6.

The lower general position number of the product of complete graphs is given
by

$\operatorname{gp}^{-}(K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}\operatorname{\,\square\,}\cdots\operatorname{\,\square\,}K_{n_{k}})=\min\\{n_{1},n_{2},\dots,n_{k}\\}.$

###### Proof.

Suppose without loss of generality that
$\min\\{n_{1},n_{2},\dots,n_{k}\\}=n_{k}$. By Lemma 2.3 it follows that

$\operatorname{gp}^{-}(K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}\operatorname{\,\square\,}\cdots\operatorname{\,\square\,}K_{n_{k}})\leq
n_{k}.$

Suppose that $S$ is a general position set of
$K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}\operatorname{\,\square\,}\cdots\operatorname{\,\square\,}K_{n_{k}}$
with order strictly less than $n_{k}$. As $|S|<n_{k}$, there exists a vertex
$(u_{1},\dots,u_{k})$ such that for any $(v_{1},\dots,v_{k})\in S$ we have
$v_{i}\neq u_{i}$ for $1\leq i\leq k$. Therefore the distance of
$(u_{1},\dots,u_{k})$ from every vertex of $S$ is
$k=\operatorname{diam}(K_{n_{1}}\operatorname{\,\square\,}K_{n_{2}}\operatorname{\,\square\,}\cdots\operatorname{\,\square\,}K_{n_{k}})$.
Thus the vertex $(u_{1},u_{2},\dots,u_{k})$ could be added to $S$ whilst
maintaining the no-three-in-line property, so that $S$ is not maximal. ∎

The general position sets of products of a general graph with a clique
suggests the notion of ‘orthogonal general position sets’, which may be of
independent interest.

######  Definition 2.7.

Two (not necessarily disjoint) general position sets $S_{1}$ and $S_{2}$ are
_orthogonal_ if any shortest path starting in $S_{1}$ and ending in $S_{2}$
contains just two vertices of the multiset $S_{1}\cup S_{2}$.

Note that if there is a vertex in $S_{1}\cap S_{2}$, then this would be
counted twice if it occurs in a shortest path. Hence if $S_{1}\cap
S_{2}\neq\emptyset$, then at least one of $S_{1},S_{2}$ must contain just one
vertex. A couple of examples of orthogonal general position sets are shown in
Figure 2.

Figure 2: Examples of orthogonal general position sets in a cycle and a star
(one set in red and the other in blue).

It is easily seen that there is a one-to-one correspondence between maximal
collections of $r$ orthogonal general position sets of $G$ and the $r$ layers
of maximal general position sets in $G\operatorname{\,\square\,}K_{r}$; we
omit the simple proof.

######  Lemma 2.8.

A subset $S\subseteq V(G\operatorname{\,\square\,}K_{r})$ is in general
position if and only if the projections onto $G$ of the intersections of $S$
with the $G$-layers form a collection of orthogonal general position sets of
$G$.

In general however, the lower general position number of a product
$G\operatorname{\,\square\,}H$ and the bound of Lemma 2.3 can be arbitrarily
far apart.

######  Proposition 2.9.

For any $r\geq 2$, there exist graphs $G$ and $H$ such that
$G\operatorname{\,\square\,}H$ has a universal line and
$\min\\{\operatorname{tp}^{-}(G),\operatorname{tp}^{-}(H)\\}=r$.

###### Proof.

For a given $r\geq 2$, take $G$ and $H$ to be $K_{r+1}^{-}$, i.e. a complete
graph $K_{r+1}$ with one edge deleted. If the deleted edge is $uv$, then
$\\{u,v\\}$ induces a universal line in $K_{r+1}^{-}$; hence by condition ii)
of Theorem 2.1 we know that
$\operatorname{gp}^{-}(K_{r+1}^{-}\operatorname{\,\square\,}K_{r+1}^{-})=2$,
whilst it is easily seen that the smallest terminal sets in $K_{r+1}^{-}$ have
order $r$. ∎

We close with a conjectured lower bound for
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)$; this has been verified
computationally for all pairs $G,H$, where $G$ and $H$ both have order at most
six [9].

######  Conjecture 2.10.

For any graphs $G$ and $H$,

$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\geq\min\\{\operatorname{gp}^{-}(G),\operatorname{gp}^{-}(H)\\}.$

##  3 Existence of terminal sets

The bound of Lemma 2.3 raises the following important question: does every
graph have a terminal set? This question turns out to be quite deep. In the
following two theorems we give a constructive proof of the existence of a
terminal set for any graph with diameter at most three.

######  Theorem 3.1.

Every graph with diameter two has a terminal set.

###### Proof.

Note that a subset $S\subset V(G)$ of a graph $G$ with diameter two is in
general position if and only if it is an independent union of cliques. We
construct such a set in a greedy way. We start with a maximum clique $W_{1}$.
Then for $W_{2}$ we take the largest clique that has no edges to $W_{1}$ and,
in general, we take $W_{i}$ to be the largest clique that has no edges to
$W_{1}\cup W_{2}\cup\dots\cup W_{i-1}$. When this process terminates, we are
left with a maximal independent union of cliques $W$.

It remains to show that any vertex $x\notin W$ is the endpoint of a shortest
path containing two vertices of $W$. As $x$ was not selected by the algorithm,
it must have an edge to some vertex of $W$. Let $r$ be the smallest value such
that $x$ has an edge to $W_{r}$. If $x$ was adjacent to every vertex of
$W_{r}$, then, since $x$ has no edge to $W_{1}\cup\dots\cup W_{r-1}$, we would
have added it to $W_{r}$ at that stage of the greedy algorithm; thus there are
$y,z\in W_{r}$ such that $x\sim y$ and $x\not\sim z$, so that $x,y,z$ is a
shortest path containing three points of $W\cup\\{x\\}$. ∎

######  Theorem 3.2.

Every graph with diameter three contains a terminal set.

###### Proof.

Let $G$ be a graph with diameter three. We give an algorithm to construct a
terminal set in $G$. We begin by setting $W_{1}$ to be any maximal clique in
$G$. Once we have selected cliques $W_{1},W_{2},\dots,W_{j-1}$, we add a new
clique $W_{j}$ as follows. Set $S_{j-1}=\bigcup_{1\leq i\leq j-1}V(W_{i})$.
For $1\leq i\leq j-1$, say that a vertex $v$ is $W_{i}$-equidistant if
$d(v,w)=d(v,w^{\prime})$ for any $w,w^{\prime}\in W_{i}$. If $v$ is not
$W_{i}$-equidistant for some $1\leq i\leq j-1$, then $v$ is
$S_{j-1}$-terminal. Let $T_{j-1}$ be the set of vertices of $G$ that are
$W_{i}$-equidistant for $1\leq i\leq j-1$ such that there are no edges between
$T_{j-1}$ and $S_{j-1}$ (so that every vertex of $T_{j-1}$ is at distance two
or three from $S_{j-1})$. Within $T_{j-1}$, let $R$ be a maximal clique (i.e.
it may not be maximal within $G$, but no further vertices can be added to $R$
from $T_{j-1}$).

Notice that for some $i$ we could have some vertices in $R$ that are at
distance two from $W_{i}$ and some that are at distance three from $W_{i}$. We
refine the set $R$ so that this situation does not occur. For
$i=1,2,\dots,j-1$, if there are vertices at distance two and distance three
from $W_{i}$, then we remove from $R$ all of the vertices at distance three
from $W_{i}$. We set $W_{j}$ to be the set that results once this refining
process has been completed. Note that $W_{j}$ will be non-empty if $R$ was
non-empty, since any single vertex from $T_{j-1}$ would satisfy this
condition.

When $T_{j-1}$ is empty, the algorithm terminates. We claim that the resulting
collection of cliques $S$ is a terminal set. Certainly $S$ is in general
position, since if $W,W^{\prime}$ are cliques of $S$, then either the distance
between any vertex of $W$ and any vertex of $W^{\prime}$ is two, or else the
distance between any vertex of $W$ and any vertex of $W^{\prime}$ is three.
Suppose that $u\in V(G)-V(S)$. If $u$ is not $W$-equidistant for some clique
$W$ of $S$, then $u$ is $S$-terminal, so we can assume that $u$ is
$W$-equidistant for every clique $W$ of $S$. If there is no edge from $u$ to
$S$, then $u$ could have been added as the next stage of the algorithm, a
contradiction; therefore, let $r=\min\\{i:u\sim W_{i},W_{i}\subseteq S\\}$. As
$u$ is $W_{r}$-equidistant, $W_{r}\cup\\{u\\}$ is a clique; in particular, as
$W_{1}$ is a maximum clique of $G$, we must have $r>1$.

If follows that $u$ must have been deleted in the refining process during the
$r$-th stage of the algorithm. Hence there must be an $s<r$ such that
$d(w,w^{\prime})=2$ and $d(w,u)=3$ for all $w\in W_{s}$, $w^{\prime}\in
W_{r}$; however, this implies that $u$ is $S$-terminal, as it is the initial
vertex of a shortest path of length three to $W_{s}$ that passes through
$W_{r}$. It follows that $S$ is a terminal set. ∎

It has also been verified computationally that all graphs with order at most
eleven have terminal sets [9]. We make the following conjecture.

######  Conjecture 3.3.

Every graph has a terminal set.

The following lemma gives some information on the properties of a hypothetical
minimal graph that does not contain a terminal set.

######  Lemma 3.4.

If $G$ does not have a terminal set, but every proper isometric subgraph of
$G$ does contain a terminal set, then

  * •

$G$ is connected,

  * •

$G$ has no simplicial vertices,

  * •

no cut-set of $G$ is a clique,

  * •

$G$ is twin-free.

###### Proof.

Let $G$ be as described. In particular, $G$ is not a clique. It is trivial
that $G$ is connected, for otherwise taking the union of terminal sets of the
components of $G$ would yield a terminal set of $G$.

Suppose that $G$ has a simplicial vertex $u$. The graph $G-u$ is an isometric
subgraph of $G$, so by assumption has a terminal set $S$. If $S=N(u)$, then
$u\cup N(u)$ is terminal in $G$. Otherwise, we now show that if we add the
vertex $u$ back to $G-u$, the set $S$ remains a terminal set. If $S\cap
N(u)=\emptyset$, then any vertex $v\in N(u)$ is the endpoint of a $(v,S)$-bad
path and adding the edge $uv$ gives a $(u,S)$-bad path. If $N(u)\subset S$,
then, as we can assume that $S\neq N(u)$, there is a vertex $w\in S-N(u)$ and
any shortest $u,w$-path would be a $(u,S)$-bad path, since it passes through
$N(u)\subset S$. Finally, we can suppose that $N(u)\cap S\neq\emptyset$ and
$N(u)-S\neq\emptyset$. In this case any $w_{2}\in N(u)-S$ is the endpoint of a
$(w_{2},S)$-bad path $P$; if $P$ passes through some $w_{1}\in N(u)\cap S$,
then replacing the initial edge $w_{2}w_{1}$ by $uw_{1}$ gives a $(u,S)$-bad
path, whereas if $P$ does not pass through $N(u)\cap S$, then adding the edge
$uw_{2}$ also yields a $(u,S)$-bad path. Therefore $G$ has no simplicial
vertex.

Now let $G$ be a minimal graph without a terminal set that has a clique $W$
that is also a cut-set. For each component $C$ of $G-W$ there is a terminal
set $S_{C}$ in $G[C\cup W]$. If $S_{C}\subseteq W$, then we must have
$S_{C}=W$. If $S_{C}=W$ is a terminal set of $G[C\cup W]$ for every component
$C$ of $G-W$, then $W$ is a terminal set of $G$. Otherwise, fix a component
$C$ of $G-W$ such that there is a terminal set $S_{C}$ of $G[C\cup W]$ with
$S_{C}\cap C\neq\emptyset$.

We now show that this $S_{C}$ is a terminal set of $G$, i.e. if $x\in
V(G-S_{C})$, then $x$ is the endpoint of an $(x,S_{C})$-bad path. As $G[C\cup
W]$ is an isometric subgraph of $G$, this is true by assumption if $x\in(C\cup
W)-S_{C}$, so suppose that $x\in C^{\prime}$, where $C^{\prime}$ is a
component of $G-W$ distinct from $C$. Consider the collection of shortest
paths from $x$ to the vertices of $S_{C}\cap C$. If any of these paths passes
through another vertex of $S_{C}$, in particular a vertex of $W\cap S_{C}$
(which may be empty), then we are done. Otherwise, let $P$ be a shortest path
from $x$ to a vertex $u\in S_{C}\cap C$. Set $w$ to be the first vertex of $P$
in $W$ and $P^{\prime}$ to be the $x,w$ section of $P$. As $w\not\in S_{C}$,
by assumption there is a $(w,S_{C})$-bad path $Q$ in $G[C\cup W]$, which is
also a $(w,S_{C})$-bad path in $G$. Consider the concatenated path
$P^{\prime},Q$ in $G$. The only reason that this would not be an
$(x,S_{C})$-bad path in $G$ is if the first edge of $Q$ is $w,w^{\prime}$,
where $w^{\prime}\in W$ and $d_{G}(x,w)=d_{G}(x,w^{\prime})$; in this case, we
can replace $P^{\prime}$ by a shortest $x,w^{\prime}$-path and obtain the
concatenated $(x,S_{C})$-bad path $P_{1},Q$.

Suppose finally that $G$ contains twins $x$ and $y$. Then $G-x$ is an
isometric subgraph and hence has a terminal set $S$ by assumption. If
$y\not\in S$, then $y$ is the endpoint of a $(y,S)$-bad path $P$, and changing
the initial point of $P$ to $x$ shows that $x$ would also be the endpoint of
an $(x,S)$-bad path, so that $S$ is terminal in $G$. If $y\in S$, but $S\cap
N(y)=\emptyset$, then $S\cup\\{x\\}$ is terminal in $G$. Finally, if $y\in S$
and $S\cap N(y)\neq\emptyset$, then if $x\not\sim y$, $x$ would be the
endpoint of a shortest path to $y$ via $S\cap N(y)$ and so $x$ would be
terminal with respect to $S$ in $G$, whilst if $x\sim y$, then $S\cup\\{x\\}$
would be a terminal set in $G$. ∎

The existence of a terminal set in any cograph $G$ follows from Theorem 3.1 by
taking the union of terminal sets of the components of $G$, each of which has
diameter at most two. Lemma 3.4 gives an alternative inductive proof for
cographs.

######  Corollary 3.5.

Every cograph has a terminal set.

###### Proof.

We perform induction on the order of the cograph $G$, beginning with $K_{1}$.
Every cograph contains a pair of twins $x,y$ and by the process described in
Lemma 3.4 combined with induction we can obtain a terminal set in $G$. ∎

More significantly, Lemma 3.4 also shows that any chordal graph has a terminal
set.

######  Corollary 3.6.

Every chordal graph has a terminal set.

###### Proof.

We prove the result by induction on the order. The basis follows trivially.
For the induction step, let $G$ be a chordal graph with order $n$. The graph
$G$ contains a simplicial vertex $u$ and $G-u$ is also chordal. As $G-u$ has a
terminal set by induction, the argument of Lemma 3.4 shows that $G$ also has a
terminal set. ∎

Observe that the inductive processes described in Corollaries 3.6 and 3.5 can
also be converted into polynomial time algorithms to construct a terminal set
in any chordal graph or cograph. It is an interesting question how far away
the orders of the sets produced by these algorithms and those in Theorems 3.1
and 3.2 can be from the lower terminal position number.

##  4 Values of the terminal position number

In this final section we determine the terminal and lower terminal position
numbers of some common graph families, namely Kneser graphs, line graphs of
complete graphs and complete multipartite graphs. These graphs have diameter
two (for sufficiently large order $n$), so the existence of a terminal set is
guaranteed by Theorem 3.1. We begin with a lemma on the structure of terminal
sets in diameter two graphs.

######  Lemma 4.1.

In a diameter two graph, no terminal set is an independent set.

###### Proof.

Suppose that $S$ is an independent set that is also a maximal general position
set. Let $u\in V(G)-S$. Then $u$ cannot be the initial vertex of a path of
length two that also contains two vertices of $S$, since this would imply that
these two vertices of $S$ are adjacent. ∎

The Kneser graph $K(n,2)$ is the graph with vertex set equal to all subsets of
order two of $\\{1,2,\dots,n\\}$; two such subsets
$A,B\subset\\{1,2,\dots,n\\}$ are adjacent in $K(n,2)$ if and only if $A\cap
B=\emptyset$. It was shown in [11] that for large enough $n$ the general
position number of the Kneser graph $K(n,2)$ is $n-1$, which corresponds to a
largest independent set, whereas the lower general position number is just six
for $n\geq 12$ [7]. The terminal position number lies strictly between these
two numbers for large enough $n$. Note that in this case the algorithm of
Theorem 3.1 gives the exact answer.

######  Theorem 4.2.

The terminal and lower terminal position numbers of the Kneser graph $K(n,2)$
are given by

$\operatorname{tp}(K(n,2))=\operatorname{tp}^{-}(K(n,2))=\left\\{\begin{array}[]{ll}6;&n=5,\\\
\left\lfloor\frac{n}{2}\right\rfloor;&n\geq 6.\end{array}\right.$

###### Proof.

We start with the Petersen graph $K(5,2)$. Let $S$ be a terminal set. As the
Petersen graph is triangle-free, by Lemma 4.1 $S$ induces $rK_{2}\cup sK_{1}$,
where $r\geq 1$. The general position set displayed in Figure 1 is terminal;
this set is also a largest possible general position set. It is also shown in
[7] that the lower general position number of the Petersen graph is four.
Suppose therefore that $S$ has order four or five. Observe that a vertex
outside $S$ is the initial point of a shortest path containing two vertices of
$S$ only if it is a neighbour of a vertex in one of the $r$ copies of $K_{2}$
induced by $S$. If $r=1$, then there are just four such vertices, which,
together with the vertices of $S$, accounts for at most nine vertices. If
$r=2$, then it follows from the fact that $K(5,2)$ has diameter two that the
neighbourhoods of the two copies of $K_{2}$ are identical, so this also
accounts for at most nine vertices. It follows that there are at least six
vertices in any terminal set of $K(5,2)$.

Now we may assume that $n\geq 6$. By Lemma 4.1 and the discussion in [11], it
follows that there are just two types of maximal general position set $S$ to
consider, a clique of order $\left\lfloor\frac{n}{2}\right\rfloor$ or a copy
of $3K_{2}$ induced by subsets of size two of a subset of $[n]$ of order four
(say all pairs of vertices from $\\{1,2,3,4\\}$). In the latter case, the
vertex $\\{5,6\\}$ is adjacent to every vertex of the general position set and
hence is not terminal with respect to $S$. Suppose that $S$ is a maximum
clique and let $\\{a,b\\}$ be any vertex outside the clique. Then there are
vertices of $S$, say $\\{a,c\\}$ and $\\{d,e\\}$, such that
$|\\{a,b\\}\cap\\{a,c\\}|=1$ and $\\{a,b\\}\cap\\{d,e\\}=\emptyset$, so that
$\\{a,b\\}$ is terminal with respect to $S$. ∎

The general and lower general position numbers of line graphs were studied in
[7] and [11]; in this case we show that the terminal position number coincides
with the general position number.

######  Theorem 4.3.

The terminal position number of $L(K_{n})$ is

$\operatorname{tp}(L(K_{n}))=\operatorname{gp}(L(K_{n}))=\left\\{\begin{array}[]{ll}n;&\text{
if }3|n,\\\ n-1;&\text{ otherwise}.\end{array}\right.$

For $n\geq 4$ the lower terminal position number is
$\operatorname{tp}^{-}(L(K_{n}))=n-1$.

###### Proof.

We will think of general position sets of $L(K_{n})$ in terms of edges of the
complete graph $K_{n}$ with vertex set $[n]$. It is shown in [11] that the
general position sets of $L(K_{n})$ correspond to disjoint unions of triangles
and stars in $K_{n}$ and that $\operatorname{gp}(L(K_{n}))=n$ if $n$ is
divisible by three and $\operatorname{gp}(L(K_{n}))=n-1$ otherwise. In order
for the general position set to be maximal, none of the stars can have order
three (otherwise such a star can be extended to a triangle) and every vertex
of $K_{n}$ is contained in an edge of $K_{n}$ lying in $S$, with the possible
exception of a single vertex of $K_{n}$ if the rest of $S$ consists of
triangles.

If $n\equiv 0\pmod{3}$, let $S$ be the disjoint union of $\frac{n}{3}$
triangles. If $n\equiv 1\pmod{3}$, we let $S$ be the disjoint union of
$\frac{n-1}{3}$ triangles, and finally if $n\equiv 2\pmod{3}$, we let $S$ be
the union of $\frac{n-2}{3}$ triangles and one other edge. These sets are
maximum general position sets. Now let $e$ be any edge of $K_{n}$ that does
not belong to one of these sets. Then $e$ must have at least one endpoint $x$
in a triangle $\\{x,y,z\\}$ of $S$ and $e,xy,yz$ is a shortest path in
$L(K_{n})$ from $e$ containing two vertices of $S$. Thus these general
position sets are terminal.

Now let $S$ be a smallest possible terminal set of $L(K_{n})$. $S$ can contain
at most one star; otherwise, observe that the edge of $K_{n}$ that connects
the centres of two stars would not be terminal with respect to $S$. Thus $S$
consists of a collection of triangles and at most one star, so that $|S|\geq
n-1$. Now for $n\geq 4$, let $S$ be the edges of a star in $K_{n}$ of order
$n$. Then any edge of $K_{n}$ not lying in $S$ connects two leaves $x,y$ of
the star and, if $z$ is any other leaf and $u$ is the centre of the star, then
$xy,xu,zu$ is a shortest path in $L(K_{n})$ from $xy$ through two other points
of $S$. ∎

For $L(K_{n})$ the output of the algorithm in Theorem 3.1 is $n-1$. We
conclude by examining complete multipartite graphs and their products.

######  Theorem 4.4.

For $r\geq 2$ and $n_{1}\geq n_{2}\geq\dots\geq n_{r}\geq 2$, the terminal
position number of a complete multipartite graph $K_{n_{1},n_{2},\dots,n_{r}}$
is given by

$\operatorname{tp}(K_{n_{1},n_{2},\dots,n_{r}})=\operatorname{tp}^{-}(K_{n_{1},n_{2},\dots,n_{r}})=r.$

###### Proof.

A maximal general position set $S$ in $K_{n_{1},n_{2},\dots,n_{r}}$ consists
either of all of the vertices in one of the partite sets, or else contains one
vertex from each of the partite sets (and thus induces a clique). If $S$ is
one of the partite sets, then no vertex of $V(K_{n_{1},n_{2},\dots,n_{r}})-S$
is terminal with respect to $S$. However, if $S$ contains one vertex from each
partite set, then any vertex $u\in V(K_{n_{1},n_{2},\dots,n_{r}})-S$ has a
shortest path to the vertex of $S$ lying in the same partite set via any other
vertex of $S$. Thus the terminal position sets of complete multipartite graphs
are the maximum cliques. ∎

Theorem 4.4 allows us to prove a realisation result that compares the lower
general position, terminal position and general position numbers.

######  Corollary 4.5.

For any $2\leq a\leq b\leq c$ there exists a graph $G$ with

$\operatorname{gp}^{-}(G)=a,\operatorname{tp}(G)=\operatorname{tp}^{-}(G)=b,\operatorname{gp}(G)=c.$

###### Proof.

By Theorem 4.4 a complete $b$-partite graph with smallest part of size $a$ and
largest part of size $c$ has the required parameters. ∎

Theorem 4.4 now enables us to find the lower general position numbers of a
wide range of Cartesian products of complete multipartite graphs. The results
of [19] show that the lower general position number of the product of two
complete multipartite graphs equals two if and only if either i) at least of
the graphs is a complete bipartite graph, or ii) both graphs have a part with
just two vertices.

######  Theorem 4.6.

Let $G=K_{m_{1},m_{2},\dots,m_{r}}$ and $H=K_{n_{1},n_{2},\dots,n_{s}}$ be
complete $r$\- and $s$-partite graphs respectively, where $r,s\geq 2$,
$m_{1}\geq m_{2}\geq\dots\geq m_{r}$, $n_{1}\geq n_{2}\geq\dots\geq n_{s}$ and
$m_{1},n_{1}\geq 2$. Then the lower general position number of
$G\operatorname{\,\square\,}H$ satisfies

$\min\\{r,s,m_{r},n_{s}\\}\leq\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\leq\min\\{r,s,\max\\{m_{r},n_{s}\\}\\}.$

If either $m_{r}=n_{s}$ or $\min\\{m_{r},n_{s}\\}\geq 8$, then

$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)=\min\\{r,s,m_{r},n_{s}\\}.$

###### Proof.

Let $G$ and $H$ be as described in the statement of the theorem. Denote the
parts of $G$ by $X_{1},X_{2},\dots,X_{r}$ and the parts of $H$ by
$Y_{1},Y_{2},\dots,Y_{s}$, where $|X_{i}|=m_{i}$ and $|Y_{j}|=n_{j}$ for
$1\leq i\leq r$ and $1\leq j\leq s$.

We start by showing that
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\geq\min\\{r,s,m_{r},n_{s}\\}$.
Suppose that $S$ is a maximal general position set of
$G\operatorname{\,\square\,}H$ with $|S|<\min\\{r,s,m_{r},n_{s}\\}$. Then
there are parts $X_{a}$ and $Y_{b}$, $1\leq a\leq r$, $1\leq b\leq s$, such
that $S\cap(X_{a}\times V(H))=S\cap(V(G)\times Y_{b})=\emptyset$. Consider a
vertex $(u,v)$ in $X_{a}\times Y_{b}$. As $(u,v)\notin S$, when we add $(u,v)$
to $S$ we must create three-in-a-line.

Any neighbour of $(u,v)$ must either have first coordinate in $X_{a}$ or
second coordinate in $Y_{b}$, so $(u,v)$ has no neighbours in $S$. The
diameter of $G\operatorname{\,\square\,}H$ is four and vertices
$(x,y),(x^{\prime},y^{\prime})$ are distance four apart in
$G\operatorname{\,\square\,}H$ if and only if $x,x^{\prime}$ are distinct
vertices of some $X_{i}$ and $y,y^{\prime}$ are distinct vertices of some
$Y_{j}$. Similarly, if $(x,y)$ and $(x^{\prime},y^{\prime})$ are at distance
three, then either $x,x^{\prime}$ are in the same part of $G$ and
$y,y^{\prime}$ are in different parts of $H$, or $x,x^{\prime}$ are in
different parts of $G$ and $y,y^{\prime}$ are in the same part of $H$. Hence
any vertex at distance three or four from $(u,v)$ has first coordinate in
$X_{a}$ or second coordinate in $Y_{b}$. It follows that all vertices of $S$
are at distance two from $(u,v)$ and so $(u,v)$ is not the endpoint of a
$((u,v),S)$-bad path.

Hence we can assume that $(u,v)$ is the midpoint of a shortest path $Q$ of
length four with both endpoints in $S$. Therefore the endpoints of $Q$ must be
of the form $(x_{1},y_{1})$, $(x_{2},y_{2})$, where $x_{1},x_{2}$ belong to
some $X_{c}\neq X_{a}$ and $x_{1}\neq x_{2}$, and likewise $y_{1},y_{2}$
belong to some $Y_{d}\neq Y_{b}$ and $y_{1}\neq y_{2}$. Considering the
shortest paths between vertices of $S\cap(X_{c}\times Y_{d})$, we see that $S$
cannot contain any vertex of $(V(G)-X_{c})\times(V(H)-Y_{d})$, and if
$(x,y)\in S\cap(X_{c}\times Y_{d})$, then
$S\cap(\\{x\\}\times(V(H)-Y_{d}))=S\cap((V(G)-X_{c})\times\\{y\\})=\emptyset$.

As $|S|<\min\\{r,s,m_{r},n_{s}\\}$, there exist $\tilde{x}\in
X_{c}-\pi_{1}(S)$ and $\tilde{y}\in Y_{d}-\pi_{2}(S)$. The vertex
$(\tilde{x},\tilde{y})$ is at distance at least three from any vertex of $S$,
so by the maximality of $S$ it must be the endpoint of an
$((\tilde{x},\tilde{y}),S)$-bad path $P$ of length four. The other endpoint
$(x^{\prime},y^{\prime})$ of $P$ must lie in $X_{c}\times Y_{d}$. However,
$(x^{\prime},y^{\prime})$ has no neighbours in $S$, so $P$ cannot be bad. It
follows that we could add the vertex $(\tilde{x},\tilde{y})$ to $S$ without
creating three-in-a-line, contradicting the maximality of $S$. Thus
$|S|\geq\min\\{r,s,m_{r},n_{s}\\}$.

We now consider the existence of maximal general position sets of
$G\operatorname{\,\square\,}H$ near the lower bound of
$\min\\{r,s,m_{r},n_{s}\\}$. We will write
$X_{r}=\\{x_{1},x_{2},\dots,x_{m_{r}}\\}$ and
$Y_{s}=\\{y_{1},y_{2},\dots,y_{n_{s}}\\}$ and will assume without loss of
generality that $n_{s}\geq m_{r}$. We know from Lemma 2.3 and Theorem 4.4 that
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\leq\min\\{r,s\\}$. The
set

$S=\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m_{r}},y_{m_{r}}),(x_{m_{r}},y_{m_{r}+1}),\dots,(x_{m_{r}},y_{n_{s}})\\}$

is a maximal general position set of order $n_{s}=\max\\{m_{r},n_{s}\\}$, so
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)\leq\min\\{r,s,\max\\{m_{r},n_{s}\\}\\}$.
Hence if $m_{r}=n_{s}$, then
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)=\min\\{r,s,m_{r},n_{s}\\}$.

Now suppose that $m_{r}=\min\\{m_{r},n_{s}\\}\geq 8$. Let $Y,Y^{\prime}$ be
distinct parts of $H$ and choose vertices $y_{1},y_{2}\in V(Y)$ and
$y_{3},y_{4}\in V(Y^{\prime})$. Then, setting
$X^{\prime}=X_{r}-\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$, it is easily
seen that the set

$S=\\{(x_{1},y_{1}),(x_{2},y_{1}),(x_{3},y_{2}),(x_{4},y_{2}),(x_{5},y_{3}),(x_{6},y_{3})\\}\cup(X^{\prime}\times\\{y_{4}\\})$

is a maximal general position set of order $m_{r}$. Hence if
$\min\\{m_{r},n_{s}\\}\geq 8$ we have the equality
$\operatorname{gp}^{-}(G\operatorname{\,\square\,}H)=\min\\{r,s,m_{r},n_{s}\\}$.
∎

## Acknowledgements

The research of Eartha Kruft Welton was part of an EPSRC summer internship
with the Open University (Project: General Position Problems for Graphs). The
first and second authors are students at the University of Cardiff. The
authors thank Grahame Erskine, Sandi Klavžar and Ismael Yero for helpful
discussions of these results.

## References

  * [1] B.S. Anand, U. Chandran S.V., M. Changat, S. Klavžar, E.J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019) 84–89.
  * [2] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, London: Macmillan, Vol. 290 (1976).
  * [3] U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
  * [4] X. Chen, V. Chvátal, Problems related to a De Bruijn-Erdős theorem, Discrete Appl. Math. 156 (2008) 2101–2108.
  * [5] S. Cicerone, G. Di Stefano, S. Klavžar, On the mutual visibility in Cartesian products and triangle-free graphs, Appl. Math. Comput. 438 (2023) 127619.
  * [6] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) 126850.
  * [7] G. Di Stefano, S. Klavžar, A. Krishnakumar, J. Tuite & I.G. Yero, Lower general position sets in graphs, Discuss. Math. Graph Theory, to appear (2023) arXiv:2306.09965.
  * [8] H.E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh (1917).
  * [9] G. Erskine, personal communication (2023).
  * [10] M. Gardner, Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer, Sci. Amer. 235 (1976) 131–137.
  * [11] M. Ghorbani, H.R. Maimani, M. Momeni, F.R. Mahid, S. Klavžar, G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
  * [12] W. Imrich, S. Klavžar, D.F. Rall, Topics in Graph Theory. Graphs and their Cartesian Product, A K Peters, Ltd., Wellesley, MA, (2008).
  * [13] S. Klavžar, B. Patkós, G. Rus, I.G. Yero, On general position sets in Cartesian products, Results Math. 76 (3) (2021) 123.
  * [14] D. Korže, A. Vesel, General position sets in two families of Cartesian product graphs, Mediterr. J. Math. 20 (4) (2023) 203.
  * [15] D. Korže, D., A. Vesel, Mutual-visibility sets in Cartesian products of paths and cycles, (2023) arXiv preprint arXiv:2309.15201.
  * [16] P. Manuel, S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187.
  * [17] P. Manuel, R. Prabha, S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022) 2997–3009.
  * [18] P.K. Neethu, U. Chandran S.V., J. Tuite, On monophonic position sets in Cartesian products, preprint.
  * [19] J.A. Rodríguez-Velázquez, Universal lines in graphs, Quaest. Math. 45 (2022) 1485–1500.
  * [20] E.J. Thomas, U. Chandran S.V., J. Tuite, G. Di Stefano, On monophonic position sets in graphs, Discrete Appl. Math. (2023) doi.org/10.1016/j.dam.2023.02.021
  * [21] J. Tian, K. Xu, The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021) 126206.
  * [22] J. Tian, K. Xu, S. Klavžar, The general position number of the Cartesian product of two trees, Bull. Aust. Math. Soc. 104 (1) (2021) 1–10.


# Uniform Anderson Localization in One-Dimensional Floquet Maps

Ihor Vakulchyk  Center for Theoretical Physics of Complex Systems, Institute
for Basic Science (IBS), Daejeon 34126, Republic of Korea  Basic Science
Program, Korea University of Science and Technology (UST), Daejeon, Korea,
34113

###### Abstract

Anderson localization in discrete-time quantum map dynamics shows unique
features and provides significant numerical benefits. We propose a minimal
single-particle map in one dimension with nearest-neighbor hopping only and a
gapless spectrum. We demonstrate that strong disorder in a local phase field
leads to the universality of Anderson localization within the spectrum, such
that for every possible value of quasi-energy, localization happens in the
same way. We build an exact theory for the calculation of the localization
length, $1/L_{\text{loc}}=\left|\ln\left(|\sin(\theta)|\right)\right|$, that
is tunable between zero and infinity by variation of a control parameter
$\theta$ related to hopping.

Discrete-time quantum maps have been established as a powerful testbed for a
plethora of quantum and nonlinear phenomena. The map nature of evolution
provides remarkable numerical speeds that open the door to previously
inaccessible physical regimes, and this has been exploited in research on
localization, nonlinear delocalization, soliton formation, Lyapunov spectra
properties, and other phenomena. Moreover, maps can possess features that are
usually prohibited in continuous-time systems, such as one universal Anderson
localization length within the accessible spectrum. In this work, we propose a
simple model that exhibits this feature—Anderson localization universality in
a Floquet map—and characterize the phenomenon.

##  I Introduction

Anderson localization (AL) is a phenomenon of prohibited wave transport in
various non-interacting quantum systems when placed in an uncorrelated random
medium anderson1958absence ; lee1985disordered ; kramer1993localization ;
lifshits1982introduction . This is most notably expressed by all the states in
the Anderson phase being exponentially localized with the characteristic
length $L_{\text{loc}}$, called the localization length, which is determined
by the specifics of the given system. Since its discovery, AL has been studied
in applications to physical systems including photonic crystal waveguides
sapienza2010cavity , light Schwartz:2007aa ; lahini2008anderson , microwaves
Dalichaouch:1991aa , and ultrasound WEAVER1990129 ; Hu:2008aa . These and many
other examples indicate that AL is well understood in Hamiltonian systems,
where the spectra of the systems are defined on the real axis. This,
generally, leads to every state being uniquely classified by its energy $E$,
and the localization length becomes a function of the state
$L_{\text{loc}}(E)$. One notable counterexample is the Aubry–André model
aubry1980analyticity , where the underlying potential is pseudo-random (quasi-
periodic) and, due to self-similarity, the localization length is universal
for all eigenstates martinez2018quasiperiodic . Nevertheless, this does not
indicate the universality of the localization length within a continuous
portion of the energy spectrum, as its structure is fractal in this model.

Another somewhat less studied situation arises if the dynamics is not
continuous in time, thus representing a map. Such systems often result from
time-periodic Hamiltonians, i.e. their associated Floquet maps. One notable
example is the quantum kicked rotor, in which temporal behavior is strongly
connected to AL fishman1982chaos  and the corresponding localization length is
uniquely defined by the system parameters fishman1989scaling . Another example
is the discrete-time quantum walk (DTQW) aharonov1993quantum , a class of
systems discrete in both space and time. Under the application of a random
phase field, which uniformly covers the whole complex circle, the localization
length has a universal value for any quasi-energy vakulchyk2017anderson . In
addition to the emergence of such unique properties, quantum maps present
benefits for numerical studies, as the application of a map is much less
challenging than numerical integration malishava2020floquet ;
vakulchyk2019wave .

Figure 1:  Schematic visualization of the quantum map given by (II). The
vertical arrow represents time, and the boxes indicate the unit cells acted
upon.

In this work, we propose a new model representing a Floquet quantum map in one
dimension. Unlike previously studied models, it contains only nearest-neighbor
coupling and a gapless spectrum, so the suggested model is in a certain sense
a minimal one-dimensional quantum map. Using the transfer matrix approach, we
prove that there exist regimes with a universal localization length over the
whole spectrum. We provide an exact theory for the calculation of this
localization length based on the system parameters.

##  II Model

Consider a single particle on a periodic one-dimensional lattice with length
$N$ such that each unit cell contains two sites, or in other words, the
particle has a spinor degree of freedom. The wave function of such a system
reads
$\tilde{\Psi}=\\{\Psi_{1,+},\Psi_{1,-},\Psi_{2,+},...\Psi_{N,+},\Psi_{N,-}\\}$.
The Hilbert space can be factorized as a product of the direct space and the
spinor space, so $\Psi_{k,\pm}=\ket{k}\otimes\ket{\pm}$. We study a class of
time-periodic Hamiltonians that lead to specific Floquet maps defined on the
chain, and thus,

$\tilde{\Psi}(t+1)=\hat{S}\tilde{\Psi}(t),$ (1)

where time $t$ is measured in periods of evolution and $\hat{S}$ is the
Floquet map operator. Evolution of such a state $\tilde{\Psi}$ that both a)
preserves two sites per unit cell, i.e., is invariant under operation
$\sum_{k,\alpha=\pm}\ket{k,\alpha}\ket{k\pm 1,\alpha}$, and b) only involves
nearest-neighbor coupling in terms of the Floquet map, $\hat{S}$, can
generally (up to the definition of the unit cell) be written in the following
form:

$\displaystyle\hat{S}$ $\displaystyle=$
$\displaystyle\hat{S}_{1}\otimes\hat{S}_{2},$ $\displaystyle\hat{S}_{1}$
$\displaystyle=$
$\displaystyle\sum_{k,\alpha=\pm,\beta=\pm}u_{\alpha\beta}\ket{k,\alpha}\bra{k,\beta},$
$\displaystyle\hat{S}_{2}$ $\displaystyle=$
$\displaystyle\sum_{k,\alpha=\pm,\beta=\pm}v_{\alpha\beta}\ket{k,\alpha}\bra{k+l_{\beta},\beta},$
(2)

where $l_{\beta}=1$ if $\beta=+$ and 0 otherwise. Thus, two 2x2 matrices $u$
and $v$ contain the parameters defining the system. This evolution may be
easily understood in the following way. First, all the spinors are mapped by
$u$, then the wave function in the linear form is rotated left, after which
all the spinors are mapped by $v$, and finally the wave function is rotated
back. See the schematic representation in Fig. 1.

Figure 2:  Band structure from (4) for $\varphi=\varphi_{2}=0$ and
$\theta=0,\pi/4,\pi/2$ (red, blue, green).

One particular well-studied example of such a system is the DTQW. This can be
specifically achieved by setting $u$ as a $\mathcal{U}(2)$ matrix that
corresponds to a generalized DTQW coin chandrashekar2008optimizing , and
setting $v=\sigma^{(x)}$ ($\sigma$ is a Pauli matrix) to realize the so-called
shift operation of the DTQW.

In this paper, we are focused on the case when $u=v$. We take them as the most
general unitary matrices,

$u=v=e^{i\varphi}\begin{pmatrix}e^{i\varphi_{1}}\cos\theta&&e^{i\varphi_{2}}\sin\theta\\\
-e^{-i\varphi_{2}}\sin\theta&&e^{-i\varphi_{1}}\cos\theta\end{pmatrix},$ (3)

where $\theta,\varphi,\varphi_{1},\varphi_{2}$ are parameters characterizing
the system, with $\varphi$ being a potential-energy-like local field, and
$\theta$ a hopping-like parameter that controls coupling. Given translational
invariance, we can find the eigenstates as plain waves given by the ansatz
$\psi_{k}(n)=e^{-ikn}\\{\psi_{k,+},\psi_{k,-}\\}$. Defining the corresponding
eigenvalue of $\hat{S}$ as $e^{i\omega}$, where $\omega$ is the
eigenfrequency, we find the dispersion relation

$\cos(\omega-2\varphi)=\cos^{2}(\theta)+\cos(k-2\varphi_{2})\sin^{2}(\theta).$
(4)

Note that $\varphi$ shifts the frequency, $\varphi_{2}$ shifts the wavenumber,
and $\varphi_{1}$ is irrelevant. The band structure is presented in Fig. 2. It
generally constitutes two bands touching at $2\varphi_{2}$, where each is
exactly $0$ when $\theta=0$ and straight when $\theta=\pi/2$.

##  III Anderson localization

In this section, we study AL in the case of a random phase field applied to
each state component. We modify the translationally invariant evolution
defined by (3) by additionally multiplying each component $\Psi_{i,\alpha}$ by
$e^{i\phi_{i,\alpha}}$, where $\phi_{i,\alpha}$ are random numbers drawn
uniformly from $[-W/2,W/2)$ where $W$ is the strength of the disorder. This
modification is implemented by making the matrix $v$ unit-cell dependent.
Note, also, that while we present the result for random phases being
independent for each spinor component, the same results apply for unit-cell-
only dependent random phases.

The inverse localization length as a function of the eigenfrequency for
different values of disorder strength $W$ is depicted in Fig. 3. We notice
that for the maximum strength of disorder $W=\pi$, the localization length is
exactly the same for all the states in the spectrum. This can be explained by
the fact that such disorder smears all the frequencies uniformly over the
complex unit circle, making them indistinguishable. We will further study this
case.

To calculate the localization length, we use the transfer matrix approach. An
eigenstate with an eigenvalue $e^{i\omega}$ admits the following equation:

$\displaystyle\begin{pmatrix}\Psi_{n+1,+}\\\
\Psi_{n+1,-}\end{pmatrix}=T_{n}\begin{pmatrix}\Psi_{n,+}\\\
\Psi_{n,-}\end{pmatrix},$ (5) $\displaystyle
T_{n}=e^{2i\varphi}\begin{pmatrix}e^{i(\phi_{n+1,+}-\omega)}&&e^{-i(\varphi_{1}-\varphi_{2})}e^{i(\phi_{n+1,+}-\phi_{n,-})}\cot{\theta}(1-e^{i(\phi_{n,-}-\omega)})\\\
e^{i(\varphi_{1}-\varphi_{2})}\cot{\theta}(1-e^{i(\phi_{n+1,+}-\omega)})&&\sin^{-2}\theta
e^{-i(\phi_{n,-}-\omega)}+\cot^{2}\theta\left(e^{i(\phi_{n+1,+}-\omega)}-e^{i(\phi_{n+1,+}-\phi_{n,-})}-1\right)\end{pmatrix}.$

Figure 3:  Inverse localization length versus eigenfrequency of a state for
disorder strengths of $W=\pi/10,\pi/4,\pi/2,\pi$ (green, blue, red, black). In
this plot, $\varphi=\varphi_{1}=\varphi_{2}=0$.

Note that the transfer matrix $T_{n}$ is always unitary but symplectic if and
only if $\phi_{n+1,+}=\phi_{n,-}$. Also note that the transfer matrix is
invariant under $\phi\rightarrow\phi-\omega$. It immediately follows that for
$W=2\pi$, the ensemble of transfer matrices is completely independent of
$\omega$ as $\mathcal{U}(S^{1})$ is invariant under rotation. Also, note that
as the parameter $\varphi$ only enters as a prefactor with an absolute value
of 1, it does not affect the localization length. Thus we omit it. We now
introduce a transformation,

$\displaystyle\begin{pmatrix}\Psi_{n+1,+}\\\
\Psi_{n+1,-}\end{pmatrix}=A_{n}\begin{pmatrix}y_{n}\\\ 1\end{pmatrix}.$ (6)

In order to calculate the localization length, we need to study the behavior
of the Riccati variable $y_{n}$ at $n\rightarrow\infty$ crisanti2012products .
We can exclude $A_{n}$ and write a closed iterative expression for the Riccati
variable ($\omega=0$ as it can be chosen arbitrarily) as follows:

$\displaystyle
y_{n+1}=e^{-i(\varphi_{1}-\varphi_{2})}\frac{y_{n}e^{i(\varphi_{1}-\varphi_{2})}e^{i\phi_{n+1,+}}+\cot\theta
e^{i(\phi_{n+1,+}-\phi_{n,-})}(1-e^{i\phi_{n,-}})}{y_{n}e^{i(\varphi_{1}-\varphi_{2})}\cot\theta(1-e^{i\phi_{n+1,+}})+\sin^{-2}\theta\left(e^{-i\phi_{n,-}}+\cos^{2}\theta
e^{i\phi_{n+1,+}}-\cos^{2}\theta(1+e^{i(\phi_{n+1,+}-\phi_{n,-})})\right)}.$
(7)

Rescaling the phase with a constant factor $y_{n}\rightarrow
y_{n}e^{-i(\varphi_{1}-\varphi_{2})}$ does not change the localization length,
so we get rid of these factors, thereby demonstrating that the localization
length depends only on the parameter $\theta$ of the model. Let us call the
resulting map $z\rightarrow f(z)$. First, we transform the space by a shift
and rescaling,

$\displaystyle z=\cot\theta+z_{1}/\sin\theta.$ (8)

The map $z_{1}\rightarrow f_{1}(z_{1})$ then reads

$\displaystyle
f_{1}(z_{1})=\frac{z_{1}e^{i\phi_{n,-}}(1-2e^{i\phi_{n+1,+}}+\cos(2\theta))-2(e^{i\phi_{n+1,+}}-1)\cos\theta}{2z_{1}e^{i\phi_{n,-}}(e^{i\phi_{n+1,+}}-1)\cos\theta+e^{i\phi_{n+1,+}}\cos(2\theta)-2+e^{i\phi_{n+1,+}}}.$
(9)

This map has a single invariant submanifold $|z_{1}|=1$, and thus the
stationary distribution of $z_{1}$ is located on this unit circle and it is
sufficient to calculate the stationary distribution of $\arg(z_{1})$. However,
the projection of (9) on $\arg(z_{1})$ is highly non-trivial and virtually
impossible to work with; it is much more common to work with distributions of
unbound variables. To make this possible, we transform the $z_{1}$ plane using
a conformal map,

$\displaystyle z_{1}=\frac{z_{2}-i}{z_{2}+i},$ (10)

thus mapping the circle $|z_{1}|=1$ onto the real axis. The map
$z_{2}\rightarrow f_{2}(z_{2})$ reads

$\displaystyle
f_{2}(z_{2})=\frac{\tan^{2}\left(\frac{\theta}{2}\right)\left(\cos\theta\left(e^{i\phi_{1}}(z_{2}-i)+e^{i\phi_{2}}(z_{2}+i)\right)+(z_{2}-i)e^{i(\phi_{1}+\phi_{2})}+z_{2}+i\right)}{-i\cos(\theta)\left(e^{i\phi_{1}}(z_{2}-i)-e^{i\phi_{2}}(z_{2}+i)\right)+(1+iz_{2})e^{i(\phi_{1}+\phi_{2})}-iz_{2}+1}.$
(11)

After additionally taking into account that the stationary distribution is
located on the real axis, we may get the map for the real part
$x=\real(z_{2})$,

$\displaystyle
f(x)=\tan^{2}\left(\frac{\theta}{2}\right)\frac{x\left(\cos(\frac{\phi_{1}-\phi_{2}}{2})\cos\theta+\cos(\frac{\phi_{1}+\phi_{2}}{2})\right)+\sin(\frac{\phi_{1}+\phi_{2}}{2})+\sin(\frac{\phi_{1}-\phi_{2}}{2})\cos\theta}{x\left(\sin(\frac{\phi_{1}-\phi_{2}}{2})\cos\theta-\sin(\frac{\phi_{1}+\phi_{2}}{2})\right)+\cos(\frac{\phi_{1}+\phi_{2}}{2})-\cos(\frac{\phi_{1}-\phi_{2}}{2})\cos\theta}.$
(12)

The stationary distribution of $x$ can now be found as the solution to the
integral equation derrida1983singular ,

$\displaystyle
p(x^{\prime})=\int_{0}^{2\pi}\frac{\text{d}\phi_{1}}{2\pi}\int_{0}^{2\pi}\frac{\text{d}\phi_{2}}{2\pi}\int_{-\infty}^{\infty}\text{d}x\;p(x)\delta(x^{\prime}-f(x)).$
(13)

Figure 4:  Localization length for $W=2\pi,\theta=\pi/5$. The orange histogram
shows the probability distribution of localization length for 50 samples with
length $N=2*500$. The red area is the range of values calculated for various
eigenfrequencies within $[0,2\pi)$ using numerical transfer matrices with
$10^{6}$ iterations each. The black line indicates the analytical value from
(17). The first moment of the probability distribution is within $0.025$
relative error from the analytic value.

Unfortunately, the structure of (12) is too complicated to allow a direct
solution of (13). To get a hint, we notice that the ratios of two random
variables are themselves Cauchy distributed under a wide range of
circumstances pillai2016ratios . This is in particular always the case for
ratios of elliptically symmetric distributions arnold1992distributions . Thus,
we may hypothesize that the stationary distribution $p(x)$ is indeed a Cauchy
distribution. To prove this, we note that for any values of random phases
$\phi_{1}$ and $\phi_{2}$, the map from (12) is an element of the real Möbius
group $\text{SL}(2,\mathbf{R})$, and then note that the Cauchy distribution
family is closed under this group mccullagh1996mobius . Consequently, the
stationary distribution of (12) is necessarily a Cauchy distribution. We
choose it as follows,

$\displaystyle
p(x)=\frac{1}{\pi\gamma(1+x^{2}/\gamma^{2})},\qquad\gamma=\tan\left(\theta/2\right)^{2},$
(14)

and we prove that this is the correct choice of the parameter $\gamma$ by
showing that it solves (13). Integrating (13) over $x$, we get

$\displaystyle
p(x^{\prime})=\int_{0}^{2\pi}\frac{\text{d}\phi_{1}}{2\pi}\int_{0}^{2\pi}\frac{\text{d}\phi_{2}}{2\pi}p\left(f^{-1}(x^{\prime})\right)/|f^{\prime}(f^{-1}(x^{\prime})|,$
(15)

where $f^{-1}$ is the inverse function of $f$. It generally has more than one
value, but not in this case. As we have already proven that the solution is a
Cauchy distribution, we only need to confirm the parameter choice, for which
it is adequate to integrate at $x^{\prime}=0$ only. Substituting (14) into
(15), we get

$\displaystyle\frac{\sec^{4}\left(\frac{\theta}{2}\right)}{4}=\int_{0}^{2\pi}\frac{\text{d}\phi_{1}}{2\pi}\int_{0}^{2\pi}\frac{\text{d}\phi_{2}}{2\pi}\times$
$\displaystyle\times\frac{1}{\left(\cos(\theta)\cos\left(\frac{\phi_{1}-\phi_{2}}{2}\right)+\cos\left(\frac{\phi_{1}+\phi_{2}}{2}\right)\right)^{2}+\cot^{4}\left(\frac{\theta}{2}\right)\left(\cos(\theta)\sin\left(\frac{\phi_{1}-\phi_{2}}{2}\right)+\sin\left(\frac{\phi_{1}+\phi_{2}}{2}\right)\right)^{2}},$
(16)

which is indeed a true identity.

As a result of all the above findings, we are finally able to calculate the
localization length through

$\displaystyle\frac{1}{L_{\text{loc}}}$ $\displaystyle=$
$\displaystyle\int\text{d}z\;p(z)\ln\left(|z|\right)$ (17) $\displaystyle=$
$\displaystyle\int_{-\infty}^{\infty}\text{d}x\;p(x)\frac{1}{2}\ln\left[\frac{1}{2}\csc(\theta)\left(\frac{4\left(x^{2}-1\right)\cot(\theta)}{x^{2}+1}+(\cos(2\theta)+3)\csc(\theta)\right)\right]=\left|\ln\left(|\sin(\theta)|\right)\right|.$

We now provide two kinds of numerical verification: exact diagonalization with
a subsequent fitting of the tails of the eigenstates, and numerical transfer
matrix propagation, see Fig. 4. The functional behavior is verified using
transfer matrices as demonstrated in Fig. 5.

Figure 5:  Inverse localization length versus the hopping-like parameter
$\theta$. The red line is the analytical calculation from (17), and the black
dots are the numerical results from the transfer matrix approach with $10^{6}$
iterations for each value of $\theta$.

##  IV Discussion

We proposed a minimal one-dimensional Floquet map with only nearest-neighbor
coupling of the unit cells and a gapless spectrum. We demonstrated that the
Anderson localization length is universal for all the eigenstates and for
every value of the quasi-energy on the complex unit circle (in the
thermodynamic limit), and depends only on the hopping-like parameter of the
model. Furthermore, the localization length can be tuned from $0$ to $\infty$.

These facts can be widely used in numerical studies. For example, in a recent
paper, the authors employed a similar system in the absence of disorder to
study Lyapunov spectrum scaling malishava2022lyapunov  and conjectured its
behavior in the presence of disorder. The universality and ability to control
the disordered phase that we showed in this work may benefit subsequent
related studies. Further applications may include research into
thermalization, ergodization, localization phenomena in the presence of
interactions, the interplay between nonlinearity-induced chaos and
localization, delocalization due to dissipation, and many others.

Acknowledgment.This work was supported by the Institute for Basic Science
(Project numbers: IBS-R024-D1, IBS-R024-Y3.). The author would like to thank
Sergej Flach, Alexei Andreanov, and Merab Malishava for their valuable
discussions and help, and Joel Rasmussen from Recon for proofreading.

## References

  * [1] Philip W Anderson.  Absence of diffusion in certain random lattices.  Physical review, 109(5):1492, 1958.
  * [2] Patrick A Lee and TV Ramakrishnan.  Disordered electronic systems.  Reviews of modern physics, 57(2):287, 1985.
  * [3] Bernhard Kramer and Angus MacKinnon.  Localization: theory and experiment.  Reports on Progress in Physics, 56(12):1469, 1993.
  * [4] Il’ya M Lifshits, SI Gredeskul, and Leonid Andreevich Pastur.  Introduction to theory of non-ordered systems.  Moscow Eds Nauka, 1982.
  * [5] Luca Sapienza, Henri Thyrrestrup, Søren Stobbe, Pedro David Garcia, Stephan Smolka, and Peter Lodahl.  Cavity quantum electrodynamics with anderson-localized modes.  Science, 327(5971):1352–1355, 2010.
  * [6] Tal Schwartz, Guy Bartal, Shmuel Fishman, and Mordechai Segev.  Transport and anderson localization in disordered two-dimensional photonic lattices.  Nature, 446:52, 03 2007.
  * [7] Yoav Lahini, Assaf Avidan, Francesca Pozzi, Marc Sorel, Roberto Morandotti, Demetrios N. Christodoulides, and Yaron Silberberg.  Anderson localization and nonlinearity in one-dimensional disordered photonic lattices.  Phys. Rev. Lett., 100:013906, Jan 2008.
  * [8] Rachida Dalichaouch, J. P. Armstrong, S. Schultz, P. M. Platzman, and S. L. McCall.  Microwave localization by two-dimensional random scattering.  Nature, 354:53, 11 1991.
  * [9] R.L. Weaver.  Anderson localization of ultrasound.  Wave Motion, 12(2):129 – 142, 1990.
  * [10] Hefei Hu, A. Strybulevych, J. H. Page, S. E. Skipetrov, and B. A. van Tiggelen.  Localization of ultrasound in a three-dimensional elastic network.  Nature Physics, 4:945, 10 2008.
  * [11] Serge Aubry and Gilles André.  Analyticity breaking and anderson localization in incommensurate lattices.  Ann. Israel Phys. Soc, 3(133):18, 1980.
  * [12] Alejandro J Martínez, Mason A Porter, and PG Kevrekidis.  Quasiperiodic granular chains and hofstadter butterflies.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376(2127):20170139, 2018.
  * [13] Shmuel Fishman, DR Grempel, and RE Prange.  Chaos, quantum recurrences, and anderson localization.  Physical Review Letters, 49(8):509, 1982.
  * [14] Shmuel Fishman, RE Prange, and Meir Griniasty.  Scaling theory for the localization length of the kicked rotor.  Physical Review A, 39(4):1628, 1989.
  * [15] Yakir Aharonov, Luiz Davidovich, and Nicim Zagury.  Quantum random walks.  Physical Review A, 48(2):1687, 1993.
  * [16] Ihor Vakulchyk, Mikhail V Fistul, Pinquan Qin, and Sergej Flach.  Anderson localization in generalized discrete-time quantum walks.  Physical Review B, 96(14):144204, 2017.
  * [17] Merab Malishava, Ihor Vakulchyk, Mikhail Fistul, and Sergej Flach.  Floquet anderson localization of two interacting discrete time quantum walks.  Physical Review B, 101(14):144201, 2020.
  * [18] Ihor Vakulchyk, Mikhail V Fistul, and Sergej Flach.  Wave packet spreading with disordered nonlinear discrete-time quantum walks.  Physical review letters, 122(4):040501, 2019.
  * [19] C Madaiah Chandrashekar, Radhakrishna Srikanth, and Raymond Laflamme.  Optimizing the discrete time quantum walk using a su (2) coin.  Physical Review A, 77(3):032326, 2008.
  * [20] Andrea Crisanti, Giovanni Paladin, and Angelo Vulpiani.  Products of random matrices: in Statistical Physics, volume 104\.  Springer Science & Business Media, 2012.
  * [21] Bernard Derrida and HJ715727 Hilhorst.  Singular behaviour of certain infinite products of random 2$\times$ 2 matrices.  Journal of Physics A: Mathematical and General, 16(12):2641, 1983\.
  * [22] Natesh S Pillai.  Ratios and cauchy distribution.  arXiv preprint arXiv:1602.08181, 2016.
  * [23] Barry C Arnold and Patrick L Brockett.  On distributions whose component ratios are cauchy.  The American Statistician, 46(1):25–26, 1992.
  * [24] Peter McCullagh et al.  Möbius transformation and cauchy parameter estimation.  Annals of statistics, 24(2):787–808, 1996.
  * [25] Merab Malishava and Sergej Flach.  Lyapunov spectrum scaling for classical many-body dynamics close to integrability.  Physical Review Letters, 128(13):134102, 2022.