Rochester Institute of Technology, Rochester, NY, 14623<EMAIL_ADDRESS>https://orcid.org/0000-0001-5590-5235 Zohair Raza Hassan [500]Theory of
computation Problems, reductions and completeness

###### Acknowledgements.

I want to thank my advisors Edith Hemaspaandra and Stanisław Radziszowski.

# The Complexity of $\mathbf{(P_{3},H)}$-Arrowing and Beyond

Zohair Raza Hassan

###### Abstract

Often regarded as the study of how order emerges from randomness, Ramsey
theory has played an important role in mathematics and computer science,
giving rise to applications in numerous domains such as logic, parallel
processing, and number theory. The core of graph Ramsey theory is arrowing:
For fixed graphs $F$ and $H$, the $(F,H)$-Arrowing problem asks whether a
given graph, $G$, has a red/blue coloring of the edges of $G$ such that there
are no red copies of $F$ and no blue copies of $H$. For some cases, the
problem has been shown to be coNP-complete, or solvable in polynomial time.
However, a more systematic approach is needed to categorize the complexity of
all cases.

We focus on $(P_{3},H)$-Arrowing as $F=P_{3}$ is the simplest meaningful case
for which the complexity question remains open, and the hardness for this case
likely extends to general $(F,H)$-Arrowing for nontrivial $F$. In this
pursuit, we also gain insight into the complexity of a class of matching
removal problems, since $(P_{3},H)$-Arrowing is equivalent to $H$-free
Matching Removal. We show that $(P_{3},H)$-Arrowing is coNP-complete for all
$2$-connected $H$ except when $H=K_{3}$, in which case the problem is in P. We
introduce a new graph invariant to help us carefully combine graphs when
constructing the gadgets for our reductions. Moreover, we show how
$(P_{3},H)$-Arrowing hardness results can be extended to other
$(F,H)$-Arrowing problems. This allows for more intuitive and palatable
hardness proofs instead of ad-hoc constructions of SAT gadgets, bringing us
closer to categorizing the complexity of all $(F,H)$-Arrowing problems.

###### keywords:

Graph arrowing, Ramsey theory, Complexity.

###### category:

##  1 Introduction and related work

At what point, if ever, does a system get large enough so that certain
patterns become unavoidable? This question lies at the heart of Ramsey theory,
which, since its inception in the 1930s, aims to find these thresholds for
various combinatorial objects. Ramsey theory has played an important role in
mathematics and computer science, finding applications in fields such as
cryptography, algorithms, game theory, and more [11]. A key operator within
Ramsey theory is the arrowing operator, which is defined for graphs like so:
given graphs $F,G$, and $H$, we say that $G\rightarrow(F,H)$ (read, $G$ arrows
$F,H$) if every red/blue coloring of $G$’s edges contains a red $F$ or a blue
$H$. In this work, we analyze the complexity of computing this operator when
$F$ and $H$ are fixed graphs. The general problem is defined as follows.

######  Problem 1 ($(F,H)$-Arrowing).

For fixed $F$ and $H$, given a graph $G$, does $G\rightarrow(F,H)$?

The problem is clearly in coNP; a red/blue coloring of $G$’s edges with no red
$F$ and no blue $H$ forms a certificate that can be verified in polynomial
time since $F$ and $H$ are fixed graphs. Such a coloring is referred to as an
$(F,H)$-good coloring. The computational complexity of $(F,H)$-Arrowing has
been categorized for several—but not all—pairs $(F,H)$. For instance,
$(P_{2},H)$-Arrowing is in P for all $H$, where $P_{2}$ is the path graph on
$2$ vertices. This is because any coloring of an input graph $G$ that does not
contain a red $P_{2}$ must be entirely blue, and thereby $(P_{2},H)$-Arrowing
is equivalent to determining whether $G$ is $H$-free. Burr showed that
$(F,H)$-Arrowing is coNP-complete when $F$ and $H$ are 3-connected
graphs—these are graphs which remain connected after the removal of any two
vertices, e.g., $(K_{5},K_{6})$-Arrowing [3]. More results of this type are
discussed in Section 2.

In this work, we explore the simplest nontrival case for $F$, $F=P_{3}$, and
provide a complete classification of the complexity when $H$ is a
$2$-connected graph—a graph that remains connected after the removal of any
one vertex. In particular, we prove:

######  Theorem 1.1.

$(P_{3},H)$-Arrowing is coNP-complete for all $2$-connected $H$ except when
$H=K_{3}$, in which case the problem is in P.

We do this by reducing an NP-complete SAT variant to $(P_{3},H)$-Arrowing’s
complement, $(P_{3},H)$-Nonarrowing (for fixed $H$, does there exist a
$(P_{3},H)$-good coloring of a given graph?), and showing how to construct
gadgets for any $2$-connected $H$. It is important to note that combining
different copies of $H$ can be troublesome; it is possible to combine graphs
in a way so that we end up with more copies of it than before, e.g., combining
two $P_{n}$’s by their endpoints makes several new $P_{n}$’s across the
vertices of both paths. Results such as Burr’s which assume $3$-connectivity
avoid such problems, in that we can combine several copies of $3$-connected
graphs without worrying about forming new ones. If $G$ is $3$-connected with
vertices $u,v\in V(G)$ and we construct a graph $F$ by taking two copies of
$G$ and identifying $u$ across both copies, then identifying $v$ across both
copies, no new copies of $G$ are constructed in this process; if a new $G$ is
created then it must be disconnected by the removal of the two identified
vertices, contradicting $F$’s $3$-connectivity. This makes it easier to
construct gadgets for reductions. To work with $2$-connected graphs and show
how to combine them carefully, we present a new measure of intra-graph
connectivity called edge pair linkage, and use it to prove sufficient
conditions under which two copies of a $2$-connected graph $G$ can be combined
without forming new copies of $G$.

By targeting the $(P_{3},H)$ case we gain new insight and tools for the
hardness of $(F,H)$-Arrowing in the general case since $F=P_{3}$ is the
simplest case for $F$. We conjecture that if $(P_{3},H)$-Arrowing is hard,
then $(F,H)$-Arrowing is also hard for all nontrivial $F$, but this does not
at all follow immediately. Towards the goal of categorizing the complexity of
all $(F,H)$-Arrowing problems, we show how to extend the hardness results of
$(P_{3},H)$-Arrowing to other $(F,H)$-Arrowing problems in Section 5. These
extensions are more intuitive and the resulting reductions are more palatable
compared to constructing SAT gadgets. We believe that techniques similar to
the ones shown in this paper can be used to eventually categorize the
complexity of $(F,H)$-Arrowing for all $(F,H)$ pairs.

The rest of the paper is organized as follows. Related work is discussed in
Section 2. We present preliminaries in Section 3, wherein we also define and
analyze edge pair linkage. Our complexity results for $(P_{3},H)$-Arrowing are
proven in Section 4. We show how our hardness results extend to other arrowing
problems in Section 5, and we conclude in Section 6. All proofs omitted in the
main text are provided in the appendix.

##  2 Related work

Complexity of $(F,H)$-Arrowing. Burr showed that $(F,H)$-Arrowing is in P when
$F$ and $H$ are both star graphs, or when $F$ is a matching [3]. Hassan et al.
showed that $(P_{3},P_{3})$\- and $(P_{3},P_{4})$-Arrowing are also in P [6].
For hardness results, Burr showed that $(F,H)$-Arrowing is coNP-complete when
$F$ and $H$ are members of $\Gamma_{3}$, the family of all $3$-connected
graphs and $K_{3}$. The generalized $(F,H)$-Arrowing problem, where $F$ and
$H$ are also part of the input, was shown to be $\Pi^{p}_{2}$-complete by
Schaefer, who focused on constructions where $F$ is a tree and $H$ is a
complete graph [13].111$\Pi_{2}^{p}={\rm coNP}^{{\rm NP}}$, the class of all
problems whose complements are solvable by a nondeterministic polynomial-time
Turing machine having access to an NP oracle. Hassan et al. recently showed
that $(P_{k},P_{\ell})$-Arrowing is coNP-complete for all $k$ and $\ell$ aside
from the exceptions listed above [6]. We note that $(P_{4},P_{4})$-Arrowing
was shown to be coNP-complete by Rutenburg much earlier [12].

Matching removal. A matching is a collection of disjoint edges in a graph.
Interestingly, there is an overlap between matching removal problems, defined
below, and $(P_{3},H)$-Arrowing.

######  Problem 2.1 ($\Pi$-Matching Removal [9]).

Let $\Pi$ be a fixed graph property. For a given graph $G$, does there exist a
matching $M$ such that $G^{\prime}=(V(G),E(G)-M)$ has property $\Pi$?

Let $\Pi$ be the property that $G$ is $H$-free for some fixed graph $H$. Then,
this problem is equivalent to $(P_{3},H)$-Nonarrowing; a lack of red $P_{3}$’s
implies that only disjoint edges can be red, as in a matching, and the
remaining (blue) subgraph must be $H$-free. Lima et al. showed that the
problem is NP-complete when $\Pi$ is the property that $G$ is acyclic [7], or
that $G$ contains no odd cycles [8, 9].

Ramsey and Folkman numbers. The major research avenue involving arrowing is
that of finding Ramsey and Folkman numbers. Ramsey numbers are concerned with
the smallest complete graphs with arrowing properties, whereas Folkman numbers
allow for any graph with some extra structural constraints. We refer the
reader to surveys by Radziszowski [10] and Bikov [2] for more information on
Ramsey and Folkman numbers, respectively.

##  3 Preliminaries

###  3.1 Notation and terminology

All graphs discussed in this work are simple and undirected. $V(G)$ and $E(G)$
denote the vertex and edge set of a graph $G$, respectively. We denote an edge
in $E(G)$ between $u,v\in V(G)$ as $(u,v)$. For two disjoint subsets
$A,B\subsetneq V(G)$, $E_{G}(A,B)$ refers to the edges with one vertex in $A$
and one vertex in $B$. For a subset $A\subseteq V(G)$, $G[A]$ denotes the
induced subgraph on $A$. The neighborhood of a vertex $v\in V(G)$ is denoted
as $N_{G}(v)=\\{u\leavevmode\nobreak\ |\leavevmode\nobreak\ (u,v)\in E(G)\\}$
and its degree as $d_{G}(v):=|N_{G}(v)|$. A connected graph is called
$k$-connected if it has more than $k$ vertices and remains connected whenever
fewer than $k$ vertices are removed.

Vertex identification is the process of replacing two vertices $u$ and $v$
with a new vertex $w$ such that $w$ is adjacent to all remaining neighbors
$N(u)\cup N(v)$. For edges $(u,v)$ and $(p,q)$, edge identification is the
process of identifying $u$ with $p$, and $v$ with $q$.

The path, cycle, and complete graphs on $n$ vertices are denoted as $P_{n}$,
$C_{n}$, and $K_{n}$, respectively. The complete graph on $n$ vertices missing
an edge is denoted as $J_{n}$. $K_{1,n}$ is the star graph on $n+1$ vertices.
For $n\geq 3$, we define $TK_{n}$ (tailed $K_{n}$) as the graph obtained by
identifying a vertex of a $K_{2}$ and any vertex in $K_{n}$. The vertex of
degree one in a $TK_{n}$ is called the tail vertex of $TK_{n}$.

We introduce a new notion, defined below, to measure how “connected” a pair of
edges in a graph is, which will be useful when identifying edges between
multiple copies of the same graph. Examples have been shown in Figure 1.

######  Definition 3.1.

For a pair of edges $e,f\in E(G)$, we define its edge pair linkage,
$\mathrm{epl}_{G}(e,f)$, as the number of edges adjacent to both $e$ and $f$.
It is infinity if $e$ and $f$ share at least one vertex. Note that
$\mathrm{epl}_{G}(e,f)\leq 4$ when $e$ and $f$ share no vertices. For a graph
$G$, we define $\mathrm{mepl}(G):=\min_{e,f\in E(G)}\mathrm{epl}(e,f)$ as the
minimum edge pair linkage across all edge pairs.

It is easy to see that the only graphs with $\mathrm{mepl}(G)=\infty$ are the
star graphs, $K_{1,n}$, and $K_{3}$ since these are the only graphs that do
not have disjoint edges. When the context is clear, the subscript $G$ for
$\mathrm{epl}_{G}(\cdot)$, $d_{G}(\cdot)$, etc. will be omitted.

An $(F,H)$-good coloring of a graph $G$ is a red/blue coloring of $E(G)$ where
the red subgraph is $F$-free, and the blue subgraph is $H$-free. We say that
$G$ is $(F,H)$-good if it has at least one $(F,H)$-good coloring. When the
context is clear, we will omit $(F,H)$ and refer to the coloring as a good
coloring.

###  3.2 Combining graphs

Suppose $H$ is a $3$-connected graph. Consider the graph $A_{H,e}$, obtained
by taking two disjoint copies of $H$ and identifying some arbitrary $e\in
E(H)$ from each copy. Observe that no new copy of $H$—referred to as a rogue
copy of $H$ in $A_{H,e}$—is constructed during this process; if a new $H$ is
created then it must be disconnected by the removal of the two identified
vertices, contradicting $H$’s $3$-connectivity. This is especially useful when
proving the existence of good colorings; to show that a coloring of $A_{H,e}$
has no blue $H$, we know that only two copies of $H$ need to be looked at,
without worrying about any other rogue $H$. Unfortunately, this property does
not hold for all $2$-connected graphs. Instead, we use minimum edge pair
linkage to explore sufficient conditions that allow us to combine multiple
copies of graphs without concerning ourselves with any potential rogue copies.

Figure 1: Graphs with different $\mathrm{mepl}(G)$ values. Bold edges have
$\mathrm{epl}_{G}=\mathrm{mepl}(G)$.  Figure 2: Proof for Lemma 3.2 when
$|V(H)|=4$. It is easy to see that $A_{H,e}$ for $H\in\\{C_{4},K_{4}\\}$ has
exactly two copies of $H$ for arbitrary $e$. Moreover, constructing
$A_{J_{4},e}$ introduces a new $J_{4}$ (highlighted in red) for both
nonisomorphic choices of $e\in E(J_{4})$. Identified edges are bolded.

######  Lemma 3.2.

Suppose $H$ is a $2$-connected graph such that $|V(H)|\geq 4$ and
$\mathrm{mepl}(H)\geq 2$. Given $H$ and $e\in E(H)$, let $A_{H,e}$ be the
graph obtained by taking two disjoint copies of $H$ and identifying $e$ from
each copy. For all such $H$, except $J_{4}$, there exists $e\in E(H)$ such
that $A_{H,e}$ has exactly two copies of $H$, i.e., no new copy of $H$ is
formed after identifying $e$.

######  Proof 3.3.

For $|V(H)|=4$, the statement is easily observed as the only cases to consider
are $C_{4}$, $J_{4}$, and $K_{4}$. See Figure 2. Suppose $|V(H)|\geq 5$. We
will first construct $A_{H,e}$ using an arbitrary $e=(u,v)\in E(H)$ and assume
that a new copy of $H$ is constructed after identifying $e$. Let $X$ and $Y$
denote the subgraphs of $A_{H,e}$ corresponding to the two copies of $H$ in
$A_{H,e}$ that identify $(u,v)$. It follows that, $V(X)\cap V(Y)=\\{u,v\\}$
and $V(X)\cup V(Y)=V(A_{H,e})$. Similarly, $E(X)\cap E(Y)=\left\\{e\right\\}$
and $E(X)\cup E(Y)=E(A_{H,e})$. Suppose $Z$ is a subgraph corresponding to
another copy of $H$ in $A_{H,e}$, i.e. $V(Z)\not=V(X)$ and $V(Z)\not=V(Y)$.
Let $V_{Z_{X}}=(V(X)-V(Y))\cap V(Z)$ be the vertices of $Z$ only in $X$, and
$E_{Z_{X}}=\left\\{(p,q)\in E(Z)\leavevmode\nobreak\ |\leavevmode\nobreak\
p,q\in V_{Z_{X}}\right\\}$. $V_{Z_{Y}}$ and $E_{Z_{Y}}$ are defined similarly.
In the following claim, we observe the properties of $Z$ and the original
graph $H$ with $\mathrm{mepl}(H)\geq 2$.

######  Claim 1.

If $Z$ exists in $A_{H,e}$, the following must be true: (1) Both $V_{Z_{X}}$
and $V_{Z_{Y}}$ are nonempty, (2) $u\in V(Z)$ and $v\in V(Z)$, (3) at least
one of $E_{Z_{X}}$ and $E_{Z_{Y}}$ is empty, and (4) there exists $w\in V(H)$
with $d_{H}(w)=2$.

The proof of Claim 1 is given in Appendix A. Now, let $e=(u,v)\in E(H)$ such
that $d_{H}(v)=2$. Consider the graph $A_{H,e}$. Note that since $d_{H}(v)=2$,
we have $d_{A_{H,e}}(v)=d_{H}(v)+d_{H}(v)-1=3$. Let $w_{X}$ and $w_{Y}$ be the
neighbors of $v$ in $V(X)-V(Y)$ and $V(Y)-V(X)$, respectively. We know that
$V(Z)$ includes $u$ and $v$ from Claim 1(2). We now show that $w_{X}$ and
$w_{Y}$ must also belong to $V(Z)$: if neither belong to $V(Z)$, then
$d_{Z}(v)=1$, contradicting $H$’s $2$-connectivity (removing $u$ disconnects
$H$). Suppose w.l.o.g., that $w_{X}\not\in V(Z)$. Since $V_{Z_{X}}$ is
nonempty and $H$ is connected, there is at least one vertex in $V_{Z_{X}}$
connected to $u$. However, removing $u$ would disconnect $Z$, again
contradicting $H$’s $2$-connectivity. Thus, $\\{u,v,w_{X},w_{Y}\\}\subseteq
V(Z)$. Using a similar argument, we can also show that both $(v,w_{X})$ and
$(v,w_{Y})$ must belong to $E(Z)$.

Let $p$ be a vertex in $V(Z)-\\{u,v,w_{X},w_{Y}\\}$. We know $p$ exists since
$|V(H)|\geq 5$. W.l.o.g., we assume that $p\in V_{Z_{X}}$. Note that $p$
cannot be adjacent to $v$ since $N_{A_{H,e}}(v)=\\{u,w_{X},w_{Y}\\}$. We now
consider the neighborhood of $p$ in $Z$. If $p$ has a neighbor $q\in
V_{Z_{X}}-\\{w_{X}\\}$, then $\mathrm{epl}_{Z}\left((p,q),(v,w_{Y})\right)=0$,
contradicting our assumption that $\mathrm{mepl}(H)\geq 2$. Since
$d_{Z}(p)=d_{H}(p)\geq 2$ and the only options remaining for $p$’s
neighborhood are $u$ and $w_{X}$, we must have that $p$ is connected to both
$u$ and $w_{X}$. In this case, we have that
$\mathrm{epl}_{Z}((p,w_{X}),(v,w_{Y}))\leq 1$, which is still a contradiction.

##  4 The complexity of $\mathbf{(P_{3},H)}$-Arrowing

In this section, we discuss our complexity results stated in Theorem 1.1. We
first show that $(P_{3},K_{3})$-Arrowing is in P (Theorem 4.1). The rest of
the section is spent setting up our hardness proofs for all $2$-connected
$H\not=K_{3}$, which we prove formally in Theorems 4.13 and 4.15.

######  Theorem 4.1.

$(P_{3},K_{3})$-Arrowing is in P.

######  Proof 4.2.

Let $G$ be the input graph. Let $\gamma:E(G)\rightarrow\mathbb{Z}_{\geq 0}$ be
a function that maps each edge to the number of triangles it belongs to in
$G$. Note that $\gamma$ can be computed in $O(|E(G)|^{3})$ time via brute-
force. Let $t$ be the number of triangles in $G$. Clearly, any
$(P_{3},K_{3})$-good coloring of $G$ corresponds to a matching of total weight
$\geq t$; otherwise, there would be some $K_{3}$ in $G$ in the blue subgraph
of $G$. Now, suppose there exists a matching $M$ with weight at least $t$ that
does not correspond to a $(P_{3},K_{3})$-good coloring of $G$. Then, there
must exist a copy of $K_{3}$ in $G$ with at least two of its edges in $M$.
However, since $K_{3}$’s maximal matching contains only one edge, $M$ must
contain a $P_{3}$, which is a contradiction. Thus, we can solve
$(P_{3},K_{3})$-Arrowing by finding the maximum weight matching of
$(G,\gamma)$, which can be done in polynomial time [5], and checking if said
matching has weight equal $t$.

To show that $(P_{3},H)$-Arrowing is coNP-complete we show that its
complement, $(P_{3},H)$-Nonarrowing, is NP-hard. We reduce from the following
NP-complete SAT variant:

######  Problem 4.3 ($(2,2)$-3SAT [1]).

Let $\phi$ be a 3CNF formula where each clause has exactly three distinct
variables, and each variable appears exactly four times: twice unnegated and
twice negated. Does there exist a satisfying assignment for $\phi$?

Important definitions and the idea behind our reduction are provided in
Section 4.1, while the formal proofs are presented in Section 4.2.

###  4.1 Defining special graphs and gadgets for proving hardness

We begin by defining a useful term for specific vertices in a coloring, after
which we describe and prove the existence of some special graphs. We then
define the two gadgets necessary for our reduction and describe how they
provide a reduction from $(2,2)$-3SAT.

######  Definition 4.4.

For a graph $G$ and a coloring $c$, a vertex $v\in V(G)$ is called a free
vertex if it is not adjacent to any red edge in $c$. Otherwise, it is called a
nonfree vertex.

Note that in any $(P_{3},H)$-good coloring, a vertex can be adjacent to at
most one red edge, otherwise, a red $P_{3}$ is formed. Intuition suggests
that, by exploiting this restrictive property, we could freely force “any”
desired blue subgraph if we can “append red edges” to it. This brings us to
our next definition, borrowed from Schaefer’s work on $(F,H)$-Arrowing [13]:

######  Definition 4.5 ([13]).

A graph $G$ is called an $(F,H)$-enforcer with signal vertex $v$ if it is
$(F,H)$-good and the graph obtained from $G$ by attaching a new edge to $v$
has the property that this edge is colored blue in all $(F,H)$-good colorings.

Throughout our text, when the context is clear, we will use the shorthand
append an enforcer to $u\in V(G)$ to mean we will add an $(F,H)$-enforcer to
$G$ and identify its signal vertex with $u$. We prove the existence of
$(F,H)$-enforcers when $F=P_{3}$ below. This proof provides a good example of
the role $2$-connectivity plays while constructing our gadgets, showcasing how
we combine graphs while avoiding constructing new copies of $H$. The arguments
made are used frequently in our other proofs as well.

Figure 3: (a) The graph $A^{\prime}$ when $u$ and $w$ are adjacent to a red
edge. (b) The graph $A^{\prime}$ when either $u$ or $w$ is adjacent to a red
edge. (c) The graph $B$. (d) A zoomed in look at $B$.  Figure 4: (a) The
$(P_{3},H)$-signal extender described in Lemma 4.9, where enforcers are
labeled $EN$ and the copy of $H$ is labeled $U$. Edges whose colors are fixed
in all $(P_{3},H)$-good colorings have been pre-colored. The edge
$(u_{1},u_{3})$ is dashed to signify it may or may not exist in the
construction. (b) At the top, we show how extenders can be connected
sequentially to form arbitrarily large extenders. The enforcers have been
removed from the illustration for clarity. The in- and out-vertices are marked
$a$ and $b$, respectively. At the bottom, we show how signal extenders will be
depicted in our figures, where $\ell$ is the number of concatenated
constructed extenders. (c) At the top, we show the coloring of the signal
extender when vertex $a$ is a free vertex. At the bottom, we show the
corresponding coloring of our representation of signal extenders.

######  Lemma 4.6.

$(P_{3},H)$-enforcers exist for all $2$-connected $H$.

######  Proof 4.7.

We extend an idea presented by Burr [3]. Let $A$ be a “minimally bad” graph
such that $A\rightarrow(P_{3},H)$, but removing any edge $e$ from $A$ gives a
$(P_{3},H)$-good graph. Let $e=(u,w)$ and $A^{\prime}=A-e$. This graph is
illustrated in Figure 3. Observe that in any $(P_{3},H)$-good coloring of
$A^{\prime}$, at least one edge adjacent to $u$ or $w$ must be red; otherwise,
such a coloring and a red $(u,w)$ gives a good coloring for $A$, contradicting
the fact that $A\rightarrow(P_{3},H)$. If both $u$ and $w$ are adjacent to red
edges in all good colorings, then $A^{\prime}$ is a $(P_{3},H)$-enforcer, and
either $u$ or $w$ can be the signal vertex .

If there exists a coloring where only one of $\\{u,w\\}$ is adjacent to a red
edge, then we can construct an enforcer, $B$, as follows. Let $n=|V(H)|$. Make
$2n$ copies of $A^{\prime}$, where $u_{i}$ and $w_{i}$ refer to the vertex $u$
and $w$ in the $i^{\text{th}}$ copy of $A^{\prime}$, called $A^{\prime}_{i}$.
Now, identify each $w_{i}$ with $u_{i+1}$ for $i\in\\{1,2,\ldots,2n-1\\}$, and
identify $w_{2n}$ with $u_{1}$ (see Figure 3). Although $w_{i}$ and $u_{i+1}$
are now the same vertex in $B$, we will use their original names to make the
proof easier to follow. It is easy to see that when $w_{1}$ is adjacent to a
red edge in $A^{\prime}_{1}$, then $u_{2}$ cannot be adjacent to any red edge
in $A^{\prime}_{2}$, causing $w_{2}$ to be adjacent to a red edge in
$A^{\prime}_{2}$, and so on. A similar argument holds when considering the
case where $u_{1}$ is adjacent to a red edge in $A^{\prime}_{1}$. Since every
$u_{i}$ and $w_{i}$ is adjacent to a red edge, any of them can be our desired
signal vertex.

Note that $B$ must be $(P_{3},H)$-good because each $A^{\prime}_{i}$ is
$(P_{3},H)$-good, and no new $H$ is made during the construction of the graph;
since $H$ is $2$-connected, $H$ cannot be formed between two copies of
$A^{\prime}_{i}$’s, otherwise there is a single vertex that can be removed to
disconnect such an $H$, contradicting $2$-connectivity. Thus, any new copy of
$H$ must go through all $A_{i}$’s, which is not possible since such an $H$
would have $\geq 2|V(H)|$ vertices.

Using enforcers, we construct another graph that plays an important role in
our reductions.

######  Definition 4.8.

A graph $G$ is called a $(P_{3},H)$-signal extender with in-vertex $a$ and
out-vertex $b$ if it is $(P_{3},H)$-good and, in all $(P_{3},H)$-good
colorings, $b$ is nonfree if $a$ is free.

######  Lemma 4.9.

$(P_{3},H)$-signal extenders exist for all $2$-connected $H$.

######  Proof 4.10.

Let $n=|V(H)|$. Construct a graph $G$ like so. Take a copy of $H$, and let
$u_{1},u_{2},\ldots,u_{n}\in U$ be the vertices of $H$ in $G$, such that
$(u_{1},u_{2})$ and $(u_{2},u_{3})$ are edges of $H$. For each $u_{i}$ for
$i\in\\{4,5,\ldots,n\\}$, append an enforcer to $u_{i}$. Observe that no “new”
$H$ is constructed during this process since $H$ is $2$-connected. Since each
vertex except $u_{1},u_{2},$ and $u_{3}$ is connected to an enforcer, each
edge in $G[U]$, except $(u_{1},u_{2})$, $(u_{2},u_{3})$, and $(u_{1},u_{3})$
must be blue. However, not all of them can be blue, otherwise $G[U]$ is a blue
$H$. Therefore, in any good coloring, if $u_{1}$ is a free vertex,
$(u_{2},u_{3})$ must be red, making $u_{3}$ a nonfree vertex. Thus, $u_{1}$ is
our in-vertex, and $u_{3}$ is our out-vertex. We illustrate $G$ in Figure
4(a).

Observe that multiple copies of these extenders can be used to form larger
ones (see Figure 4). With the enforcer and extender graphs defined, we are
ready to construct the gadgets for our reductions. Below, we define variable
and clause gadgets and describe how they are used in our proofs. Recall that
we are reducing from $(2,2)$-3SAT. We will explain how our graphs encode
clauses and variables after the definitions.

######  Definition 4.11.

For a fixed $H$, a clause gadget is a $(P_{3},H)$-good graph $CG$ containing
vertices $i_{1},i_{2},$ and $i_{3}$—referred to as input vertices, such that
if vertices outside the gadget, $o_{1}$, $o_{2}$ and $o_{3}$, are connected to
$i_{1}$, $i_{2}$, and $i_{3}$, respectively, then each of the eight possible
combinations of $(o_{j},i_{j})$’s colors should allow a $(P_{3},H)$-good
coloring for $CG$, except the coloring where all $(o_{j},i_{j})$’s are red,
which should not allow a good coloring of $CG$.

######  Definition 4.12.

For a fixed $H$, a variable gadget is a $(P_{3},H)$-good graph $VG$ containing
four output vertices: two unnegated output vertices, $u_{1}$ and $u_{2}$, and
two negated output vertices, $n_{1}$ and $n_{2}$, such that:

  1. 1.

In each $(P_{3},H)$-good coloring of $VG$:

    1. (a)

If $u_{1}$ or $u_{2}$ is a free vertex, then $n_{1}$ and $n_{2}$ must be
nonfree vertices.

    2. (b)

If $n_{1}$ or $n_{2}$ is a free vertex, then $u_{1}$ and $u_{2}$ must be
nonfree vertices.

  2. 2.

There exists at least one $(P_{3},H)$-good coloring of $VG$ where $u_{1}$ and
$u_{2}$ are free vertices.

  3. 3.

There exists at least one $(P_{3},H)$-good coloring of $VG$ where $n_{1}$ and
$n_{2}$ are free vertices.

Note how clause gadgets and their input vertices correspond to OR gates and
their inputs; the external edges, denoted as $(o_{j},i_{j})$’s in the
definition, behave like true or false signals: blue is true, and red is false.
Similarly, output vertices of variable gadgets behave like sources for these
signals. The reduction is now straightforward: for a formula $\phi$, construct
$G_{\phi}$ like so. For each variable and clause, add a corresponding gadget.
Then, identify the output and input vertices according to how they appear in
each clause. It is easy to see that any satisfying assignment of $\phi$
corresponds to a $(P_{3},H)$-good coloring of $G_{\phi}$, and vice versa. To
complete the proof we must show that the gadgets described exist and that no
new $H$ is formed while combining the gadgets during the reduction.

Note that it is possible for a variable gadget to have a coloring where both
unnegated and negated output vertices are nonfree. This does not affect the
validity of the gadgets. A necessary restriction is that if variable $x$
appears unnegated in clause $L_{1}$ and negated in $L_{2}$, then $x$ cannot
satisfy both clauses. Our gadgets clearly impose that restriction.

Figure 5:  On the left, we show the variable gadget constructed using two
copies of $A$ as described in Theorem 4.13’s proof and signal extenders. The
vertices in the square are the vertices of $A$ which had enforcers appended to
them. The edge $(b,c)$ is dashed to signify that it may or may not exist.
Edges have been precolored wherever possible. Note that if $(b,c)$ exists, it
must be blue: if $(b,c)$ is red, the attached signal extenders will force
$(a^{\prime},b^{\prime})$, $(b^{\prime},c^{\prime})$, and
$(c^{\prime},d^{\prime})$ to be blue, forming a blue $H$. By symmetry,
$(b^{\prime},c^{\prime})$ must also be blue. Now, observe that at least one
edge in $\\{(a,b),(c,d)\\}$ must be red, otherwise we form a blue $H$ in $A$.
Suppose $(a,b)$ is red: the signal extender forces $(a^{\prime},b^{\prime})$
to be blue. To avoid a blue $H$, $(c^{\prime},d^{\prime})$ must be red, which
forces $(c,d)$ to be blue. In this case, the vertices marked $\mathbf{U}$ are
nonfree vertices, and the vertices marked $\mathbf{N}$ are free. A similar
pattern can be observed when we color $(c,d)$ red instead, giving us colorings
where vertices marked $\mathbf{U}$ are free and vertices marked $\mathbf{N}$
are nonfree.  Figure 6:  This figure shows the clause gadget used in the
proofs of Theorem 4.13 and 4.15. (a) Each block represents the induced
subgraph in a $H$ when: (1) $\mathrm{mepl}(H)=2$ and $H$ has an induced
$C_{4}$, (2) $\mathrm{mepl}(H)=1$, and (3) $\mathrm{mepl}(H)=0$. (b) Each
block represents how a fifth vertex, denoted $e$ in the proofs of Theorems
4.13 and 4.15, may be connected to the induced subgraphs from (a). For each
case, the solid line going from $e$ represents an edge that must exist in
$E(H)$ since $d_{H}(v)\geq 2$ for all $v\in H$ due to $2$-connectivity. In the
first case, any edge can be chosen w.l.o.g. due to the symmetry of $C_{4}$.
The dashed edges may or may not exist, but their existence is inconsequential
to the correctness of our gadget. (c) An illustration of the clause gadget,
where each vertex of $H$ attached to an enforcer is in the square. The input
vertices have been filled in. (d) We show the eight possible combinations of
inputs that can be given to the gadget. Observe that a $(P_{3},H)$-good
coloring is always possible unless the input is three red edges.

###  4.2 Hardness proofs

Using the ideas and gadgets presented in Section 4.1, we provide our hardness
results below.

######  Theorem 4.13.

$(P_{3},H)$-Arrowing is coNP-complete when $H$ is a $2$-connected graph on at
least four vertices with $\mathrm{mepl}(H)\leq 1$.

######  Proof 4.14.

We reduce $(2,2)$-3SAT to $(P_{3},H)$-Nonarrowing as described in the end of
Section 4.1; given a $(2,2)$-3SAT formula $\phi$, we construct a graph
$G_{\phi}$ such that $G_{\phi}$ is $(P_{3},H)$-good if and only if $\phi$ is
satisfiable. Since we have $\mathrm{mepl}(H)\leq 1$, we must have two edges
$(a,b),(c,d)\in E(H)$ that have at most one edge adjacent to both. We
construct a graph $A$ like so: take a copy of $H$ and append an enforcer to
each vertex of $H$ except $a,b,c,$ and $d$. We construct the variable gadget
using two copies of $A$ joined by signal extenders, as shown in Figure 5. The
vertices labeled $\mathbf{U}$ (resp., $\mathbf{N}$) correspond to unnegated
(resp., negated) output vertices. Note that there are no rogue $H$’s made
during this construction. Recall that because of $2$-connectivity, a copy of
$H$ cannot go through a single vertex. Thus, if a copy of $H$ other than the
ones in $A$ and the signal extenders exists, it must go through both copies of
$A$ and the signal extenders. However, this is not possible because by
including the two signal extenders, we would have a copy of $H$ with at least
$2|V(H)|$ vertices.

We now describe our clause gadget. As observed in Section 3.2, there is no
$2$-connected graph with $\mathrm{mepl}(\cdot)\leq 1$ on four vertices so we
assume $|V(H)|\geq 5$. Let $(a,b)$ and $(c,d)$ be the edges that achieve this
$\mathrm{epl}(\cdot)$. Let $e$ be a fifth vertex connected to at least one of
$\\{a,b,c,d\\}$. We construct a clause gadget by taking a copy of $H$ and
appending an enforcer to each vertex except $a,b,c,d,$ and $e$. In Figure
6—which also includes a special case for $\mathrm{mepl}(H)=2$ used in Theorem
4.15—we show how $e$ and two vertices from $\\{a,b,c,d\\}$ can be used as
input vertices so that a blue $H$ is formed if and only if all three input
vertices are connected to red external edges. Observe that we can make the
clause gadget arbitrarily large by attaching the out-vertex of a signal
extender to each input vertex of a clause gadget. We attach a signal extender
with at least $|V(H)|$ vertices to each input vertex. This ensures that no
copies of $H$ other than the ones in each gadget and extender are present in
$G_{\phi}$.

Figure 7: On the top, we show the variable gadget constructed using two copies
of $F$ as described in Theorem 4.13’s proof and signal extenders. $A$ and $B$
have been marked. The vertices in the square (resp., triangle) are the
vertices of $A$ (resp., $B$) which had enforcers appended to them. Dashed
edges signify edges that may or may not exist. Edges have been precolored
wherever possible. Observe that $(b,e)$ must be blue: if $(b,e)$ is red, the
attached extenders will force $(b^{\prime},c^{\prime})$,
$(b^{\prime},e^{\prime})$, and $(c^{\prime},e^{\prime})$ to be blue, forming a
blue $H$ in the copy of $B$ on the right. We show that $(a,b)$, $(a,c)$,
$(b,d)$, and $(c,d)$ must always be blue. Observe that at least one edge in
$\\{(b,c),(c,e)\\}$ must be red, otherwise we form a blue $H$ in $B$. Note
that if $(b,c)$ is red, the edges $(a,b)$, $(a,c)$, $(b,d)$, and $(c,d)$ must
be blue. If $(b,c)$ is blue, $(c,e)$ is red. Thus, $(c,d)$ and $(a,c)$ are
blue. Moreover, a red $(c,e)$ forces $(c^{\prime},e^{\prime})$ to be blue via
the extender. Thus, $(b^{\prime},c^{\prime})$ must be red to avoid a blue $H$.
The extender on the top will in turn force edge $(a,b)$ and $(b,d)$ to be
blue. Therefore, $(a,b)$, $(a,c)$, $(b,d)$, and $(c,d)$ are blue in all good
colorings. By symmetry, $(a^{\prime},b^{\prime})$, $(a^{\prime},c^{\prime})$,
$(b^{\prime},d^{\prime})$, $(c^{\prime},d^{\prime})$, and
$(b^{\prime},e^{\prime})$ must also be blue in all good colorings. Observe
that when a vertex marked $\mathbf{U}$ is nonfree, i.e., $(a,d)$ is blue,
$(b,c)$ must be red. Thus, $(b^{\prime},c^{\prime})$ is blue, and
$(a^{\prime},d^{\prime})$ must be red, making the vertices marked $\mathbf{N}$
nonfree. A similar pattern can be observed when vertices marked $\mathbf{N}$
are free, wherein the vertices marked $\mathbf{U}$ are forced to be nonfree.
These colorings are shown at the bottom of the figure.  Figure 8:  This figure
shows the clause gadget used in Theorem 4.15 when $H$ contains a $TK_{3}$. (a)
Each block represents the induced subgraph in a $H$ when: (1)
$\mathrm{mepl}(H)=4$, (2) $\mathrm{mepl}(H)=3$, and (3) $\mathrm{mepl}(H)=2$
and $H$ has an induced $TK_{3}$. (b) An illustration of the clause gadget,
where each vertex of $H$ attached to an enforcer is in the square. The input
vertices have been filled in. Dashed edges may or may not exist, but their
existence is inconsequential to the correctness of our gadget. (c) We show the
eight possible combinations of inputs that can be given to the gadget. Observe
that a $(P_{3},H)$-good coloring is always possible unless the input is three
red edges.

######  Theorem 4.15.

$(P_{3},H)$-Arrowing is coNP-complete when $H$ is a $2$-connected graph on at
least four vertices with $\mathrm{mepl}(H)\geq 2$.

######  Proof 4.16.

We follow the same argument as in the proof of Theorem 4.13. We first discuss
the variable gadget. Using Lemma 3.2 and the fact that $\mathrm{mepl}(H)\geq
2$, we know that we can construct a graph $F$ with exactly two copies of $H$
that share a single edge, unless $H=J_{4}$. The variable gadget for this
exception is shown in Appendix A. For now, we assume $H\not=J_{4}$. Let $A$
and $B$ the copies of $H$ in $F$ and let $(b,c)$ be the edge that was
identified. Let $e\not=b$ be a vertex in $B$ adjacent to $c$, and let $(a,d)$
be an edge in $A$ where $a,d\not\in\\{b,c\\}$. Note that if such an $(a,d)$
does not exist in $H$, then $(b,c)$ must be an edge that shares a vertex with
every other edge in $H$. However, it is easy to see that in this case two
copies of $H$ cannot be identified on $(b,c)$ without forming new copies of
$H$. Thus, $(a,d)$ must exist. We now append enforcers to each vertex in $A$
and $B$ except $a,b,c,d,$ and $e$. Our variable gadget is constructed using
two copies of $F$ joined via signal extenders as shown in Figure 7.

We use a clause gadget similar to the one used in Theorem 4.13, but with some
modifications. Since $\mathrm{mepl}(H)\geq 2$, we know that $H$ must contain a
$C_{4}$ or a $TK_{3}$. If $H$ contains a $TK_{3}$, we can use the gadget shown
in Figure 8. However, if $\mathrm{mepl}(H)=2$ and we only have induced
$C_{4}$’s, we can use the gadget shown in Figure 6 when $|V(H)|\geq 5$ using
the induced $C_{4}$ and another vertex $e$. The only case left is $H=C_{4}$,
which is discussed in Appendix A.

##  5 Extending the hardness of $\mathbf{(P_{3},H)}$-Arrowing

In this section, we discuss how hardness results for $(P_{3},H)$-Arrowing can
be extended to other $(F,H)$-Arrowing problems. We believe this provides an
easier method for proving hardness compared to constructing SAT gadgets. We
discuss two methods in which our results can be extended: (1) showing that
$G\rightarrow(P_{3},H)\iff G\rightarrow(P_{3},H^{\prime})$ for some pairs of
$H$ and $H^{\prime}$ (Section 5.1), and (2) given a graph $G$, showing how to
construct a graph $G^{\prime}$ such that $G\rightarrow(P_{3},H)\iff
G^{\prime}\rightarrow(F,H)$ for some $F$ (Section 5.2).

###  5.1 $\mathbf{P_{3}}$ versus tailed complete graphs

We first observe that edges not belonging to $H$ can be removed while working
on $(P_{3},H)$-Arrowing for a graph $G$; we can always color said edge blue
without forming a blue $H$.

Let $G$ be a graph and $e\in E(G)$. If $e$ does not belong to a copy of $H$ in
$G$, then $G\rightarrow(P_{3},H)$ if an only if $G-e\rightarrow(P_{3},H)$.

######  Theorem 5.1.

For $n\geq 3$, $G\rightarrow(P_{3},TK_{n})$ if and only if
$G\rightarrow(P_{3},K_{n})$.

######  Proof 5.2.

Clearly if $G\rightarrow(P_{3},TK_{n})$ then $G\rightarrow(P_{3},K_{n})$ since
$K_{n}$ is a subgraph of $TK_{n}$. For the other direction, consider a graph
$G$ such that $G\rightarrow(P_{3},K_{n})$ but is $(P_{3},TK_{n})$-good. By
Observation 5.1, we can assume that each edge in $G$ belongs to a $K_{n}$. We
can also assume that $G$ is connected. Let $c$ be a $(P_{3},TK_{n})$-good
coloring of $G$. Since $G\rightarrow(P_{3},K_{n})$ there must exist a blue
$K_{n}$ in $c$. Let $U=\\{u_{1},u_{2},\ldots,u_{n}\\}$ be the vertices of said
$K_{n}$. Let $e=(u_{i},v)$ be an edge going from some $u_{i}\in U$ to a vertex
$v\not\in U$. We know that such an edge exists otherwise $G$ is just a
$K_{n}$, and a $K_{n}$ is $(P_{3},K_{n})$-good, so this would contradict our
assumption. W.l.o.g., let $u_{i}=u_{1}$. Note that $(u_{1},v)$ must be red,
otherwise, we have a blue $TK_{n}$. Since $(u_{1},v)$ is part of a $K_{n}$
(Observation 5.1), at least one vertex $w$ must be connected to both $u_{1}$
and $v$. Note that $(u_{1},w)$ and $(v,w)$ must be blue to avoid a red
$P_{3}$. If $w\in U$, then $U$ and $(v,w)$ form a blue $TK_{n}$. If $w\in
V(G)-U$, then $U$ and $(u_{1},w)$ form a blue $TK_{n}$.

######  Corollary 5.3.

$(P_{3},TK_{n})$-Arrowing is coNP-complete when $n\geq 4$ and in P when $n=3$.

With this result, we have categorized the complexity of all
$(P_{3},H)$-Arrowing problems for connected $H$ with $|V(H)|\leq 4$; the star
and path graphs were shown to be in P [4, 6].

###  5.2 Stars versus $\mathbf{2}$-connected graphs

Note that $P_{3}=K_{1,2}$. Given a graph $G$, suppose we construct a graph
$G^{\prime}$ by taking a copy of $G$ and appending an edge (one for each
vertex in $G$) to each vertex, where each appended edge is forced to be red in
all colorings. It is easy to see that if a coloring of $G$ contains a red
$K_{1,2}$, then said coloring in $G^{\prime}$ contains a red $K_{1,3}$, using
the appended red edge. Thus, if we can find a $(K_{1,3},H)$-good graph $F$
with an edge $(u,v)$ such that, in all good colorings, $(u,v)$ is red and no
other edge adjacent to $v$ is red, we could reduce $(K_{1,2},H)$-Arrowing to
$(K_{1,3},H)$-Arrowing by appending a copy of $F$ (identifying $v$) to each
vertex of $G$. Recall that we do not have to worry about new copies of $H$ due
to its $2$-connectivity.

Generalizing this argument, if we attach $k$ red edges to each vertex of $G$,
then a coloring of $G$ with a red $K_{1,\ell}$ corresponds to a coloring of
$G^{\prime}$ with a red $K_{1,k+\ell}$. In Appendix B, we show that for all
$n\geq 3$, there exists some $m$ for which there is a $(K_{1,n},H)$-good graph
with a vertex $v$ that is always the center of a $K_{1,m}$ for some $1\leq
m<n$. This allows us to reduce $(K_{1,n-m},H)$-Arrowing to
$(K_{1,n},H)$-Arrowing. Thus, we can assert the following:

######  Lemma 5.4.

Suppose $H$ is a $2$-connected graph. If $(K_{1,k},H)$-Arrowing is coNP-hard
for all $2\leq k<n$, then $(K_{1,n},H)$-Arrowing is also coNP-hard.

Also in Appendix B, we reduce $(2,2)$-3SAT to $(K_{1,3},K_{3})$-Nonarrowing
and show how that result can be extended to $(K_{1,n},K_{3})$-Arrowing for
$n\geq 4$, giving us the following result:

######  Theorem 5.5.

For all $2$-connected $H$ and $n\geq 2$, $(K_{1,n},H)$-Arrowing is coNP-
complete with the exception of $(K_{1,2},K_{3})$-Arrowing, which is in P.

Finally, recall that $(P_{3},H)$-Nonarrowing is equivalent to $H$-free
Matching Removal. We can assert a similar equivalence between $H$-free
$b$-Matching Removal and $(K_{1,b+1},H)$-Nonarrowing, giving us the following
corollary:

######  Corollary 5.6.

For all 2-connected $H$, $H$-free $b$-Matching Removal is NP-complete for all
$b\geq 1$, except the case where $b=1$ and $H=K_{3}$, which is in P.

##  6 Conclusion and future work

This paper provided a complete categorization for the complexity of
$(P_{3},H)$-Arrowing when $H$ is $2$-connected. We provided a polynomial-time
algorithm when $H=K_{3}$, and coNP-hardness proofs for all other cases. Our
gadgets utilized a novel graph invariant, minimum edge pair linkage, to avoid
unwanted copies of $H$. We showed that our hardness results can be extended to
$(P_{3},TK_{n})$\- and $(K_{1,n},H)$-Arrowing using easy-to-understand graph
transformations.

Our ultimate goal is to categorize the complexity of all $(F,H)$-Arrowing
problems. Our first objective is to categorize the complexity of
$(P_{3},H)$-Arrowing for all $H$, and to find more graph transformations to
extend hardness proofs between different arrowing problems.

## References

  * [1] P. Berman, M. Karpiński, and A. Scott.  Approximation Hardness of Short Symmetric Instances of MAX-3SAT.  ECCC, 2003.
  * [2] A. Bikov.  Computation and Bounding of Folkman Numbers.  PhD thesis, Sofia University “St. Kliment Ohridski”, 06 2018.
  * [3] S.A. Burr.  On the Computational Complexity of Ramsey-Type Problems.  Mathematics of Ramsey Theory, Algorithms and Combinatorics, 5:46–52, 1990.
  * [4] S.A. Burr, P. Erdős, and L. Lovász.  On graphs of Ramsey type.  Ars Combinatoria, 1(1):167–190, 1976.
  * [5] J. Edmonds.  Paths, Trees, and Flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.
  * [6] Z.R. Hassan, E. Hemaspaandra, and S. Radziszowski.  The Complexity of $(P_{k},P_{\ell})$-Arrowing.  In FCT 2023, volume 14292, pages 248–261, 2023.
  * [7] C.V.G.C. Lima, D. Rautenbach, U.S. Souza, and J.L. Szwarcfiter.  Decycling with a Matching.  Information Processing Letters, 124:26–29, 2017.
  * [8] C.V.G.C. Lima, D. Rautenbach, U.S. Souza, and J.L. Szwarcfiter.  Bipartizing with a Matching.  In COCOA 2018, pages 198–213, 2018.
  * [9] C.V.G.C. Lima, D. Rautenbach, U.S. Souza, and J.L. Szwarcfiter.  On the Computational Complexity of the Bipartizing Matching Problem.  Ann. Oper. Res., 316(2):1235–1256, 2022.
  * [10] S. Radziszowski.  Small Ramsey Numbers.  Electronic Journal of Combinatorics, DS1:1–116, January 2021.  URL: https://www.combinatorics.org/.
  * [11] V. Rosta.  Ramsey Theory Applications.  Electronic Journal of Combinatorics, DS13:1–43, December 2004.  URL: https://www.combinatorics.org/.
  * [12] V. Rutenburg.  Complexity of Generalized Graph Coloring.  In MFCS 1986, volume 233 of Lecture Notes in Computer Science, pages 573–581. Springer, 1986.
  * [13] M. Schaefer.  Graph Ramsey Theory and the Polynomial Hierarchy.  Journal of Computer and System Sciences, 62:290–322, 2001.

##  Appendix A Proof of Claim 1 and missing gadgets

See 1

  1. 1.

This follows from our definition of $Z$.

  2. 2.

If at most one vertex in $\\{u,v\\}$ were in $Z$, deleting it would disconnect
said copy of $H$, contradicting the fact that $H$ is $2$-connected.

  3. 3.

Suppose that both $E_{Z_{X}}$ and $E_{Z_{Y}}$ are nonempty. Let $f_{1}\in
E_{Z_{X}}$ and $f_{2}\in E_{Z_{Y}}$. We have
$\mathrm{epl}_{A_{H,e}}(f_{1},f_{2})=0$ since, by construction,
$E_{A_{H,e}}(X-Y,Y-X)=\emptyset$. Since both of these edges belong to $Z$,
which is isomorphic to $H$, we also have $\mathrm{epl}_{H}(f_{1},f_{2})=0$,
which contradicts our assumption that $\mathrm{mepl}(H)\geq 2$.

  4. 4.

Note that $k$-connected graphs must have minimum degree at least $k$ as a
vertex with fewer neighbors could be disconnected from the rest of the graph
with fewer than $k$ vertex deletions. So, we have $d_{H}(w)\geq 2$ for each
$w\in V(H)$. W.l.o.g., assume that $E_{Z_{X}}=\emptyset$. Then, each vertex in
$w\in Z_{X}$ can only be connected to $u$ and $v$. Thus, we have
$d_{H}(w)=d_{Z}(w)\leq 2$, and consequently $d_{H}(w)=2$.

Missing gadgets for $\mathbf{(P_{3},H)}$-Nonarrowing. In Figure 9 we show the
variable gadget for $(P_{3},J_{4})$-Nonarrowing. In Figure 10 we show the
clause gadget for $(P_{3},C_{4})$-Nonarrowing.

Figure 9: The variable gadget for $(P_{3},J_{4})$-Nonarrowing is shown on the
left. The colorings on the right show that when vertices marked $\mathbf{U}$
(resp., $\mathbf{N}$) are free, those marked $\mathbf{N}$ (resp.,
$\mathbf{U}$) are nonfree.  Figure 10: The clause gadget for
$(P_{3},C_{4})$-Nonarrowing is shown on the left. Possible inputs for the
gadget are shown on the right. A good coloring is possible unless the input is
three red edges.

##  Appendix B Extending to stars

We first define the following special graph which will be used in our
extension proof.

######  Definition B.1.

A graph $G$ is called an $(F,H)$-leaf sender with leaf-signal edge $(u,v)$ if
it is $(F,H)$-good, $(u,v)$ is red in all good colorings, and there exists a
good coloring where $(u,v)$ is not adjacent to any other red edge.

When the context is clear, we will use the shorthand append a leaf sender to
$u\in V(G)$ to mean we will add an $(F,H)$-leaf sender to $G$ and identify a
vertex of its leaf-signal edge with $u$. This graph essentially simulates
“appending a red edge” as described in Section 5.2.

###  B.1 Proof of Lemma 5.4

See 5.4

######  Proof B.2.

Suppose we are trying to prove the hardness of $(K_{1,n},H)$-Arrowing for
$2$-connected $H$ and $n\geq 3$. Let $A$ be a “minimally bad” graph such that
$A\rightarrow(K_{1,n},H)$, but removing any edge $e$ from $A$ gives a
$(K_{1,n},H)$-good graph. Let $e=(u,w)$ and $A^{\prime}=A-e$. Let
$\mathcal{C}$ be the set of all good colorings of $A^{\prime}$. For a coloring
$c\in\mathcal{C}$ and vertex $v$, let $r_{c}(v)$ be the number of red edges
that $v$ is adjacent to in $c$. Let
$r_{\mathcal{C}}(v)=\min_{c\in\mathcal{C}}r_{c}(v)$. We consider different
cases for $r_{\mathcal{C}}(u)$. Since $c$ is a good coloring, we know that
$r_{\mathcal{C}}(u)\leq n-1$.

  1. 1.

$r_{\mathcal{C}}(u)=n-1$. In this case, it is easy to see that $A^{\prime}$ is
a $(K_{1,n},H)$-enforcer with signal vertex $u$. Let $(p,q)\in V(H)$.
Construct a graph $B$ like so. Take a copy of $H$ and append an enforcer to
each vertex of $H$ except $p$ and $q$. It is easy to see that $(p,q)$ must be
red in all good colorings, i.e., $B$ is a $(K_{1,n},H)$-leaf sender with leaf-
signal edge $(p,q)$. For any graph $G$, we append a leaf-sender to each of
$G$’s vertices to obtain a graph $G^{\prime}$ such that
$G^{\prime}\rightarrow(K_{1,n},H)\iff G\rightarrow(K_{1,{n-1}},H)$, as
discussed in Section 5.2.

  2. 2.

$r_{\mathcal{C}}(u)=0$. Let $m=|V(H)|$. In this case, we can construct a
$(K_{1,n},H)$-enforcer, $B$, by combining $2m$ copies of $A^{\prime}$ as we
did in Lemma 4.6. Note that in any good coloring $c$ of $A^{\prime}$, we have
that $r_{c}(u)\geq n-1$ or $r_{c}(w)\geq n-1$; if not, such a coloring and a
red $(u,w)$ gives a good coloring for $A$, contradicting the fact that
$A\rightarrow(K_{1,n},H)$. Make $2m$ copies of $A^{\prime}$, where $u_{i}$
(resp., $w_{i})$ refers to the vertex $u$ (resp., $w$) in the $i^{\text{th}}$
copy of $A^{\prime}$, referred to as $A^{\prime}_{i}$. Now, identify each
$w_{i}$ with $u_{i+1}$ for $i\in\\{1,2,\ldots,2m-1\\}$, and identify $w_{2m}$
with $u_{1}$. Observe that when $w_{1}$ is adjacent to $n-1$ red edges in
$A^{\prime}_{1}$, then $u_{2}$ cannot be adjacent to any red edge in
$A^{\prime}_{2}$, causing $w_{2}$ to be adjacent to $n-1$ red edges in
$A^{\prime}_{2}$, and so on. Since every $u_{i}$ and $w_{i}$ is adjacent to
$n-1$ red edges, any of them can be our signal vertex $v$. We can now proceed
as we did in the previous case to reduce from $(K_{1,n-1},H)$-Arrowing.

  3. 3.

$r_{\mathcal{C}}(u)\in\\{1,2,\ldots,n-2\\}$. For any graph $G$, we can attach
a copy of $A^{\prime}$ to each of $G$’s vertices—identifying $u\in
V(A^{\prime})$ with each vertex—to obtain a graph $G^{\prime}$ such that
$G^{\prime}\rightarrow(K_{1,n},H)\iff
G\rightarrow(K_{1,{n-r_{\mathcal{C}}(u)}},H)$, as discussed in Section 5.2,
thereby providing a reduction from
$(K_{1,{n-r_{\mathcal{C}}(u)}},H)$-Arrowing.

Figure 11: The variable gadget for $(K_{1,3},K_{3})$-Nonarrowing is shown on
the left. Edges with the same color in all good colorings have been pre-
colored. Both good colorings are shown on the right.

###  B.2 Hardness of $\mathbf{(K_{1,n},K_{3})}$-Nonarrowing for $n\geq 3$

To show that $(K_{1,3},K_{3})$-Arrowing is coNP-complete, we provide gadgets
as we did for $(P_{3},H)$-Arrowing. We provide gadgets in Figures 11 and 12 to
show that $(2,2)$-3SAT can be reduced to $(K_{1,3},K_{3})$-Nonarowing. Note
that the output vertices are either attached to a single red edge or two red
edges. When they are attached to a single red edge, they behave like true
output signals. When adjacent to two red edges, they behave like a false
output signal. The clause gadget behaves like an OR gate, in that it has no
good coloring when the three input vertices all have false inputs.

Figure 12: The clause gadget for $(K_{1,3},K_{3})$-Nonarrowing is shown on
top. The eight combinations of inputs that can be given to the gadget are
shown on the bottom. Observe that a $(K_{1,3},K_{3})$-good coloring is always
possible unless the input is three red $K_{1,2}$’s.  Figure 13: The smallest
cycle made when joining $(K_{1,3},K_{3})$ variable and clause gadgets is a
$C_{6}$.  Figure 14: $A^{\prime}_{1}$ and $A^{\prime}_{2}$ are graphs with
$r_{\mathcal{C}}(u_{i})=n-2$. We show how to construct a new graph using these
in (a). In (b), we show a good coloring where $u_{i}$’s are now adjacent to
$n-1$ red edges. Finally, in (c), we observe that the coloring in (b) is the
only good coloring since at most one edge from outside $A^{\prime}_{i}$ that
is adjacent to $u_{i}$ can be red.

Recall that in the hardness proofs for $(P_{3},H)$-Arrowing, we also had to
show that no new $H$ is constructed while combining gadget graphs to construct
$G_{\phi}$. It is easy to see that no new $K_{3}$ is constructed when our
gadgets are combined; since each clause has unique literals, a cycle formed
while constructing $G_{\phi}$ would have to go through at least two clause
gadgets and at least two variable gadgets, but this cycle has more than three
vertices (see Figure 13).

To show the hardness of $(K_{1,n},K_{3})$-Arrowing for $n\geq 4$, we can
proceed exactly as we did in Lemma 5.4. The only case where the proof fails is
when $r_{\mathcal{C}}(u)=n-2$, because now the proof says we have to reduce
$(K_{1,2},K_{3})$-Arrowing to $(K_{1,n},K_{3})$-Arrowing, which is unhelpful
since $(K_{1,2},K_{3})$-Arrowing is in P. In Figure 14 we show how vertices
attached to $n-2$ red edges can be combined to make a
$(K_{1,n},K_{3})$-enforcer. Using the enforcer, we can create a
$(K_{1,n},K_{3})$-leaf sender and reduce from $(K_{1,n-1},K_{3})$-Arrowing.


#  _Ab intio_ description of the electronic structure of high-temperature
cuprate superconductors: A Comparative Density Functional Study

Kanun Pokharel<EMAIL_ADDRESS>Department of Physics and Engineering
Physics, Tulane University, Louisiana 70118 New Orleans, USA  Christopher Lane
<EMAIL_ADDRESS>Theoretical Division, Los Alamos National Laboratory, Los
Alamos, New Mexico 87545, USA  Center for Integrated Nanotechnologies, Los
Alamos National Laboratory, Los Alamos, New Mexico 87545, USA  James W.
Furness  Department of Physics and Engineering Physics, Tulane University,
Louisiana 70118 New Orleans, USA  Ruiqi Zhang  Department of Physics and
Engineering Physics, Tulane University, Louisiana 70118 New Orleans, USA
Jinliang Ning  Department of Physics and Engineering Physics, Tulane
University, Louisiana 70118 New Orleans, USA  Bernardo Barbiellini  LUT
University, P.O. Box 20, FI-53851, Lappeenranta, Finland  Physics Department,
Northeastern University, Boston, Massachusetts 02115, USA  Robert S.
Markiewicz  Physics Department, Northeastern University, Boston, Massachusetts
02115, USA  Yubo Zhang  Department of Physics and Engineering Physics, Tulane
University, Louisiana 70118 New Orleans, USA  Arun Bansil<EMAIL_ADDRESS>Physics Department, Northeastern University, Boston, Massachusetts 02115, USA
Jianwei Sun<EMAIL_ADDRESS>Department of Physics and Engineering Physics,
Tulane University, Louisiana 70118 New Orleans, USA

###### Abstract

In this work we have studied the crystal, electronic, and magnetic structure
of $\mathrm{La_{2-x}Sr_{x}CuO_{4}}$ for $x=0.0$ and $x=0.25$ employing nine
functionals, representing the local, semi-local, and hybrid density functional
approximations on the first four rungs of Jacob’s ladder. Our assessment finds
that the meta-generailized gradient approximation (meta-GGA) class of
functionals perform well in capturing the key properties of the prototypical
high-temperature superconductor. In contrast, the local spin density
approximation (LDA), GGA, and the considered hybrid density functional fail to
capture the metal-insulator transition (MIT) under doping. We further explore
the capability of hybrid functionals to capture the MIT transition upon doping
by varying the admixture parameter of its exact exchange component.

##  I Introduction

Ever since the discovery of cuprates in 1986 by Bednorz and Muller[1], the
anomalous behavior of the pristine and especially the doped compounds have
eluded theoretical explanation and remain as a central unsolved problem in
condensed matter physics. $\mathrm{La_{2}CuO_{4}}$, in particular, has been a
significant challenge to capture within a single coherent theoretical
framework. The Hohenberg-Kohn-Sham density functional theory (DFT)[2; 3]
framework failed spectacularly to capture the insulating antiferromagnetic
ground state, let alone the doped phase [4]. Specifically, the local spin-
density approximation (LSDA) exchange-correlation functional incorrectly
predicts the parent compound to be a metal, yielding a vastly underestimated
value for copper magnetic moment of 0.1${\mathrm{\mu}}_{B}$ [5; 6] in
comparison to the experimental value of 0.5 ${\mathrm{\mu}}_{B}$ [7; 8]. The
generalized gradient approximation (GGA) still predicts it as a metal with a
slightly improved magnetic moment of 0.2${\mathrm{\mu}}_{B}$ [9]. Studies
using the Becke-3-Lee-Yang-Parr (B3LYP)[10; 11; 12; 13] hybrid functional have
been shown to correctly explain the AFM ground state in LCO but fail to
capture the transition to a metal upon doping [14]. These failures have led to
the belief that DFT was insufficient to correctly capture the physics of the
cuprates and other correlated materials. Therefore, methodologies “beyond DFT”
such as quantum Monte carlo methods [15], DFT+U [16; 17], and DMFT[18; 19; 20]
had to be introduced to handle the strong electron correlation effects.
However these approaches typically introduce ad hoc parameters to tune the
correlation strength, thereby limiting their predictive power.

Recent progress in constructing advanced density-functionals provides a new
path forward in addressing the electronic structures of correlated materials
at the first-principles level. In particular, the strongly-constrained-and-
appropriately-normed (SCAN) meta-GGA functional[21], which obeys all 17 known
constraints applicable to a meta-GGA functional, has been shown to accurately
predict many of the key properties of the undoped and doped
$\mathrm{La_{2}CuO_{4}}$ and $\mathrm{YBa_{2}Cu_{3}O_{6}}$ [22; 23; 24]. In
$\mathrm{La_{2}CuO_{4}}$, one correctly captures the size of the optical band
gap, value of the copper magnetic moment and its alignment in the cuprate
plane, and the magnetic form factor in good accord with the corresponding
experimental results [23]. In near-optimally
doped$\mathrm{YBa_{2}Cu_{3}O_{7}}$, 26 competing uniform and stripe phases are
identified, where the treatment of charge, spin, and lattice degrees of
freedom on the same footing was crucial in stabilizing the stripe phases
without invoking any free parameters. Furthermore, SCAN has been applied to
$\mathrm{Sr_{2}IrO_{4}}$ parent compound yielding the subtle balance between
electron correlations and strong spin-orbit coupling in excellent accord with
experimental observations.[25]

SCAN’s success in the copper and iridium oxide systems is a significant
achievement for DFT and suggests promising results in the wider class of
correlated materials. In light of these recent milestones, a few questions
arise. Is SCAN a unique density functional that is able to correctly capture
these properties of cuprates or do other meta-GGAs behave similarly?
Furthermore, how do hybrid functionals behave in comparison?

In this paper the accuracy of nine density functionals, including LSDA [26;
27], PBE[28], SCAN[21], SCANL [29], TPSS[30], RTPSS[31], MS0[32], MS2[33],
M06L [34], and HSE06[35; 36; 37; 38; 39], are assessed with respect to the
experimental crystal, electronic, and magnetic structure of pristine and doped
prototypical high-temperature superconductor $\mathrm{La_{2-x}Sr_{x}CuO_{4}}$.
The various functionals employed span the first four rungs of the so-called
DFT _Jacob’s Ladder_[40] allowing us to judge the performance of each
functional class for the description of correlated condensed matter systems.

##  II Computational Details

The calculations were performed using the pseudopotential projector-augmented
wave method [41] implemented in the Vienna ab initio simulation package
(VASP)[42; 43]. The energy cutoff for the plane-wave basis set was taken to be
550 eV for all meta-GGA calculation whereas 520 eV for HSE functional. To
sample the Brillouin zone, for meta-GGAs, $8\times 8\times 4$
$\Gamma$-centered k-point mesh was used while a smaller mesh of $6\times
6\times 2$ was used for HSE functional. The structures were initially relaxed
for meta-GGAs using conjugate gradient algorithm with an atomic force
tolerance of $\mathrm{{eV}/{A^{o}}}$ and total energy tolerance of
$\mathrm{10^{-5}}$ eV. For HSE06 functional, the unrelaxed experimental
structure was used for calculations. The pristine system used conjugate
gradient algorithm while the doped system uses damped algorithm in HSE06
calculations. The computational cost for HSE06 increases drastically as
compared to meta-GGA calculations so smaller energy, smaller k-point and
unrelaxed structure were used. Also, only LTO phase calculation for HSE06 for
the doped system was performed. The unit cell was rotated to obtain $\sqrt{2}$
$\times$ $\sqrt{2}$ AFM structure [44] where Sr was doped in place of one La
to obtain a doped structure. In the AFM structure obtained, due to the crystal
symmetry, lanthanum substitution position was equivalent at all position so
replacing one La by Sr resulted in an effective average doping of 25$\%$.

##  III Comparative study of different functionals

### Ground State Crystal Structure

The phase diagram of the cuprates displays a complex intertwining of magnetic
and charge ordered states that evolve with doping to reveal a superconducting
dome. Interestingly, structural phase transitions associated with various
octahedral tilt modes[7; 8] mainly follow the electronic phase boundaries.[45]
At high temperatures LCO is found to be tetragonal (HTT) with all
$\mathrm{CuO_{6}}$ octahedra aligned axially. A phase transition occurs upon
lowering the temperature resulting in a low-temperature orthorhombic (LTO)
phase where the octahedra are tilted along the (110) zone diagonal. An
additional low-temperature tetragonal (LTT) phase arises upon substituting La
by Ba or Nd, which has the octahedral tilts aligned along the (100) and (010)
directions in alternating CuO2 layers. Therefore, to properly disentangle the
connection between the electronic and the physical properties of the high-Tc
cuprates it is imperative to capture the correct ground state crystal
structure.

Figure 1: $(\textbf{a})$ Theoretical predicted crystal structure of
$\mathrm{La_{2-x}Sr_{x}CuO_{4}}$ in the LTO phase for $x=0.0$ and $0.25$. The
copper, oxygen, lanthanum, and strontium atoms are represented by blue, green
and yellow spheres, respectively. Octahedral faces are shaded in blue (orange)
to denote spin-up (down). Black dotted lines mark the unit cell.
$(\textbf{b})$ ) A schematic of the NM and AFM Brillouin zones; where the path
followed in the electronic dispersions in Fig. 6 is marked. Figure 2:
$(\textbf{a})$ The energy difference between the G-AFM and NM phases for the
HTT (green upside-down triangle), LTO (white dimond), and LTT (blue triangle)
crystal structures for various density functionals. The relative energy per
formula unit for AFM between LTO and HTT $(\textbf{b})$ and LTO and LTT
$(\textbf{c})$ structures for pristine LCO. $(\textbf{d})$, $(\textbf{e})$ and
$(\textbf{f})$ same as $(\textbf{a})$, $(\textbf{b})$, and $(\textbf{a})$
except for LSCO.

To calculate the total energy of each crystalline phase, we consider the
$\sqrt{2}$ $\times$ $\sqrt{2}$ supercell of the body-centered-tetragonal
I4/mmm primitive unit-cell to accommodate both the octahedral tilts and
$(\pi,\pi)$ AFM order originating within the CuO2 plane. We treat the doping
within the relatively simple “$\delta$\- doping” scheme where a single La is
replaced by Sr in the supercell. This approach has been recently reported for
doping LSCO via molecular beam epitaxy techniques[44]. Overall, this scheme
yields an average hole-doing of 25%[22]. Figure 1 $(\textbf{a})$ shows the
crystal structures of LCO and LSCO in the LTO phase where the CuO6 octahedra
have been shaded blue and orange following the AFM order. The Sr doping site
is also indicated.

Figure 3: Comparison of the theoretically obtained and experimental lattice
constants for the HTT, LTT, and LTO crystal structures using various density
functionals for La2CuO4.

Figure 2 (a) and (d) presents the relative energy between the AFM and NM
phases for pristine and doped $\mathrm{La_{2-x}Sr_{x}CuO_{4}}$ in each crystal
structure for the various density fuctionals. Firstly, we note LDA does not
stabilize an AFM order over the Cu sites, whereas in GGA the AFM phase is
marginally more stable, consistent with previous studies[22]. The meta-GGA
functionals all find the AFM phase to be the ground state, displaying a range
of $-0.2$ to $-0.9$ eV separating the AFM and NM states in the pristine
structure, whereas in doped case the energy difference reduces by a factor of
two. These trends are consistent across the various crystal structures.

Figure 2 (b-c) and (e-f) presents the relative energy between the HTT, LTT,
and LTO crystal structures for pristine and doped
$\mathrm{La_{2-x}Sr_{x}CuO_{4}}$ obtained within various density functional
approximations. Across all density functionals the HTT phase lies at much
higher energies compared to the LTO and LTT phases. The difference between LTO
and LTT appears more delicate. For SCAN, SCANL, and M06L, the LTO phase is
correctly predicted in the undoped case, while TPSS, RTPSS, MS0, and MS2
incorrectly predict the LTT phase as the ground state. We note that the LTO
and LTT phases are found experimentally to be virtually degenerate with
multiple domains displaying the coexistence of these two phases. This suggests
that SCANL and M06L over estimate the stability of the LTO phase, while the
near degeneracy predicted by SCAN is in favor with the experimental
observations. In the doped case, all functionals rightly predict the ground
state to be LTT phase[46], with SCAN and SCANL displaying a marginal energy
difference with respect to LTO.

Figure 3 shows the equilibrium lattice constants for LCO in the HTT, LTT, and
LTO phases using various density functionals. The LSDA and PBE values were
taken from reference [22] and experimental values were obtained from [47; 48;
49]. Firstly, we observe that LSDA underestimates the values of lattice
constants, by over binding the atoms, for all crystal structures. PBE, on the
other hand, under-binds the atoms yielding an exaggerated orthorhombicity in
the LTO phase, similar to the super-tetragonality spuriously predicted by PBE
for ferroelectric materials [50]. TPSS, RTPSS, MS0, and MS2 correct upon the
GGA results by reducing the $b$ lattice constant in line with the experimental
value in LTO and LTT. Curiously, all functionals under estimate the lattice
parameters in the HTT phase, except for GGA and M06L. Furthermore, the
emperical M06L functional predicts all lattice constants for each crystal
phase with better accuracy than the other functionals. We note that HTT is a
high-temperature phase and the experimenatl lattice constant should be
corrected by removing the finite temperature expansion and the zero-point
vibrational expansion for comparison with DFT results. Figure 4 is the same as
Fig. 3, except compares the octahedra tilt angles. Here, the M06L finds a
reduced tilt angle, whereas all other functionals tend to over estimate the
angle within a few degrees. However, we should note that the calculated and
experimental tilt angles should be regarded as average values. That is, the
CuO6 octahedra are not rigid objects, but can dynamically deform and should
couple strongly to various phonon modes. Therefore, to capture the octahedra
tilts more accurately a molecular dynamics or phonon calculation should be
performed.

Figure 4: Theoretically predicted values of octahedra tilt angle using various
density functionals for LCO. The LSDA and PBE value are taken from reference
[22] The octahedra tilt values for LTO, LTT and HTT are divided by
corresponding experimental values. Figure 5: Bar graph of the theoretical
predicted values of $(\textbf{a})$ electronic band gap $(\textbf{b})$ copper
magnetic moment for all three phases of pristine LCO obtained within various
density functional approximations. The dotted grey lines represent
experimental values for the respective values. The LSDA and PBE values are
taken from reference [22]

### Electronic And Magnetic Structure

Figure 5 compares the theoretically predicted electronic band gap
$(\textbf{a})$ and copper magntic moment $(\textbf{b})$ within the various
density functional approximations for all three crystal phases of pristine
LCO. The experimental band gap and copper magnetic moment of 1.0 eV and 0.5
$\mu_{B}$, respectively, are marked by the grey dashed lines. Clearly, LDA and
GGA spectacularly underestimate the band gap and magnetic moments, due to the
failure to stabilize the AFM order. Moving up Jacob’s ladder, a large
variation in behavior amongst the meta-GGAs is observed. Specifically, TPSS
and RTPSS both underestimate the band gap and magnetic moments, while the MS
family of functionals, yield the experimental values or slightly over estimate
them. SCAN gives accurate results in both cases, whereas SCANL predicts a
reduced band gap by almost a factor of two. M06L under estimates both the
moment and the gap value, possibly due to its bias towards molecular systems
during its empirical construction. Finally, the hybrid HSE06 functional,
predicts a $3$ eV band gap completely out of step with experiment.

Figure 6 shows the electronic band dispersions of pristine and doped La2CuO4
in the LTO crystal structure for the AFM phase for various density
functionals. The copper (red circles) and planar oxygen (blue dots) atomic
weights are overlayed. For all functionals LCO is clearly seen to be an
insulator. At the valence edge, SCAN produces a significant avoided crossing
between the $\mathrm{d}_{\mathrm{x^{2}}-\mathrm{y^{2}}}$ and in-plane oxygen
dominated bands along $\Gamma-\mathrm{M}$ and $\mathrm{M}-\bar{\Gamma}$.
Comparing this feature across the various functionals, it is reduced in SCANL
and virtually non-existent in M06L. In SCAN, the gap is indirect, with the
lowest energetic transition occurring at $\mathrm{M}\pm\delta$ and
$\mathrm{M}$ for the valence and conduction bands ($\delta$ is a small
displacement away from $\mathrm{M}$), respectively. In contrast, SCANL and
M06L predict indirect transitions connecting valence and conduction between
$\mathrm{X}$ and $\mathrm{M}$. These slight differences in alignment between
the oxygen and copper states suggest that the various functionals are
capturing an effective on-site potential to a varying degree, which is
possibly derived from the reduced magnetic moment found by each functional.

Figure 6: Electronic band structure and density of states of LCO and LSCO in
the LTO phase using $(\textbf{a})$ SCAN $(\textbf{b})$ SCANL $(\textbf{c})$
M06L $(\textbf{d})$HSE06. The contribution of
Cu-$\mathrm{d}_{\mathrm{x^{2}}-\mathrm{y^{2}}}$ and O
-$\mathrm{p_{x}}+\mathrm{p_{y}}$ are marked by the red and blues shadings,
respectively. The path followed by the dispersion in the Brillouin zone is
shown in Fig 1$(\textbf{b})$.

For the doped system, all meta-GGAs capture transition to a metal, with each
functional producing slightly different band splittings around the Fermi
level. In contrast, HSE06 maintains a small gap and predicts a nearly flat
impurity-like band just above the Fermi level, consistent with the B3LYP
result [14]. Moreover, the conduction bands display significant spin splitting
indicative of a strong uncompensated ferrimagnetic order.

##  IV Why does HSE06 open a gap for the doped LSCO

The exchange-correlation energy for the screened hybrid functional of Heyd,
Scuseria and Ernzerhof (HSE) is given by

$\displaystyle\mathrm{E_{xc}^{HSE}=\alpha
E_{x}^{HF,SR}(\mu)+(1-\alpha)E_{x}^{PBE,SR}(\mu)}$
$\displaystyle+\mathrm{E_{x}^{PBE,LR}(\mu)+E_{c}^{PBE}(\mu)}$

where “$\alpha$” is the exact exchange admixing parameter whose value is 1/4
[51]. $\mathrm{E_{x}^{HF,SR}(\mu)}$ is the short-range HF exact exchange,
$\mathrm{E_{x}^{PBE,SR}(\mu)}$ and $\mathrm{E_{x}^{PBE,LR}(\mu)}$ are the
short and long-range components respectively of the PBE exchange functional.
Hybrid density functionals were originally designed to combine semilocal
density functionals with the Hartree-Fock approximation for thermochemical
properties of molecules, the former and the latter of which typically
overbinds and underbinds molecules, respectively. The admixing parameter value
of 1/4 has been justified for molecular thermochemical properties based on a
perturbation consideration [52]. HSE06 with the admixing parameter value of
1/4 later turned out to work well for band gap predictions of semiconductors.
This can be understood from its better dealing with the orbital localization
by neutralizing the over-delocalization of PBE due to their self-interaction
errors with the over-localization of Hartree-Fock [53; 54]. However, due to
its over-localization error, Hartree-Fock is well known for not being
applicable for metallic systems where no band gap is present to separate the
occupied from unoccupied bands. Therefore, hybrid functionals are not
recommended for metallic systems even if only a fraction of the exact exchange
is mixed in.

Consistently, the HSE06 functional correctly captures LCO as insulator but
fails to capture the metallic transition under doping in LSCO. Figure 7 shows
the band structures of HSE06 by varying the mixing parameter “$\alpha$”. For
$\alpha$ = 0, HSE06 is reduced to PBE, and thus predicts LSCO to be metallic.
As the mixing parameter is increased to $\alpha$ =0.05, a slight change in the
band structure is observed. The conduction bands are slightly pushed up and
split due to the stabilization of magnetic moments of Cu. Also, the bands
around Fermi level at point X start to separate from one another. Further
increasing the value to 0.15 results in larger band separation and splitting
of conduction bands. The two valence bands near Fermi level are separated out
with some portion of both bands crossing the Fermi level. Finally, at the
standard value of $\alpha$= 0.25, bands completely split into conduction band
at around 0.2 eV and valence band below Fermi level with a small gap,
resulting in the doped system being an insulator. From the band structures it
can be seen that at lower admixing values, the conductions band and valence
bands around Fermi level are more dominated by copper orbitals at M point with
color of projection being more red. As the value of admixing parameter
increases, the oxygen orbitals gain more weight and color changes from red
dominant to mixture of red and blue, indicating more characteristic of charge
transfer. This implies that electrons are more localized around oxygen atoms,
as expected for higher portions of exact exchange in HSE06.

Figure 7: Band structure comparison by varying mixing parameter for
$(\textbf{a})$ $\alpha$ = 0 $(\textbf{b})$ $\alpha$ = 0.05 $(\textbf{c})$
$\alpha$ = 0.15 and $(\textbf{d})$ $\alpha$ = 0.25 in doped LTO phase. The
blue filled and red empty circles correspond to oxygen
$\mathrm{p_{x}}$+$\mathrm{p_{y}}$ orbitals and the copper
d${}_{\mathrm{x^{2}}-\mathrm{y^{2}}}$ orbitals respectively. The projection
strength is shown by marker size.

##  V Concluding remarks

Our results show that all meta-GGAs behave similarly by predicting the
pristine LCO as an insulator and capturing the metallic transition with Sr
doping. Among different meta-GGAs considered, SCAN’s performance on
structural, electronic, and magnetic properties of LCO/LSCO is closest to
experimental results. The hybrid functional (HSE06) in contrast, captures the
pristine system as an insulator, predicting a very large values of band gap
and copper magnetic moment and completely incorrectly predicting the doped
system as an insulator. The incorrect prediction of doped system is linked to
the standard value of the admixing parameter, which has to be adjusted for the
metal-insulator transition prediction of LCO under doping. We have shown that
the standard value of 25$\%$ mixing needs to be revisited while considering
the metallic system.

##  VI acknowledgments

The work at Tulane University was supported by the US Department of Energy
under EPSCoR Grant No. DE-SC0012432 with additional support from the Louisiana
Board of Regents, and by the U.S. DOE, Office of Science, Basic Energy
Sciences grant number DE-SC0019350. Calculations were partially done using the
National Energy Research Scientific Computing Center supercomputing center and
the Cypress cluster at Tulane University. The work at Northeastern University
was supported by the US Department of Energy (DOE), Office of Science, Basic
Energy Sciences grant number DE-FG02-07ER46352 (core research), and benefited
from Northeastern University’s Advanced Scientific Computation Center (ASCC),
the NERSC supercomputing center through DOE grant number DE-AC02-05CH11231,
and support (testing efficacy of advanced functionals) from the DOE EFRC:
Center for Complex Materials from First Principles (CCM) under grant number
DE-SC0012575. C.L. was supported by the U.S. DOE NNSA under Contract No.
89233218CNA000001 and by the Center for Integrated Nanotechnologies, a DOE BES
user facility, in partnership with the LANL Institutional Computing Program
for computational resources. Additional support was provided by DOE Office of
Basic Energy Sciences Program E3B5. B.B. acknowledges support from the COST
Action CA16218.

## References

  * [1] J. G. Bednorz and K. A. Müller, “Possible hight c superconductivity in the ba- la- cu- o system,” Zeitschrift für Physik B Condensed Matter, vol. 64, no. 2, pp. 189–193, 1986.

  * [2] P. Hohenberg and W. Kohn, “Inhomogeneous electron gas,” Physical review, vol. 136, no. 3B, p. B864, 1964.
  * [3] W. Kohn and L. J. Sham, “Self-consistent equations including exchange and correlation effects,” Physical review, vol. 140, no. 4A, p. A1133, 1965\.
  * [4] W. E. Pickett, “Electronic structure of the high-temperature oxide superconductors,” Reviews of Modern Physics, vol. 61, no. 2, p. 433, 1989\.
  * [5] L. Mattheiss, “Electronic band properties and superconductivity in la 2- y x y cuo 4,” Physical review letters, vol. 58, no. 10, p. 1028, 1987.
  * [6] J. P. Perdew and A. Zunger, “Self-interaction correction to density-functional approximations for many-electron systems,” Physical Review B, vol. 23, no. 10, p. 5048, 1981.
  * [7] D. Vaknin, S. Sinha, D. Moncton, D. Johnston, J. Newsam, C. Safinya, and H. King Jr, “Antiferromagnetism in la 2 cuo 4- y,” Physical review letters, vol. 58, no. 26, p. 2802, 1987.
  * [8] T. Freltoft, G. Shirane, S. Mitsuda, J. Remeika, and A. Cooper, “Magnetic form factor of cu in la 2 cu o 4,” Physical Review B, vol. 37, no. 1, p. 137, 1988.
  * [9] D. Singh and W. Pickett, “Gradient-corrected density-functional studies of cacuo 2,” Physical Review B, vol. 44, no. 14, p. 7715, 1991.
  * [10] A. D. Becke, “Density-functional exchange-energy approximation with correct asymptotic behavior,” Physical review A, vol. 38, no. 6, p. 3098, 1988\.
  * [11] C. Lee, W. Yang, and R. G. Parr, “Development of the colle-salvetti correlation-energy formula into a functional of the electron density,” Physical review B, vol. 37, no. 2, p. 785, 1988.
  * [12] A. D. Becke, “A new mixing of hartree–fock and local density-functional theories,” The Journal of chemical physics, vol. 98, no. 2, pp. 1372–1377, 1993.
  * [13] P. Stephens, F. Devlin, C. Chabalowski, and M. J. Frisch, “Ab initio calculation of vibrational absorption and circular dichroism spectra using density functional force fields,” The Journal of Physical Chemistry, vol. 98, no. 45, pp. 11623–11627, 1994.
  * [14] J. K. Perry, J. Tahir-Kheli, and W. A. Goddard III, “Ab initio evidence for the formation of impurity d 3 z 2- r 2 holes in doped la 2- x sr x cuo 4,” Physical Review B, vol. 65, no. 14, p. 144501, 2002.
  * [15] L. K. Wagner and P. Abbamonte, “Effect of electron correlation on the electronic structure and spin-lattice coupling of high-t c cuprates: Quantum monte carlo calculations,” Physical Review B, vol. 90, no. 12, p. 125129, 2014.
  * [16] M. Czyżyk and G. Sawatzky, “Local-density functional and on-site correlations: the electronic structure of la 2 cuo 4 and lacuo 3,” Physical Review B, vol. 49, no. 20, p. 14211, 1994.
  * [17] S. Pesant and M. Côté, “Dft+ u study of magnetic order in doped la 2 cuo 4 crystals,” Physical Review B, vol. 84, no. 8, p. 085104, 2011.
  * [18] G. Kotliar, S. Y. Savrasov, K. Haule, V. S. Oudovenko, O. Parcollet, and C. Marianetti, “Electronic structure calculations with dynamical mean-field theory,” Reviews of Modern Physics, vol. 78, no. 3, p. 865, 2006.
  * [19] K. Held, I. Nekrasov, G. Keller, V. Eyert, N. Blümer, A. McMahan, R. Scalettar, T. Pruschke, V. Anisimov, and D. Vollhardt, “Realistic investigations of correlated electron systems with lda+ dmft,” physica status solidi (b), vol. 243, no. 11, pp. 2599–2631, 2006.
  * [20] H. Park, K. Haule, and G. Kotliar, “Cluster dynamical mean field theory of the mott transition,” Physical review letters, vol. 101, no. 18, p. 186403, 2008.
  * [21] J. Sun, A. Ruzsinszky, and J. P. Perdew, “Strongly constrained and appropriately normed semilocal density functional,” Physical review letters, vol. 115, no. 3, p. 036402, 2015.
  * [22] J. W. Furness, Y. Zhang, C. Lane, I. G. Buda, B. Barbiellini, R. S. Markiewicz, A. Bansil, and J. Sun, “An accurate first-principles treatment of doping-dependent electronic structure of high-temperature cuprate superconductors,” Communications Physics, vol. 1, no. 1, p. 11, 2018.
  * [23] C. Lane, J. W. Furness, I. G. Buda, Y. Zhang, R. S. Markiewicz, B. Barbiellini, J. Sun, and A. Bansil, “Antiferromagnetic ground state of la 2 cuo 4: A parameter-free ab initio description,” Physical Review B, vol. 98, no. 12, p. 125140, 2018.
  * [24] Y. Zhang, C. Lane, J. W. Furness, B. Barbiellini, J. P. Perdew, R. S. Markiewicz, A. Bansil, and J. Sun, “Competing stripe and magnetic phases in the cuprates from first principles,” Proceedings of the National Academy of Sciences, vol. 117, no. 1, pp. 68–72, 2020.
  * [25] C. Lane, Y. Zhang, J. W. Furness, R. S. Markiewicz, B. Barbiellini, J. Sun, and A. Bansil, “First-principles calculation of spin and orbital contributions to magnetically ordered moments in sr 2 iro 4,” Physical Review B, vol. 101, no. 15, p. 155110, 2020.
  * [26] R. O. Jones and O. Gunnarsson, “The density functional formalism, its applications and prospects,” Reviews of Modern Physics, vol. 61, no. 3, p. 689, 1989.
  * [27] J. P. Perdew and Y. Wang, “Accurate and simple analytic representation of the electron-gas correlation energy,” Physical review B, vol. 45, no. 23, p. 13244, 1992.
  * [28] J. P. Perdew, K. Burke, and M. Ernzerhof, “Generalized gradient approximation made simple,” Physical review letters, vol. 77, no. 18, p. 3865, 1996.
  * [29] D. Mejia-Rodriguez and S. Trickey, “Deorbitalization strategies for meta-generalized-gradient-approximation exchange-correlation functionals,” Physical Review A, vol. 96, no. 5, p. 052512, 2017.
  * [30] J. Tao, J. P. Perdew, V. N. Staroverov, and G. E. Scuseria, “Climbing the density functional ladder: Nonempirical meta–generalized gradient approximation designed for molecules and solids,” Physical Review Letters, vol. 91, no. 14, p. 146401, 2003.
  * [31] J. P. Perdew, A. Ruzsinszky, G. I. Csonka, L. A. Constantin, and J. Sun, “Workhorse semilocal density functional for condensed matter physics and quantum chemistry,” Physical Review Letters, vol. 103, no. 2, p. 026403, 2009.
  * [32] J. Sun, B. Xiao, and A. Ruzsinszky, “Communication: Effect of the orbital-overlap dependence in the meta generalized gradient approximation,” 2012\.
  * [33] J. Sun, R. Haunschild, B. Xiao, I. W. Bulik, G. E. Scuseria, and J. P. Perdew, “Semilocal and hybrid meta-generalized gradient approximations based on the understanding of the kinetic-energy-density dependence,” The Journal of Chemical Physics, vol. 138, no. 4, p. 044113, 2013.
  * [34] Y. Zhao and D. G. Truhlar, “A new local density functional for main-group thermochemistry, transition metal bonding, thermochemical kinetics, and noncovalent interactions,” The Journal of chemical physics, vol. 125, no. 19, p. 194101, 2006.
  * [35] J. Heyd, “J. heyd, ge scuseria, and m. ernzerhof, j. chem. phys. 124, 219906 (2006).,” J. Chem. Phys., vol. 124, p. 219906, 2006.
  * [36] J. Heyd, J. E. Peralta, G. E. Scuseria, and R. L. Martin, “Energy band gaps and lattice parameters evaluated with the heyd-scuseria-ernzerhof screened hybrid functional,” The Journal of chemical physics, vol. 123, no. 17, p. 174101, 2005.
  * [37] J. Heyd, “J. heyd and ge scuseria, j. chem. phys. 121, 1187 (2004).,” J. Chem. Phys., vol. 121, p. 1187, 2004.
  * [38] J. Heyd, “J. heyd, je peralta, ge scuseria, and rl martin, j. chem. phys. 123, 174101 (2005).,” J. Chem. Phys., vol. 123, p. 174101, 2005.
  * [39] J. E. Peralta, J. Heyd, G. E. Scuseria, and R. L. Martin, “Spin-orbit splittings and energy band gaps calculated with the heyd-scuseria-ernzerhof screened hybrid functional,” Physical Review B, vol. 74, no. 7, p. 073101, 2006.
  * [40] J. Cumings and A. Zettl, “Aip conf. proc. series in electronic properties of molecular nanostructures,” 2001.
  * [41] G. Kresse and D. Joubert, “From ultrasoft pseudopotentials to the projector augmented-wave method,” Physical review b, vol. 59, no. 3, p. 1758, 1999\.
  * [42] G. Kresse and J. Furthmüller, “Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set,” Physical review B, vol. 54, no. 16, p. 11169, 1996.
  * [43] G. Kresse and J. Hafner, “Ab initio molecular dynamics for open-shell transition metals,” Physical Review B, vol. 48, no. 17, p. 13115, 1993\.
  * [44] A. Suter, G. Logvenov, A. Boris, F. Baiutti, F. Wrobel, L. Howald, E. Stilp, Z. Salman, T. Prokscha, and B. Keimer, “Superconductivity drives magnetism in $\delta$-doped la 2 cuo 4,” Physical Review B, vol. 97, no. 13, p. 134522, 2018.
  * [45] I. Askerzade, “Physical properties of unconventional superconductors,” in Unconventional Superconductors, pp. 1–26, Springer, 2012.
  * [46] J. Tranquada, B. Sternlieb, J. Axe, Y. Nakamura, and S. Uchida, “Evidence for stripe correlations of spins and holes in copper oxide superconductors,” nature, vol. 375, no. 6532, p. 561, 1995.
  * [47] a. J. Jorgensen, B. Dabrowski, S. Pei, D. Hinks, L. Soderholm, B. Morosin, J. Schirber, E. Venturini, and D. Ginley, “Superconducting phase of la 2 cu o 4+ $\delta$: A superconducting composition resulting from phase separation,” Physical Review B, vol. 38, no. 16, p. 11337, 1988.
  * [48] D. Cox, P. Zolliker, J. Axe, A. Moudden, A. Moodenbaugh, and Y. Xu, “Structural studies of la 2- x ba x cuo 4 between 11–293 k,” MRS Online Proceedings Library Archive, vol. 156, 1989.
  * [49] S. A. Wolf and V. Z. Kresin, Novel superconductivity.  Springer Science & Business Media, 2012.
  * [50] Y. Zhang, J. Sun, J. P. Perdew, and X. Wu, “Comparative first-principles studies of prototypical ferroelectric materials by lda, gga, and scan meta-gga,” Physical Review B, vol. 96, no. 3, p. 035143, 2017.
  * [51] J. Heyd, G. E. Scuseria, and M. Ernzerhof, “Hybrid functionals based on a screened coulomb potential,” The Journal of chemical physics, vol. 118, no. 18, pp. 8207–8215, 2003.
  * [52] K. Burke, M. Ernzerhof, and J. P. Perdew, “The adiabatic connection method: a non-empirical hybrid,” Chemical Physics Letters, vol. 265, no. 1-2, pp. 115–120, 1997.
  * [53] P. Mori-Sánchez, A. J. Cohen, and W. Yang, “Localization and delocalization errors in density functional theory and implications for band-gap prediction,” Physical review letters, vol. 100, no. 14, p. 146401, 2008.
  * [54] Y. Zhang, J. Furnes, R. Zhang, Z. Wang, A. Zunger, and J. Sun, “Symmetry-breaking polymorphous descriptions for complex materials without interelectronic u,” arXiv preprint arXiv:1906.06467, 2019.