# Functionality of box intersection graphs

Clément Dallard
Université d’Orléans, INSA Centre Val de Loire, LIFO EA 4022, Orléans, France
<EMAIL_ADDRESS>
Vadim Lozin
Mathematics Institute, University of Warwick
<EMAIL_ADDRESS>
Martin Milanič
FAMNIT and IAM, University of Primorska
<EMAIL_ADDRESS>
Kenny Štorgel
Faculty of Information Studies in Novo mesto
FAMNIT, University of Primorska
<EMAIL_ADDRESS>
Viktor Zamaraev
Department of Computer Science, University of Liverpool
<EMAIL_ADDRESS>
###### Abstract

Functionality is a graph complexity measure that extends a variety of
parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In
the present paper, we show that functionality is bounded for box intersection
graphs in $\mathbb{R}^{1}$, i.e. for interval graphs, and unbounded for box
intersection graphs in $\mathbb{R}^{3}$. We also study a parameter known as
symmetric difference, which is intermediate between twin-width and
functionality, and show that this parameter is unbounded both for interval
graphs and for unit box intersection graphs in $\mathbb{R}^{2}$.

Keywords: interval graphs; box intersection graphs; graph functionality;
symmetric difference; twin-width

##  1 Introduction

The notion of graph functionality provides a common generalisation for various
graph parameters, such as maximum vertex degree, degeneracy, clique-width and
twin-width, in the sense that boundedness of any of these parameters implies
bounded functionality, but not necessarily vice versa. Originally, this notion
appeared in an implicit form in [2] in the context of graph representation. A
formal definition of graph functionality was introduced in [1], where
boundedness or unboundedness of functionality was shown for a variety of graph
classes. In particular, it was proved in [1] that functionality is bounded for
permutation graphs, line graphs and unit interval graphs. However, the
question of boundedness or unboundedness of functionality in the entire class
of interval graphs was left open in [1]. In the present paper we answer this
question by showing that the functionality of any interval graph is at most
$8$.

We observe that interval graphs are precisely box intersection graphs in
$\mathbb{R}^{1}$ (all definitions can be found in Section 2). This
observation, together with our result for interval graphs, naturally leads to
the question of boundedness or unboundedness of functionality for box
intersection graphs in $\mathbb{R}^{d}$ for $d>1$. We answer this question for
$d\geq 3$ by showing that in this case the functionality is unbounded.

We also observe that the result for unit interval graphs proved in [1] is, in
fact, stronger than showing boundedness of functionality in this class. The
result deals with a restricted version of functionality called _symmetric
difference_. This parameter is intermediate between twin-width and
functionality in the sense that bounded twin-width implies bounded symmetric
difference, which in turn implies bounded functionality, but neither of the
reverse implications is valid in general. The result in [1] proves bounded
symmetric difference for unit interval graphs. In the present paper, we show
that this result cannot be extended to interval graphs by providing an
explicit construction of interval graphs of unbounded symmetric difference
(and hence of unbounded twin-width). Finally, we show that boundedness of
symmetric difference in the class of unit interval graphs, i.e. unit box
intersection graphs in $\mathbb{R}^{1}$, cannot be extended to unit box
intersection graphs in $\mathbb{R}^{2}$. However, functionality of unit box
intersection graphs in $\mathbb{R}^{2}$ remains a challenging open question.

The organisation of the paper is as follows. All definitions and notations
related to the topic of the paper can be found in Section 2.

In Section 3 we show that the functionality of any interval graph is at most
$8$. Then, in Section 4 we prove that the functionality of box intersection
graphs in $\mathbb{R}^{3}$ is unbounded. Finally, in Section 5 we focus on the
symmetric difference and show that this parameter is unbounded both for
interval graphs and for unit box intersections graphs in $\mathbb{R}^{2}$. Our
proofs are constructive and describe explicitly families of graphs of
unbounded symmetric difference, and hence of unbounded twin-width and clique-
width. Section 6 concludes the paper with a number of open questions.

##  2 Preliminaries

For a positive integer $k$, we denote by $[k]$ the set $\\{1,\ldots,k\\}$. All
graphs in this paper are finite, undirected, without loops and multiple edges.
The vertex set and the edge set of a graph $G$ are denoted $V(G)$ and $E(G)$,
respectively. The neighbourhood of a vertex $x\in V(G)$, denoted $N(x)$, is
the set of vertices of $G$ adjacent to $x$, and the degree of $x$, denoted
$\deg(x)$, is the size of its neighbourhood. We denote by $N[x]$ the closed
neighbourhood of $x$, that is, the set $N(x)\cup\\{x\\}$. Two vertices $x$ and
$y$ are twins if $N(x)\setminus\\{y\\}=N(y)\setminus\\{x\\}$, or,
equivalently, if $N[x]\setminus\\{x,y\\}=N[y]\setminus\\{x,y\\}$. The minimum
vertex degree and the maximum vertex degree in $G$ are denoted by $\delta(G)$
and $\Delta(G)$, respectively.

Let $G$ be a graph and $A=A_{G}$ the adjacency matrix of $G$. We say that a
vertex $y\in V(G)$ is a function of vertices $x_{1},x_{2},\ldots,x_{k}\in
V(G)\setminus\\{y\\}$ if there is a Boolean function $f$ of $k$ variables such
that for every vertex $z\in V(G)$ different from $y,x_{1},x_{2},\ldots,x_{k}$
we have $A(y,z)=f(A(y,x_{1}),\ldots,A(y,x_{k}))$. We observe that every vertex
is a function of some other vertices. In particular, every vertex is a
function of its neighbours, for the function $f\equiv 0$, and a function of
its non-neighbours, for the function $f\equiv 1$. The minimum $k$ such that
$y$ is a function of $k$ other vertices is the functionality of $y$ and is
denoted $\mathrm{fun}_{G}(y)$, or simply $\mathrm{fun}(y)$ if the graph is
clear from the context. The functionality of $G$ is denoted and defined as
follows:

$\mathtt{fun}(G)=\max_{H}\min_{y\in V(H)}\mathrm{fun}(y),$

where the maximum is taken over all induced subgraphs $H$ of $G$. If in this
definition we replace $\mathrm{fun}(y)$ with $\deg(y)$, then we obtain the
definition of degeneracy. Together with the observation that
$\mathrm{fun}(y)\leq\deg(y)$, we conclude that functionality of a graph is
always bounded from above by its degeneracy. In particular, bounded degeneracy
implies bounded functionality. Similarly, boundedness of some other graph
parameters implies bounded functionality. For clique-width, this was proved in
[1] by showing that in any graph of bounded clique-width, there must exist two
vertices whose neighbourhoods have small symmetric difference. This motivates
the study of one more graph parameter, implicitly introduced in [2], and
called the symmetric difference of a graph in [1].

Given a graph $G$ and a pair of vertices $x,y$ in $G$, let
$\mathrm{sd}_{G}(x,y)$ (or simply $\mathrm{sd}(x,y)$ if the graph is clear
from the context) be the number of vertices different from $x$ and $y$ that
are adjacent to exactly one of $x$ and $y$. In other words, if $x$ and $y$ are
non-adjacent, then $\mathrm{sd}(x,y)$ is the size of the symmetric difference
of $N(x)$ and $N(y)$, and if $x$ and $y$ are adjacent, then $\mathrm{sd}(x,y)$
is the size of the symmetric difference of $N[x]$ and $N[y]$. Then, the
symmetric difference of $G$ is denoted by $\mathtt{sd}(G)$ and defined to be 0
if $G$ is a single-vertex graph, and otherwise

$\mathtt{sd}(G)=\max_{H}\min_{\begin{subarray}{c}x,y\in V(H)\\\ x\neq
y\end{subarray}}\mathrm{sd}(x,y),$

where the maximum is taken over all induced subgraphs $H$ of $G$ with at least
two vertices.

If $x$ and $y$ are twins, then $\mathrm{sd}(x,y)=0$ and the functionality of
both vertices is at most $1$, i.e. $x$ and $y$ are functions of each other.
More generally, any two vertices $x$ and $y$ are functions of each other and
of the vertices distinguishing them, i.e.
$\mathrm{fun}(x)\leq\mathrm{sd}(x,y)+1$ and
$\mathrm{fun}(y)\leq\mathrm{sd}(x,y)+1$.111To see that any two vertices $x$
and $y$ are functions of each other and of the vertices distinguishing them,
let us denote by $Z$ the set of vertices distinguishing $x$ and $y$, i.e.
$Z=\\{z\in V(G)\setminus\\{x,y\\}\mid z$ is adjacent to exactly one of $x$ and
$y\\}$. Then $x$ is a function of $\\{y\\}\cup Z$, since any vertex $v\in
V(G)\setminus(\\{y\\}\cup Z)$ is adjacent to $x$ if and only if $v$ is
adjacent to $y$ (in particular, the vertices in $Z$ are inessential in this
function). Similarly, the vertex $y$ is a function of the vertices in
$\\{x\\}\cup Z$. The above discussion shows that symmetric difference is a
parameter intermediate between clique-width and functionality in the sense
that bounded clique-width implies bounded symmetric difference, which in turn
implies bounded functionality.

The recently introduced parameter twin-width [6] lies strictly between clique-
width and symmetric difference, i.e. bounded clique-width implies bounded
twin-width, which in turn implies bounded symmetric difference. Therefore, any
construction of graphs of unbounded (i.e. arbitrarily large) symmetric
difference is also of unbounded twin-width and clique-width.

In the present paper, we study functionality and symmetric difference of box
intersection graphs.

######  Definition 2.1.

A _box_ in $\mathbb{R}^{d}$ is a solid $d$-dimensional rectangle with axis-
parallel sides. A unit box is a box with all sides of length $1$. A graph $G$
is a _box intersection graph in $\mathbb{R}^{d}$_ (resp., a _unit box
intersection graph in $\mathbb{R}^{d}$_) if each vertex of $G$ can be
associated with a box (resp., a unit box) in $\mathbb{R}^{d}$ so that two
vertices of $G$ are adjacent if and only if the corresponding boxes intersect.

Box intersection graphs in $\mathbb{R}^{1}$ are known as interval graphs, i.e.
intersection graphs of intervals on the real line.

##  3 Functionality of interval graphs is bounded

Let $G$ be an interval graph with $n$ vertices given together with an interval
representation. Without loss of generality we assume that the endpoints of the
intervals are pairwise distinct. This allows us to label the endpoints of the
intervals by numbers from $1$ to $2n$ consecutively from left to right, and to
represent each interval (vertex of $G$) by a pair of numbers $(i,j)$, where
$i$ is the left endpoint and $j$ is the right endpoint of the interval (and
thus $i<j$). We can therefore represent each interval (vertex of $G$) by a
point in $\mathbb{N}^{2}$ above the diagonal $\\{(i,i)\mid 1\leq i\leq n\\}$.

We denote the vertex of $G$ corresponding to the point $(i,j)$ by $v_{i,j}$.
The Manhattan distance between two points $(i,j)$ and $(p,q)$ in
$\mathbb{N}^{2}$ is $|i-p|+|j-q|$. We also define the horizontal distance
between $(i,j)$ and $(p,q)$ to be $|i-p|$, and the vertical distance between
$(i,j)$ and $(p,q)$ to be $|j-q|$.

######  Lemma 3.1.

If the Manhattan distance between two points $(i,j)$ and $(p,q)$ is $k$, then
the symmetric difference of $v_{i,j}$ and $v_{p,q}$ is at most $k-2$.

###### Proof.

It is easy to check that if a vertex $v_{s,t}$ is in the symmetric difference
of the neighbourhoods of $v_{i,j}$ and $v_{p,q}$ and different from the two
vertices, then one of the endpoints of $(s,t)$ belongs to the interval
$(\min\\{i,p\\},\max\\{i,p\\})$ or to the interval
$(\min\\{j,q\\},\max\\{j,q\\})$. Since the endpoints of all intervals are
pairwise distinct and the Manhattan distance between $(i,j)$ and $(p,q)$ is
$k$, there could be at most $k-2$ possible vertices $v_{s,t}$ satisfying this
property. ∎

######  Theorem 3.2.

The functionality of any interval graph is at most $8$.

###### Proof.

Since the class of interval graphs is hereditary, to prove the theorem it
suffices to show that each interval graph contains a vertex of functionality
at most $8$.

Let $G$ be an interval graph. We use a representation of $G$ by points in
$\mathbb{N}^{2}$ that has been described in the beginning of the section. All
points representing the vertices of $G$ are located above the diagonal in the
$[2n]\times[2n]$ area of the integer grid. Each vertical line and each
horizontal line in this area contains at most one vertex of $G$. We split the
$2n$ horizontal lines in this area into $\lceil 2n/5\rceil$ stripes, each
containing $5$ consecutive lines, except possibly one stripe containing at
most $4$ consecutive lines if $2n$ is not a multiple of $5$. Similarly, we
split vertical lines into $\lceil 2n/5\rceil$ stripes. The intersection of a
horizontal stripe and a vertical stripe will be called a block.

Assume first that there is a block containing two vertices of $G$. Then the
Manhattan distance between these two vertices is at most $8$ and hence,
according to Lemma 3.1, the symmetric difference of these two vertices is at
most $6$, implying that the functionality of each of them is at most $7$.

From now on, we assume that each block contains at most one vertex of $G$. We
call blocks containing no vertex of $G$ empty. To find a vertex of low
functionality, let us start by considering the case when there exist two
consecutive horizontal lines, say $L_{\sf h}$ and $L^{\prime}_{\sf h}$, and
two consecutive vertical lines, say $L_{\sf v}$ and $L^{\prime}_{\sf v}$, such
that

  * •

one of the four points in the intersections of these lines (that is, $L_{\sf
h}\cap L_{\sf v}$, $L_{\sf h}\cap L^{\prime}_{\sf v}$, $L^{\prime}_{\sf h}\cap
L_{\sf v}$, and $L^{\prime}_{\sf h}\cap L^{\prime}_{\sf v}$) is a vertex of
$G$, say vertex $x\in L_{\sf h}\cap L_{\sf v}$,

  * •

there is a vertex of $G$ above $x$ in the other vertical line $L^{\prime}_{\sf
v}$, say vertex $y$,

  * •

there is a vertex of $G$ to the left of $x$ in the other horizontal line
$L^{\prime}_{\sf h}$, say vertex $z$.

In this case, we claim that $x$ is a function of $y$ and $z$. More precisely,
a vertex $v\in V(G)\setminus\\{x,y,z\\}$ is adjacent to $x$ if and only if
$A(v,y)=A(v,z)=1$, where $A$ is the adjacency matrix of $G$. Indeed, by
construction the four lines contain vertices $x,y,z$ only, and any other
vertex $v$ is either adjacent to $x$, in which case it is also adjacent to
both $y$ and $z$, or non-adjacent to $x$, in which case it is non-adjacent to
at least one of $y$ or $z$.

The requirement that the two vertical lines and the two horizontal lines are
consecutive can be relaxed by asking that $x$ and $y$ are of bounded
horizontal distance from each other, while $x$ and $z$ are of bounded vertical
distance from each other, say both distances are at most $k$, i.e. there are
at most $k-1$ vertical lines between $x$ and $y$ and at most $k-1$ horizontal
lines between $x$ and $z$. Then the vertical lines between $x$ and $y$ contain
at most $k-1$ vertices $y_{1},\ldots,y_{k-1}$ and the horizontal lines between
$x$ and $z$ contain at most $k-1$ vertices $z_{1},\ldots,z_{k-1}$. In this
case, $x$ is a function of $y,y_{1},\ldots,y_{k-1},z,z_{1},\ldots,z_{k-1}$ for
the same reason as above. The only difference is that
$y_{1},\ldots,y_{k-1},z_{1},\ldots,z_{k-1}$ are inessential variables of the
function, i.e. the function does not depend on them.

To find a vertex $x$ satisfying the above conditions, we introduce the
following terminology. The leftmost non-empty block in any horizontal stripe
and the topmost non-empty block in any vertical stripe will be called marginal
blocks.

Let $B$ be a non-empty block and let $x$ be the only vertex of $G$ that
belongs to $B$. If $B$ is not marginal, then there is a vertex $y$ above $x$
in the same vertical stripe and a vertex $z$ to the left of $x$ in the same
horizontal stripe. In this case, $x$ is a function of $y$ and $z$ and at most
$3$ vertices in the vertical lines between $x$ and $y$ and at most $3$
vertices in the horizontal lines between $x$ and $z$, i.e. the functionality
of $x$ is at most $8$.

It remains to show that a non-empty non-marginal block does exist. Each
horizontal stripe contains at most one marginal block and each vertical stripe
contains at most one marginal block. Therefore, there are at most $2\lceil
2n/5\rceil$ marginal blocks. Since the total number of non-empty blocks is
exactly $n$, and $n>2\lceil 2n/5\rceil$ holds for any $n\geq 9$, we conclude
that there is at least one non-empty non-marginal block and hence a vertex of
functionality at most $8$ for all $n\geq 9$. In graphs with at most $8$
vertices, the functionality of each vertex is at most $7$. ∎

##  4 Functionality of box intersection graphs in $\mathbb{R}^{3}$ is
unbounded

Having proved boundedness of functionality for interval graphs, i.e. for box
intersection graphs in $\mathbb{R}^{1}$, it is natural to ask whether this
parameter is bounded for box intersection graphs in $\mathbb{R}^{d}$ for
larger values of $d$. In the present section, we answer this question in the
negative for $d\geq 3$. We start with a helpful lemma, where $K_{n,m}$ stands
for the complete bipartite graph with parts of size $n$ and $m$.

######  Lemma 4.1.

Let $p\geq 2$ be an integer and let $X$ be a class of $K_{2,p}$-free triangle-
free graphs such that there exists an increasing function
$g:\mathbb{N}\rightarrow\mathbb{N}$, and an infinite sequence of graphs
$G_{1},G_{2},\ldots$ in $X$ with $|V(G_{n})|=g(n)$ such that
$a(n):=\delta(G_{n})$ is in $\omega(1)$ and $b(n):=\Delta(G_{n})$ is in
$o(g(n))$. Then $X$ has unbounded functionality.

###### Proof.

Suppose towards a contradiction that $X$ and $(G_{n})_{n\in\mathbb{N}}$ is a
class and a sequence, respectively, as in the statement of the lemma, but $X$
has functionality bounded by $k$ for some constant $k$.

Let $n$ be a large enough integer such that

$\delta(G_{n})\geq kp+1\quad\quad\quad\textrm{ and
}\quad\quad\quad\Delta(G_{n})\leq\frac{g(n)-k-2}{k+1}\,.$

Such an $n$ exists by the assumption on the functions $a$ and $b$. By
assumption, there exist vertices $x,y_{1},y_{2},\ldots,y_{k}\in V(G_{n})$ such
that $x$ is a function of $y_{1},y_{2},\ldots,y_{k}$. To prove the lemma it is
enough to find a pair of vertices $u,w$ distinct from
$x,y_{1},y_{2},\ldots,y_{k}$ such that $u$ is adjacent to $x$, $w$ is _not_
adjacent to $x$, but $u,w$ are not distinguished by $y_{1},y_{2},\ldots,y_{k}$
(i.e. $u$ and $w$ have the same neighbourhood in
$\\{y_{1},y_{2},\ldots,y_{k}\\}$). Indeed, this will contradict the assumption
that $x$ is a function of $y_{1},y_{2},\ldots,y_{k}$.

First, note that since $G_{n}$ is $K_{2,p}$-free and triangle-free, $x$ has at
most $p-1$ neighbours in common with $y_{i}$ for every $i\in[k]$. Thus, from
$\deg(x)\geq kp+1$ we conclude that there exists a neighbour $u$ of $x$ that
is distinct from $y_{1},\ldots,y_{k}$ and is not adjacent to any of these
vertices. On the other hand, from $\Delta(G_{n})\leq\frac{g(n)-k-2}{k+1}$, we
conclude that there exists a vertex $w$ that is distinct from
$x,y_{1},\ldots,y_{k}$ and adjacent to none of them. ∎

We denote by $Q_{n}$ the $n$-dimensional hypercube, and by $\mathcal{Q}$ the
hereditary closure of hypercubes, that is, the class of all induced subgraphs
of hypercubes. As a corollary of Lemma 4.1 we recover a result from [1].

######  Corollary 4.2.

The class $\mathcal{Q}$ has unbounded functionality.

###### Proof.

The corollary follows by applying Lemma 4.1 to the sequence
$Q_{1},Q_{2},Q_{3},\ldots$. Indeed, every graph in $\mathcal{Q}$ is
$K_{2,3}$-free [8], and the functions $a(n)=b(n)=\log g(n)$, where
$g(n)=2^{n}$, satisfy the conditions of Lemma 4.1. ∎

A bipartite graph $G=(P,B,E)$ is a _point-box incidence_ graph if the vertices
in $P$ (which we call _point-vertices_) can be associated with points in the
Euclidean plane ($\mathbb{R}^{2}$) and the vertices in $B$ (which we call
_box-vertices_) can be associated with boxes in the plane so that $p\in P$ and
$b\in B$ are adjacent if and only if the box associated with $b$ contains the
point associated with $p$.

######  Lemma 4.3.

The class of point-box incidence graphs has unbounded functionality.

###### Proof.

To prove the lemma we will show that there is a sequence of point-box
incidence graphs $(G_{n})_{n\in\mathbb{N}}$ that satisfies the conditions of
Lemma 4.1.

We will use the construction presented in [4] (see Proposition 3.5 and Lemma
3.3) that was used to show the existence of $K_{2,2}$-free point-box incidence
graphs with superlinear number of edges. The minimum and the maximum degrees
of the vertices, which are important for applications of Lemma 4.1, were not
analysed explicitly in [4]. In order to do this, below we describe the
construction in graph theoretic terms, from which we can easily infer the
minimum and the maximum degrees of the graphs.

Let $n$ be a positive integer. We define $H^{n}_{1}:=(P_{1},B_{1},E_{1})$ to
be the star $K_{1,n}$ with the central vertex in $B_{1}$ and $n$ leaves in
$P_{1}$. For every $i=2,\ldots,n$, we define $H^{n}_{i}$ inductively as
follows. The graph $H^{n}_{i}=(P_{i},B_{i},E_{i})$ is obtained by taking $n$
vertex-disjoint copies of $H^{n}_{i-1}$, adding $|P_{i-1}|$ box-vertices to
$B_{i}$, and adding a perfect matching between these vertices and the point-
vertices of each of the copies of $H^{n}_{i-1}$.222To see that each graph
$H_{i}^{n}$ is a point-box incidence graph, we provide an informal description
of the corresponding geometric construction. If $i\geq 2$ and, by induction
hypothesis, $\mathcal{R}_{i-1}$ is a geometric realisation of $H^{n}_{i-1}$ in
which all points representing point-vertices have different $y$-coordinates,
then a geometric realisation $\mathcal{R}_{i}$ of $H^{n}_{i}$ is defined as
follows. Take $n$ disjoint copies of $\mathcal{R}_{i-1}$ that are translations
of $\mathcal{R}_{i-1}$ along $x$-axis. In these $n$ copies, every point-vertex
of $\mathcal{R}_{i-1}$ has $n$ copies and, by assumption, all of them have the
same $y$-coordinate, which is different from the $y$-coordinates of the
remaining point-vertices of $\mathcal{R}_{i-1}$. Thus, we can add $|P_{i-1}|$
new disjoint boxes such that each of them contains the $n$ copies of a point-
vertex in $\mathcal{R}_{i-1}$ and no other point-vertices. To obtain
$\mathcal{R}_{i}$, in each of the newly added boxes we shift point-vertices
contained in it vertically so that they all have pairwise distinct
$y$-coordinates and each point stays in the boxes it belongs to. Notice that,
if $p_{i}$ and $b_{i}$ denote the number of point- and box-vertices in
$H^{n}_{i}$, respectively, then $p_{1}=n$, $b_{1}=1$, and $p_{i}=n\cdot
p_{i-1}$, $b_{i}=n\cdot b_{i-1}+p_{i-1}$. From these recurrence relations, it
is easy to deduce that $p_{i}=n^{i}$ and $b_{i}=i\cdot n^{i-1}$ for all
$i\in\\{1,\ldots,n\\}$. In particular, $p_{n}=b_{n}=n^{n}$.

Note that each of the graphs $H^{n}_{i}$ is $K_{2,2}$-free. We further observe
that every time we add a new box-vertex its degree is $n$ and it does not
change in the subsequent graphs. The degree of every copy of a point-vertex
from $H^{n}_{i-1}$ increases by one in $H^{n}_{i}$, i.e. the degree of every
point-vertex in $H^{n}_{i}$ is $i$. Hence, $G_{n}:=H^{n}_{n}$ is a
$K_{2,2}$-free point-box incidence graph with $g(n):=2n^{n}$ vertices in which
every vertex has degree $n\in\Theta\left(\frac{\log g(n)}{\log\log
g(n)}\right)$. Applying Lemma 4.1 to $(G_{n})_{n\in\mathbb{N}}$ implies the
lemma. ∎

It is known that point-box incidence graphs are box intersection graphs in
$\mathbb{R}^{3}$ (see, e.g., [9]). Summarising, we derive the main result of
this section.

######  Theorem 4.4.

The class of box intersection graphs in $\mathbb{R}^{3}$ has unbounded
functionality.

Clearly, Theorem 4.4 implies that the class of box intersection graphs in
$\mathbb{R}^{d}$ has unbounded functionality for all $d\geq 3$.

##  5 Symmetric difference is unbounded for the classes of interval graphs and
unit box intersection graphs in $\mathbb{R}^{2}$

Bonnet et al. showed in [5] that the class of interval graphs has unbounded
twin-width based on a construction of a class of interval graphs that can
represent an arbitrary permutation. The construction relies on the notion of a
_half graph_ , that is, a bipartite graph with $2n$ vertices, $n\geq 1$, that
admits a partition of its vertex set into two equally sized independent sets
$X=\\{x_{1},\ldots,x_{n}\\}$ and $Y=\\{y_{1},\ldots,y_{n}\\}$ such that for
all $i,j\in[n]$, vertex $x_{i}$ is adjacent to vertex $y_{j}$ if and only if
$i<j$.

######  Definition 5.1.

An _ABC graph_ is any graph $G$ with $3n$ vertices, $n\geq 1$, such that the
vertex set of $G$ can be partitioned into three cliques $A$, $B$ and $C$, each
of size $n$, such that there are no edges between $A$ and $C$, the edges
between $A$ and $B$ form a half graph, and the edges between $B$ and $C$ form
a half graph. More precisely, there exists an order $a_{1},\ldots,a_{n}$ for
the vertices in $A$ and an order $b_{1},\ldots,b_{n}$ for the vertices in $B$
such that $a_{i}$ is adjacent to $b_{j}$ if and only if $i<j$. Similarly,
there exists another order $b_{1}^{\prime},\ldots,b_{n}^{\prime}$ for the
vertices in $B$ and an order $c_{1},\ldots,c_{n}$ for the vertices in $C$ such
that $b_{i}^{\prime}$ is adjacent to $c_{j}$ if and only if $i<j$.

It is important to note that the orders $b_{1},\ldots,b_{n}$ and
$b_{1}^{\prime},\ldots,b_{n}^{\prime}$ for the vertices in $B$ are completely
independent from each other. In particular, they may differ.

ABC graphs have been studied in [7], where they have been shown to be of
unbounded clique-width. Bonnet et al. extended this result by showing that the
twin-width of ABC graphs is unbounded. However, the proof in [5] is non-
constructive and relies on a counting argument. We now improve this result in
two different ways. First, we extend it by showing that the ABC graphs have
unbounded symmetric difference, which is a stronger conclusion. Second, our
proof is constructive and provides an explicit family of induced subgraphs of
ABC graphs with increasing symmetric difference.

######  Theorem 5.2.

The class of ABC graphs has unbounded symmetric difference.

###### Proof.

We will show that for every integer $k\geq 2$ there exists a graph $G_{k}$
that is an induced subgraph of an ABC graph and such that the symmetric
difference of $G_{k}$ is at least $k$. The construction is as follows. The
graph $G_{k}$ consists of three disjoint cliques $A$, $B$ and $C$, and some
edges between them. The two cliques $A$ and $C$ are each of size $t$ where
$t=k^{3}$. The clique $B$ has size $k^{4}$, its vertices correspond to pairs
of integers, and it is partitioned into $k^{2}$ smaller sets, each of size
$k^{2}$,

$B=\bigcup_{1\leq i,j\leq k}B_{ij}\,,$

where the sets $B_{ij}$ are defined as follows:

  * •

$B_{11}=\\{(pk-q,qk+p)\mid 1\leq p\leq k\,,0\leq q\leq k-1\\}$

  * •

for all $(i,j)\in[k]^{2}\setminus\\{(1,1)\\}$, the set $B_{ij}$ is a translate
of the set $B_{11}$:

$B_{ij}=B_{11}+((i-1)k^{2},(j-1)k^{2})=\\{(x+(i-1)k^{2},y+(j-1)k^{2})\mid(x,y)\in
B_{11}\\}\,.$

See Figure 1 for an example of $G_{k}$ for $k=4$. Note that for each vertex
$b=(b_{x},b_{y})$ in $B$, it holds that $1\leq b_{x}\leq t$ and $1\leq
b_{y}\leq t$. To describe the edges between the cliques $A$, $B$ and $C$, we
fix an ordering of the vertices in $A$ and in $C$ as
$A=\\{a_{1},\ldots,a_{t}\\}$ and $C=\\{c_{1},\ldots,c_{t}\\}$, respectively.
Then, the edges between the cliques $A$, $B$ and $C$ are as follows.

  * •

For every vertex $a_{i}\in A$ and every vertex $b=(b_{x},b_{y})\in B$,
vertices $a_{i}$ and $b$ are adjacent if and only if $i<b_{x}$.

  * •

For every vertex $b=(b_{x},b_{y})\in B$ and every vertex $c_{j}\in C$,
vertices $b$ and $c_{j}$ are adjacent if and only if $b_{y}<j$.

  * •

There are no edges between $A$ and $C$.

This completes the description of the graph $G_{k}$.

$a_{1}$$a_{64}$$c_{1}$$c_{64}$$B_{1,1}$$B_{1,2}$$B_{1,3}$$B_{1,4}$$B_{2,1}$$B_{2,2}$$B_{2,3}$$B_{2,4}$$B_{3,1}$$B_{3,2}$$B_{3,3}$$B_{3,4}$$B_{4,1}$$B_{4,2}$$B_{4,3}$$B_{4,4}$
Figure 1: A schematic representation of the graph $G_{k}$, for $k=4$, as
defined in Theorem 5.2. The bottom-most vertices belong to the clique $A$; the
right-most vertices belong to the clique $C$; vertices on the grid belong to
the clique $B$. For each $i\in[t]$, vertex $a_{i}$ (on column $i$) is adjacent
to all the vertices in $B$ on a column $j>i$. Similarly, for each $i\in[t]$,
vertex $c_{i}$ (on row $i$) is adjacent to all the vertices in $B$ on a row
$j<i$.

Next, we show that the symmetric difference of $G_{k}$ is at least $k$, that
is, that for any two distinct vertices $u,v\in V(G_{k})$ we have
$\mathrm{sd}(u,v)\geq k$. We distinguish several cases depending on which of
the cliques $A$, $B$ and $C$ vertices $u$ and $v$ belong to (and taking into
account the fact that $\mathrm{sd}(u,v)=\mathrm{sd}(v,u)$).

We first observe that for any fixed $i\in[t]$, the number of vertices
$(b_{x},b_{y})$ in $B$ with $b_{x}=i$ is $k$. Similarly, the number of
vertices in $B$ with $b_{y}=i$ is also $k$.

Case 1: $u,v\in A$. Let $u=a_{i}$ and $v=a_{j}$ be any two vertices of $A$
with $1\leq i<j\leq t$. By construction we have that $\\{(b_{x},b_{y})\in
B\mid b_{x}=j\\}\subseteq N(u)\setminus N(v)$. Therefore, by the above
observation, $\mathrm{sd}(u,v)\geq k$.

Case 2: $u,v\in C$. Let $u=c_{i}$ and $v=c_{j}$ be any two vertices of $C$
with $1\leq i<j\leq t$. Again, by construction we have that
$\\{(b_{x},b_{y})\in B\mid b_{y}=i\\}\subseteq N(v)\setminus N(u)$. Thus, we
again obtain that $\mathrm{sd}(u,v)\geq k$.

Case 3: $u\in A$ and $v\in C$. By construction we have that
$A\setminus\\{u\\}\subseteq N(u)$ and $(A\setminus\\{u\\})\cap
N(v)=\emptyset$. Thus, $\mathrm{sd}(u,v)\geq t-1=k^{3}-1\geq k$ (here we use
the assumption that $k\geq 2$).

Case 4: $u\in A$ and $v\in B$. Let $u=a_{i}\in A$, $i\in[t]$, and let
$v=(b_{x},b_{y})\in B$. Note that by definition, no vertex in $A$ is adjacent
to any vertex $b\in B$ with the first coordinate equal to $1$. As we have
already observed, there are exactly $k$ such vertices in $B$. Thus, if
$b_{x}\geq 2$, then, since $B$ is a clique, $\mathrm{sd}(u,v)\geq k$ and we
are done. Therefore, we may assume that $b_{x}=1$. But then $N(v)\cap
A=\emptyset$, while $A\setminus\\{u\\}$ is of size $t-1$ contained in $N(u)$.
Thus, we again have that $\mathrm{sd}(u,v)\geq t-1\geq k$.

Case 5: $u\in B$ and $v\in C$. In this case the arguments are similar to those
in Case 4. Let $u=(b_{x},b_{y})\in B$ and $v=c_{j}\in C$, $j\in[t]$. No vertex
in $C$ is adjacent to any vertex $b\in B$ with the second coordinate equal to
$t$ and there are exactly $k$ such vertices in $1$. Thus, if $b_{y}\leq t-1$,
then, since $B$ is a clique, $\mathrm{sd}(u,v)\geq k$ and we are done.
Therefore, we may assume that $b_{y}=t$. But then $N(u)\cap C=\emptyset$,
while $C\setminus\\{v\\}$ is of size $t-1$ contained in $N(v)$, and
$\mathrm{sd}(u,v)\geq k$.

Case 6: $u,v\in B$. Let $u=(u_{x},u_{y})\in B_{ij}$ and $v=(v_{x},v_{y})\in
B_{i^{\prime}j^{\prime}}$ be two distinct vertices of $B$. By construction of
the graph $G_{k}$, exactly $|u_{x}-v_{x}|$ vertices in $A$ are adjacent to
precisely one of $u$ and $v$ and, similarly, exactly $|u_{y}-v_{y}|$ vertices
in $C$ are adjacent to precisely one of $u$ and $v$. Therefore,
$\mathrm{sd}(u,v)\geq k$ whenever the Manhattan distance
$|u_{x}-v_{x}|+|u_{y}-v_{y}|$ between $u$ and $v$ is at least $k$. If
$|i^{\prime}-i|\geq 2$, then $|u_{x}-v_{x}|\geq k^{2}+1$. Consequently,
$\mathrm{sd}(u,v)\geq k^{2}+1\geq k$ whenever $|i^{\prime}-i|\geq 2$ and a
similar conclusion holds if $|j^{\prime}-j|\geq 2$.

We may therefore assume that $|i^{\prime}-i|\leq 1$ and $|j^{\prime}-j|\leq
1$. Let us verify that in this case the Manhattan distance between $u$ and $v$
is at least $k$. We have $u=(x+(i-1)k^{2},y+(j-1)k^{2})$ where $x=pk-q$ and
$y=qk+p$ for some $1\leq p\leq k$ and $0\leq q\leq k-1$ and, similarly,
$v=(x^{\prime}+(i^{\prime}-1)k^{2},y^{\prime}+(j^{\prime}-1)k^{2})$ where
$x^{\prime}=p^{\prime}k-q^{\prime}$ and $y^{\prime}=q^{\prime}k+p^{\prime}$
for some $1\leq p^{\prime}\leq k$ and $0\leq q^{\prime}\leq k-1$. We thus have

$|u_{x}-v_{x}|=|(i-i^{\prime})k^{2}+(p-p^{\prime})k+q^{\prime}-q|$

and

$|u_{y}-v_{y}|=|(j-j^{\prime})k^{2}+(q-q^{\prime})k+p-p^{\prime}|\,.$

Consider first the case when $i^{\prime}=i$ and $j^{\prime}=j$. In this case,
the Manhattan distance between $u$ and $v$ is equal to
$|(p-p^{\prime})k+q^{\prime}-q|+|(q-q^{\prime})k+p-p^{\prime}|$. If
$p^{\prime}=p$ then $q^{\prime}\neq q$ and the expression simplifies to
$(k+1)|q-q^{\prime}|\geq k+1$. Similarly, if $q^{\prime}=q$ then
$p^{\prime}\neq p$ and the above expression simplifies to
$(k+1)|p-p^{\prime}|\geq k+1$. If $p^{\prime}\neq p$ and $q^{\prime}\neq q$,
then we may assume without loss of generality that $p>p^{\prime}$. Suppose to
a contradiction that the Manhattan distance between $u$ and $v$ is less than
$k$, that is,

$|(p-p^{\prime})k+q^{\prime}-q|+|(q-q^{\prime})k+p-p^{\prime}|<k\,.$

Since $p-p^{\prime}\in[k-1]$ and $q^{\prime}\neq q$, we obtain from the second
term on the left side of the inequality that $q-q^{\prime}=-1$. Thus, we have
that $q^{\prime}>q$, and from the first term on the left side of the
inequality we obtain that $p-p^{\prime}=-1$, a contradiction with the
assumption that $p>p^{\prime}$.

Next, consider the case when $i^{\prime}\neq i$. We may assume without loss of
generality that $i^{\prime}>i$, and hence $i^{\prime}=i+1$ (recall that
$|i^{\prime}-i|\leq 1$). The Manhattan distance between $u$ and $v$ is hence
equal to
$|k^{2}+(p^{\prime}-p)k+(q-q^{\prime})|+|(j^{\prime}-j)k^{2}+(q^{\prime}-q)k+(p^{\prime}-p)|$.
Suppose for a contradiction that the Manhattan distance between $u$ and $v$ is
less than $k$. In that case, we must have that $(p^{\prime}-p)=-(k-1)$ and
$(q-q^{\prime})<0$. Recall that $|j^{\prime}-j|\leq 1$. First, if
$j^{\prime}-j=0$, we must have that $q^{\prime}-q=1$, but then the Manhattan
distance between $u$ and $v$ is equal to $|k^{2}-(k-1)k-1|+|k-(k-1)|=k$, a
contradiction. Second, if $j^{\prime}-j=1$, then, as $(q-q^{\prime})<0$, we
have that $|v_{y}-u_{y}|\geq k^{2}$, a contradiction. Third, if
$j^{\prime}-j=-1$, then we must have that $(q-q^{\prime})=-(k-1)$. However, in
that case the Manhattan distance between $u$ and $v$ is equal to
$|k^{2}-(k-1)k-(k-1)|+|-k^{2}+(k-1)k-(k-1)|=1+|-2k+1|=2k$, again a
contradiction.

Finally, consider the case when $i^{\prime}=i$ and $j^{\prime}\neq j$.
Similarly as in the previous case, we may assume without loss of generality
that $j^{\prime}>j$, and hence $j^{\prime}=j+1$. The Manhattan distance
between $u$ and $v$ is equal to
$|(p^{\prime}-p)k+(q-q^{\prime})|+|k^{2}+(q^{\prime}-q)k+(p^{\prime}-p)|$.
Suppose for a contradiction that the Manhattan distance between $u$ and $v$ is
less than $k$. Similarly as in the previous case, we must have that
$(q^{\prime}-q)=-(k-1)$ and $(p^{\prime}-p)<0$. Furthermore, we must have
$p^{\prime}-p=-1$, since otherwise the first term
$|(p^{\prime}-p)k+(q-q^{\prime})|=|(p^{\prime}-p)k+(k-1)|$ would exceed $k$.
But then the Manhattan distance between $u$ and $v$ is equal to
$|-k+(k-1)|+|k^{2}-(k-1)k-1|=k$, a contradiction.

Finally, we show that $G_{k}$ is an induced subgraph of an ABC graph. To this
end, we show that it is possible to add vertices to the clique $A$ and to the
clique $C$ so that each of the resulting cliques $A^{\prime}$ and $C^{\prime}$
has cardinality equal to the cardinality of $B$, that is, $k^{4}$, the edges
between $A^{\prime}$ and $B$ form a half graph, the edges between $B$ and
$C^{\prime}$ form a half graph and there are no edges between $A^{\prime}$ and
$C^{\prime}$.

By symmetry, it suffices to show that it is possible to add vertices to the
clique $C$ to obtain a clique $C^{\prime}$ with $|C^{\prime}|=k^{4}$ so that
the edges between $B$ and $C^{\prime}$ form a half graph. First, notice that
for every vertex $b=(b_{x},b_{y})$ in $B$, its neighbourhood in $C$ depends
only on the value of $b_{y}$. Denoting for each $j\in[t]$ by $B_{j}$ the set
of all vertices $(b_{x},b_{y})$ in $B$ such that $b_{y}=j$, it holds that
$|B_{j}|=k$. Fix an arbitrary ordering of the vertices of $B$ as
$B=\\{b_{1},\ldots,b_{k^{4}}\\}$ such that the vertices in the same part
$B_{j}$ appear consecutively and the vertices of $B_{j}$ appear before the
vertices of $B_{j+1}$, for all $j\in[t-1]$. It follows from the construction
that for every $j\in[t]$, the neighbourhood of $c_{j}$ in $B$ equals to the
union $\bigcup_{i<j}B_{i}=\\{b_{\ell}:\ell\leq k\times(j-1)\\}$. In
particular, for any two consecutive vertices in $C$, their neighbourhoods in
$B$ are nested and differ in precisely $k$ vertices. We extend the clique $C$
to a larger clique $C^{\prime}$ by adding, for each $j\in[t]$, a set of $k-1$
new vertices $c_{j}^{1},\dots,c_{j}^{k-1}$ such that, writing
$c_{j}^{0}=c_{j}$, for each $i\in\\{0,\ldots,k-1\\}$ the neighbourhood of
$c_{j}^{i}$ in $B$ equals $\\{b_{\ell}:\ell\leq k\times(j-1)+i\\}$. This
implies that the $k^{4}$ vertices of $C^{\prime}$ all have distinct but
comparable neighbourhoods in $B$, with $N(c_{1})\cap B=\emptyset$ and
$N(c_{t}^{k-1})\cap B=B\setminus\\{b_{k^{4}}\\}$. In particular, the edges
between $B$ and $C^{\prime}$ form a half graph, as desired. ∎

As observed by Bonnet et al. [5], every ABC graph is an interval graph. Thus,
Theorem 5.2 implies the following.

######  Corollary 5.3.

The class of interval graphs has unbounded symmetric difference.

Theorem 5.2 has another consequence for the class of unit box intersection
graphs in $\mathbb{R}^{2}$.

######  Proposition 5.4.

Every ABC graph is a unit box intersection graph in $\mathbb{R}^{2}$.

###### Proof.

Bonnet et al. showed in [5], with a proof by picture, that every ABC graph is
a unit disk graph. We adapt their approach (and their figure) to show that
every ABC graph is a unit box intersection graph in $\mathbb{R}^{2}$. Let $G$
be any ABC graph with $3n$ vertices, $n\geq 1$, with cliques $A$, $B$ and $C$,
and orderings $a_{1},\ldots,a_{n}$, $b_{1},\ldots,b_{n}$,
$b_{1}^{\prime},\ldots,b_{n}^{\prime}$, and $c_{1},\ldots,c_{n}$ as in the
definition of ABC graphs. We explain how to represent $G$ as a unit box
intersection graph in $\mathbb{R}^{2}$; see the right part of Figure 2.

Place $n$ unit boxes in $\mathbb{R}^{2}$ representing vertices of $A$ so that
their centers are close to each other and decreasing in both coordinates, in
order $a_{1},\ldots,a_{n}$. Then, place $n$ other unit boxes in
$\mathbb{R}^{2}$ representing vertices of $B$ above the $A$-boxes so that
their centers are close to each other and the intersections between $A$-boxes
and $B$-boxes realise the half graph formed by the edges between $A$ and $B$,
taking into account the ordering $b_{1},\ldots,b_{n}$. Note that this imposes
constraints on the vertical positions (that is, values of $y$-coordinates) of
the centers of the $B$-boxes, but leaves some freedom about shifting the
$B$-boxes horizontally. Next, place additional $n$ unit boxes in
$\mathbb{R}^{2}$ representing vertices of $C$ to the right of the boxes
representing vertices of $B$ so that the centers of the $C$-boxes are close to
each other, decrease in both coordinates, in order $c_{1},\ldots,c_{n}$, and
no $C$-box intersects any $A$-box. Finally, if necessary, shift the $B$-boxes
horizontally so that the intersections between $B$-boxes and $C$-boxes realise
the half graph formed by the edges between $B$ and $C$, taking into account
the ordering $b_{1}^{\prime},\ldots,b_{n}^{\prime}$. ∎

Theorem 5.2 and Proposition 5.4 imply the following.

######  Corollary 5.5.

The class of unit box intersection graphs in $\mathbb{R}^{2}$ has unbounded
symmetric difference.

$A$$B$$C$$A$$B$$C$ Figure 2: On the left, an ABC-graph with 15 vertices
represented by intervals. On the right, the same graph, this time represented
as a unit box intersection graph in $\mathbb{R}^{2}$.

##  6 Conclusion

In this paper we proved a number of results on functionality and symmetric
difference of box intersection graphs. A summary of our results is presented
in Table 1.

|  $\mathbb{R}^{1}$ |  $\mathbb{R}^{2}$ |  $\mathbb{R}^{\geq 3}$
---|---|---|---
Symmetric | unit box |  bounded [1] | unbounded (Corollary 5.5)
difference | general | unbounded (Corollary 5.3)
Functionality | unit box |  bounded [1] | open
general |  bounded |  open |  unbounded
(Theorem 3.2) |  |  (Theorem 4.4)
Table 1: Functionality and symmetric difference of box intersection graphs in
$\mathbb{R}^{d}$.

As indicated in the table, the functionality of box intersection graphs in
$\mathbb{R}^{2}$ remains an open question. It also remains open whether the
functionality is bounded for unit box intersection graphs in $\mathbb{R}^{d}$
for any fixed $d\geq 2$.

Among other classes with unknown behaviour of functionality we distinguish the
following two important extensions of interval graphs: circular-arc graphs and
trapezoid graphs.

Finally, we mention one more open problem related to graph functionality:
characterisation and recognition of graphs of small functionality. By
definition, vertices of functionality $0$ are either isolated or dominating,
and hence graphs of functionality $0$ are threshold graphs, i.e. graphs every
induced subgraph of which contains either an isolated or dominating vertex.
However, the class of graphs of functionality at most $1$ remains a mystery.
It contains

  * •

all forests (as every forest contains a vertex of degree at most $1$) and
their complements,

  * •

all cographs, as every cograph with at least two vertices contains a pair of
twins,

  * •

all distance hereditary graphs, as every graph in this class can be
constructed from a single vertex by successively adding either a pendant
vertex or a twin [3].

Note that the class of graphs of functionality at most $1$ is substantially
more complex, as it also contains graphs with anti-twins, i.e. vertices whose
neighbourhoods complement each other. Similarly to twin vertices, anti-twins
are functions of each other. More generally, any two vertices are functions of
each other and of the vertices that do not distinguish them.333Let $Z$ be the
set of vertices not distinguishing $x$ and $y$, i.e. $Z=\\{z\in
V(G)\setminus\\{x,y\\}\mid z$ is adjacent to either both of $x$ and $y$ or to
none of them$\\}$. Then $x$ is a function of $\\{y\\}\cup Z$, since any vertex
$v\in V(G)\setminus(\\{y\\}\cup Z)$ is adjacent to $x$ if and only if $v$ is
not adjacent to $y$ (in particular, the vertices in $Z$ are inessential in
this function). Similarly, the vertex $y$ is a function of the vertices in
$\\{x\\}\cup Z$. This observation gives rise to a new notion, analogous to
symmetric difference, and to a new line of research related to graph
functionality.

### Acknowledgements.

This work is supported in part by the Slovenian Research and Innovation Agency
(I0-0035, research programs P1-0285 and P1-0383, research projects J1-3001,
J1-3002, J1-3003, J1-4008, J1-4084, N1-0102, and N1-0160 and a Young
Researchers Grant) and by the research program CogniCom (0013103) at the
University of Primorska.

## References

  * [1] Bogdan Alecu, Aistis Atminas, and Vadim Lozin.  Graph functionality.  Journal of Combinatorial Theory, Series B, 147:139–158, 2021.
  * [2] Aistis Atminas, Andrew Collins, Vadim Lozin, and Viktor Zamaraev.  Implicit representations and factorial properties of graphs.  Discrete Math., 338(2):164–179, 2015.
  * [3] Hans-Jürgen Bandelt and Henry Martyn Mulder.  Distance-hereditary graphs.  J. Combin. Theory Ser. B, 41(2):182–208, 1986.
  * [4] Abdul Basit, Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran.  Zarankiewicz’s problem for semilinear hypergraphs.  Forum Math. Sigma, 9:Paper No. e59, 23, 2021.
  * [5] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width II: small classes.  Comb. Theory, 2(2):Paper No. 10, 42, 2022.
  * [6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: Tractable FO model checking.  J. ACM, 69(1):Art. 3, 46, 2022.
  * [7] Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, and Vadim V. Lozin.  Clique-width for 4-vertex forbidden subgraphs.  Theory Comput. Syst., 39(4):561–590, 2006.
  * [8] Michael R. Garey and Ronald L. Graham.  On cubical graphs.  Journal of Combinatorial Theory, Series B, 18(1):84–95, 1975.
  * [9] István Tomon and Dmitriy Zakharov.  Turán-type results for intersection graphs of boxes.  Combinatorics, Probability and Computing, 30(6):982–987, 2021.


taken care of by the charge strings, the bottom link is not (unless
$n_{y}=1$). As graphically explained in Fig. 7(a), to increase only the
desired link, we can lower all rotators $\hat{R}_{(n_{x},r_{y})}$ with
$r_{y}=0,...,n_{y}-2$ below, yielding
$f_{(n_{x},n_{y}),\boldsymbol{e}_{x}}=\prod_{r_{y}=0}^{n_{y}-1}\hat{P}_{(n_{x},r_{y})}$.

The remaining panels in Fig. 7 further illustrate the cases of pairs that are
connected by vertical links and pairs that are created on links closing the
periodic boundary conditions, where we require the strings $\hat{R}_{x,y}$. By
following the same procedure above, it is then possible to determine the
functions $f_{\boldsymbol{n},\boldsymbol{e}_{\mu}}$ for all allowed choices of
$\boldsymbol{n}$ and $\mu=x,y$, yielding Eq. (5.2).

##  Appendix C Diagonalisation of the magnetic gauge field Hamiltonian

The magnetic Hamiltonian $\hat{H}_{B}$ is composed of the lowering and raising
operators $\hat{P}_{j}$, $\hat{P}_{j}^{\dagger}$, $j=1,2,\dots,N-1$, where $N$
is the total number of plaquettes. In the $\mathbb{Z}_{2L+1}$ group, these
operators are the so-called cyclant matrices, which can be diagonalised
exactly. Before truncation, the lowering operators are defined according to
Eq. (27),

$\displaystyle\hat{P}_{j}=|{L_{j}}\rangle\\!\langle{-L_{j}}|+\sum_{r_{j}=-L_{j}+1}^{L_{j}}|{r_{j}-1}\rangle\\!\langle{r_{j}}|.$
(73)

For the sake of simplicity, we drop the index $j$ and note that the procedure
is equivalent for all subsystems. The spectrum of the lowering operators is

$\displaystyle\omega_{k}=e^{-i\frac{2\pi}{2L+1}k},$ (74)

while the corresponding eigenvectors are given by

$\displaystyle
v_{k}=\frac{1}{\sqrt{2L+1}}(\omega_{k}^{L},\omega_{k}^{L-1},\dots,\omega_{k}^{-L})^{\textrm{T}},$
(75)

with $k=-L,\dots,L$. Hence, $\hat{U}$ is diagonalised by the matrix

$\displaystyle V^{\dagger}$ $\displaystyle=$
$\displaystyle(v_{-L},v_{-L+1},\dots,v_{L})$ (76) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2L+1}}\sum_{\mu,\nu=-L}^{L}\textrm{e}^{-i\frac{2\pi}{2L+1}\mu\nu}|{\mu}\rangle\\!\langle{\nu}|$
$\displaystyle\equiv$ $\displaystyle\hat{\mathcal{F}}_{2L+1}^{\dagger},$

which is the discrete Fourier transform. Hence, it is straightforward to show
that

$\displaystyle\hat{\mathcal{F}}_{2L+1}\hat{P}^{\gamma}\hat{\mathcal{F}}_{2L+1}^{{\dagger}}=\sum_{r=-L}^{L}{\mathrm{exp}}^{-i\frac{2\pi}{2L+1}\gamma
r}|{r}\rangle\\!\langle{r}|,$ (77)

where $\gamma\in\mathbbm{Z}$. Moreover, for any $N-1\geq J\in\mathbb{N}$, we
have that

$\displaystyle\hat{\mathcal{F}}_{2L+1}\Bigg{[}\bigotimes_{j=1}^{J}$
$\displaystyle\hat{P}_{j}^{\gamma}$
$\displaystyle\Bigg{]}\hat{\mathcal{F}}_{2L+1}^{{\dagger}}$ (78)
$\displaystyle=$
$\displaystyle\sum_{\boldsymbol{r}=-\boldsymbol{L}}^{\boldsymbol{L}}{\mathrm{exp}}^{-i\frac{2\pi}{2L+1}\boldsymbol{\gamma}\boldsymbol{r}}|{\boldsymbol{r}}\rangle\\!\langle{\boldsymbol{r}}|.$

Here, we use $\boldsymbol{r}=(r_{1},r_{2},\dots,r_{J})^{\textrm{T}}$ and
$\boldsymbol{\gamma}=(\gamma_{1},\gamma_{2},\dots,\gamma_{J})^{\textrm{T}}$,
while we waived to denote that the Fourier transform is now understood as the
product of the Fourier transforms in the separate $N-1$ spaces. Note that, in
particular $(\hat{P}^{\gamma})^{\dagger}=\hat{P}^{-\gamma}$ and therefore:

$\displaystyle\hat{\mathcal{F}}_{2L+1}$
$\displaystyle\bigg{[}\bigotimes_{j=1}^{J}\hat{P}_{j}^{\gamma}\pm\bigotimes_{j=1}^{J}\hat{P}_{j}^{-\gamma}\bigg{]}\hat{\mathcal{F}}_{2L+1}^{{\dagger}}$
(79) $\displaystyle=$ $\displaystyle
2\sum_{\boldsymbol{r}=-\boldsymbol{L}}^{\boldsymbol{L}}\begin{cases}\cos(\frac{2\pi\boldsymbol{r}\boldsymbol{\gamma}}{2L+1})|{\boldsymbol{r}}\rangle\\!\langle{\boldsymbol{r}}|&\;\textrm{for}\,+\\\
-i\sin(\frac{2\pi\boldsymbol{r}\boldsymbol{\gamma}}{2L+1})|{\boldsymbol{r}}\rangle\\!\langle{\boldsymbol{r}}|&\;\textrm{for}\,-\end{cases}.$

Let us finally remark that these relations hold interchangeably for $\hat{P}$
in the rotator formalism and $\hat{U}$ for the electric fields as introduced
in Sec. 2.1.

##  Appendix D Asymptotic behaviour of the ground state expectation value of
$\Box$

In this appendix, we describe the behaviour of the ground state expectation
value $\langle\Box\rangle$ both in the electric and magnetic representation.
We look at the extremal regimes and study truncation effects.

We indicate the average value of the observable $\Box$ in the electric
(magnetic) representation with $\langle\Box^{(\mathrm{e})}\rangle$
($\langle\Box^{(\mathrm{b})}\rangle$). Recall that $\Box=-g^{2}\hat{H}_{B}/4$,
and consider the electric representation first. Here,
$\hat{H}_{B}^{(\mathrm{e})}$ is composed of the Hermitian operators
$\hat{P}_{i}+\hat{P}_{i}^{\dagger}$ ($i=1,2,3$), and of
$\hat{P}_{1}\hat{P}_{2}\hat{P}_{3}+(\hat{P}_{1}\hat{P}_{2}\hat{P}_{3})^{\dagger}$,
where the latter is the replacement for $\hat{P}_{4}+\hat{P}_{4}^{\dagger}$
(see Sec. 2.2). Hence, we can bound the spectrum of $-\hat{H}_{B}$ as
$-\langle{\psi}|\hat{H}_{B}|{\psi}\rangle\leq
4\langle{\psi}|(\hat{P}_{i}+\hat{P}_{i}^{\dagger})|{\psi}\rangle/(2g^{2})=2\lambda_{\textrm{max}}/g^{2}$.
Importantly, this holds for all $i$ since the operators describe the rotators
which represent identical systems. In the regime where $g\ll 1$,
$-2\lambda_{\textrm{max}}/g^{2}$ corresponds to the ground state energy and
consequently $\lambda_{\textrm{max}}/2$ to
$\langle\Box^{(\mathrm{e})}\rangle$. Now, as long as the Hamiltonian is not
truncated, i.e. $l=L$, we have that $\hat{P}_{i}+\hat{P}_{i}^{\dagger}$ is a
circulant matrix [98] and thus its eigenvalues are given as

$\xi_{j}=2\cos\left(\frac{2\pi j}{2L+1}\right),\quad j=0,1,\dots,2L.$ (80)

Consequently, $\lambda_{\textrm{max}}=2$ and thus
$\langle\Box^{(\mathrm{e})}(g=0)\rangle=1$. However, as soon as the
Hamiltonian is truncated, $\hat{P}_{i}+\hat{P}_{i}^{\dagger}$ is a tridiagonal
Toeplitz matrix [98] with eigenvalues

$\xi_{j}=2\cos\left(\frac{\pi(j+1)}{2l+2}\right),\quad j=0,1,\dots,2l.$ (81)

This yields $-\langle{\psi}|\hat{H}_{B}|{\psi}\rangle\leq
4\cos\left(\frac{\pi}{2l+2}\right)$, which results in a monotonic increase of
$\langle\Box^{(\mathrm{e})}(g=0)\rangle$ with respect to an increase of $l$.
The continuous limit is found for $l\rightarrow\infty$. Since the electric
representations is based on the truncated $U(1)$ group, we conclude that for
$g\ll 1$ it approximates the true $U(1)$ value from below.

Consider now the magnetic representation. The curves in Fig. 4 suggest that
$\langle\Box^{(\mathrm{b})}\rangle$ is monotonically decreasing over the whole
range of $g$ when $l$ is increased. In the following, we qualitatively
motivate this behaviour in the strong coupling regime. When $g\gg 1$,
$\langle\Box^{(\mathrm{b})}\rangle$ can be understood as a Riemann sum of the
discrete eigenvalues of $\hat{H}_{B}^{(\mathrm{b})}$, weighted with the
probabilities corresponding to the different basis states
$|{\boldsymbol{r}}\rangle$. Assume for now $l=L$. Then, the ground state
emerges as the equal superposition of all states (as in Eq. (36), where we
considered the electric representation for $g\ll 1$). The weights of the
Riemann sum are thus all equal to $(2L+1)^{-3}$, meaning that

$\displaystyle\langle\Box^{(\mathrm{b})}\rangle$ $\displaystyle=$
$\displaystyle\sum_{\boldsymbol{r}=-\boldsymbol{L}}^{\boldsymbol{L}}\frac{1}{(2L+1)^{3}}\left[\sum_{i}\cos\left(\frac{2\pi}{2L+1}r_{i}\right)\right.$
(82) $\displaystyle+$
$\displaystyle\left.\cos\left(\frac{2\pi}{2L+1}(r_{1}+r_{2}+r_{3})\right)\right]=0.$

Under the assumption that the distribution of the ground state’s coefficients
$p^{(\mathrm{b})}(g\gg 1,\boldsymbol{r},L)$ (see Sec. 4.1) remains uniform in
$\boldsymbol{r}$ for $l<L$, one can show that this value is larger than zero
for any truncation. In particular,

$\displaystyle\langle\Box^{(\mathrm{b})}\rangle\sim
3(2l+1)^{3}\sin\left(\frac{2\pi(L-l)}{2L+1}\right)\underset{l\rightarrow
L}{\longrightarrow}0^{+}.$ (83)

However, the distribution $p^{(\mathrm{b})}(g\gg 1,\boldsymbol{r},L)$ is not
uniform when $l<L$, but remains center-symmetric. We numerically show in App.
E that removing higher levels increases the amplitudes of states with low
values of $|\boldsymbol{r}|$, and hence enhances positive contributions of the
Riemann sum. In other words, truncation not only removes the negative
contributions stemming from large values of $|\boldsymbol{r}|$ [they appear
for $r_{i}>(2L+1)/4$, see Eq. (82)], but also emphasises positive
contributions. While the first process is analogous to the decrease of the
spread when decreasing $g$, the second is solely originating from the
truncation and we therefore conclude that for any $L$ the approximated value
of $\langle\Box^{(\mathrm{b})}\rangle$ is always larger than the one obtained
from a hypothetical exact diagonalisation employing $U(1)$. Qualitatively,
this effect emerges from the removal of the cyclic property present in the
lowering operator $\hat{P}$ (see Eq. (27) and App. E).

##  Appendix E Truncation effects in the strong coupling regime

Figure 8: Transformation of the ground state distribution after truncation.
Both panels correspond to $l=7$ and $L=8$, the x-axis labels the amplitudes
belonging to $|{\boldsymbol{r}}\rangle$. Compared to (a), (b) shows the effect
when only the elements corresponding to the cyclic property of
$\mathbb{Z}_{2L+1}$ are removed.

In this appendix, we sketch the treatment of the truncation of the cyclic
$\mathbb{Z}_{2L+1}$ group. We consider the strong coupling regime, but employ
the magnetic representation of the Hamiltonian. In the limit
$g\rightarrow\infty$, the electric term, which is composed of operators
$\hat{P}_{j}$, $j=1,2,3$ [see Eq. (27)], is dominant. As such, we ignore the
magnetic Hamiltonian in the following and employ the following ansatz to
obtain the truncated electric field Hamiltonian

$\displaystyle
H_{E,\textrm{truncated}}^{(\mathrm{b})}=\hat{H}_{E,\textrm{untruncated}}^{(\mathrm{b})}-\hat{V}.$
(84)

We hence define the operator $\hat{V}$ to study the effects of the truncation.

In the untruncated $\mathbbm{Z}_{2L+1}$ formulation we can decompose any
$\hat{P}_{j}$ into four terms,

$\displaystyle\hat{P}_{j}$ $\displaystyle=$
$\displaystyle|{L_{j}}\rangle\\!\langle{-L_{j}}|+\sum_{r_{j}=l+1}^{L}|{r_{j}-1}\rangle\\!\langle{r_{j}}|$
(85) $\displaystyle+\sum_{r_{j}=1-L}^{-l}|{r_{j}-1}\rangle\\!\langle{r_{j}}|$
$\displaystyle+\sum_{r_{j}=1-l}^{l}|{r_{j}-1}\rangle\\!\langle{r_{j}}|$
$\displaystyle\equiv$
$\displaystyle\hat{V}^{\prime}_{j}+\hat{P}^{\prime}_{j},$

where
$\hat{P}^{\prime}_{j}=\sum_{r_{j}=1-l}^{l}|{r_{j}-1}\rangle\\!\langle{r_{j}}|$
and $\hat{P}^{\prime}_{j}$ is the rest. Notice that $\hat{P}^{\prime}_{j}$ is
the truncated operator as defined in Eq. (26). We now have to collect all
contributions from $\hat{V}^{\prime}_{j}$ in the electric Hamiltonian
$\hat{H}_{E}^{(\mathrm{b})}$ of Eq. (33). In particular, $\hat{V}$ can be
found from $\hat{H}_{E}^{(\mathrm{b})}$ by applying the rules

$\displaystyle P_{j}+P_{k}^{\dagger}$ $\displaystyle\mapsto$
$\displaystyle\hat{V}^{\prime}_{j}+(\hat{V}_{k}^{\prime})^{\dagger},$
$\displaystyle P_{j}P_{k}$ $\displaystyle\mapsto$
$\displaystyle\hat{V}^{\prime}_{j}(\hat{V}_{k}^{\prime})^{\dagger}+\hat{V}^{\prime}_{j}(\hat{P}_{k}^{\prime})^{\dagger}+\hat{P}^{\prime}_{j}(\hat{V}_{k}^{\prime})^{\dagger}.$
(86)

Note that $\hat{V}$ has as well a diagonal contribution given by

$\displaystyle\sum_{j=1}^{3}\sum_{r_{j}=l+1}^{L}|{r_{j}}\rangle\\!\langle{r_{j}}|+|{-r_{j}}\rangle\\!\langle{-r_{j}}|,$
(87)

stemming from the $\nu=0$ terms in Eq. (33).

The result of a numerical procedure to find the elements of ground state is
shown in Fig. 8(a). We denote the amplitudes of a state obtained with the
untruncated Hamiltonian with the red dashed line. Clearly, the truncation
shifts population from the high $|\boldsymbol{r}|$ states to lower ones. Note
that each $|\boldsymbol{r}|$ can appear multiple times. A crucial fact is
shown in Fig. 8(b), where we removed only the cyclic elements from the
operators $P_{j}$, i.e., the first terms in Eq. (85). This cyclic property is
the reason why the distributions $p^{(\mathrm{b})}(\boldsymbol{r})$ of the
ground state’s coefficients (see Sec. 4.1) are uniform in the untruncated
case. Hence, their removal has a large impact on the derived results.

##  Appendix F Numerical determination of $L_{\rm opt}$

Figure 9: Sequence infidelity for $g^{-2}=100$ and $l=2,3,\dots,10$. The
minimum corresponds to the value of $L$ with the best compromise between
available domain and resolution. Note that this minimum is not always the
global one.

The sequence fidelity calculated in Sec. 4.2 for the ground state of the pure
gauge QED Hamiltonian involves and optimization over $L$. We plot the sequence
infidelity varying the parameters $l$ and $L$ for $g^{-2}=100$ in Fig. 9. For
any value of $l$, a kink is clearly visible, corresponding to $L=L_{\rm opt}$.
Notice that this kink does not always correspond to a global minimum, as can
be seen from the points characterised by $l=2$. As discussed in the main text,
this is the signature of the freezing effect. In fact, the global minimum is
found for $L=l+1=3$ (i.e. its minimal value), where the resolution is
insufficient for both $l=1$ and $l=2$ to capture the distribution of the
untruncated ground state. By increasing $g^{-2}$, the position of the kink is
shifted to higher values of $L$. In particular, $L_{\rm opt}$ takes its
minimal allowed value in the strong coupling regime, and starts to increase at
$g^{-2}\approx 5$ [see Fig. 3(d)]. This follows from the fact that,
approaching the weak coupling regime, the distribution of the untruncated
$U(1)$ ground state becomes more and more localised, and the tails less
important. Note that the value $L_{\rm opt}$ can be determined by a greed
search, starting at the lowest allowed value of $L$.


# Robust excitons across the phase transition of two-dimensional hybrid
perovskites

Jonas D. Ziegler  Dresden Integrated Center for Applied Physics and Photonic
Materials and Würzburg-Dresden Cluster of Excellence ct.qmat, Technische
Universität Dresden, 01062 Dresden, Germany  Department of Physics, University
of Regensburg, 93053 Regensburg, Germany  Kai-Qiang Lin  Department of
Physics, University of Regensburg, 93053 Regensburg, Germany  Barbara
Meisinger  Department of Physics, University of Regensburg, 93053 Regensburg,
Germany  Xiangzhou Zhu  Department of Physics, Technical University of Munich,
85748 Garching, Germany  Manuel Kober-Czerny  Department of Physics,
University of Oxford, Clarendon Laboratory, Oxford OX1 3PU, United Kingdom
Pabitra K. Nayak  Department of Physics, University of Oxford, Clarendon
Laboratory, Oxford OX1 3PU, United Kingdom  TIFR Centre for Interdisciplinary
Sciences, Tata Institute of Fundamental Research, 36/P, Gopanpally Village,
Serilingampally Mandal, Hyderabad 500046, India  Cecilia Vona  Institut für
Physik and IRIS Adlershof, Humboldt-Universität zu Berlin, Berlin Germany
Takashi Taniguchi  International Center for Materials Nanoarchitectonics,
National Institute for Materials Science, Tsukuba, Ibaraki 305-004, Japan
Kenji Watanabe  Research Center for Functional Materials, National Institute
for Materials Science, Tsukuba, Ibaraki 305-004, Japan  Claudia Draxl
Institut für Physik and IRIS Adlershof, Humboldt-Universität zu Berlin, Berlin
Germany  Henry J. Snaith  Department of Physics, University of Oxford,
Clarendon Laboratory, Oxford OX1 3PU, United Kingdom  John M. Lupton
Department of Physics, University of Regensburg, 93053 Regensburg, Germany
David A. Egger  Department of Physics, Technical University of Munich, 85748
Garching, Germany  Alexey Chernikov<EMAIL_ADDRESS>Dresden
Integrated Center for Applied Physics and Photonic Materials and Würzburg-
Dresden Cluster of Excellence ct.qmat, Technische Universität Dresden, 01062
Dresden, Germany  Department of Physics, University of Regensburg, 93053
Regensburg, Germany

###### Abstract

Two-dimensional halide perovskites are among intensely studied materials
platforms profiting from solution based growth and chemical flexibility. They
feature exceptionally strong interactions among electronic, optical as well as
vibrational excitations and hold a great potential for future optoelectronic
applications. A key feature for these materials is the occurrence of
structural phase transitions that can impact their functional properties,
including the electronic band gap and optical response dominated by excitons.
However, to what extent the phase-transitions in two-dimensional perovskites
alter the fundamental exciton properties remains barely explored so far. Here,
we study the influence of the phase transition on both exciton binding energy
and exciton diffusion, demonstrating their robust nature across the phase
transition. These findings are unexpected in view of the associated
substantial changes of the free carrier masses, strongly contrast broadly
considered effective mass and drift-diffusion transport mechanisms,
highlighting the unusual nature of excitons in two-dimensional perovskites.

Keywords: 2D perovskites, excitons, phase-transition, diffusion

Coulomb-bound electron-hole pairs, commonly known as excitons, dominate the
optical response of nanostructured materials [1]. A prominent example are two-
dimensional (2D) Ruddlesden-Popper halide perovskites hosting tightly-bound,
mobile exciton quasiparticles [2, 3, 4, 5, 6, 7, 8, 9]. Excitons in 2D
perovskites are primarily responsible for the absorption and emission of
light, governing key material properties for high-efficiency photovoltaic and
lighting applications [10, 11, 12, 13, 14, 15, 16]. They combine very high
binding energies up to 0.5 eV with sizable mobilities [17, 18, 19], exhibiting
efficient transport from ambient conditions down to cryogenic temperatures
[20]. These properties render the material system a promising platform for
future optoelectronics and offers a rich playground to study fundamental
physics of interacting quasiparticles.

In addition to strongly bound excitons, 2D halide perovskites incorporate a
soft crystal lattice featuring highly efficient exciton-phonon coupling and
possible polaronic effects [4, 21, 22, 23, 24, 25]. A particularly interesting
phenomenon in this regard are the structural phase transitions [26, 27] that
2D perovskites inherit from their bulk counterparts. It involves temperature-
induced changes of the crystal symmetry with more recent findings indicating a
dynamic order-disorder transition [28]. Phase transitions in 2D perovskites
often occur close to room-temperature, strongly affect the optical properties
[29, 30], are sensitive to the layer thickness [5], and were recently shown to
change the effective masses of the charge carriers [7, 31]. They represent a
key feature of this class of materials with potential implications for the
design of perovskite-based optoelectronic devices and their response to
temperature.

However, the fundamental properties of excitons in 2D perovskites remain
essentially unexplored at the phase transition. While a recent study finds
strong changes in the diamagnetic shifts [7] attributed to changes of the
exciton total mass, the impact of the phase transition on both binding energy
and diffusion of excitons are not known. Moreover, the occurrence of a
structural phase transition offers a unique opportunity to investigate
fundamental properties of excitons including their transport behavior in a
well-defined experimental scenario. This is particularly relevant for the case
of 2D halide perovskites, as the excitons represent a considerable challenge
for appropriate descriptions, exacerbated by their intermediate Wannier-
Frenkel nature and the strong coupling to phonons.

Here, we address these questions by studying excitonic properties across a
structural phase transition in 2D perovskites. Using a combination of non-
linear spectroscopy and transient microscopy we determine temperature-
dependent exciton binding energies and monitor exciton diffusion at
temperatures directly above and below the phase transition. First-principles
calculations demonstrate changes of the carrier masses between the two phases
that are concurrent with modification of the single-particle band gap
accounting for the observed spectral shift. Surprisingly, both exciton binding
energies and the diffusion coefficients are found to be constant between low-
and high-temperature phases. These results strongly suggest that excitonic
properties do not trivially scale with free carrier masses, challenging the
appropriate description of excitons and their dynamics in 2D halide
perovskites.

In our study we used thin layers exfoliated from 2D butylammonium-lead-iodide
crystals, $(n=1)$ BA2-PbI4, with about 50 nm thickness, encapsulated between
hBN layers for environmental protection [32] and transferred onto SiO2/Si
substrates. The samples were placed into helium-cooled microscopy cryostats
for optical measurements. We used a 80 MHz tunable 140 fs Ti:Sapphire laser
for excitation in photoluminescence (PL) experiments and a tungsten-halogen
whitelight source for reflectance. The incident light was focused to a spot
with about 1 $\mu$m diameter. The PL was then either dispersed by a grating or
deflected by a mirror to obtain spectrally- and spatially-resolved response,
respectively. A CCD-sensor was used for time-integrated signals and we
employed a streak-camera for time-resolved detection; additional details are
provided in the Supplementary Information (SI).

Phase Transition in 2D Perovskites. The structure of the studied BA2PbI4
crystals is schematically illustrated in Fig. 1 (a). The inorganic layers
composed of PbI4 octahedra host the electronic states forming conduction and
valence bands at the fundamental band gap of the material. The organic chains
between the layers effectively serve as barriers in this natural multi-
quantum-well structure. The phase transition, driven by the ordering of the
butylammonium chains, changes the relative alignment of the octahedra between
the phases [29]. In the high-temperature phase (HT), recent findings emphasize
both strong anharmonic fluctuations of the tilt angle and indications of an
order-disorder transition [28]. In the low-temperature (LT) phase, the
octahedra become effectively locked at a larger average distortion angle
$\delta$ [31] illustrated in Fig. 1 (b).

Figure 1: Structural phase transition in two-dimensional perovskites a.
Schematic illustration of the layered structure of $(n=1)$ BA2PbI4, consisting
of alternating organic (butylammonium, BA) and inorganic layers (PbI4) with
layer number $n$. b. Illustration of thermally-induced anharmonic fluctuations
of the octahedral tilting in the high-temperature phase (HT), and an effective
locking with a larger average distortion $\delta$ in the low temperature phase
(LT). c. Measured PL spectra of an hBN-encapsulated BA2PbI4 thin layer for
different temperatures across the phase transition at T${}_{PT}=270K$.

The impact of the phase transition on the optical response of layered
alkylammonium lead-iodide perovskites is primarily associated with a spectral
shift on the order of 100 meV [29, 5]. PL spectra of the studied BA2PbI4
samples presented in Fig. 1 (c) demonstrate this characteristic effect. As the
temperature increases, the dominant exciton peak abruptly shifts to lower
energies by 120 meV at about $T=270$ K, corresponding to the known temperature
range of the phase transition in this class of materials [27, 29]. In
addition, the spectra exhibit a continuous, smooth increase of the spectral
linewidth from thermal population of vibrational modes and increasingly rapid
exciton-phonon scattering at higher temperatures [4].

For a theoretical analysis, we perform electronic-structure calculations using
density-functional theory (DFT). To this end we utilize two different DFT
codes: VASP [33], implementing the projector augmented wave potentials [34]
uses a plane-wave basis set, and the all-electron full-potential code exciting
[35], based on the linearized augmented planewave method. We first apply the
PBE functional [36], augmented by van-der Waals corrections calculated with
the Tkatchenko-Scheffler method [37] to describe exchange-correlation
interactions, and include the effects of the spin-orbit coupling (SOC).
Following previous work [31], in Fig. 2 we show the main changes of the
electronic band structure across the phase transition. We observe a
substantial difference of 240 meV in the electronic band gap between the HT
and LT phase. Thereby SOC has a substantial contribution as verified by
additional calculations for a model structure where the BA cations are
replaced by Cs (see SI and Ref. [38]). More specifically, without accounting
for SOC we find that the gap changes by only about 110 meV going from the LT
to the HT phase.

Using the same procedure, we also perform calculations with the hybrid
functional HSE06 [39] as implemented in exciting [40]. As expected, the HSE06
functional has a strong impact on the band-gap, increasing it in both phases
by $\sim$0.6 eV (see Fig. 2) but, hence, does not alter the differences across
the phase transition. Similarly, the absolute values of the effective masses
that are substantially lower in the HT phase are confirmed by both PBE and
HSE06 calculations.

Figure 2: Electronic band structure across the phase transition. The Kohn-Sham
band energies, computed by PBE including SOC are shown between $\Gamma$ and S
(S=0.5 0.5 0) for the optimized crystal structures of BA2PbI4. The VBM of both
phases are aligned at zero. The trends in the differences of the band gap and
effective masses are consistent between PBE and HSE06 (see SI and Ref. [38]).
Figure 3: Temperature-dependent exciton binding energy  a. Two-photon
photoluminescence excitation (TPLE) and PL spectra of BA2PbI4 at $T=5$ K. The
reflectance contrast spectrum corresponding to the changes of reflectance
relative to the substrate is presented in the same graph for comparison. b. PL
and TPLE spectra measured for the LT and HT phases at $T=260$ K and $T=275$ K,
respectively. The spectra are corrected for changes in the effective
absorption due to the multi-layer interference effects. The energy separation
between ground and excited state $\Delta_{2p-1s}$, proportional to the
respective exciton binding energy, is indicated by the dashed lines. c.
Temperature-dependent $\Delta_{2p-1s}$ and the corresponding exciton binding
energy $E_{b}$, indicated on the right y-axis. For this analysis, the $1s$
energy was determined from reflectance contrast to exclude influence of the
temperature-dependent Stokes shift, presented in the inset. The fitting error
is below the size of spheres and the gray line is a guide to the eye.

Hence, based on various electronic-structure methods, we find that part of the
experimentally observed energy shift, can already be attributed to effects
that occur at the single-particle level. Specifically, the effect is a direct
consequence of the changes in the average out-of-plane distortion angle of
PbI4 octahedra [31]: a smaller distortion angle in the HT phase leads to a
stronger electronic coupling between individual octahedra and hence to a
larger bandwidth and a smaller band gap. For the same reason, the effective
masses are substantially smaller in the HT than in the LT phase, which is in
line with previous measurements of the diamagnetic shifts and theoretical work
[7]. Moreover, by lifting certain degeneracies of the Pb states SOC manifests
itself in additional changes of the band gap and effective masses. Therefore,
when assuming Wannier-type excitons and band-like transport, one would expect
both exciton binding energy and exciton diffusion to change accordingly across
the phase transition.

Figure 4: Exciton diffusion at the phase transition a. Representative streak
camera image of the spatially- and time-resolved exciton emission for the LT
phase ($T=260$ K). The data is normalized at each time step. b. Extracted
change of the mean-squared displacement $\Delta\sigma^{2}$ for the LT and HT
phases as a function of time. Diffusion coefficients are obtained from the
slope $\Delta\sigma^{2}(t)$ indicated by solid lines. c. Temperature dependent
PL linewidth determined from Lorentz fits presented as full-width-at-half-
maximum, corresponding to the change of the exciton-phonon scattering rate. d.
Box chart summarizing measured exciton diffusion coefficients ($N=29$) across
the phase transition for both phases in the temperature range between 260 and
274 K. The spread in the data stems from different samples and sample
positions. Estimated values from a semi-classical drift-diffusion model based
on calculated effective masses and scattering times obtained from PL
linewidths are indicated.

Exciton binding energy. To measure exciton binding energy as a function of
temperature across the phase transition we employed two-photon
photoluminescence excitation (TPLE) spectroscopy; details of the setup are
given in the SI and Ref. [41]. The PL signal of the ground state exciton above
2.3 eV was detected as a function of the laser photon energy tuned between
1.24 and 1.77 eV. In this spectral range, exciton states with $p$-type orbital
symmetry determine two-photon absorption [42] and the resulting TPLE signal is
usually dominated by the $2p$ transition [42, 43, 44]. The advantage of TPLE,
in contrast to linear spectroscopy, is the suppression of direct optical
transitions allowing us to detect spectrally broad, weaker signals from
excited exciton states both at low and elevated temperatures. An exemplary
TPLE spectrum of a BA2PbI4 sample is presented in the top panel of Fig. 3 (a)
together with the corresponding PL data at lattice temperature of 5 K. Both
the ground and excited states are in good agreement with the measured
reflectance contrast spectrum, shown for direct comparison. The analysis of
the reflectance spectra using a transfer matrix approach further allows us to
correct the measured TPLE spectra for effective two-photon absorption from
multi-layer interferences (see SI).

The strongest resonance in the reflectance spectra and the high-energy peak of
the PL at 2.54 eV stems from the ground-state exciton transition ($1s$). It
features weaker replica on the high energy side, commonly attributed to
phonon-sidebands [21, 24] mimicking the low-energy side of the PL at 5 K (c.f.
Fig. 1 (b)). The maximum of the TPLE spectrum at 2.85 eV corresponds to the
$2p$ energy with the high-energy flank attributed to weaker contributions of
$3p$, $4p$,… etc. resonances. In addition, the $2p$ peak closely corresponds
to the energy of the $2s$ transition weakly visible in the reflectance
spectrum. The energy separation between $2p$ and $1s$ as well as the near-
degeneracy of $2p$ and $2s$ excited states are consistent with large exciton
binding energies and the properties of excited states in 2D perovskites [3, 5,
6, 8].

Figure 3 (b) presents PL and TPLE spectra for two temperatures close to the
structural phase transition in the HT and LT regime. At these elevated
temperatures, the $1s$ and $2p$ resonances broaden and their energy separation
slightly increases in comparison to the 5 K data. The main difference between
HT and LT spectra is a shift of both ground and excited state peaks to lower
energies of about 120$\pm 10$ meV. The magnitude of the shift is thus
essentially the same as for the single-photon PL presented in Fig. 1 (c),
compared to values between 110 and 240 meV predicted by first-principles
calculations (c.f. Fig. 2). Their relative separation $\Delta_{2p-1s}$,
however, remains constant. Temperature-dependent values for $\Delta_{2p-1s}$
are summarized in Fig. 3 (c). Here, the $1s$ energy is determined from
reflectance contrast instead of PL to exclude the influence of the
temperature-dependent Stokes shift, presented in the inset. The Stokes shift
is on the order of 20 meV for both LT and HT regions at the phase transition
and changes smoothly as a function of temperature. The exciton binding energy
$E_{b}$ is then estimated by taking advantage of linear scaling with the
energy separation $\Delta_{2p-1s}$. We use the relationship
$E_{b}=1.2\times\Delta_{2p-1s}$ from the literature [8] and present
temperature-dependent binding energy on the right y-axis in Fig. 3 (c).

The absolute values for the exciton binding energy around 400 meV in BA2PbI4
correspond well to the previously reported low-temperature results [3, 5, 6].
Interestingly, however, the binding energy does not change between LT and HT
phases across the phase transition. This result is rather surprising, since
the reduced effective mass $\mu=m_{h}m_{e}/(m_{h}+m_{e})$ (see Fig. 2 (b))
changes from 0.15 (LT) to 0.11 m0 (HT) across the phase transition. Since the
exciton binding energy typically scales linearly with the reduced mass in the
Wannier model [1], these changes should lead to a sharp decrease of the
binding energy by as much as about 40% in the HT phase. Instead, the exciton
binding energy is not only constant between LT and HT phases, but also appears
to continuously increase with temperature up to 20% from 5 to 290 K. We note
that if we neglect the influence of the Stokes shift, the increase of the
binding energy would appear even more pronounced.

Exciton Diffusion Coefficient. Following the analysis of exciton binding
energies, we examine the exciton diffusion – a process commonly expected to be
affected by the total mass of the exciton. Experimentally, exciton propagation
is monitored by detecting spatially- and time-resolved PL for a series of
temperatures across the phase transition. The samples are excited using energy
densities from a few to several 10’s of nJ/cm2 per pulse. We confirm the
absence of density-dependent effects such as exciton-exciton annihilation [45]
(see SI) and perform a series of measurements on different samples and spot
positions. A typical streak camera image of the time-dependent cross-section
$x$ is shown in Fig. 4 (a) for the LT phase at $T=260$ K. The signal is
normalized at each time step, illustrating continuous broadening of the
exciton cloud. For the analysis the PL intensity profiles are fitted with
Gaussian distributions $\propto exp[-x^{2}/2\sigma(t)^{2}]$ at time intervals
of $\Delta t=100$ ps. The extracted time-dependent change of the variance
$\Delta\sigma(t)^{2}$ is presented in Fig. 4 (b) for LT and HT phases at the
temperatures of 260 and 270 K, respectively. The corresponding phase is
verified ahead of the diffusion measurements at every temperature and sample
position using spectrally resolved PL, as shown in Fig. 1 (c).

As it is characteristic for diffusive propagation, the variance increases
linearly with time for both LT and HT cases. In contrast to the spectral shift
of the emission energy, however, the diffusion coefficients $D$ extracted from
the slope of $\Delta\sigma^{2}=2Dt$ [46] are essentially the same. This
observation is accompanied by a nearly continuous increase of the exciton-
phonon scattering rate with temperature, reflected in the change of the PL
spectral linewidth [4] in Fig. 4 (c). Within the framework of the semi-
classical band-like propagation model, the diffusion coefficient scales with
the temperature $T$, exciton mass $M_{X}$ and scattering rate $\hbar/\tau$ as
$D=(k_{B}T\times\tau)/M_{X}$. Consequently, we would expect the diffusivity to
follow the change of the total exciton mass by a factor of 1.5 across the
phase transition (see Fig. 2), taking into account the nearly constant
scattering rate. In contrast to that, the nearly equal diffusion coefficients
of the LT and HT phase mimic the lack of change in the exciton binding energy.
We further note that the absolute values of the diffusion coefficients vary
for different flakes and sample positions, as illustrated by the box chart in
Fig. 4 (d). Nevertheless, we do not find any systematic differences of the
diffusion coefficients across the phase transition, compared to the semi-
classical expectation values from calculated exciton masses (c.f. Fig. 2).

Discussion Excitons in 2D perovskites combine seemingly conflicting
properties: on the one hand, they show large exciton binding energies that are
typically associated with localized Frenkel-type states. On the other, the
relatively low effective masses and the efficient exciton transport suggest
wavefunctions extending over many unit cells, which is typically a Wannier-
type feature. The latter consideration also manifests itself in the successful
application of effective mass models with modified thin-film Coulomb
potentials in combination with first-principles calculations to describe key
exciton properties such as binding energies and Bohr radii [3, 6, 7, 8, 9].
These models typically involve parameters such as appropriate dielectric
screening constants of the organic and inorganic layers and the reduced
exciton mass.

Our study provides a unique opportunity to assess such models for BA2PbI4,
since the phase transition is associated with a change in the average crystal
structure, as mentioned above. Indeed we find, in line with previous work,
that along with the change of the structure the band gap and effective masses
of the system are also modified across the phase transition. Interestingly,
while the band gap change is at least qualitatively reflected in the spectral
shift of the optical transition, the difference of effective masses does not
manifest itself in any accompanying changes of the exciton binding energy and
diffusion constant. Clearly, the canonical effective-mass theory for these two
key properties does not appear fully consistent with the experimental
findings. Consequently, our understanding of the exciton properties of 2D
perovskites should be reconsidered, potentially along the following lines.

In this context, the observation of a constant exciton binding energy at the
structural phase transition strongly implies that the dependence on the
effective mass of the free carriers is substantially weaker than commonly
assumed. It is conceivable that the exciton wavefunction could spread over a
sufficiently large region of the reciprocal space beyond the effective mass
approximation, where the effect of the phase transition on the band curvature
may be reduced. Another possibility involves the change of the dielectric
screening [47] in the appropriate frequency range, given by the binding
energy, that offsets the difference of the carrier masses. It is also possible
that the relevant values for the quasiparticle masses are determined by
polaronic effects that may not change too drastically at the phase transition.
Renormalization of the effective mass could also be connected to the observed
increase of the exciton binding energy with rising temperature.

Similar considerations can be suggested for exciton diffusion in BA2PbI4. In
3D halide perovskites, a dynamic disorder picture has been put forward, which
takes into account the strong local fluctuations in the lattice away from the
average structure and rationalizes key transport properties in this manner
[48, 49, 50]. While there are important differences between 3D and 2D
perovskites, it is interesting that anharmonic fluctuations were recently
demonstrated also for the 2D systems [28]. Since exciton diffusion appears to
be essentially immune to changes in the effective mass of the average
structure, one could speculate that it could be also largely governed by local
fluctuations of the lattice. It is still intriguing, however, that the semi-
classical description seems to account for temperature-dependent transport of
free excitons in a related system, 2D phenylethylammonium-lead iodide [20].
However, the general applicability of such models can be challenged in view of
the exciton mean free path being typically smaller than their wavepacket size,
given by the de Broglie wavelength [51, 50]. The observed inadequacy of the
semi-classical prediction for the change of the diffusion coefficients at the
phase transition provides additional experimental evidence that alternative
descriptions for the exciton transport in 2D perovskites should be explored.

## Conclusions

In summary, we have explored the impact of the structural phase transition in
2D perovskites on the exciton properties. Temperature-dependent exciton
binding energy and exciton diffusion was monitored across the phase transition
using a combination of non-linear spectroscopy and time-resolved microscopy.
Both exciton binding energy and exciton diffusion are found to be unaffected
by the phase transition. These findings go beyond the expectations of the
effective mass description of the excitons and the semi-classical
understanding of their transport. Our results highlight the unusual behavior
of excitons in this class of materials and strongly motivate further
developments for their description. Moreover, the robust nature of the
excitons with respect to substantial changes of the crystal structure seems
particularly promising from the perspective of applications.

## Acknowledgements

We thank our colleagues Matan Menahem, Omer Yaffe, Paulina Plochocka, and
Michal Baranowski for helpful discussions. Financial support by the DFG via
SPP2196 Priority Program (Project-ID: 424709454) and Emmy Noether Initiative
(CH 1672/1, Project-ID: 287022282) as well as the Würzburg-Dresden Cluster of
Excellence on Complexity and Topology in Quantum Matter ct.qmat (EXC 2147,
Project-ID 390858490) is gratefully acknowledged. D.A.E. acknowledges funding
from the Alexander von Humboldt Foundation within the framework of the Sofja
Kovalevskaja Award, endowed by the German Federal Ministry of Education and
Research; the Technical University of Munich - Institute for Advanced Study,
funded by the German Excellence Initiative and the European Union Seventh
Framework Programme under Grant Agreement No. 291763; the DFG under Germany’s
Excellence Strategy - EXC 2089/1–390776260, and the Gauss Centre for
Supercomputing e.V. (www.gauss-centre.eu) for funding this project by
providing computing time through the John von Neumann Institute for Computing
(NIC) on the GCS Supercomputer JUWELS at Jülich Supercomputing Centre (JSC).
K.W. and T.T. acknowledge support from the Elemental Strategy Initiative
conducted by the MEXT, Japan (Grant Number JPMXP0112101001) and JSPS KAKENHI
(Grant Numbers 19H05790, 20H00354 and 21H05233). C.V. acknowledges the North-
German Supercomputing Alliance (HLRN) for providing computational resources.

## References

  * Haug and Koch [2009] H. Haug and S. W. Koch,  _Quantum theory of the optical and electronic properties of semiconductors_ , 5th ed. (World Scientific, Singapore, 2009).
  * Ishihara  _et al._ [1989] T. Ishihara, J. Takahashi, and T. Goto, Exciton state in two-dimensional perovskite semiconductor (C10H21NH3)2PbI4, Solid State Commun. 69, 933 (1989).
  * Tanaka  _et al._ [2005] K. Tanaka, T. Takahashi, T. Kondo, T. Umebayashi, K. Asai, and K. Ema, Image charge effect on two-dimensional excitons in an inorganic-organic quantum-well crystal, Phys. Rev. B 71, 045312 (2005).
  * Gauthron  _et al._ [2010] K. Gauthron, J.-S. Lauret, L. Doyennette, G. Lanty, A. Al Choueiry, S. J. Zhang, A. Brehier, L. Largeau, O. Mauguin, J. Bloch, and E. Deleporte, Optical spectroscopy of two-dimensional layered (C6H5C2H4-NH3)2-PbI4 perovskite, Opt. Express 18, 5912 (2010).
  * Yaffe  _et al._ [2015] O. Yaffe, A. Chernikov, Z. M. Norman, Y. Zhong, A. Velauthapillai, A. van der Zande, J. S. Owen, and T. F. Heinz, Excitons in ultrathin organic-inorganic perovskite crystals, Phys. Rev. B 92, 045414 (2015).
  * Blancon  _et al._ [2018] J.-C. Blancon, A. V. Stier, H. Tsai, W. Nie, C. C. Stoumpos, B. Traoré, L. Pedesseau, M. Kepenekian, F. Katsutani, G. T. Noe, J. Kono, S. Tretiak, S. A. Crooker, C. Katan, M. G. Kanatzidis, J. J. Crochet, J. Even, and A. D. Mohite, Scaling law for excitons in 2D perovskite quantum wells, Nat. Commun. 9, 2254 (2018).
  * Baranowski  _et al._ [2019] M. Baranowski, S. J. Zelewski, M. Kepenekian, B. Traoré, J. M. Urban, A. Surrente, K. Galkowski, D. K. Maude, A. Kuc, E. P. Booker, R. Kudrawiec, S. D. Stranks, and P. Plochocka, Phase-Transition-Induced Carrier Mass Enhancement in 2D Ruddlesden–Popper Perovskites, ACS Energy Lett. 4, 2386 (2019).
  * Cho and Berkelbach [2019] Y. Cho and T. C. Berkelbach, Optical Properties of Layered Hybrid Organic–Inorganic Halide Perovskites: A Tight-Binding GW-BSE Study, J. Phys. Chem. Lett. 10, 6189 (2019).
  * Cho  _et al._ [2021] Y. Cho, S. M. Greene, and T. C. Berkelbach, Simulations of Trions and Biexcitons in Layered Hybrid Organic-Inorganic Lead Halide Perovskites, Phys. Rev. Lett. 126, 216402 (2021).
  * Kumar  _et al._ [2016] S. Kumar, J. Jagielski, S. Yakunin, P. Rice, Y.-C. Chiu, M. Wang, G. Nedelcu, Y. Kim, S. Lin, E. J. G. Santos, M. V. Kovalenko, and C.-J. Shih, Efficient Blue Electroluminescence Using Quantum-Confined Two-Dimensional Perovskites, ACS Nano 10, 9720 (2016).
  * Tsai  _et al._ [2016] H. Tsai, W. Nie, J.-C. Blancon, C. C. Stoumpos, R. Asadpour, B. Harutyunyan, A. J. Neukirch, R. Verduzco, J. J. Crochet, S. Tretiak, L. Pedesseau, J. Even, M. A. Alam, G. Gupta, J. Lou, P. M. Ajayan, M. J. Bedzyk, M. G. Kanatzidis, and A. D. Mohite, High-efficiency two-dimensional Ruddlesden–Popper perovskite solar cells, Nature 536, 312 (2016).
  * Wang  _et al._ [2016] N. Wang, L. Cheng, R. Ge, S. Zhang, Y. Miao, W. Zou, C. Yi, Y. Sun, Y. Cao, R. Yang, Y. Wei, Q. Guo, Y. Ke, M. Yu, Y. Jin, Y. Liu, Q. Ding, D. Di, L. Yang, G. Xing, H. Tian, C. Jin, F. Gao, R. H. Friend, J. Wang, and W. Huang, Perovskite light-emitting diodes based on solution-processed self-organized multiple quantum wells, Nat. Photonics 10, 699 (2016).
  * Tsai  _et al._ [2018] H. Tsai, W. Nie, J.-C. Blancon, C. C. Stoumpos, C. M. M. Soe, J. Yoo, J. Crochet, S. Tretiak, J. Even, A. Sadhanala, G. Azzellino, R. Brenes, P. M. Ajayan, V. Bulović, S. D. Stranks, R. H. Friend, M. G. Kanatzidis, and A. D. Mohite, Stable Light-Emitting Diodes Using Phase-Pure Ruddlesden-Popper Layered Perovskites, Adv. Mater. 30, 1704217 (2018).
  * Chen  _et al._ [2018] Y. Chen, Y. Sun, J. Peng, J. Tang, K. Zheng, and Z. Liang, 2D Ruddlesden-Popper Perovskites for Optoelectronics, Adv. Mater. 30, 1703487 (2018).
  * Liang  _et al._ [2021] C. Liang, H. Gu, Y. Xia, Z. Wang, X. Liu, J. Xia, S. Zuo, Y. Hu, X. Gao, W. Hui, L. Chao, T. Niu, M. Fang, H. Lu, H. Dong, H. Yu, S. Chen, X. Ran, L. Song, B. Li, J. Zhang, Y. Peng, G. Shao, J. Wang, Y. Chen, G. Xing, and W. Huang, Two-dimensional Ruddlesden–Popper layered perovskite solar cells based on phase-pure thin films, Nat. Energy 6, 38 (2021).
  * Chen  _et al._ [2020] H. Chen, J. Lin, J. Kang, Q. Kong, D. Lu, J. Kang, M. Lai, L. N. Quan, Z. Lin, J. Jin, L. Wang, M. F. Toney, and P. Yang, Structural and spectral dynamics of single-crystalline Ruddlesden-Popper phase halide perovskite blue light-emitting diodes, Sci. Adv. 6, eaay4045 (2020).
  * Deng  _et al._ [2020] S. Deng, E. Shi, L. Yuan, L. Jin, L. Dou, and L. Huang, Long-range exciton transport and slow annihilation in two-dimensional hybrid perovskites, Nat. Commun. 11, 664 (2020).
  * Seitz  _et al._ [2020] M. Seitz, A. J. Magdaleno, N. Alcázar-Cano, M. Meléndez, T. J. Lubbers, S. W. Walraven, S. Pakdel, E. Prada, R. Delgado-Buscalioni, and F. Prins, Exciton diffusion in two-dimensional metal-halide perovskites, Nat. Commun. 11, 2035 (2020).
  * Xiao  _et al._ [2020] K. Xiao, T. Yan, Q. Liu, S. Yang, C. Kan, R. Duan, Z. Liu, and X. Cui, Many-body effect in optical properties of monolayer molybdenum diselenide,  (2020), arXiv:2008.10801 .
  * Ziegler  _et al._ [2020] J. D. Ziegler, J. Zipfel, B. Meisinger, M. Menahem, X. Zhu, T. Taniguchi, K. Watanabe, O. Yaffe, D. A. Egger, and A. Chernikov, Fast and Anomalous Exciton Diffusion in Two-Dimensional Hybrid Perovskites, Nano Lett. 20, 6674 (2020).
  * Straus  _et al._ [2016] D. B. Straus, S. Hurtado Parra, N. Iotov, J. Gebhardt, A. M. Rappe, J. E. Subotnik, J. M. Kikkawa, and C. R. Kagan, Direct Observation of Electron–Phonon Coupling and Slow Vibrational Relaxation in Organic–Inorganic Hybrid Perovskites, J. Am. Chem. Soc. 138, 13798 (2016).
  * Guo  _et al._ [2016] Z. Guo, X. Wu, T. Zhu, X. Zhu, and L. Huang, Electron–Phonon Scattering in Atomically Thin 2D Perovskites, ACS Nano 10, 9992 (2016).
  * Wright  _et al._ [2016] A. D. Wright, C. Verdi, R. L. Milot, G. E. Eperon, M. A. Pérez-Osorio, H. J. Snaith, F. Giustino, M. B. Johnston, and L. M. Herz, Electron–phonon coupling in hybrid lead halide perovskites, Nat. Commun. 7, 11755 (2016).
  * Urban  _et al._ [2020] J. M. Urban, G. Chehade, M. Dyksik, M. Menahem, A. Surrente, G. Trippé-Allard, D. K. Maude, D. Garrot, O. Yaffe, E. Deleporte, P. Plochocka, and M. Baranowski, Revealing Excitonic Phonon Coupling in 2D Layered Perovskites, J. Phys. Chem. Lett. 11, 5830 (2020).
  * Srimath Kandada and Silva [2020] A. R. Srimath Kandada and C. Silva, Exciton Polarons in Two-Dimensional Hybrid Metal-Halide Perovskites, J. Phys. Chem. Lett. 11, 3173 (2020).
  * Kind [1980] R. Kind, Structural phase transitions in perovskite layer structures, Ferroelectrics 24, 81 (1980).
  * Billing and Lemmerer [2007] D. G. Billing and A. Lemmerer, Synthesis, characterization and phase transitions in the inorganic–organic layered perovskite-type hybrids, Acta Crystallogr. Sect. B Struct. Sci. 63, 735 (2007).
  * Menahem  _et al._ [2021] M. Menahem, Z. Dai, S. Aharon, R. Sharma, M. Asher, Y. Diskin-Posner, R. Korobko, A. M. Rappe, and O. Yaffe, Strongly Anharmonic Octahedral Tilting in Two-Dimensional Hybrid Halide Perovskites, ACS Nano 15, 10153 (2021).
  * Ishihara  _et al._ [1990] T. Ishihara, J. Takahashi, and T. Goto, Optical properties due to electronic transitions in two-dimensional semiconductors (CnH2n+1NH3)2PbI4, Phys. Rev. B 42, 11099 (1990).
  * Martín-García  _et al._ [2021] B. Martín-García, D. Spirito, G. Biffi, S. Artyukhin, Francesco Bonaccorso, and R. Krahne, Phase Transitions in Low-Dimensional Layered Double Perovskites: The Role of the Organic Moieties, J. Phys. Chem. Lett. 12, 280 (2021).
  * Dyksik  _et al._ [2020] M. Dyksik, H. Duim, X. Zhu, Z. Yang, M. Gen, Y. Kohama, S. Adjokatse, D. K. Maude, M. A. Loi, D. A. Egger, M. Baranowski, and P. Plochocka, Broad Tunability of Carrier Effective Masses in Two-Dimensional Halide Perovskites, ACS Energy Lett. 5, 3609 (2020).
  * Seitz  _et al._ [2019] M. Seitz, P. Gant, A. Castellanos-Gomez, and F. Prins, Long-Term Stabilization of Two-Dimensional Perovskites by Encapsulation with Hexagonal Boron Nitride, Nanomaterials 9, 1120 (2019).
  * Kresse and Furthmüller [1996] G. Kresse and J. Furthmüller, Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set, Phys. Rev. B 54, 11169 (1996).
  * Kresse and Joubert [1999] G. Kresse and D. Joubert, From ultrasoft pseudopotentials to the projector augmented-wave method, Phys. Rev. B 59, 1758 (1999).
  * Gulans  _et al._ [2014] A. Gulans, S. Kontur, C. Meisenbichler, D. Nabok, P. Pavone, S. Rigamonti, S. Sagmeister, U. Werner, and C. Draxl, exciting: a full-potential all-electron package implementing density-functional theory and many-body perturbation theory, J. Phys.: Condens. Matter 26, 363202 (2014).
  * Perdew  _et al._ [1996] J. P. Perdew, K. Burke, and M. Ernzerhof, Generalized Gradient Approximation Made Simple, Phys. Rev. Lett. 77, 3865 (1996).
  * Tkatchenko and Scheffler [2009] A. Tkatchenko and M. Scheffler, Accurate Molecular Van Der Waals Interactions from Ground-State Electron Density and Free-Atom Reference Data, Phys. Rev. Lett. 102, 073005 (2009).
  * Vona  _et al._ [2022a] C. Vona, X. Zhu, D. Egger, and C. Draxl, in preparation (2022a).
  * Krukau  _et al._ [2006] A. V. Krukau, O. A. Vydrov, A. F. Izmaylov, and G. E. Scuseria, Influence of the exchange screening parameter on the performance of screened hybrid functionals, J. Chem. Phys. 125, 224106 (2006).
  * Vona  _et al._ [2022b] C. Vona, D. Nabok, and C. Draxl, Electronic structure of (organic-)inorganic metal halide perovskites: The dilemma of choosing the right functional, Adv. Theory Simul. 5, 2100496 (2022b).
  * Lin  _et al._ [2021] K.-Q. Lin, C. S. Ong, S. Bange, P. E. Faria Junior, B. Peng, J. D. Ziegler, J. Zipfel, C. Bäuml, N. Paradiso, K. Watanabe, T. Taniguchi, C. Strunk, B. Monserrat, J. Fabian, A. Chernikov, D. Y. Qiu, S. G. Louie, and J. M. Lupton, Narrow-band high-lying excitons with negative-mass electrons in monolayer WSe2, Nat. Commun. 12, 5500 (2021).
  * Wang  _et al._ [2005] F. Wang, G. Dukovic, L. E. Brus, and T. F. Heinz, The optical resonances in carbon nanotubes arise from excitons., Science 308, 838 (2005).
  * Ye  _et al._ [2014] Z. Ye, T. Cao, K. O’Brien, H. Zhu, X. Yin, Y. Wang, S. G. Louie, and X. Zhang, Probing excitonic dark states in single-layer tungsten disulphide, Nature 513, 214 (2014).
  * Berkelbach  _et al._ [2015] T. C. Berkelbach, M. S. Hybertsen, and D. R. Reichman, Bright and dark singlet excitons via linear and two-photon spectroscopy in monolayer transition-metal dichalcogenides, Phys. Rev. B 92, 085413 (2015).
  * Warren  _et al._ [2000] J. T. Warren, K. E. O’Hara, and J. P. Wolfe, Two-body decay of thermalized excitons in CuO2, Phys. Rev. B 61, 8215 (2000).
  * Ginsberg and Tisdale [2020] N. S. Ginsberg and W. A. Tisdale, Spatially Resolved Photogenerated Exciton and Charge Transport in Emerging Semiconductors, Annu. Rev. Phys. Chem. 71, 1 (2020).
  * Guo  _et al._ [2019] Y. Guo, O. Yaffe, T. D. Hull, J. S. Owen, D. R. Reichman, and L. E. Brus, Dynamic emission Stokes shift and liquid-like dielectric solvation of band edge carriers in lead-halide perovskites, Nat. Commun. 10, 1175 (2019).
  * Mayers  _et al._ [2018] M. Z. Mayers, L. Z. Tan, D. A. Egger, A. M. Rappe, and D. R. Reichman, How Lattice and Charge Fluctuations Control Carrier Dynamics in Halide Perovskites, Nano Lett. 18, 8041 (2018).
  * Lacroix  _et al._ [2020] A. Lacroix, G. T. de Laissardière, P. Quémerais, J.-P. Julien, and D. Mayou, Modeling of Electronic Mobilities in Halide Perovskites: Adiabatic Quantum Localization Scenario, Phys. Rev. Lett. 124, 196601 (2020).
  * Schilcher  _et al._ [2021] M. J. Schilcher, P. J. Robinson, D. J. Abramovitch, L. Z. Tan, A. M. Rappe, D. R. Reichman, and D. A. Egger, The Significance of Polarons and Dynamic Disorder in Halide Perovskites, ACS Energy Lett. 6, 2162 (2021).
  * Glazov [2020] M. M. Glazov, Quantum Interference Effect on Exciton Transport in Monolayer Semiconductors, Phys. Rev. Lett. 124, 166802 (2020).