# Pattern avoidance and smoothness of Hessenberg Schubert varieties

Soojin Cho  Department of Mathematics, Ajou University, Suwon 16499, Republic
of Korea<EMAIL_ADDRESS>,  JiSun Huh  Department of Mathematics, Ajou
University, Suwon 16499, Republic of Korea<EMAIL_ADDRESS>and  Seonjeong
Park  Department of Mathematics Education, Jeonju University, Jeonju 55069,
Republic of Korea<EMAIL_ADDRESS>
###### Abstract.

A _Hessenberg Schubert variety_ is the closure of a Schubert cell inside a
given Hessenberg variety. We consider the smoothness of Hessenberg Schubert
varieties of regular semisimple Hessenberg varieties of type $A$ in this
paper. We use known combinatorial characterizations of torus fixed points of a
Hessenberg Schubert variety $\Omega_{w,h}$ to find a necessary condition for
$\Omega_{w,h}$ to be smooth, in terms of the pattern avoidance of the
permutation $w$. First, we show useful theorems regarding the structure of the
subposet of the Bruhat order induced by the torus fixed points of
$\Omega_{w,h}$. Then we apply them to prove that the regularity of the
associated graph, which is known to be a necessary condition for the
smoothness of $\Omega_{w,h}$, is completely characterized by the avoidance of
the patterns we found.

###### Key words and phrases:

Hessenberg variety, Hessenberg Schubert variety, smoothness, pattern
avoidance, GKM graph, Bruhat order, $h$-Bruhat order

###### 2010 Mathematics Subject Classification:

Primary 14M15, 05E14; Secondary 14L30, 57S12

This work was supported by the National Research Foundation of Korea
[NRF-2020R1A2C1A01011045]

##  1\. Introduction

Schubert varieties of the full flag varieties form an important class of
complex projective varieties that appear in many areas, including algebraic
geometry, representation theory, and combinatorics. Schubert varieties of the
full flag variety of type $A_{n-1}$ are subvarieties of
$\operatorname{GL}_{n}(\mathbb{C})/B$, where $B$ is the Borel subgroup of
upper triangular matrices in $\operatorname{GL}_{n}(\mathbb{C})$. They are
indexed by the permutations in the symmetric group $\mathfrak{S}_{n}$, the
Weyl group of $\operatorname{GL}_{n}(\mathbb{C})$, and defined as the closure
of the Schubert cell; $X_{w}\coloneqq\overline{BwB/B}$ for
$w\in\mathfrak{S}_{n}$. The closure of the opposite Schubert cell
$\Omega_{w}^{\circ}\coloneqq B^{-}wB/B$ is the opposite Schubert variety
$\Omega_{w}$ of $\operatorname{GL}_{n}(\mathbb{C})/B$, where $B^{-}$ is the
subgroup of lower triangular matrices in $\operatorname{GL}_{n}(\mathbb{C})$.
The characterization of the smoothness of $X_{w}$ (hence of $\Omega_{w}$) was
done in different ways; in terms of pattern avoidance, the regularity of the
Bruhat subgraph, the Poincaré polynomial of the cohomology, and
Kazhdan–Lusztig polynomial; see Section 13.2 in [1]. We write some of them,
which are relevant to our work, in the following theorem. Note that a maximal
torus $T$ contained in $B$ acts on the flag variety
$\operatorname{GL}_{n}(\mathbb{C})/B$ as left multiplication and the opposite
Schubert varieties are $T$-invariant subvarieties of
$\operatorname{GL}_{n}(\mathbb{C})/B$.

######  Theorem 1.1.

The following statements are equivalent:

  1. (1)

The opposite Schubert variety $\Omega_{w}$ is smooth.

  2. (2)

The subgraph of the Bruhat graph of $\mathfrak{S}_{n}$ (equivalently, the GKM
graph of $\operatorname{GL}_{n}(\mathbb{C})/B$) induced by the set
$\Omega_{w}^{T}$ of torus fixed points is a regular graph.

  3. (3)

The permutation $w$ avoids patterns $2143$ and $1324$.

Hessenberg varieties are subvarieties of the full flag variety, which were
introduced by De Mari, Shayman, and Proceci [9] in the 1990s. A diagonal
matrix $S$ with distinct eigenvalues and a nondecreasing function
$h\colon\\{1,\dots,n\\}\to\\{1,\dots,n\\}$ with $h(i)\geq i$ for
$i=1,\dots,n$, defines a regular semisimple Hessenberg variety
$\operatorname{Hess}(S,h)$ of type $A$. Owing to their interesting
characteristics, Hessenberg varieties have become one of the central objects
of research in the related areas, including combinatorics and algebraic
geometry. A surprising instance is that the well-known Stanley–Stembridge
conjecture in algebraic combinatorics is shown to be equivalent to a
conjecture on the $\mathfrak{S}_{n}$-module structure of the cohomology of the
corresponding Hessenberg variety $\operatorname{Hess}(S,h)$ [4, 13]. In this
context, Cho, Hong, and Lee [7], considered the minus cell decomposition
(Białynicki–Birula decomposition)
$\bigsqcup_{w\in\mathfrak{S}_{n}}\Omega_{w,h}^{\circ}$ of
$\operatorname{Hess}(S,h)$ and the cohomology class $\sigma_{w,h}$ of
$\Omega_{w,h}\coloneqq\overline{\Omega_{w,h}^{\circ}}$ to investigate the
$\mathfrak{S}_{n}$-module structure of the cohomology space, where the closure
$\Omega_{w,h}$ is called an _opposite Hessenberg Schubert variety_. In the
same paper, they showed that the support of the class $\sigma_{w,h}$ is the
set $\Omega_{w,h}^{T}$ of torus fixed points of the Hessenberg Schubert
variety and provided an explicit combinatorial description of the torus fixed
points. In the Hessenberg variety $\operatorname{Hess}(S,h)$, the permutations
are partitioned according to the Hessenberg function $h$, and there is a set
of natural representatives of the partition, called the _generators_ for the
Hessenberg function $h$; see Section 3 of [6]. Notably, Hessenberg Schubert
varieties corresponding to the permutations in the same part resemble each
other. For example, all of them have the same number of $T$-fixed points,
where the action of the torus $T$ on a Hessenberg Schubert variety is induced
from that of $T$ on the flag variety [15].

In this paper, we aim to extend the results (in Theorem 1.1) regarding the
characterization of the smoothness of Schubert varieties $\Omega_{w}$ to
Hessenberg Schubert varieties $\Omega_{w,h}$. The Hessenberg variety
$\operatorname{Hess}(S,h)$ is known to be a GKM variety and its GKM graph
(denoted by $\Gamma_{h}$) is a subgraph of the GKM graph of the full flag
variety, with the same set $\mathfrak{S}_{n}$ of vertices [9]. This defines a
partial order on $\mathfrak{S}_{n}$, which we call the _$h$ -Bruhat order_. We
first interpret the set $\Omega_{w,h}^{T}$, which has been shown in [15] as
the interval $[w,w_{0}]$ in the Bruhat order for a generator $w$, in terms of
the $h$-Bruhat order. We use $[n]$ for the set $\\{1,2,\dots,n\\}$.

######  Theorem A (Theorem 3.4).

Let $w\in\mathfrak{S}_{n}$ be a generator for a given Hessenberg function
$h\colon[n]\to[n]$. Then, $\Omega_{w,h}^{T}=[w,w_{0}]_{h}$, the interval
between $w$ and $w_{0}$ in the $h$-Bruhat order.

Let $\Gamma_{w,h}$ be the subgraph of $\Gamma_{h}$ induced by the set
$\Omega_{w,h}^{T}$ of torus fixed points. In the following theorem, we show
that for a generator $w$, the degree of the vertices in $\Gamma_{w,h}$ is
nondecreasing with respect to the $h$-Bruhat order. This theorem is essential
for characterizing of the smoothness of $\Omega_{w,h}$. For two permutations
$u$ and $v$, we use $u\preceq_{h}v$ to denote the $h$-Bruhat order relation.

######  Theorem B (Theorem 3.8).

For a Hessenberg function $h$ and a generator $w\in\mathfrak{S}_{n}$, if $u$
and $v$ are vertices in $\Gamma_{w,h}$ with $u\preceq_{h}v$, then
$\deg(u)\leq\deg(v)$.

We then consider the regularity of $\Gamma_{w,h}$ in the relation with
patterns in the permutation $w$, where the patterns depend upon the given
Hessenberg functions $h$. We found all the patterns that $w$ must avoid for
$\Gamma_{w,h}$ to be regular as stated in the following theorem. The patterns
are defined in Definitions 3.9 and 4.9 for the definition of the patterns.

######  Theorem C (Theorems 3.11, 4.8 and 4.14).

Let $h\colon[n]\to[n]$ be a Hessenberg function.

  1. (1)

If $w\in\mathfrak{S}_{n}$ is a generator for $h$, then the graph
$\Gamma_{w,h}$ is regular if and only if $w$ avoids all the associated
patterns $\overline{2143}$, $\overline{1324}$, $\overline{1243}$,
$\overline{2134}$, $\overline{1423}$, $\overline{2314}$, and
$\overline{2413}$.

  2. (2)

Let $w\in\mathfrak{S}_{n}$ be a permutation. Then the graph $\Gamma_{w,h}$ is
regular if and only if $w$ avoids all the associated patterns
$\overline{2143}$, $\overline{1324}$, $\overline{1243}$, $\overline{2134}$,
$\overline{1423}$, $\overline{2314}$, $\overline{25314}$, $\overline{24315}$,
$\overline{14325}$, and $\overline{15324}$.

Because the smoothness of $\Omega_{w,h}$ implies the regularity of the
subgraph $\Gamma_{w,h}$, as stated in Proposition 2.6, our result provides a
necessary condition for the smoothness of $\Omega_{w,h}$ in terms of pattern
avoidance.

######  Theorem D (Theorems 3.12 and 4.15).

Let $h\colon[n]\to[n]$ be a Hessenberg function.

  1. (1)

If $w\in\mathfrak{S}_{n}$, a generator for $h$, contains one of the seven
patterns in $\\{\overline{2143}$, $\overline{1324}$, $\overline{1243}$,
$\overline{2134}$, $\overline{1423}$, $\overline{2314}$, $\overline{2413}\\}$,
then $\Omega_{w,h}$ is not smooth.

  2. (2)

If a permutation $w\in\mathfrak{S}_{n}$ contains one of the ten patterns in
$\\{\overline{2143}$, $\overline{1324}$, $\overline{1243}$, $\overline{2134}$,
$\overline{1423}$, $\overline{2314}$, $\overline{25314}$, $\overline{24315}$,
$\overline{14325}$, $\overline{15324}\\}$, then $\Omega_{w,h}$ is not smooth.

We believe that the pattern avoidance condition we found is also an equivalent
condition for the smoothness of $\Omega_{w,h}$ (see Conjecture 4.16).

This paper is organized as follows. In Section 2, first, we set up notation
and terminology, and then review some basic theories on Schubert varieties and
Hessenberg Schubert varieties. In Section 3, we focus on the GKM graph
$\Gamma_{h}$ of a Hessenberg variety and its subgraph $\Gamma_{w,h}$. The set
of vertices of $\Gamma_{w,h}$ is characterized in terms of the $h$-Bruhat
order, and a nice injective map from the set of edges of a vertex to the set
of edges of an incident vertex is introduced. Further, seven patterns that
generator permutations must avoid are presented such that the corresponding
Hessenberg Schubert variety is smooth. In Section 4, we attempt to prove that
avoiding the seven patterns of length $4$ for generators and ten patterns of
length $4$ or $5$ for an arbitrary permutation is enough to guarantee that the
corresponding graph $\Gamma_{w,h}$ is regular.

##  2\. Preliminaries

###  2.1. Basic terminologies and properties.

Let $\mathfrak{S}_{n}$ be a symmetric group on $[n]$. For a permutation
$w\in\mathfrak{S}_{n}$, we use the one-line notation $w=w(1)w(2)\cdots w(n).$
For $1\leq i<j\leq n$, the permutation that acts on $[n]$ by swapping $i$ and
$j$ is called a _transposition_ , and it is denoted by $(i,j)$. The _Bruhat
order_ on $\mathfrak{S}_{n}$ is the transitive closure of the relation

$u\prec v\quad\text{ if and only if }\quad v=u(i,j)\text{ for some $(i,j)$ and
}\ell(u)<\ell(v)\,.$

The _length_ of $w$ is defined by the number of inversions and denoted by
$\ell(w)$, i.e., $\ell(w)=\left|\\{(i,j)\mid w(i,j)\prec w\\}\right|$. Then
the poset $(\mathfrak{S}_{n},\prec)$ is a graded poset whose rank function is
given by the length of a permutation. Notably, $(\mathfrak{S}_{n},\prec)$ has
the unique minimal element $e=1\,2\,\cdots\,n$ and the unique maximal element
$w_{0}=n\,(n-1)\,\cdots\,1.$ The _Bruhat interval_ $[v,w]$ is the subposet of
$(\mathfrak{S}_{n},\prec)$ defined by $[v,w]=\\{u\in\mathfrak{S}_{n}\mid
v\preceq u\preceq w\\}$. The _Bruhat graph_ for $\mathfrak{S}_{n}$ is the
graph with the vertex set $\mathfrak{S}_{n}$ and edges $\\{v,w\\}$ if
$w=u(i,j)$ for some $(i,j)$.

For $w\in\mathfrak{S}_{n}$ and $p\in\mathfrak{S}_{k}$ with $k\leq n$, we say
that the permutation $w$ _contains_ the pattern $p$ if a sequence $1\leq
i_{1}<\cdots<i_{k}\leq n$ exists such that $w(i_{1})\cdots w(i_{k})$ has the
same relative order with $p(1)\cdots p(k)$. If $w$ does not contain $p$, then
we say that $w$ _avoids_ $p$ or is _$p$ -avoiding_.

For positive integers $k_{1}\leq k_{2}$, we denote the set
$\\{k_{1},k_{1}+1,\dots,k_{2}\\}$ by $[k_{1},k_{2}]$. For a permutation
$w\in\mathfrak{S}_{n}$, we let $w[k_{1},k_{2}]$ be the set $\\{w(i)\mid
k_{1}\leq i\leq k_{2}\\}$. We use $A\\!\\!\uparrow$ to represent the
increasing arrangement $\\{a_{1}<a_{2}<\cdots<a_{k}\\}$ of the elements in
$A$, where $A$ is a set of $k$ integers. For two finite sets $A$ and $B$ of
integers of the same cardinality, $A\\!\\!\uparrow\leq B\\!\\!\uparrow$ means
$a_{i}\leq b_{i}$ for all $i$, where $a_{i}$ and $b_{i}$ are the $i$th
elements of $A\\!\\!\uparrow$ and $B\\!\\!\uparrow$, respectively.

There are many equivalent conditions to $u\prec v$ in the Bruhat order; we
give some of them that we use in this paper. We refer to the book [3] for more
general theories on (Bruhat orders of) Coxeter groups.

######  Proposition 2.1.

For $u,v\in\mathfrak{S}_{n}$, the following statements are equivalent:

  1. (1)

$u\preceq v$ in the Bruhat order.

  2. (2)

$u[k]\\!\\!\uparrow\leq v[k]\\!\\!\uparrow$ for all $k\in[n]$.

  3. (3)

$u[k]\\!\\!\uparrow\leq v[k]\\!\\!\uparrow$ for all $k\in[n-1]-D(v)$, where
$D(v)\coloneqq\\{i\in[n-1]\mid v(i)>v(i+1)\\}$ is the set of _descents_ of
$v$.

######  Lemma 2.2.

[2, Lemma 2.1] Suppose two permutations $u$ and $v$ agree everywhere except on
positions $i_{1}<\cdots<i_{k}$. Then $u\preceq v$ in the Bruhat order if and
only if
$\\{u(i_{1}),\dots,u(i_{j})\\}\\!\\!\uparrow\leq\\{v(i_{1}),\dots,v(i_{j})\\}\\!\\!\uparrow$
for all $j=1,\dots,k$. In particular, $u\prec u(i,j)$ if and only if
$u(i)<u(j)$.

The Bruhat order on $\mathfrak{S}_{n}$ satisfies the chain property as
follows.

######  Proposition 2.3 (Chain Property).

If $u\prec v$ in $\mathfrak{S}_{n}$, then there exist elements
$v_{i}\in\mathfrak{S}_{n}$, satisfying $\ell(v_{i})=\ell(u)+i$ for $0\leq
i\leq k$, and $u=v_{0}\prec v_{1}\prec\cdots\prec v_{k}=v$.

###  2.2. Flag varieties, Schubert varieties, and Opposite Schubert varieties.

The flag variety $\mathcal{F}\ell(\mathbb{C}^{n})$ is the homogeneous space
$\operatorname{GL}_{n}(\mathbb{C})/B$, where $B$ is the Borel subgroup of
upper triangular matrices in $\operatorname{GL}_{n}(\mathbb{C})$. Then
$\mathcal{F}\ell(\mathbb{C}^{n})$ is a smooth projective variety of (complex)
dimension $\binom{n}{2}$, and it can be identified with the set

$\mathcal{F}\ell(\mathbb{C}^{n})=\\{(\\{0\\}\subset V_{1}\subset
V_{2}\subset\cdots\subset
V_{n}=\mathbb{C}^{n})\mid\dim_{\mathbb{C}}V_{i}=i\text{ for }i=1,\dots,n\\}$

of chains of subspaces of $\mathbb{C}^{n}$. Each element of
$\mathcal{F}\ell(\mathbb{C}^{n})$ is called a flag. For instance, an element
$w\in\mathfrak{S}_{n}$ defines a flag given by

$(\\{0\\}\subset\langle\mathbf{e}_{w(1)}\rangle\subset\langle\mathbf{e}_{w(1)},\mathbf{e}_{w(2)}\rangle\subset\cdots\subset
V_{n}=\mathbb{C}^{n}),$

where $\mathbf{e}_{1},\dots,\mathbf{e}_{n}$ are the standard basis vectors in
$\mathbb{C}^{n}$. We denote by $wB$ this standard coordinate flag.

Let $G=\operatorname{GL}_{n}(\mathbb{C})$ and $B^{-}$ be the Borel subgroup of
lower triangular matrices in $G$. Then, the left action of $B$ (respectively,
$B^{-}$) on $G/B$ has finitely many orbits $BwB/B$ (respectively,
$B^{-}wB/B$), where $w$ is a permutation in $\mathfrak{S}_{n}$, and we get a
cell decomposition called the _Bruhat decomposition_ :

(2.1)
$G/B=\bigsqcup_{w\in\mathfrak{S}_{n}}BwB/B\,=\bigsqcup_{w\in\mathfrak{S}_{n}}B^{-}wB/B\,.$

For each $w\in\mathfrak{S}_{n}$, the cells $BwB/B$ and $B^{-}wB/B$ are
isomorphic to $\mathbb{C}^{\ell(w)}$ and $\mathbb{C}^{\binom{n}{2}-\ell(w)}$,
respectively. We call $X_{w}^{\circ}\coloneqq BwB/B$ the _Schubert cell_ and
$\Omega_{w}^{\circ}\coloneqq B^{-}wB/B$ the _opposite Schubert cell_ indexed
by $w$. The (Zariski) closures $X_{w}\coloneqq\overline{X_{w}^{\circ}}$ and
$\Omega_{w}\coloneqq\overline{\Omega_{w}^{\circ}}$ are called the _Schubert
variety_ and the _opposite Schubert variety_ indexed by $w$, respectively.
Notably, $\Omega_{w}=w_{0}X_{w_{0}w}$ because $B^{-}=w_{0}Bw_{0}$, and we only
consider opposite Schubert varieties throughout the paper.

For $v,w\in\mathfrak{S}_{n}$, we have

$v\prec w\quad\text{ if and only if }\quad\Omega_{w}\subset\Omega_{v},$

and we obtain the cell decomposition of $\Omega_{w}$ as follows:

(2.2) $\Omega_{w}=\bigsqcup_{v\succeq w}\Omega_{v}^{\circ}\,.$

An opposite Schubert variety is not necessarily smooth. It is known from [17]
that $\Omega_{w}$ is smooth if and only if $w$ avoids patterns $2143$ and
$1324$.

We refer a reader to [10] and references therein for the geometry and
combinatorics related to flag varieties and their subvarieties.

###  2.3. Torus actions and GKM varieties.

Let $X$ be a complex projective variety with an action of algebraic torus
$T\cong(\mathbb{C}^{\ast})^{n}$. Then, the variety $X$ is called a _GKM
(Goresky–Kottwitz–MacPherson) variety_ if it satisfies the following three
conditions:

  * •

The fixed point set $X^{T}$ consists of isolated points.

  * •

There are finitely many one-dimensional orbits of $T$ on $X$.

  * •

The space $X$ is equivariantly formal with respect to the action of $T$.

Note that the equivariantly formal condition is quite technical, but (2.1) and
(2.2) imply that $\mathcal{F}\ell(\mathbb{C}^{n})$ and $\Omega_{w}$ are
equivariantly formal with respect to every torus action. We refer a reader to
[12, 14, 11] for the GKM theory.

For a GKM variety $X$, the boundary of each one-dimensional $T$-orbit contains
two $T$-fixed points and the closure of each one-dimensional orbit is
isomorphic to $\mathbb{C}P^{1}$ with fixed points at the north and south
poles. Based on the zero- and one-dimensional orbits of a GKM variety, we
construct the GKM graph $\Gamma$ as follows:

  1. (1)

the vertex set of $\Gamma$ is identified with the set $X^{T}$ of $T$-fixed
points; and

  2. (2)

two vertices $p$ and $q$ of $X^{T}$ are connected by an edge if there exists a
one-dimensional orbit whose closure has $p$ and $q$ as the $T$-fixed points.

Let $E_{\Gamma}$ be the set of directed edges of $\Gamma$.111Note that
$E_{\Gamma}$ is not the set of edges of $\Gamma$; the cardinality of
$E_{\Gamma}$ is twice that of the edge set. The _axial function_ of a GKM
graph $\Gamma$ is a map $\alpha\colon E_{\Gamma}\to\mathfrak{t}^{\ast}$ given
by $\alpha(e)$ is the $T$-weight on the corresponding one-dimensional orbit,
where $\mathfrak{t}^{\ast}$ is the dual of the Lie algebra $\mathfrak{t}$ of
$T$. When $X$ is a smooth manifold of (complex) dimension $d$, the GKM graph
of $X$ is a $d$-valent graph and the tangent space $T_{p}X$ for $p\in X^{T}$
is isomorphic to
$\mathbb{C}(\alpha(e_{1}))\oplus\cdots\oplus\mathbb{C}(\alpha(e_{d}))$ as a
$T$-representation, where $e_{1},\dots,e_{d}$ are the edges emanating from $p$
in $E_{\Gamma}$.

Now, we let $T$ be the set of diagonal matrices in $G$. Then $T$ is isomorphic
to $(\mathbb{C}^{\ast})^{n}$ and acts on $G/B$ by left multiplication, and the
set of $T$-fixed points of $G/B$ consists of the standard coordinate flags.
Thus, we identify $(G/B)^{T}$ with $\mathfrak{S}_{n}$. Furthermore, the flag
variety $\mathcal{F}\ell(\mathbb{C}^{n})$ with the action of $T$ becomes a GKM
variety, and the GKM graph $\Gamma$ of $\mathcal{F}\ell(\mathbb{C}^{n})$ is
the Bruhat graph for $\mathfrak{S}_{n}$.

For every $w\in\mathfrak{S}_{n}$, the opposite Schubert variety $\Omega_{w}$
is a GKM subvariety of $\mathcal{F}\ell(\mathbb{C}^{n})$. The set of $T$-fixed
points of $\Omega_{w}$ is identified with the Bruhat interval $[w,w_{0}]$ and
the GKM graph of $\Omega_{w}$ is the subgraph of $\Gamma$ induced by
$[w,w_{0}]$.

###  2.4. Hessenberg-Schubert varieties.

A _Hessenberg function_ is a nondecreasing function $h\colon[n]\to[n]$
satisfying $h(i)\geq i$ for each $i\in[n]$. Let $S$ be a regular semisimple
linear operator on $\mathbb{C}^{n}$. That is, a Jordan form of $S$ is a
diagonal matrix with $n$ distinct eigenvalues. A regular semisimple
_Hessenberg variety_ determined by $h$ and $S$ is defined as

$\operatorname{Hess}(S,h)\coloneqq\\{(\\{0\\}\subset V_{1}\subset\cdots\subset
V_{n})\in\mathcal{F}\ell(\mathbb{C}^{n})\,\,|\,\,S(V_{i})\subseteq
V_{h(i)}\mbox{ for }i=1,\dots,n\\}\,.$

Then, $\operatorname{Hess}(S,h)$ is a smooth projective variety of (complex)
dimension $d_{h}\coloneqq\sum_{i}(h(i)-i)$ [9].

We often use the list of values $(h(1),h(2),\dots,h(n))$ of $h$ to represent a
Hessenberg function $h\colon[n]\to[n]$. Moreover, we can depict a Hessenberg
function using a graph. For each Hessenberg function $h$, the graph with the
vertex set $[n]$ and the edge set $\\{\\{i,j\\}\mid 1\leq i<j\leq h(i)\\}$ is
called the _incomparability graph_ of $h$. For instance, when
$h=(n,n,\dots,n)$, the complete graph $K_{n}$ is the incomparability graph of
$h$.

Using (2.1), we obtain an affine paving of $\operatorname{Hess}(S,h)$

$\operatorname{Hess}(S,h)=\bigsqcup_{w\in\mathfrak{S}_{n}}\left(\Omega^{\circ}_{w}\cap\operatorname{Hess}(S,h)\right),$

so $\operatorname{Hess}(S,h)$ is also equivariantly formal with respect to
every torus action [8, 16]. For each $w\in\mathfrak{S}_{n}$, the intersection
$\Omega_{w,h}^{\circ}\coloneqq\Omega^{\circ}_{w}\cap\operatorname{Hess}(S,h)$
is isomorphic to $\mathbb{C}^{d_{h}-\ell_{h}(w)}$, and it is called the
_(opposite) Hessenberg Schubert cell_ indexed by $w$, where

$\ell_{h}(w)=\left|\\{i<j\mid w(i)>w(j),\,\,j\leq h(i)\\}\right|\,.$

######  Proposition 2.4 ([18]).

A regular semisimple Hessenberg variety $\operatorname{Hess}(S,h)$ is a
$T$-invariant subvariety of $\mathcal{F}\ell(\mathbb{C}^{n})$, and it is a GKM
variety with the associated GKM graph $\Gamma_{h}=(V,E)$, where
$V=\mathfrak{S}_{n}$ and $E=\\{\\{u,v\\}\mid v=u(i,j)\mbox{ for }1\leq i<j\leq
h(i)\\}$.

######  Remark 2.5.

  1. (1)

For a Hessenberg function $h$, if $S$ and $S^{\prime}$ are regular semisimple
linear operators on $\mathbb{C}^{n}$, then their associated Hessenberg
varieties are diffeomorphic:

$\operatorname{Hess}(S,h)\approx\operatorname{Hess}(S^{\prime},h)\,.$

  2. (2)

When $h=(n,n,\dots,n)$, $\operatorname{Hess}(S,h)$ is the full flag variety
$\mathcal{F}\ell(\mathbb{C}^{n})$.

The closure $\Omega_{w,h}\coloneqq\overline{\Omega_{w,h}^{\circ}}$ is called
the _(opposite) Hessenberg Schubert variety_ indexed by $w$, and it is shown
in [15] that $\Omega_{w,h}$ is an irreducible component of

$\Omega_{w}\cap\operatorname{Hess}(S,h)=\bigsqcup_{v\succeq
w}\Omega_{v,h}^{\circ}\,.$

Since $\Omega_{w}$ and $\operatorname{Hess}(S,h)$ are $T$-invariant
subvarieties of $\mathcal{F}\ell(\mathbb{C}^{n})$ and $\Omega_{w,h}$ is
irreducible, $\Omega_{w,h}$ is also $T$-invariant. However, we cannot conclude
that $\Omega_{w,h}$ is a GKM variety because the equivariant formality of
$\Omega_{w,h}$ is unknown for the action of $T$. Fortunately, we can acquire
some geometric information of $\Omega_{w,h}$ from the fact that $\Omega_{w,h}$
is an irreducible $T$-invariant subvariety of
$\mathcal{F}\ell(\mathbb{C}^{n})$. Let $\Gamma_{w,h}$ be the subgraph of
$\Gamma_{h}$ induced by $\Omega_{w,h}^{T}$.

######  Proposition 2.6 ([5], Lemma 2.4).

For $w\in\mathfrak{S}_{n}$ and $v\in\Omega_{w,h}^{T}$,

$\dim T_{v}(\Omega_{w,h})\geq\deg(v)\geq\dim\Omega_{w,h}=d_{h}-\ell_{h}(w),$

where $T_{v}(\Omega_{w,h})$ is the Zariski tangent space of $\Omega_{w,h}$ at
$v\in\Omega_{w,h}^{T}$. When $\Omega_{w,h}$ is smooth, all the inequalities in
the above are equal.

For a given Hessenberg function $h\colon[n]\to[n]$, the set of _generators_ is
defined by

$\\{w\in\mathfrak{S}_{n}\mid w^{-1}(w(i)+1)\leq h(i)\text{ for all }w(i)\leq
n-1\\}\,.$

When $h=(3,3,4,4)$, $2134$ is a generator but $w=1324$ is not because
$h(2)=3<w^{-1}(4)=4$. In [6], it is shown that the Białynicki–Birula basis
elements corresponding to the set of generators satisfying $\ell_{h}(w)=k$
form a module generator set of the $\mathfrak{S}_{n}$-module
$H^{2k}(\operatorname{Hess}(S,h);\mathbb{C})$.

For a permutation $w$, there is a unique generator $\widetilde{w}$ satisfying
that

(2.3) $\widetilde{w}(i)<\widetilde{w}(j)\quad\text{ if and only if }\quad
w(i)<w(j)\,\quad\text{ for all }i<j\text{ with }j\leq h(i)\,.$

See Proposition 3.8 in [6]. We call $\widetilde{w}$ the _corresponding
generator of $w$_. Then $\Omega_{w,h}^{T}$ is characterized as follows.

######  Proposition 2.7 ([7], [15]).

Let $h$ be a Hessenberg function on $[n]$. For a permutation
$w\in\mathfrak{S}_{n}$, the following statements hold.

  1. (1)

If w is a generator, then $\Omega_{w,h}^{T}$ is identified with the Bruhat
interval $[w,w_{0}]$.

  2. (2)

If $w$ is not a generator, then $\Omega_{w,h}^{T}$ is identified with the set
$w\widetilde{w}^{-1}[\widetilde{w},w_{0}]$.

In particular, $\Omega_{w,h}^{T}$ and $\Omega_{\widetilde{w},h}^{T}$ have the
same cardinality.

It should be noted that if $w$ is not a generator, then $\Omega_{w,h}^{T}$ may
not form an interval. For example, when $h=(3,3,4,4)$, $w=1324$ is not a
generator and the corresponding generator of $w$ is $\widetilde{w}=1423$. In
this case, $w_{0}\in\Omega_{w,h}^{T}$, but the permutation
$1432\not\in\Omega_{w,h}^{T}$ even though $w\prec 1432\prec w_{0}$.
Nevertheless, we can show that $\Omega_{w,h}^{T}$ and
$\Omega_{\widetilde{w},h}^{T}$ induce the isomorphic subgraphs of
$\Gamma_{h}$.

######  Proposition 2.8.

For $w\in\mathfrak{S}_{n}$, $\Gamma_{w,h}$ is isomorphic to
$\Gamma_{\widetilde{w},h}$.

###### Proof.

For each $w\in\mathfrak{S}_{n}$, by definition of $\Gamma_{w,h}$, there is an
edge $\\{u,v\\}\in E(\Gamma_{w,h})$ if and only if there exists a
transposition $(i,j)$ such that $u(i,j)=v$ and $1\leq i<j\leq h(i)$. If $w$ is
not a generator, then $\Omega_{w,h}^{T}=\\{w\widetilde{w}^{-1}u\mid
u\in[\widetilde{w},w_{0}]\\}$ by Proposition 2.7. Therefore, for
$u^{\prime}=w\widetilde{w}^{-1}u$ and $v^{\prime}=w\widetilde{w}^{-1}v$ in
$\Omega_{w,h}^{T}$, $\\{u^{\prime},v^{\prime}\\}$ is an edge of $\Gamma_{w,h}$
if and only if $\\{u,v\\}$ is an edge of $\Gamma_{\widetilde{w},h}$. ∎

##  3\. Properties of $h$-Bruhat order and induced subgraphs of GKM graphs

In this section, we first introduce the notion of the $h$-Bruhat order and
investigate the properties of the order in relation to the Bruhat order.
Subsequently, in the second subsection, we proceed to look at the subgraphs
$\Gamma_{w,h}$ inside $\Gamma_{h}$; we define a nice injective map from the
set of incident edges of $u$ to that of $v$ when $v$ is greater than $u$ in
the $h$-Bruhat order. Finally, we use the injection to introduce seven special
patterns that a generator $w$ for $h$ has to avoid for $\Gamma_{w,h}$ to be
regular.

###  3.1. The $h$-Bruhat order

Proposition 2.7 characterizes the $T$-fixed points of Hessenberg Schubert
varieties for a generator $w\in\mathfrak{S}_{n}$ in relation to the Bruhat
order; $\Omega_{w,h}^{T}=[w,w_{0}]$. It is natural to ask if
$\Omega_{w,h}^{T}$ can be characterized in terms of an order on
$\mathfrak{S}_{n}$, which respects the Hessenberg function $h$ in some way.
Indeed, we can think of a natural order that respects $h$:

######  Definition 3.1.

Let $h\colon[n]\to[n]$ be a Hessenberg function.

  1. (1)

The _$h$ -Bruhat order_ on $\mathfrak{S}_{n}$ is the transitive closure of the
following relation

$u\prec_{h}v\quad\text{ if and only if }\quad v=u(i,j)\text{ for some $(i,j)$
such that $j\leq h(i)$ and }\ell(v)>\ell(u)\,.$

  2. (2)

For permutations $u\prec_{h}v$, let $[u,v]_{h}$ denote the _$h$ -Bruhat
interval_ $\\{w\mid u\preceq_{h}w\preceq_{h}v\\}$.

It is clear that $v\prec_{h}w$ implies $v\prec w$; however, the converse does
not hold true in general. For instance, when $h=(4,4,4,5,5)$, $54132\prec
54231$, but $54132\not\prec_{h}54231$. The unique maximum permutation $w_{0}$
in the Bruhat order is not necessarily the maximum in the $h$-Bruhat order: if
$h=(2,3,3,5,5)$, then $54231\not\prec_{h}54321=w_{0}$. However, we obtain the
following lemma when $w$ is a generator.

######  Lemma 3.2.

For a Hessenberg function $h$, if $w$ is a generator and $w\preceq_{h}u$, then
$u\preceq_{h}w_{0}$.

###### Proof.

Let $h$ be a Hessenberg function on $[n]$. If $h(i)>i$ for all $i<n$ then we
can successively apply the adjacent transpositions to $u$ on the right to make
a chain
$u\prec_{h}u_{1}\prec_{h}u_{2}\prec_{h}\cdots\prec_{h}u_{k}\prec_{h}w_{0}$;
first move $1$ to the $n$th position, then move $2$ to the $(n-1)$st position,
and so on until we obtain $w_{0}$.

If $h(i)=i$ for some $i<n$, let $i_{1}<i_{2}<\cdots<i_{k}=n$ be the such
numbers; $h(i_{j})=i_{j}$ for $j=1,\dots,k$, and $i_{0}\coloneqq 0$. Then,
since $w$ is a generator and $w\preceq_{h}u$, for $j=1,2,\dots,k$

$u[i_{j-1}+1,i_{j}]=w[i_{j-1}+1,i_{j}]=[n-i_{j}+1,n-i_{j-1}]\,.$

Each $u[i_{j-1}+1,i_{j}]$ can be arranged in increasing order by applying a
sequence of adjacent transpositions $(a,a+1)$, $a=i_{j-1}+1,\dots,i_{j}-1$, to
$w$. This shows that there is a chain
$u\prec_{h}u_{1}\prec_{h}u_{2}\prec_{h}\cdots\prec_{h}u_{k}\prec_{h}w_{0}$. ∎

There is a nice result on the $T$-fixed set of $\Omega_{w,h}$ in relation to
the $h$-Bruhat order.

######  Proposition 3.3.

[7, Proposition 2.11] Let $h$ be a Hessenberg function and $w$ be a
permutation. If $v\in\Omega_{w,h}^{T}$, then $w\preceq_{h}v$. In particular,
when $w$ is a generator if $w\preceq v$, then $w\preceq_{h}v$.

Now, we can characterize the $T$-fixed points of the Hessenberg Schubert
variety in terms of the $h$-Bruhat order. Proposition 3.3 together with Lemma
3.2 prove the following theorem.

######  Theorem 3.4.

Let $w$ be a generator for a Hessenberg function $h$. Then, as sets

$[w,w_{0}]_{h}=[w,w_{0}]\,.$

Finally, we show that the chain property of the Bruhat order extends to the
$h$-Bruhat order.

######  Theorem 3.5 (Chain Property of the $h$-Bruhat order).

Let $h$ be a Hessenberg function on $[n]$. If $u\prec_{h}v$ in
$\mathfrak{S}_{n}$, then there exist $v_{i}\in\mathfrak{S}_{n}$ satisfying
$\ell(v_{i})=\ell(u)+i$ for $0\leq i\leq k$, and
$u=v_{0}\prec_{h}v_{1}\prec_{h}\cdots\prec_{h}v_{k}=v$.

###### Proof.

We show the theorem when $v=u(a,b)$. That is, we show that ‘if
$u\prec_{h}u(a,b)$ then there is a chain
$u=v_{0}\prec_{h}v_{1}\prec_{h}\cdots\prec_{h}v_{k}\coloneqq u(a,b)$ with
$\ell(v_{i})=\ell(u)+i$ for $i=1,\dots,k$.’ This will prove the theorem by the
definition of the $h$-Bruhat order.

Suppose that $u\prec_{h}u(a,b)$. Then $b\leq h(a)$, and by Proposition 2.3
there is a chain $u=v_{0}\prec v_{1}\prec\cdots\prec v_{k}=u(a,b)$ with
$\ell(v_{i})=\ell(u)+i$ for $0\leq i\leq k$. The main observation is that, if
we only look at the subword $u(a)u(a+1)\cdots u(b)$ of $u$ and
$u(b)u(a+1)\cdots u(a)$ of $u(a,b)$, then they are permutations of
$\\{u(a),u(a+1)\cdots,u(b)\\}$. Thus, we can locally apply the chain property
to obtain a chain from $u(a)u(a+1)\cdots u(b)$ to $u(b)u(a+1)\cdots u(a)$,
which means that we can assume that $v_{i+1}=v_{i}(a_{i},b_{i})$ for $a\leq
a_{i}<b_{i}\leq b$. This implies that $b_{i}\leq h(a_{i})$ and
$v_{i}\prec_{h}v_{i+1}$, which completes the proof. ∎

###  3.2. An injection for the induced subgraphs of GKM graphs

Recall that for a generator $w$ for a Hessenberg function $h$, $\Gamma_{w,h}$
is the induced subgraph of $\Gamma_{h}$ whose vertex set is
$[w,w_{0}]=[w,w_{0}]_{h}$. Note that $\\{u,v\\}$ is an edge of $\Gamma_{w,h}$
if and only if $w\preceq u,v$ and $u=v(i,j)$ for some $(i,j)$ with $j\leq
h(i)$. For each vertex $u$ in $\Gamma_{w,h}$, we denote by

$E_{w,h}(u)\coloneqq\\{(i,j)\mid u(i,j)\succeq w\text{~{}for~{}}1\leq i<j\leq
h(i)\\}$

the set of transpositions $(i,j)$ satisfying that $\\{u,u(i,j)\\}$ is an edge
of $\Gamma_{w,h}$. Thus, it is evident that

$E_{w,h}(w)=\\{(i,j)\mid w(i)<w(j)\text{~{}for~{}}1\leq i<j\leq h(i)\\}\,.$

For vertices $u$ and $v$ in $\Gamma_{w,h}$ satisfying that $v=u(a,b)$ for some
$(a,b)\in E_{w,h}(u)$ and $u\prec_{h}v$, we define a map $\phi_{uv}\colon
E_{w,h}(u)\to E_{w,h}(v)$ by $(i,j)\mapsto(\overline{i},\overline{j})$, where

$(\overline{i},\overline{j})\coloneqq\begin{cases}(b,j)&\mbox{if $i=a$, $j>b$,
and $(b,j)\not\in E_{w,h}(u)$},\\\ (i,a)&\mbox{if $i<a$, $j=b$, and
$(i,a)\not\in E_{w,h}(u)$},\\\ (i,j)&\mbox{otherwise}.\end{cases}$

######  Lemma 3.6.

Let $w$ be a generator for a Hessenberg function $h$. If $u$ and $v$ are
vertices in $\Gamma_{w,h}$ satisfying that $v=u(a,b)$ for some $(a,b)\in
E_{w,h}(u)$ and $u\prec_{h}v$, then the map $\phi_{uv}\colon E_{w,h}(u)\to
E_{w,h}(v)$ is well-defined and injective.

###### Proof.

From the definition of $\phi_{uv}$, it is enough to show that the map
$\phi_{uv}$ is well-defined. Note that from the assumption, we have $a<b\leq
h(a)$, $u(a)<u(b)$, and $v(a,b)=u\succeq w$. We show that $\phi_{uv}$ is well-
defined by showing $\overline{i}<\overline{j}\leq h(\overline{i})$ and
$v(\overline{i},\overline{j})\succeq w$. Let $(i,j)\in E_{w,h}(u)$. If
$(i,j)=(a,b)$, then $\phi_{uv}(a,b)=(a,b)$. If
$\\{i,j\\}\cap\\{a,b\\}=\emptyset$, then $(\overline{i},\overline{j})=(i,j)$
so that we have $\overline{i}<\overline{j}\leq h(\overline{i})$ and

$v(\overline{i},\overline{j})=v(i,j)=u(a,b)(i,j)=u(i,j)(a,b)\succ
u(i,j)\succeq w\,.$

Hence, if $|\\{i,j\\}\cap\\{a,b\\}|\neq 1$, then $\phi_{uv}$ is well-defined.
For the remaining $(i,j)$, we split them into four cases as follows.

Case i) Let $i=a$ and $j<b$. Since $\phi_{uv}(a,j)=(a,j)$, we only need to
show that $v(a,j)\succeq w$. In this case, since
$(u(a,j))(j)=u(a)<u(b)=(u(a,j))(b)$, by Lemma 2.2

$v(a,j)=u(a,j)(j,b)\succ u(a,j)\succeq w\,.$

Case ii) Let $i>a$ and $j=b$. Similarly to the above case, since
$\phi_{uv}(i,b)=(i,b)$, let us show $v(i,b)\succeq w$. Since
$(u(i,b))(a)=u(a)<u(b)=(u(i,b))(i)$, we have

$v(i,b)=u(i,b)(a,i)\succ u(i,b)\succeq w\,.$

Case iii) Let $i<a$ and $j\in\\{a,b\\}$. If $(i,a)\in E_{w,h}(u)$, then
$\phi_{uv}(i,a)=(i,a)$. Since $(u(i,a))(i)=u(a)<u(b)=(u(i,a))(b)$, we have

$v(i,a)=u(a,b)(i,a)=u(i,a)(i,b)\succ u(i,a)\succeq w\,.$

In addition, if $(i,b)\in E_{w,h}(u)$, then $\phi_{uv}(i,b)=(i,b)$. Since
$u(i,a),u(i,b)\succeq w$, and

$(v(i,b))[k]=\begin{cases}(u(i,a))[k]&\mbox{if $k<a$},\\\
(u(i,b))[k]&\mbox{otherwise},\end{cases}$

for all $k$, we have $v(i,b)\succeq w$ by Proposition 2.1 (2).

On the other hand, if $(i,a)\not\in E_{w,h}(u)$ and $(i,b)\in E_{w,h}(u)$,
then $\phi_{uv}(i,b)=(i,a)$. Here, $i<a<b\leq h(i)$. In this case, we need to
show that $v(i,a)\succeq w$. If $u(i)<u(b)$, then $v(i,a)\succ v\succeq w$.
Otherwise, we have $u(a)<u(b)<u(i)$, so it follows that

$v(i,a)=u(i,b)(a,b)\succ u(i,b)\succeq w$

since $(u(i,b))(a)=u(a)<u(i)=(u(i,b))(b)$.

Case iv) Let $i\in\\{a,b\\}$ and $j>b$. Similarly to Case iii), if $(b,j)\in
E_{w,h}(u)$, then $\phi_{uv}(b,j)=(b,j)$. Since
$(u(b,j))(a)=u(a)<u(b)=(u(b,j))(j)$, we have

$v(b,j)=u(a,b)(b,j)=u(b,j)(a,j)\succ u(b,j)\succeq w\,.$

In addition, if $(a,j)\in E_{w,h}(u)$, then $\phi_{uv}(a,j)=(a,j)$ and
$v(a,j)\succeq w$ as $u(a,j),u(b,j)\succeq w$ and for all $k$

$(v(a,j))[k]=\begin{cases}(u(a,j))[k]&\mbox{if $k<b$, }\\\
(u(b,j))[k]&\mbox{otherwise}.\end{cases}$

On the other hand, if $(b,j)\not\in E_{w,h}(u)$ and $(a,j)\in E_{w,h}(u)$,
then $\phi_{uv}(a,j)=(b,j)$. Here, $a<b<j\leq h(a)\leq h(b)$. In this case, we
need to show that $v(b,j)\succeq w$. If $u(a)<u(j)$, then $v(b,j)\succ
v\succeq w$. Otherwise, we have $u(j)<u(a)<u(b)$, so it follows that

$v(b,j)=u(a,j)(a,b)\succ u(a,j)\succeq w$

since $(u(a,j))(a)=u(j)<u(b)=(u(a,j))(b)$.

Thus, we conclude that $\phi_{uv}$ is well-defined. ∎

######  Example 3.7.

Consider a generator $w=2134$ for the Hessenberg function $h=(3,3,4,4)$. The
graph $\Gamma_{w,h}$ is depicted in Figure 1.

  1. (1)

If $u=2314$ and $v=u(3,4)=2341$, then we have
$E_{w,h}(u)=\\{(1,2),(2,3),(3,4)\\}$ and
$E_{w,h}(v)=\\{(1,2),(1,3),(2,3),(3,4)\\}$. The map $\phi_{uv}\colon
E_{w,h}(u)\to E_{w,h}(v)$ is an injection defined by $\phi_{uv}(i,j)=(i,j)$
for all $(i,j)\in E_{w,h}(u)$.

  2. (2)

If $u=3124$ and $v=u(2,3)=3214$, then we have
$E_{w,h}(u)=\\{(1,3),(2,3),(3,4)\\}$ and $E_{w,h}(v)=\\{(1,2),(2,3),(3,4)\\}$.
The map $\phi_{uv}$ sends $(1,3)$ to $(1,2)$ and fixes the others.

The following theorem is immediate from the previous lemma due to Theorem 3.5
and Lemma 3.2.

######  Theorem 3.8.

For a Hessenberg function $h$ and its generator $w$, if $u$ and $v$ are
vertices in $\Gamma_{w,h}$ with $u\preceq_{h}v$, then
$|E_{w,h}(u)|\leq|E_{w,h}(v)|$. Furthermore,
$|E_{w,h}(w)|\leq|E_{w,h}(w_{0})|.$

As an example, Figure 1 shows that the strict inequality holds in the previous
theorem. Here, $|E_{w,h}(u)|=3$ and $|E_{w,h}(v)|=4$ for red vertices $u$ and
black vertices $v$, respectively.

123412431324213414231342214331242314143241232413314223413214413242133412243132414312423134214321
Figure 1. The induced subgraph $\Gamma_{w,h}$ of $\Gamma_{h}$ for a Hessenberg
function $h=(3,3,4,4)$ and a generator $w=2134$.

###  3.3. Associated patterns for irregularity

Recall that for a Hessenberg function $h=(n,n,\dots,n)$, the induced subgraph
$\Gamma_{w,h}$ is irregular if and only if $w\in\mathfrak{S}_{n}$ contains
pattern $2143$ or pattern $1324$. We provide seven patterns associated with a
Hessenberg function $h$ for irregularity of $\Gamma_{w,h}$ when $w$ is a
generator. Using the injection $\phi_{uv}$ that we defined in the previous
section, we show that $\Gamma_{w,h}$ is not regular when a generator $w$
contains one of the seven patterns.

######  Definition 3.9.

Let $h$ be a Hessenberg function on $[n]$. For a permutation
$w\in\mathfrak{S}_{n}$, we say that $w$ contains the associated pattern

  1. (1)

$\overline{2143}$ if $w(j)<w(i)<w(\ell)<w(k)$ for some $i<j<k<\ell\leq h(i)$;

  2. (2)

$\overline{1324}$ if $w(i)<w(k)<w(j)<w(\ell)$ for some $i<j<k<\ell\leq h(j)$
with $k\leq h(i)$;

  3. (3)

$\overline{1243}$ if $w(i)<w(j)<w(\ell)<w(k)$ for some $i<j<k<\ell\leq h(j)$
with $j\leq h(i)<\ell$;

  4. (4)

$\overline{2134}$ if $w(j)<w(i)<w(k)<w(\ell)$ for some $i<j<k<\ell\leq h(k)$
with $k\leq h(i)<\ell$;

  5. (5)

$\overline{1423}$ if $w(i)<w(k)<w(\ell)<w(j)$ for some $i<j<k<\ell\leq h(j)$
with $k\leq h(i)<\ell$;

  6. (6)

$\overline{2314}$ if $w(k)<w(i)<w(j)<w(\ell)$ for some $i<j<k<\ell\leq h(j)$
with $k\leq h(i)<\ell$;

  7. (7)

$\overline{2413}$ if $w(k)<w(i)<w(\ell)<w(j)$ for some $i<j\leq h(i)<k\leq
h(j)<\ell\leq h(k)$.

Figure 2 presents the appropriate induced subgraphs of the incomparability
graphs of Hessenberg functions for the associated patterns.

$\overline{2143}$$i$$j$$k$$\ell$$\overline{1324}$$i$$j$$k$$\ell$$i$$j$$k$$\ell$$\overline{1243}$$i$$j$$k$$\ell$$i$$j$$k$$\ell$$\overline{2134}$$i$$j$$k$$\ell$$i$$j$$k$$\ell$$\overline{1423},~{}\overline{2314}$$i$$j$$k$$\ell$$\overline{2413}$$i$$j$$k$$\ell$
Figure 2. Seven associated patterns and induced subgraphs on
$\\{i,j,k,\ell\\}$.

######  Remark 3.10.

When $h=(2,3,\dots,n,n)$, the corresponding Hessenberg variety is the
permutohedral variety, which is a smooth projective toric variety. From the
definition, every permutation avoids the patterns (1) to (6). Furthermore,
every generator of the permutohedral variety avoids the associated pattern
$\overline{2413}$, see [7, Lemma 5.21]. It should be noted that $\Gamma_{w,h}$
is regular, and $\Omega_{w,h}$ is smooth for every $w\in\mathfrak{S}_{n}$
because $\Gamma_{w,h}$ forms a face containing $w$ and $w_{0}$ in the
permutohedron if $w$ is a generator.

######  Theorem 3.11.

For a Hessenberg function $h$, let $w$ be a generator. If $w$ contains one of
associated patterns in the set
$\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314},\overline{2413}\\}$,
then the graph $\Gamma_{w,h}$ is irregular.

###### Proof.

By Lemma 3.6, the map $\phi_{uv}\colon E_{w,h}(u)\to E_{w,h}(v)$ is injective
for every edge $\\{u,v\\}\in\Gamma_{w,h}$ with $u\prec v$. For a permutation
$w$ containing an associated pattern in Definition 3.9, to show that
$\Gamma_{w,h}$ is irregular, we find an appropriate edge $\\{u,v\\}$ of
$\Gamma_{w,h}$ with $u\prec v$ such that $\phi_{uv}$ is not surjective.

Case $\overline{2143}$. Suppose that $w(j)<w(i)<w(\ell)<w(k)$ for some
$i<j<k<\ell\leq h(i)$. Set $u\coloneqq w(i,k)(j,k)$ and $v\coloneqq
u(k,\ell)$. Note that $(i,k)\in E_{w,h}(v)$ since $k\leq h(i)$ and

$v(i,k)=w(j,\ell)(i,j)\succ w(j,\ell)\succ w\,.$

In this case, if $\phi_{uv}(\tau)=(i,k)$, then $\tau\in\\{(i,k),(i,\ell)\\}$.
However, $u(i,k)=w(i,j)\prec w$ and $u(i,\ell)\not\succeq w$ since

$(u(i,\ell))[k]\\!\\!\uparrow=\\{w(1),w(2),\dots,w(k-1),w(\ell)\\}\\!\\!\uparrow<w[k]\\!\\!\uparrow.$

Therefore $(i,k),(i,\ell)\not\in E_{w,h}(u)$ and $\phi_{uv}$ is not
surjective.

Case $\overline{1324}$. Suppose that $w(i)<w(k)<w(j)<w(\ell)$ for some
$i<j<k<\ell\leq h(j)$ with $k\leq h(i)$. Set $u\coloneqq w(k,\ell)$ and
$v\coloneqq u(i,k)$. Note that $(j,\ell)\in E_{w,h}(v)$ since $\ell\leq h(j)$
and

$v(j,\ell)=w(i,k)(j,\ell)(i,j)\succ w(i,k)(j,\ell)\succ w(i,k)\succ w\,.$

By the definition of $\phi_{uv}$, if $\phi_{uv}(\tau)=(j,\ell)$, then $\tau$
must be $(j,\ell)$. However,

$(u(j,\ell))[j]\\!\\!\uparrow=\\{w(1),w(2),\dots,w(j-1),w(k)\\}\\!\\!\uparrow<w[j]\\!\\!\uparrow,$

and this yields that $u(j,\ell)\not\succeq w$. Hence $(j,\ell)\not\in
E_{w,h}(u)$ and $\phi_{uv}$ is not surjective.

Case $\overline{1243}$. Suppose that $w(i)<w(j)<w(\ell)<w(k)$ for some
$i<j<k<\ell\leq h(j)$ with $j\leq h(i)<\ell$. Set $u\coloneqq w(j,k)$ and
$v\coloneqq u(i,j)$. Note that $(j,\ell)\in E_{w,h}(v)$ since $\ell\leq h(j)$
and $v(j,\ell)\succ v\succeq w$. In this case, if $\phi_{uv}(\tau)=(j,\ell)$,
then $\tau$ must be $(j,\ell)$ since $h(i)<\ell$. However,
$u(j,\ell)\not\succeq w$ since

$(u(j,\ell))[k]\\!\\!\uparrow=\\{w(1),w(2),\dots,w(k-1),w(\ell)\\}\\!\\!\uparrow<w[k]\\!\\!\uparrow.$

So $(j,\ell)\not\in E_{w,h}(u)$ and $\phi_{uv}$ is not surjective.

Case $\overline{2134}$. Suppose that $w(j)<w(i)<w(k)<w(\ell)$ for some
$i<j<k<\ell\leq h(k)$ with $k\leq h(i)<\ell$. Set $u\coloneqq w(j,k)$ and
$v\coloneqq u(k,\ell)$. Note that $(i,k)\in E_{w,h}(v)$ since $k\leq h(i)$ and
$v(i,k)\succ v\succeq w$. Similarly to the above case, if
$\phi_{uv}(\tau)=(i,k)$, then $\tau$ must be $(i,k)$ since $h(i)<\ell$.
However, $u(i,k)\not\succeq w$ since

$(u(i,k))[i]\\!\\!\uparrow=\\{w(1),w(2),\dots,w(i-1),w(j)\\}\\!\\!\uparrow<w[i]\\!\\!\uparrow.$

Thus $(i,k)\not\in E_{w,h}(u)$ and $\phi_{uv}$ is not surjective.

Case $\overline{1423}$. Suppose that $w(i)<w(k)<w(\ell)<w(j)$ for some
$i<j<k<\ell\leq h(j)$ with $k\leq h(i)<\ell$. Set $u\coloneqq w(i,k)$ and
$v\coloneqq u(i,j)$. Note that $(j,\ell)\in E_{w,h}(v)$ since $\ell\leq h(j)$
and $v(j,\ell)\succ v\succeq w$. Similarly to the above case, if
$\phi_{uv}(\tau)=(j,\ell)$, then $\tau$ must be $(j,\ell)$ since $h(i)<\ell$.
However, $u(j,\ell)\not\succeq w$ since

$(u(j,\ell))[k]\\!\\!\uparrow=((w[k]-\\{w(j)\\})\cup\\{w(\ell)\\})\\!\\!\uparrow<w[k]\\!\\!\uparrow.$

Thus $(j,\ell)\not\in E_{w,h}(u)$ and $\phi_{uv}$ is not surjective.

Case $\overline{2314}$. Suppose that $w(k)<w(i)<w(j)<w(\ell)$ for some
$i<j<k<\ell\leq h(j)$ with $k\leq h(i)<\ell$. Set $u\coloneqq w(j,\ell)$ and
$v\coloneqq u(k,\ell)$. Note that $(i,k)\in E_{w,h}(v)$ since $k\leq h(i)$ and
$v(i,k)\succ v\succeq w$. Again, if $\phi_{uv}(\tau)=(i,k)$, then $\tau$ must
be $(i,k)$ since $h(i)<\ell$. However, $u(i,k)\not\succeq w$ since

$(u(i,k))[i]\\!\\!\uparrow=\\{w(1),w(2),\dots,w(i-1),w(k)\\}\\!\\!\uparrow<w[i]\\!\\!\uparrow.$

Thus $(i,k)\not\in E_{w,h}(u)$ and $\phi_{uv}$ is not surjective.

Case $\overline{2413}$. Suppose that $w(k)<w(i)<w(\ell)<w(j)$ for some
$i<j\leq h(i)<k\leq h(j)<\ell\leq h(k)$. Set $u\coloneqq w(i,j)$ and
$v\coloneqq u(k,\ell)$. Note that $(j,k)\in E_{w,h}(v)$ since $k\leq h(j)$ and
$v(j,k)\succ v\succeq w$. Again, if $\phi_{uv}(\tau)=(j,k)$, then $\tau$ must
be $(j,k)$ since $h(j)<\ell$. However, $u(j,k)\not\succeq w$ since

$(u(j,k))[j]\\!\\!\uparrow=((w[j]-\\{w(i)\\})\cup\\{w(k)\\})\\!\\!\uparrow<w[j]\\!\\!\uparrow.$

Thus $(j,k)\not\in E_{w,h}(u)$ and $\phi_{uv}$ is not surjective. This
completes the proof.

∎

As a consequence of Theorem 3.11, we can provide a necessary condition for
$\Omega_{w,h}$ to be smooth when $w$ is a generator.

######  Theorem 3.12.

For a Hessenberg function $h$, if $w$ is a generator containing one of the
associated patterns in the set
$\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314},\overline{2413}\\}$,
then the Hessenberg Schubert variety $\Omega_{w,h}$ is not smooth.

###### Proof.

If $w$ is a generator containing one of the associated patterns in the set
above, then $\Gamma_{w,h}$ is an irregular graph, so
$\deg(w_{0})=|E_{w,h}(w_{0})|>|E_{w,h}(w)|=\dim\Omega_{w,h}$ due to Theorem
3.8. Therefore, $\Omega_{w,h}$ is not smooth by Proposition 2.6. ∎

##  4\. Regular subgraphs of GKM graphs

In this section, we aim to characterize the regularity of $\Gamma_{w,h}$ in
terms of pattern avoidance. First, we focus on the generators for the given
Hessenberg function $h$ and extend our work described in Theorem 3.11 by
considering the converse of the theorem. The generators for $h$ avoiding the
seven patterns are shown to have nice properties that ensure the regularity of
$\Gamma_{w,h}$. Subsequently, we assess more patterns to deal with an
arbitrary permutation. The fact that a unique generator $\widetilde{w}$ exists
for each $w$, where $\Gamma_{w,h}$ and $\Gamma_{\widetilde{w},h}$ are
isomorphic graphs, plays an essential role.

###  4.1. Subgraphs of GKM graphs for well-organized generators

Here, we define the notion of well-organized permutation and study the
properties of well-organized generators.

For a permutation $w\in\mathfrak{S}_{n}$, we denote

$Y(w)\coloneqq\\{w(i)\mid i\geq w^{-1}(1)\mbox{~{}and~{}}w(i)\leq w(n)\\}\,.$

We always denote $Y(w)=\\{y_{0},y_{1},\dots,y_{r}\\}$ with
$1=y_{0}<y_{1}<\cdots<y_{r}=w(n)$. Furthermore, we say that $w$ is a _well-
organized_ if it satisfies that
$w^{-1}(y_{0})<w^{-1}(y_{1})<\cdots<w^{-1}(y_{r})=n$. The following lemma
shows a property of a generator.

######  Lemma 4.1.

For a Hessenberg function $h$, if $w$ is a generator with
$Y(w)=\\{y_{0},y_{1},\dots,y_{r}\\}$, then $w^{-1}(y_{i})\leq
h(w^{-1}(y_{i-1}))$ for $1\leq i\leq r$.

###### Proof.

Recall that $w^{-1}(a+1)\leq h(w^{-1}(a))$ for $1\leq a\leq n-1$ since $w$ is
a generator. If $y_{i}=y_{i-1}+1$, then $w^{-1}(y_{i})=w^{-1}(y_{i-1}+1)\leq
h(w^{-1}(y_{i-1}))$. On the other hand, if $y_{i}>y_{i-1}+1$, then
$y_{i}-1\not\in Y(w)$ and $w^{-1}(y_{i}-1)<w^{-1}(1)\leq w^{-1}(y_{i-1})$ so
that

$w^{-1}(y_{i})\leq h(w^{-1}(y_{i}-1))\leq h(w^{-1}(1))\leq
h(w^{-1}(y_{i-1}))\,.$

This proves the lemma. ∎

For a well-organized permutation $w$, we let
$\overline{w}_{m}\coloneqq(1,y_{m})\overline{w}_{m-1}$ for $m=1,2,\dots,r$,
where $\overline{w}_{0}\coloneqq w$. Note that
$\overline{w}_{m}=\overline{w}_{m-1}(w^{-1}(y_{m-1}),w^{-1}(y_{m}))$ and
$\overline{w}_{0}\prec\overline{w}_{1}\prec\cdots\prec\overline{w}_{r}$. For
example, $w=213654$ is well-organized permutation with $Y(w)=\\{1,3,4\\}$.
Here,

$\overline{w}_{0}=213654\prec\overline{w}_{1}=231654\prec\overline{w}_{2}=234651\,.$

The following proposition shows several properties of $\overline{w}_{r}$ for a
well-organized generator $w$ with $Y(w)=\\{y_{0},y_{1},\dots,y_{r}\\}$. For
the sake of simplicity, let $\overline{w}\coloneqq\overline{w}_{r}$.

######  Proposition 4.2.

For a Hessenberg function $h$ on $[n]$, if $w$ is a well-organized generator
with $Y(w)=\\{y_{0},y_{1},\dots,y_{r}\\}$, then the following hold.

  1. (1)

$\overline{w}$ is a generator.

  2. (2)

$[\overline{w},w_{0}]=\\{u\in[w,w_{0}]\mid u(n)=1\\}$.

  3. (3)

$\\{(i,n)\in E_{w,h}(\overline{w})\\}=\\{(w^{-1}(y_{s}),n)\mid
h(w^{-1}(y_{s}))=n\text{~{}for~{}}0\leq s<r\\}$.

###### Proof.

Note that $\overline{w}^{-1}(a)=w^{-1}(a)$ for all $a\not\in Y(w)$.

  1. (1)

Since $w$ is a generator, for $1\leq a\leq n-1$, if $a,a+1\not\in Y(w)$, then

$\overline{w}^{-1}(a+1)=w^{-1}(a+1)\leq
h(w^{-1}(a))=h(\overline{w}^{-1}(a))\,.$

Hence, it suffices to show that $\overline{w}^{-1}(a+1)\leq
h(\overline{w}^{-1}(a))$ for $1\leq a\leq n-1$ such that $a\in Y(w)$ or
$a+1\in Y(w)$. First, consider the case $a\not\in Y(w)$ and $a+1\in Y(w)$. Let
$y_{s}-1\not\in Y(w)$ for some $1\leq s\leq r$. Since $w$ is a well-organized
generator, we have

$\overline{w}^{-1}(y_{s})=w^{-1}(y_{s-1})<w^{-1}(y_{s})\leq
h(w^{-1}(y_{s}-1))=h(\overline{w}^{-1}(y_{s}-1))\,.$

Now consider the case $a=y_{s}$ for $0\leq s\leq r$. If $r=0$, then
$\overline{w}^{-1}(2)\leq h(\overline{w}^{-1}(1))=n$. If $s=r$, then by Lemma
4.1 we have

$\overline{w}^{-1}(y_{r}+1)<n=w^{-1}(y_{r})\leq
h(w^{-1}(y_{r-1}))=h(\overline{w}^{-1}(y_{r}))\,.$

For $0<s<r$, if $y_{s}+1\in Y(w)$, then $y_{s}+1=y_{s+1}$ so that
$\overline{w}^{-1}(y_{s}+1)=w^{-1}(y_{s})$. From Lemma 4.1 it follows that

$\overline{w}^{-1}(y_{s}+1)=w^{-1}(y_{s})\leq
h(w^{-1}(y_{s-1}))=h(\overline{w}^{-1}(y_{s}))\,.$

On the other hand, if $y_{s}+1\not\in Y(w)$, then we have

$\overline{w}^{-1}(y_{s}+1)=w^{-1}(y_{s}+1)<w^{-1}(1)<w^{-1}(y_{s})\leq
h(w^{-1}(y_{s-1}))=h(\overline{w}^{-1}(y_{s}))\,.$

  2. (2)

Since $[\overline{w},w_{0}]\subseteq\\{u\in[w,w_{0}]\mid u(n)=1\\}$, it
suffices to show that $\overline{w}\preceq u$ for each $u\in\mathfrak{S}_{n}$
with $w\preceq u$ and $u(n)=1$. Suppose that
$u[k]\\!\\!\uparrow<\overline{w}[k]\\!\\!\uparrow$ for some $k$. Since
$w[m]=\overline{w}[m]$ for $m<w^{-1}(1)$ or $m=n$, it follows that
$w^{-1}(1)\leq k<n$ and $\overline{w}[k]=(w[k]-\\{1\\})\cup\\{y_{s}\\}$ for
some $s>0$. More precisely, since $w$ is well-organized, if we denote
$w[k]\\!\\!\uparrow$, $u[k]\\!\\!\uparrow$, and
$\overline{w}[k]\\!\\!\uparrow$ by ordered sets
$\\{a_{1},a_{2},\dots,a_{k}\\}$, $\\{b_{1},b_{2},\dots,b_{k}\\}$, and
$\\{c_{1},c_{2},\dots,c_{k}\\}$, respectively, then $a_{i}=i$ and $c_{i}=i+1$
for $1\leq i<y_{s}$, and $a_{i}=c_{i}$ for $y_{s}\leq i\leq k$. Note that
$w\preceq u$ implies that $a_{i}\leq b_{i}$ for $1\leq i\leq k$. Hence, if
$a_{i}\leq b_{i}<c_{i}$ for some $i$, then $i<y_{s}$ so that $i\leq
c_{i}<i+1$, or equivalently, $\\{c_{1},c_{2},\dots,c_{i}\\}=[i]$. This
contradicts that $u(n)=1$ and $k<n$. Therefore, there is no such $k$.

  3. (3)

We first check the inclusion ($\subseteq$). Let $(i,n)\in
E_{w,h}(\overline{w})$. Then $h(i)=n$ and $\overline{w}(i)<y_{r}$ since
$\overline{w}(i,n)\succeq w$ and
$(\overline{w}(i,n))[n-1]=(w[n-1]-\\{\overline{w}(i)\\})\cup\\{y_{r}\\}$. Note
that $i<w^{-1}(1)$ yields that $(\overline{w}(i,n))[i]=w[i-1]\cup\\{1\\}$ and
$\overline{w}(i,n)\not\succeq w$. Hence, $i\geq w^{-1}(1)$ so that
$\overline{w}(i)=y_{s+1}$, or equivalently $w(i)=y_{s}$, for some $0\leq s<r$.
Therefore $(i,n)=(w^{-1}(y_{s}),n)$ and $h(w^{-1}(y_{s}))=n$.

Now we check the inclusion ($\supseteq$). Assume that $w(i)=y_{s}$ and
$h(i)=n$ for some $i<n$. By Lemma 2.2 $\overline{w}(i,n)\succeq w$ because
$\overline{w}(i,n)$ and $w$ agree everywhere except on positions
$w^{-1}(y_{0}),w^{-1}(y_{1}),\dots,w^{-1}(y_{r})$, and on these positions
$\overline{w}(i,n)$ and $w$ have the subsequences $y_{1}\dots
y_{s}y_{0}y_{s+2}\dots y_{r}y_{s+1}$ and $y_{0}\dots y_{s-1}y_{s}y_{s+1}\dots
y_{r-1}y_{r}$, respectively. Therefore $(w^{-1}(y_{s}),n)\in
E_{w,h}(\overline{w})$.

∎

For a well-organized permutation $w$, if $w$ satisfies that $y_{i}=i+1$
(respectively, $w(n-i)=y_{r-i}$) for $0\leq i\leq r$, then it is called a
_well-organized permutation of the first_ (respectively, _second_) _kind_. For
example, permutations $461523$ and $426135$ are of the first and second types,
respectively, and $213654$ is a permutation neither of the first type nor of
the second type. In the following, we show that the map
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}$ is a bijection if $w$ is a well-
organized generator that satisfies a certain condition.

######  Proposition 4.3.

For a Hessenberg function $h$ on $[n]$, let $w$ be a well-organized generator
with $Y(w)=\\{y_{0},y_{1},\dots,y_{r}\\}$ for some $r\geq 1$. For $1\leq m\leq
r$, let $\overline{w}_{m}=\overline{w}_{m-1}(a,b)$. If $h(p)\geq b$ for all
$(p,a)\in E_{w,h}(\overline{w}_{m})$ such that $p<w^{-1}(1)$, then

$\phi_{\overline{w}_{m-1}\overline{w}_{m}}\colon
E_{w,h}(\overline{w}_{m-1})\to E_{w,h}(\overline{w}_{m})$

is a bijection and $\phi_{\overline{w}_{m-1}\overline{w}_{m}}(i,j)=(i,j)$
except $\phi_{\overline{w}_{m-1}\overline{w}_{m}}(p,b)=(p,a)$ for
$p<w^{-1}(1)$.

In particular, if $w$ is a well-organized generator of the first kind, then
$E_{w,h}(\overline{w}_{m-1})=E_{w,h}(\overline{w}_{m})$ and
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}$ is an identity map.

###### Proof.

By Lemma 3.6, it suffices to check the surjectivity of
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}$. Let

$A\coloneqq E_{w,h}(\overline{w}_{m})-\\{(p,a)\mid p<w^{-1}(1)\\}\,.$

We show that $\phi_{\overline{w}_{m-1}\overline{w}_{m}}(i,j)=(i,j)$ for
$(i,j)\in A$ and then find the preimage of $(p,a)$ under
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}$ for each $(p,a)\in
E_{w,h}(\overline{w}_{m})$ with $p<w^{-1}(1)$. Note that since
$\overline{w}_{m}=(1,y_{m})\overline{w}_{m-1}=\overline{w}_{m-1}(a,b)$, we get
$\overline{w}_{m-1}(a)=1$ and $\overline{w}_{m-1}(b)=y_{m}$.

We first show that $A\subseteq E_{w,h}(\overline{w}_{m-1})$. Let $(i,j)\in A$.
It suffices to show that $\overline{w}_{m-1}(i,j)\succeq w$. Note that if
$\overline{w}_{m-1}(i)<\overline{w}_{m-1}(j)$, then
$\overline{w}_{m-1}(i,j)\succ\overline{w}_{m-1}\succeq w$. Now we assume that
$\overline{w}_{m-1}(i)>\overline{w}_{m-1}(j)$. Then $i\neq a$ and $i\neq b$
since $\overline{w}_{m-1}(a)=1$ and
$\overline{w}_{m-1}(b)=y_{m}=\min\overline{w}_{m-1}[a+1,n]$, respectively.
Note that if $i<b$ and $j>a$, then

$(\overline{w}_{m}(i,j))[k]=(w[k]-\\{1,\overline{w}_{m}(i)\\})\cup\\{y_{m},w(j)\\}$

for $\max\\{a,i\\}\leq k<\min\\{b,j\\}$. It follows from
$\overline{w}_{m}(i,j)\succeq w$ that $\overline{w}_{m}(i)<w(j)$. However,
this contradicts $w(i)>w(j)$ since $w(i)\leq\overline{w}_{m}(i)$. Hence it
remains the case when $i>b$ or $j\leq a$. For the remaining $(i,j)$, we split
them into two cases as follows.

  * •

Let $i>b$ or $j<a$. Then $\overline{w}_{m-1}(i,j)\succeq w$ since

$(\overline{w}_{m-1}(i,j))[k]=\begin{cases}w[k]&\mbox{if $a\leq k<b$},\\\
(\overline{w}_{m}(i,j))[k]&\mbox{otherwise}.\end{cases}$

  * •

Let $j=a$ and $i\geq w^{-1}(1)$. If $w(i)>y_{m}$, then

$(\overline{w}_{m}(i,a))[i]=(w[i-1]-\\{1\\})\cup\\{y,y_{m}\\}$

for some $y<y_{m}$, which contradicts $\overline{w}_{m}(i,a)\succeq w$.
Therefore, $w(i)<y_{m}$ so that $w(i)=y_{s}$ for some $s<m-1$. By Lemma 2.2
$\overline{w}_{m-1}(i,a)\succeq w$ since $\overline{w}_{m-1}(i,a)$ and $w$
agree everywhere except on positions
$w^{-1}(y_{0}),w^{-1}(y_{1}),\dots,w^{-1}(y_{m-1})$, and on these positions
$\overline{w}_{m-1}(i,a)$ and $w$ have the subsequences $y_{1}\dots
y_{s}y_{0}y_{s+2}\dots y_{m-1}y_{s+1}$ and $y_{0}\dots
y_{s-1}y_{s}y_{s+1}\dots y_{m-2}y_{m-1}$, respectively.

Therefore, $A\subseteq E_{w,h}(\overline{w}_{m-1})$.

Now consider the sets $P\coloneqq\\{(p,j)\mid p<a,~{}j\in\\{a,b\\}\\}$ and
$Q\coloneqq\\{(i,q)\mid i\in\\{a,b\\},~{}q>b\\}$.

  * •

Suppose that $(i,j)\in A-(P\cup Q)$. It follows from the definition of the map
that $\phi_{\overline{w}_{m-1}\overline{w}_{m}}$ fixes all $(i,j)$.

  * •

Suppose that $(i,q)\in Q$. Note that $\overline{w}_{m}(i,q)\succeq w$ since
$\overline{w}_{m}(a)=y_{m}<\overline{w}_{m}(q)$ and $\overline{w}_{m}(b)=1$.
This yields that if $h(a)\geq q$, then $(a,q),(b,q)\in A$; if $h(b)\leq
q<h(a)$, then $(a,q)\not\in A$, $(b,q)\in A$, and $(a,q)\not\in
E_{w,h}(\overline{w}_{m-1})$. In any case, we have
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}(i,q)=(i,q)$ for $(i,q)\in A\cap Q$.

  * •

Suppose that $(p,j)\in P$. Note that if $p<w^{-1}(1)$, then
$\overline{w}_{m}(p,b)\not\succeq w$ since $(\overline{w}_{m}(p,b))(p)=1$.
Thus if $(p,b)\in A$, then $p\geq w^{-1}(1)$ and $\overline{w}_{m}(p)=y_{s}$
for some $s<m$. This yields that $(p,a),(p,b)\in A$, and
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}(p,j)=(p,j)$ for $(p,j)\in A\cap P$.

This shows that $\phi_{\overline{w}_{m-1}\overline{w}_{m}}(i,j)=(i,j)$ for all
$(i,j)\in A$.

Now we assume that $(p,a)\in E_{w,h}(\overline{w}_{m})$ and $p<w^{-1}(1)$ and
find the preimage of $(p,a)$ under
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}$. By the definition of
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}$, if
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}(\tau)=(p,a)$ for some $\tau$, then
$\tau\in\\{(p,a),(p,b)\\}$. Note that $(p,a)\in E_{w,h}(\overline{w}_{m})$
implies that $w(p)<y_{m}$ and $h(p)\geq b$ from the assumption. Since
$\overline{w}_{m-1}(a)=1$ and $\overline{w}_{m-1}(b)=y_{m}$, we have
$\overline{w}_{m-1}(p,a)\not\succeq w$ and $\overline{w}_{m-1}(p,b)\succeq w$,
respectively. Therefore, $(p,a)\not\in E_{w,h}(\overline{w}_{m-1})$ and
$(p,b)\in E_{w,h}(\overline{w}_{m-1})$, so
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}(p,b)=(p,a)$ when $p<w^{-1}(1)$.
Hence the map $\phi_{\overline{w}_{m-1}\overline{w}_{m}}$ is bijective.

Note that if $w$ is a well-organized generator of the first kind, then
$w(p)>y_{m}$ for all $p<w^{-1}(1)$. Hence, $E_{w,h}(\overline{w}_{m})=A$ and
the map $\phi_{\overline{w}_{m-1}\overline{w}_{m}}$ is an identity map. This
proves the proposition. ∎

###  4.2. Subgraphs of GKM graphs for pattern avoiding generators

In this subsection, we first investigate the relationship between the
properties of well-organized generators in Section 4.1 and the generators
avoiding the associated patterns in Definition 3.9. Subsequently, we show the
regularity of $\Gamma_{w,h}$, for a generator $w$, which can be characterized
in accordance with the pattern avoidance of $w$.

For simplicity, we assume that $Y(w)=\\{y_{0},y_{1},\dots,y_{r}\\}$ in this
subsection unless otherwise stated.

######  Lemma 4.4.

Let $w$ be a generator for a Hessenberg function $h$. If $w$ avoids the
associated pattern $\overline{1324}$, then $w$ is well-organized.

###### Proof.

Suppose that $w$ is not well-organized so that we have
$w^{-1}(y_{i})<w^{-1}(y_{j})<w^{-1}(y_{i+1})$ for some $i$ and $j$ with
$0<i+1<j<r$. Let $k$ be the smallest integer such that $k>j$ and
$w^{-1}(y_{i+1})<w^{-1}(y_{k})$. Note that if $w^{-1}(y_{k-1})<w^{-1}(y_{i})$,
then the subsequence $y_{i}y_{j}y_{i+1}y_{k}$ gives the associated pattern
$\overline{1324}$ since $w^{-1}(y_{k})\leq h(w^{-1}(y_{k-1}))\leq
h(w^{-1}(y_{i}))$ by Lemma 4.1. On the other hand, if
$w^{-1}(y_{i})<w^{-1}(y_{k-1})$, then the subsequence
$y_{i}y_{k-1}y_{i+1}y_{k}$ gives the associated pattern $\overline{1324}$
since $w^{-1}(y_{i+1})\leq h(w^{-1}(y_{i}))$ and $w^{-1}(y_{k})\leq
h(w^{-1}(y_{k-1}))$ by Lemma 4.1. Hence, $w$ always contains the associated
pattern $\overline{1324}$. ∎

Note that for a generator $w$, avoiding the associated pattern
$\overline{1324}$ is not a necessary condition to be well-organized. For
instance, when $h=(7,7,7,7,7,7,7)$, the permutation $4651273$ is well-
organized but contains the pattern $1324$.

If a well-organized generator avoids certain patterns in Definition 3.9, then
it is of the first or second type.

######  Lemma 4.5.

Assume that $w$ is a well-organized generator for a Hessenberg function $h$.

  1. (1)

If $h(w^{-1}(1))<n$ and $w$ avoids the associated pattern $\overline{2134}$,
then $w$ is a well-organized generator of the first kind. In addition, if $w$
also avoids $\overline{1243}$ and $\overline{1423}$, then $w(i)\in Y(w)$ for
all $i$ such that $h(i)=n$ .

  2. (2)

If $h(w^{-1}(1))=n$ and $w$ avoids the associated patterns $\overline{2143}$
and $\overline{2134}$, then $w$ is a well-organized generator of the first or
the second kind.

###### Proof.

  1. (1)

First note that $y_{r}>2$ and $y_{r}-1\in Y(w)$, otherwise we have
$h(w^{-1}(1))=n$. Now suppose that $\\{x+1,x+2,\dots,y_{r}\\}\subset Y(w)$ and
$x\not\in Y(w)$ for some $1<x<y_{r}$. Since $w^{-1}(x+1)\leq h(w^{-1}(x))$ and
$h(w^{-1}(1))<n$, we have $w^{-1}(x+j)\leq h(w^{-1}(x))<w^{-1}(x+j+1)$ for
some $1\leq j<y_{r}-x$. Then the subsequence $x1(x+j)(x+j+1)$ gives the
associated pattern $\overline{2134}$ since $w^{-1}(x+j+1)\leq h(w^{-1}(x+j))$.
Hence, there is no such $x$, and $w$ is a well-organized generator of the
first kind.

For the latter part, suppose that there is $i$ satisfying that $h(i)=n$ and
$w(i)>r+1=w(n)$. Let $x$ be the smallest integer satisfying that $1\leq x<r$
and $h(w^{-1}(x+1))=n$. Note that if $w^{-1}(x+1)<i$, then the subsequence
$x(x+1)w(i)(r+1)$ gives the associated pattern $\overline{1243}$. On the other
hand, if $w^{-1}(x+1)>i$, then the subsequence $x\,w(i)\,(x+1)\,(r+1)$ gives
the associated pattern $\overline{1423}$. Therefore there is no such $i$.

  2. (2)

Suppose that $w$ is not of the first kind so that $y_{s}-1\not\in Y(w)$ for
some $1\leq s\leq r$. Now assume that there is $x$ satisfying that $x>w(n)$
and $w^{-1}(1)<w^{-1}(x)$. If $w^{-1}(x)<w^{-1}(y_{s})$, then the subsequence
$(y_{s}-1)1xy_{s}$ gives the associated pattern $\overline{2143}$ since
$w^{-1}(y_{s})\leq h(w^{-1}(y_{s}-1))$. Hence, $w^{-1}(y_{s})<w^{-1}(x)$. In
this case, if $w^{-1}(x)\leq h(w^{-1}(y_{s}-1))$, then the subsequence
$(y_{s}-1)1xy_{r}$ gives the associated pattern $\overline{2143}$ since
$h(w^{-1}(1))=n$. On the other hand, if $w^{-1}(x)>h(w^{-1}(y_{s}-1))$, then
the subsequence $(y_{s}-1)1y_{s}x$ gives the associated pattern
$\overline{2134}$ since $w^{-1}(y_{s})\leq h(w^{-1}(y_{s}-1))$ and
$h(w^{-1}(1))=n$, but this contradicts the fact that $w$ avoids
$\overline{2143}$ and $\overline{2134}$. Therefore there is no such $x$, and
$w$ is well-organized of the second kind.

This completes the proof. ∎

######  Proposition 4.6.

Let $w$ be a generator for a Hessenberg function $h$. Assume that $w$ avoids
the three associated patterns $\overline{2143}$, $\overline{1324}$, and
$\overline{2134}$. Then the following hold.

  1. (1)

If $w$ also avoids the associated pattern $\overline{2314}$, then
$|E_{w,h}(w)|=|E_{w,h}(\overline{w})|$.

  2. (2)

If $w$ also avoids the two associated patterns $\overline{1243}$ and
$\overline{1423}$, then

$\\{(i,n)\in E_{w,h}(w_{0})\\}=\\{(i,n)\mid n-k+1\leq i<n\\},$

where $k=|\\{y_{i}\mid h(w^{-1}(y_{i}))=n\\}|$.

###### Proof.

From the assumption, $w$ is a well-organized generator of the first or the
second kind by Lemmas 4.4 and 4.5.

  1. (1)

Note that from Proposition 4.3 if $w$ is well-organized of the first kind,
then we have

$E_{w,h}(w)=E_{w,h}(\overline{w}_{0})=E_{w,h}(\overline{w}_{1})=\cdots=E_{w,h}(\overline{w}_{r})=E_{w,h}(\overline{w})\,.$

Hence we only need to consider when $w$ is well-organized of the second kind.
Let $Y(w)\neq[r+1]$. It follows from Lemma 4.5 that $h(w^{-1}(1))=n$. Suppose
that for some $1\leq m\leq r$, the injection
$\phi_{\overline{w}_{m-1}\overline{w}_{m}}\colon
E_{w,h}(\overline{w}_{m-1})\to E_{w,h}(\overline{w}_{m})$ is not surjective.
Let $\overline{w}_{m}=\overline{w}_{m-1}(a,b)$. Then there exists $p$ such
that $p<w^{-1}(1)$, $w(p)<y_{m}$, $(p,a)\in E_{w,h}(\overline{w}_{m})$, and
$a\leq h(p)<b$ by Proposition 4.3. Note that $w(a)=y_{m-1}$ and $w(b)=y_{m}$.
If $w(p)<y_{m-1}$, then the subsequence $w(p)1y_{m-1}y_{m}$ gives the
associated pattern $\overline{2134}$. Hence $y_{m-1}<w(p)<y_{m}$ and
$y_{m-1}\neq y_{m}-1$. Note that $p<w^{-1}(y_{m}-1)<w^{-1}(1)$ since
$h(p)<w^{-1}(y_{m})\leq h(w^{-1}(y_{m}-1))$. Then the subsequence
$w(p)(y_{m}-1)y_{m-1}y_{m}$ gives the associated pattern $\overline{2314}$.
Thus there is no such $p$ for all $m=1,2,\dots,r$ so that

$|E_{w,h}(w)|=|E_{w,h}(\overline{w}_{0})|=|E_{w,h}(\overline{w}_{1})|=\cdots=|E_{w,h}(\overline{w}_{r})|=|E_{w,h}(\overline{w})|\,.$

  2. (2)

Let $|\\{y_{i}\mid h(w^{-1}(y_{i}))=n\\}|=k$ and $|\\{i\mid h(i)=n\\}|=m$.
Then $1\leq k\leq m$. For $n-m+1\leq i<n$, note that
$(w_{0}(i,n))[i]\\!\\!\uparrow\geq w[i]\\!\\!\uparrow$ if and only if
$w^{-1}(1)\leq i$ since

$\displaystyle w[i]$ $\displaystyle=[n]-\\{w(i+1),w(i+2),\dots,w(n)\\},$
$\displaystyle(w_{0}(i,n))[i]$ $\displaystyle=[n]-\\{2,3,\dots,n-i+1\\}\,.$

In addition, $(w_{0}(i,n))[n-1]\\!\\!\uparrow\geq w[n-1]\\!\\!\uparrow$ if and
only if $n-i+1\leq w(n)$. From Proposition 2.1 (3), it follows that
$w_{0}(i,n)\succeq w$ if and only if $(w_{0}(i,n))[i]\\!\\!\uparrow\geq
w[i]\\!\\!\uparrow$ and $(w_{0}(i,n))[n-1]\\!\\!\uparrow\geq
w[n-1]\\!\\!\uparrow$ since $\\{i,n-1\\}=[n-1]-D(w_{0}(i,n))$. Hence

$\\{(i,n)\in
E_{w,h}(w_{0})\\}=\\{(i,n)\mid\max\\{w^{-1}(1),n+1-w(n),n-m+1\\}\leq
i<n\\}\,.$

If $h(w^{-1}(1))<n$, then $w^{-1}(1)<n-m+1$, $w(n)=r+1$, and $m=k\leq r$ by
Lemma 4.5 (1). On the other hand, if $h(w^{-1}(1))=n$, then from Lemma 4.5 (2)
it follows that $k=r+1$, $w^{-1}(1)=n-r=n-k+1$, and $w(n)>r$. In any case, we
have $\max\\{w^{-1}(1),n+1-w(n),n-m+1\\}=n-k+1$, as we desired.

This completes the proof. ∎

######  Proposition 4.7.

Let $w$ be a generator for a Hessenberg function $h$. If $w$ avoids all of the
associated patterns $\overline{2143}$, $\overline{1324}$, $\overline{1243}$,
$\overline{2134}$, $\overline{1423}$, $\overline{2314}$, and
$\overline{2413}$, then so does $\overline{w}$.

###### Proof.

Since $w$ avoids the associated patterns $\overline{2143}$, $\overline{1324}$,
and $\overline{2134}$, $w$ is well-organized of the first or the second kind
by Lemma 4.5. Note that if $w$ is well-organized of the first kind, then
$w(i)<w(j)$ if and only if $\overline{w}(i)<\overline{w}(j)$ for all $1\leq
i<j<n$. Moreover, since $\overline{w}(n)=1$ and none of the seven associated
patterns ends with $1$, $\overline{w}$ avoids all of the associated patterns
if $w$ is well-organized of the first kind.

Now we consider the case when $w$ is well-organized of the second kind. Then
$h(w^{-1}(1))=n$ by Lemma 4.5. In the following, we show that if
$\overline{w}$ contains one of the associated patterns in Definition 3.9, then
so does $w$. Note that $\overline{w}$ and $w$ may contain different associated
patterns. For a given associated pattern, we suppose that $\overline{w}$
contains the subsequence
$\overline{v}\coloneqq\overline{w}(i)\overline{w}(j)\overline{w}(k)\overline{w}(\ell)$
with $1\leq i<j<k<\ell\leq n$ that gives the pattern. Since $w$ is well-
organized of the second kind that avoids all of the patterns, we may assume
that the subsequence $\overline{v}$ can be written as one of the forms
$w(i)y_{q+1}y_{s+1}y_{m+1}$, $w(i)w(j)y_{s+1}y_{m+1}$, and
$w(i)w(j)w(k)y_{m+1}$ for some $0\leq q<s<m<r$.

Case $\overline{2143}$. Suppose that
$\overline{w}(j)<\overline{w}(i)<\overline{w}(\ell)<\overline{w}(k)$ for some
$\ell\leq h(i)$. It suffices to consider the subsequence
$\overline{v}=w(i)w(j)w(k)y_{m+1}$. Then $w^{-1}(y_{m})=\ell\leq h(i)$, and we
may assume that $y_{m}<w(i)$. Note that if $w^{-1}(y_{m+1})\leq h(i)$, then
$w$ contains the subsequence $w(i)w(j)w(k)y_{m+1}$ that gives the associated
pattern $\overline{2143}$. On the other hand, if $w^{-1}(y_{m+1})>h(i)$, then
$w^{-1}(y_{m+1}-1)>i$ and $w(i)(y_{m+1}-1)y_{m}y_{m+1}$ gives the associated
pattern $\overline{2314}$.

Case $\overline{1324}$. Suppose that
$\overline{w}(i)<\overline{w}(k)<\overline{w}(j)<\overline{w}(\ell)$, $k\leq
h(i)$, and $\ell\leq h(j)$. It suffices to consider the subsequence
$\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$ or $\overline{v}=w(i)w(j)w(k)y_{m+1}$.
First, let $\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$. Then $w^{-1}(y_{s})\leq
h(i)$ and $w^{-1}(y_{m})\leq h(j)$, and we may assume that $y_{s}<w(i)$ or
$y_{m}<w(j)$. Note that if $w^{-1}(y_{m+1})\leq h(i)$, then $w$ contains
$w(i)w(j)y_{s+1}y_{m+1}$ that gives the associated pattern $\overline{1324}$.
Now we assume that $w^{-1}(y_{m+1})>h(i)$, and consider three possible cases
according to $y_{s}$ and $y_{m}$.

  * •

Let $y_{s}>w(i)$ and $y_{m}<w(j)$. If $w^{-1}(y_{m+1})\leq h(j)$, then $w$
contains $w(i)w(j)y_{s}y_{m+1}$ that gives the associated pattern
$\overline{1324}$. On the other hand, if $w^{-1}(y_{m+1})>h(j)$, then
$w(j)(y_{m+1}-1)y_{m}y_{m+1}$ gives the associated pattern $\overline{2314}$.

  * •

Let $y_{s}<w(i)$ and $y_{m}>w(j)$. If $w^{-1}(y_{m+1})\leq h(j)$, then
$w(i)w(j)y_{s}y_{m+1}$ gives the associated pattern $\overline{2314}$. On the
other hand, if $w^{-1}(y_{m+1})>h(j)$, then $w(j)y_{s}y_{m}y_{m+1}$ gives the
associated pattern $\overline{2134}$.

  * •

Let $y_{s}<w(i)$ and $y_{m}<w(j)$. If $w^{-1}(y_{m+1})\leq h(j)$, then $w$
contains $w(i)w(j)y_{s}y_{m+1}$ that gives the associated pattern
$\overline{2314}$. On the other hand, if $w^{-1}(y_{m+1})>h(j)$, then
$w(j)(y_{m+1}-1)y_{s}y_{m+1}$ gives the associated pattern $\overline{2314}$.

Now let $\overline{v}=w(i)w(j)w(k)y_{m+1}$. It follows that $w^{-1}(y_{m})\leq
h(j)$, and we may assume that $y_{m}<w(j)$. In this case if
$w^{-1}(y_{m+1})\leq h(j)$, then $w$ contains the subsequence
$w(i)w(j)w(k)y_{m+1}$ that gives the associated pattern $\overline{1324}$. On
the other hand, if $w^{-1}(y_{m+1})>h(j)$, then $w(j)(y_{m+1}-1)y_{m}y_{m+1}$
gives the associated pattern $\overline{2314}$.

Case $\overline{1243}$. Suppose that
$\overline{w}(i)<\overline{w}(j)<\overline{w}(\ell)<\overline{w}(k)$ and
$j\leq h(i)<\ell\leq h(j)$. It suffices to consider the subsequence
$\overline{v}=w(i)w(j)w(k)y_{m+1}$. In this case we have
$h(i)<w^{-1}(y_{m})\leq h(j)$, and we may assume that $y_{m}<w(j)$. Note that
if $w^{-1}(y_{m+1})\leq h(j)$, then the subsequence $w(i)w(j)w(k)y_{m+1}$ of
$w$ gives the associated pattern $\overline{1243}$. On the other hand, if
$w^{-1}(y_{m+1})>h(j)$, then $w(j)(y_{m+1}-1)y_{m}y_{m+1}$ gives the
associated pattern $\overline{2314}$.

Case $\overline{2134}$. Suppose that
$\overline{w}(j)<\overline{w}(i)<\overline{w}(k)<\overline{w}(\ell)$ and
$k\leq h(i)<\ell\leq h(k)$. In this case, we have to consider all of the forms
of $\overline{v}$. If $\overline{v}$ is one of the forms
$w(i)y_{q+1}y_{s+1}y_{m+1}$ and $\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$, then we
have $w^{-1}(y_{s})\leq h(i)<w^{-1}(y_{m})\leq h(w^{-1}(y_{s}))$, and we may
assume that $y_{s}<w(i)$. If $w^{-1}(y_{s+1})\leq h(i)$, then $w$ contains the
subsequence $w(i)y_{s}y_{s+1}y_{m+1}$ that gives the associated pattern
$\overline{2134}$. On the other hand, if $w^{-1}(y_{s+1})>h(i)$, then the
subsequence $w(i)(y_{s+1}-1)y_{s}y_{s+1}$ gives the associated pattern
$\overline{2314}$.

Now let $\overline{v}=w(i)w(j)w(k)y_{m+1}$. Then $h(i)<w^{-1}(y_{m})\leq
h(k)$, and we may assume that $y_{m}<w(k)$. If $w^{-1}(y_{m+1})\leq h(k)$,
then $w$ contains the subsequence $w(i)w(j)w(k)y_{m+1}$ that gives the
associated pattern $\overline{2134}$. On the other hand, if
$w^{-1}(y_{m+1})>h(k)$, then $w(k)(y_{m+1}-1)y_{m}y_{m+1}$ gives the
associated pattern $\overline{2314}$ in $w$.

Case $\overline{1423}$. Suppose that
$\overline{w}(i)<\overline{w}(k)<\overline{w}(\ell)<\overline{w}(j)$ and
$k\leq h(i)<\ell\leq h(j)$. It suffices to consider the subsequence
$\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$ or $\overline{v}=w(i)w(j)w(k)y_{m+1}$.
First, let $\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$. Then it follows that
$w^{-1}(y_{s})\leq h(i)<w^{-1}(y_{m})\leq h(j)$, and we may assume that
$y_{s}<w(i)$. If $w^{-1}(y_{s+1})\leq h(i)$, then $w$ contains the subsequence
$w(i)y_{s}y_{s+1}y_{m+1}$ that gives the associated pattern $\overline{2134}$.
On the other hand, if $w^{-1}(y_{s+1})>h(i)$, then
$w(i)(y_{s+1}-1)y_{s}y_{s+1}$ gives the associated pattern $\overline{2314}$
in $w$.

Now let $\overline{v}=w(i)w(j)w(k)y_{m+1}$. Then it follows that
$h(i)<w^{-1}(y_{m})\leq h(j)$, and we may assume that $y_{m}<w(k)$. If
$w^{-1}(y_{m+1})\leq h(j)$, then $w$ contains the subsequence
$w(i)w(j)w(k)y_{m+1}$ that gives the associated pattern $\overline{1423}$. On
the other hand, if $w^{-1}(y_{m+1})>h(j)$, then $w$ contains the associated
pattern $\overline{2314}$ or $\overline{2413}$. Indeed, if $w^{-1}(1)\leq
h(i)$, then $w(i)(y_{m+1}-1)1y_{m+1}$ gives $\overline{2314}$; if
$w^{-1}(1)>h(i)$, then $w(i)w(j)1y_{m+1}$ gives $\overline{2413}$.

Case $\overline{2314}$. Suppose that
$\overline{w}(k)<\overline{w}(i)<\overline{w}(j)<\overline{w}(\ell)$ and
$k\leq h(i)<\ell\leq h(j)$. Again, it suffices to consider the subsequence
$\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$ or $\overline{v}=w(i)w(j)w(k)y_{m+1}$.
First, let $\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$. Then $w^{-1}(y_{s})\leq
h(i)<w^{-1}(y_{m})\leq h(j)$, and we may assume that $y_{m}<w(j)$.
Accordingly, the subsequence $w(i)(y_{m+1}-1)y_{s}y_{m+1}$ gives the
associated pattern $\overline{2314}$.

Now we let $\overline{v}=w(i)w(j)w(k)y_{m+1}$, so we have
$h(i)<w^{-1}(y_{m})\leq h(j)$. We may assume that $y_{m}<w(j)$. If
$w^{-1}(y_{m+1})\leq h(j)$, then $w$ contains $w(i)w(j)w(k)y_{m+1}$ that gives
the associated pattern $\overline{2314}$. On the other hand, if
$w^{-1}(y_{m+1})>h(j)$, then the subsequence $w(j)(y_{m+1}-1)y_{m}y_{m+1}$
gives the associated pattern $\overline{2314}$.

Case $\overline{2413}$. Suppose that
$\overline{w}(k)<\overline{w}(i)<\overline{w}(\ell)<\overline{w}(j)$ for
$j\leq h(i)<k\leq h(j)<\ell\leq h(k)$. Again, it suffices to consider the
subsequence $\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$ or
$\overline{v}=w(i)w(j)w(k)y_{m+1}$. First, let
$\overline{v}=w(i)w(j)y_{s+1}y_{m+1}$. Then $h(i)<w^{-1}(y_{s})\leq
h(j)<w^{-1}(y_{m})\leq h(w^{-1}(y_{s}))$, and we may assume that $y_{m}<w(i)$.
Accordingly, $w$ contains the subsequence $w(i)w(j)y_{s}y_{m+1}$ that gives
the associated pattern $\overline{2413}$.

Now let $\overline{v}=w(i)w(j)w(k)y_{m+1}$. Then we have
$h(j)<w^{-1}(y_{m})\leq h(k)$, and we may assume that $y_{m}<w(i)$. If
$w^{-1}(y_{m+1})\leq h(k)$, then $w$ contains $w(i)w(j)w(k)y_{m+1}$ that gives
the associated pattern $\overline{2413}$. On the other hand, if
$w^{-1}(y_{m+1})>h(k)$, then $w$ contains $w(k)(y_{m+1}-1)1y_{m+1}$ that gives
the associated pattern $\overline{2314}$.

Thus we conclude that if $\overline{w}$ contains one of the seven associated
patterns, then so does $w$. This completes the proof. ∎

In the following, we show that the converse of Theorem 3.11 is also true.
Therefore, we characterize the regularity of $\Gamma_{w,h}$ in terms of
pattern avoidance when $w$ is a generator.

######  Theorem 4.8.

Let $w$ be a generator for a Hessenberg function $h$. The graph $\Gamma_{w,h}$
is regular if $w$ avoids all of the associated patterns $\overline{2143}$,
$\overline{1324}$, $\overline{1243}$, $\overline{2134}$, $\overline{1423}$,
$\overline{2314}$, and $\overline{2413}$.

###### Proof.

Suppose that $w$ avoids all of the associated patterns. We prove that
$\Gamma_{w,h}$ is regular by induction on $n$. For $n=1$, $\Gamma_{w,h}$ is a
single vertex graph, and this is certainly regular. Suppose that $n\geq 2$ and
$\Gamma_{w^{\prime},h^{\prime}}$ is regular for any Hessenberg function
$h^{\prime}$ on $[n-1]$ and its generator $w^{\prime}$ that avoids all of the
associated patterns. Now we consider a Hessenberg function $h$ on $[n]$ and
its generator $w$ that avoids all of the associated patterns. From Theorem 3.8
it suffices to show that $|E_{w,h}(w)|=|E_{w,h}(w_{0})|$. From Lemma 4.5 and
Proposition 4.6 (1), it follows that $w$ is a well-organized generator of the
first or the second kind satisfying that
$|E_{w,h}(w)|=|E_{w,h}(\overline{w})|$. Hence we only need to show that
$|E_{w,h}(\overline{w})|=|E_{w,h}(w_{0})|$. By Proposition 4.2, we see that
$\overline{w}$ is a generator for $h$, and $\Gamma_{\overline{w},h}$ is the
induced subgraph of $\Gamma_{w,h}$ whose vertex set is $\\{u\in[w,w_{0}]\mid
u(n)=1\\}$, and

$|E_{w,h}(\overline{w})|=|E_{\overline{w},h}(\overline{w})|+|\\{y_{i}\in
Y(w)\mid h(w^{-1}(y_{i}))=n\text{~{}for~{}}0\leq i<r\\}|\,.$

On the other hand, by Proposition 4.6 (2), we have

$|E_{w,h}(w_{0})|=|E_{\overline{w},h}(w_{0})|+|\\{y_{i}\in Y(w)\mid
h(w^{-1}(y_{i}))=n\text{~{}for~{}}0\leq i\leq r\\}|-1\,.$

Thus, it suffices to show that $\Gamma_{\overline{w},h}$ is regular. Let
$h^{\prime}$ be the Hessenberg function on $[n-1]$ whose incomparability graph
is obtained from the incomparability graph of $h$ by deleting the vertex $n$
and the edges incident to it. Let $w^{\prime}\in\mathfrak{S}_{n-1}$ be the
permutation defined by $w^{\prime}(i)=\overline{w}(i)-1$ for
$i=1,2,\dots,n-1$. As $\overline{w}$ is a generator for $h$, it follows that
$w^{\prime}$ is a generator for $h^{\prime}$. Moreover, it follows from
Proposition 4.7 that $w^{\prime}$ avoids all the patterns. Accordingly, we can
apply the induction hypothesis to $w^{\prime}$ and $h^{\prime}$ and conclude
that $\Gamma_{w^{\prime},h^{\prime}}$ is regular. This completes the proof. ∎

###  4.3. Associated patterns for an arbitrary permutation

Now, we consider not only generators but also all the permutations and provide
a set of patterns that characterize the regularity of $\Gamma_{w,h}$. We
define a few more patterns that are needed.

######  Definition 4.9.

Let $h$ be a Hessenberg function on $[n]$. For a permutation
$w\in\mathfrak{S}_{n}$, we say that $w$ contains the associated pattern

  1. (1)

$\overline{25314}$ if $w(\ell)<w(i)<w(k)<w(m)<w(j)$;

  2. (2)

$\overline{24315}$ if $w(\ell)<w(i)<w(k)<w(j)<w(m)$;

  3. (3)

$\overline{14325}$ if $w(i)<w(\ell)<w(k)<w(j)<w(m)$;

  4. (4)

$\overline{15324}$ if $w(i)<w(\ell)<w(k)<w(m)<w(j)$;

for some $i<j<k\leq h(i)<\ell\leq h(j)<m\leq h(k)$.

Figure 3 shows the induced subgraph of the incomparability graph of $h$ for
the new associated patterns.

$\overline{25314},~{}\overline{24315},~{}\overline{14325},~{}\overline{15324}$$i$$j$$k$$\ell$$m$
Figure 3. Four additional associated patterns and the induced subgraph on
$\\{i,j,k,\ell,m\\}$.

######  Remark 4.10.

Four patterns in Definition 4.9 are all the possible ones that appear when we
consider the permutations satisfying the following two conditions:

$w(i)<w(k)<w(j)\quad\text{ and }\quad w(\ell)<w(k)<w(m)\,.$

These new patterns are related to the associated pattern $\overline{2413}$.

######  Lemma 4.11.

Let $h$ be a Hessenberg function. If $w$ is a generator that avoids the
associated patterns $\overline{1243}$, $\overline{2134}$, and
$\overline{1423}$, then $w$ contains the associated pattern $\overline{2413}$
if and only if $w$ contains associated pattern $\overline{25314}$.

###### Proof.

Let $w$ contain the associated pattern $\overline{25314}$, i.e.,
$w(\ell)<w(i)<w(k)<w(m)<w(j)$ for some $i<j<k\leq h(i)<\ell\leq h(j)<m\leq
h(k)$. Then $w(\ell)<w(i)<w(m)<w(j)$ and $i<j\leq h(i)<\ell\leq h(j)<m\leq
h(\ell)$. Accordingly, $w$ contains the associated pattern $\overline{2413}$.

Conversely, let $w$ contain $w(i)w(j)w(\ell)w(m)$ that gives the associated
pattern $\overline{2413}$. Note that $w(i)+1<w(m)$ since $w$ is a generator
and $h(i)<m$. Consider the following set

$X\coloneqq\\{w(s)\mid w(i)<w(s)<w(m)\text{ for }j<s<\ell\\}\,.$

Suppose that $X$ is empty. Let $y$ be the smallest integer satisfying that
$\ell<w^{-1}(y)$ and $w(i)<y$. Then $w(i)+1<y$ and $i<w^{-1}(y-1)<j$ since
$h(i)<\ell$ and $X$ is empty. Moreover $y<w(m)$ since $h(j)<m$. Accordingly,
$w$ contains the subsequence $w(i)(y-1)w(j)y$ giving the pattern
$\overline{1243}$, which is a contradiction. Hence $X$ is not empty.

Now we show that $w(i)w(j)w(k)w(\ell)w(m)$ gives the associated pattern
$\overline{25314}$ by taking $w(k)=\max X$. It suffices to show that $k\leq
h(i)$ and $h(k)\geq m$. Note that if $h(i)<w^{-1}(x)$ for all $x\in X$, then
$w$ contains the subsequence $w(i)zw(j)x$ for some $x\in X$ and $z$ satisfying
that $i<w^{-1}(z)<j$, $w(i)<z<x$, and $h(w^{-1}(z))\leq w^{-1}(x)$. Again, it
contradicts the fact that $w$ avoids the associated pattern $\overline{1243}$.
Therefore $h(i)\geq w^{-1}(x)$ for some $x\in X$. Note that if
$w^{-1}(x_{1})\leq h(i)<w^{-1}(x_{2})$ for some $x_{1},x_{2}\in X$, then
$x_{1}>x_{2}$ since $w$ avoids the associated pattern $\overline{1423}$. It
follows that $k\leq h(i)$. In this case, if $h(k)<m$, then $w$ contains
$w(k)w(\ell)w(s)w(m)$ for some $s$ satisfying that $\ell<s<m$ and
$w(k)<w(s)<w(m)$, which gives the associated pattern $\overline{2134}$. Thus
$h(k)\geq m$, and this completes the proof. ∎

Recall that by Theorems 3.11 and 4.8, we can characterize the regularity of
the graph $\Gamma_{w,h}$ for a generator $w$ as follows: $\Gamma_{w,h}$ is
regular if and only if $w$ avoids associated patterns $\overline{2143}$,
$\overline{1324}$, $\overline{1243}$, $\overline{2134}$, $\overline{1423}$,
$\overline{2314}$, and $\overline{2413}$. Owing to Lemma 4.11, we can replace
the pattern $\overline{2413}$ with a new pattern $\overline{25314}$ in the
characterization of the regularity of $\Gamma_{w,h}$.

######  Remark 4.12.

Let $w$ be a generator for a Hessenberg function $h$. Then the following are
equivalent:

  1. (1)

$w$ avoids associated patterns $\overline{2143}$, $\overline{1324}$,
$\overline{1243}$, $\overline{2134}$, $\overline{1423}$, $\overline{2314}$,
and $\overline{2413}$.

  2. (2)

$w$ avoids associated patterns $\overline{2143}$, $\overline{1324}$,
$\overline{1243}$, $\overline{2134}$, $\overline{1423}$, $\overline{2314}$,
and $\overline{25314}$.

Now, we consider all permutations and not solely the generators for $h$.
Recall from Proposition 2.7 that if $w$ is not a generator for a Hessenberg
function $h$, then $\Omega_{w,h}^{T}$ is identified with the set
$w\widetilde{w}^{-1}[\widetilde{w},w_{0}]$, where $\widetilde{w}$ is the
corresponding generator for $h$ satisfying (2.3). Moreover, Proposition 2.8
tells us that two graphs $\Gamma_{w,h}$ and $\Gamma_{\widetilde{w},h}$ are
isomorphic, which allows us to consider the graph $\Gamma_{\widetilde{w},h}$
of the corresponding generator $\widetilde{w}$ of $w$ instead of
$\Gamma_{w,h}$.

######  Lemma 4.13.

For a Hessenberg function $h$ and a permutation $w$, let $\widetilde{w}$ be
the corresponding generator of $w$.

  1. (1)

For each associated pattern
$p\in\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314}\\}$,
$w$ contains $p$ if and only if $\widetilde{w}$ contains $p$.

  2. (2)

Let $w$ avoid the associated pattern $\overline{1324}$. Then $w$ contains one
of the associated patterns $\overline{25314}$, $\overline{24315}$,
$\overline{14325}$, and $\overline{15324}$ if and only if $\widetilde{w}$
contains the associated pattern $\overline{25314}$.

###### Proof.

  1. (1)

Suppose that $w$ contains the subsequence $w(i)w(j)w(k)w(\ell)$ that gives an
associated pattern
$p\in\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314}\\}$
for some $i<j<k<\ell$. Due to (2.3), for any $p$, the set
$A\coloneqq\\{\widetilde{w}(i),\widetilde{w}(j),\widetilde{w}(k),\widetilde{w}(\ell)\\}$
is totally ordered because

     * •

for $p=\overline{2143}$, $\ell\leq h(i)$;

     * •

for $p\in\\{\overline{1324},\overline{1243},\overline{1423}\\}$,
$\widetilde{w}(i)=\min A$, the position of the second minimum of $p$ is not
greater than $h(i)$, and $\ell\leq h(j)$;

     * •

for $p\in\\{\overline{2134},\overline{2314}\\}$, $\widetilde{w}(\ell)=\max A$
and $k\leq h(i)$.

Therefore, $\widetilde{w}$ contains $p$ if $w$ contains $p$. Since the roles
of $w$ and $\widetilde{w}$ are symmetric, the proof is completed.

  2. (2)

Let $\widetilde{w}$ contain the associated pattern $\overline{25314}$, i.e.,
$\widetilde{w}(\ell)<\widetilde{w}(i)<\widetilde{w}(k)<\widetilde{w}(m)<\widetilde{w}(j)$
for some $i<j<k\leq h(i)<\ell\leq h(j)<m\leq h(k)$. Then from (2.3), $w$
satisfies $w(i)<w(k)<w(j)$ and $w(\ell)<w(k)<w(m)$. Therefore, by Remark 4.10,
$w$ contains one of the associated patterns $\overline{25314}$,
$\overline{24315}$, $\overline{14325}$, and $\overline{15324}$.

Conversely, let $w$ contain the subsequence $w(i)w(j)w(k)w(\ell)w(m)$ that
gives an associated pattern in
$P\coloneqq\\{\overline{25314},\overline{24315},\overline{14325},\overline{15324}\\}$.
By (2.3) and Remark 4.10, the subsequence
$\widetilde{w}(i)\widetilde{w}(j)\widetilde{w}(k)\widetilde{w}(\ell)\widetilde{w}(m)$
gives an associated pattern $p\in P$. We show that
$p\not\in\\{\overline{24315},\overline{14325},\overline{15324}\\}$ by using
the fact that $\widetilde{w}$ is a generator.

     * $\bullet$

For $p\in\\{\overline{24315},\overline{14325}\\}$, let $x$ be the smallest
integer satisfying that $\widetilde{w}(j)<x$ and $k<\widetilde{w}^{-1}(x)$.
Then $\widetilde{w}^{-1}(x-1)<k$. If $i<\widetilde{w}^{-1}(x-1)$
(respectively, $i>\widetilde{w}^{-1}(x-1)$), then $\widetilde{w}$ contains
$\widetilde{w}(i)(x-1)\widetilde{w}(k)x$ (respectively,
$\widetilde{w}(i)\widetilde{w}(j)\widetilde{w}(k)x$) that gives the associated
pattern $\overline{1324}$. This contradicts the assumption by (1).

     * $\bullet$

For $p=\overline{15324}$, let $x$ be the smallest integer satisfying that
$\widetilde{w}(i)<x$ and $k<\widetilde{w}^{-1}(x)$. Then
$\widetilde{w}^{-1}(x-1)<k$ and $x\leq w(\ell)$. If $m<\widetilde{w}^{-1}(x)$
(respectively, $m>\widetilde{w}^{-1}(x)$), then $\widetilde{w}$ contains
$(x-1)\widetilde{w}(k)\widetilde{w}(\ell)\widetilde{w}(m)$ (respectively,
$(x-1)\widetilde{w}(k)x\widetilde{w}(m)$) that gives the associated pattern
$\overline{1324}$. This contradicts the assumption by (1).

Thus $p=\overline{25314}$, as we desired.

∎

The following is our main theorem.

######  Theorem 4.14.

For a Hessenberg function $h\colon[n]\to[n]$, let $w$ be a permutation on
$[n]$. The graph $\Gamma_{w,h}$ is regular if and only if $w$ avoids all of
the associated patterns $\overline{2143}$, $\overline{1324}$,
$\overline{1243}$, $\overline{2134}$, $\overline{1423}$, $\overline{2314}$,
$\overline{25314}$, $\overline{24315}$, $\overline{14325}$, and
$\overline{15324}$.

###### Proof.

Let $\widetilde{w}$ be the corresponding generator of $w$. Let us denote the
associated pattern sets,

$\displaystyle
A\coloneqq\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314}\\},$
$\displaystyle
B\coloneqq\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314},\overline{2413}\\},$
$\displaystyle
C\coloneqq\\{\overline{2143},\overline{1324},\overline{1243},\overline{2134},\overline{1423},\overline{2314},\overline{25314},\overline{24315},\overline{14325},\overline{15324}\\}\,.$

If $w$ contains an associated pattern in $A$, then so does $\widetilde{w}$ by
Lemma 4.13 (1). For a permutation $w$ that avoids all of the associated
patterns in $A$, if $w$ contains an associated pattern in
$\\{\overline{25314},\overline{24315},\overline{14325},\overline{15324}\\}$,
then $\widetilde{w}$ contains the associated pattern $\overline{2413}$ by
Lemmas 4.11 and 4.13 (2). Hence $\widetilde{w}$ contains an associated pattern
in $B$ if $w$ contains an associated pattern in $C$, and $\Gamma_{w,h}$ is
irregular by Proposition 2.8 and Theorem 3.11.

Similarly, if $w$ avoids all of the associated patterns in $C$, then
$\widetilde{w}$ avoids all of the associated patterns in $B$, and
$\Gamma_{w,h}$ is regular by Proposition 2.8 and Theorem 4.8. This completes
the proof. ∎

Once again, by Proposition 2.6, we can provide a necessary condition for
$\Omega_{w,h}$ to be smooth, which is an extension of Theorem 3.12.

######  Theorem 4.15.

For a Hessenberg function $h$, if a permutation $w$ contains any one of the
associated patterns $\overline{2143}$, $\overline{1324}$, $\overline{1243}$,
$\overline{2134}$, $\overline{1423}$, $\overline{2314}$, $\overline{25314}$,
$\overline{24315}$, $\overline{14325}$, and $\overline{15324}$, then the
Hessenberg Schubert variety $\Omega_{w,h}$ is not smooth.

We believe that the pattern avoidance condition that we found is also an
equivalent condition for the smoothness of $\Omega_{w,h}$, and we make the
following conjecture. In this paper, we proved that the second and third
conditions are equivalent and are necessary conditions for the smoothness of
the Hessenberg Schubert variety.

######  Conjecture 4.16.

For a Hessenberg function $h\colon[n]\to[n]$, the following statements are
equivalent:

  1. (1)

The Hessenberg Schubert variety $\Omega_{w,h}$ is smooth.

  2. (2)

The subgraph $\Gamma_{w,h}$ of the GKM graph $\Gamma_{h}$ induced by the torus
fixed points in $\Omega_{w,h}^{T}$ is a regular graph.

  3. (3)

The permutation $w$ avoids all the patterns $\overline{2143}$,
$\overline{1324}$, $\overline{1243}$, $\overline{2134}$, $\overline{1423}$,
$\overline{2314}$, $\overline{25314}$, $\overline{24315}$, $\overline{14325}$
and $\overline{15324}$.

## References

  * [1] Sara Billey and V. Lakshmibai, _Singular loci of Schubert varieties_ , Progress in Mathematics, vol. 182, Birkhäuser Boston, Inc., Boston, MA, 2000\.
  * [2] Sara C. Billey, _Pattern avoidance and rational smoothness of Schubert varieties_ , Adv. Math. 139 (1998), no. 1, 141–156.
  * [3] Anders Björner and Francesco Brenti, _Combinatorics of Coxeter groups_ , Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005.
  * [4] Patrick Brosnan and Timothy Y. Chow, _Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties_ , Adv. Math. 329 (2018), 955–1001. MR 3783432
  * [5] James B. Carrell and Jochen Kuttler, _Smooth points of $T$-stable varieties in $G/B$ and the Peterson map_, Invent. Math. 151 (2003), no. 2, 353–379. MR 1953262
  * [6] Soojin Cho, Jaehyun Hong, and Eunjeong Lee, _Permutation Module Decomposition of the Second Cohomology of a Regular Semisimple Hessenberg Variety_ , International Mathematics Research Notices (2022), rnac328.
  * [7] by same author, _Bases of the equivariant cohomologies of regular semisimple Hessenberg varieties_ , Adv. Math. 423 (2023), Paper No. 109018.
  * [8] Corrado De Concini, George Lusztig, and Claudio Procesi, _Homology of the zero-set of a nilpotent vector field on a flag manifold_ , J. Amer. Math. Soc. 1 (1988), no. 1, 15–34. MR 924700
  * [9] Filippo De Mari, Claudio Procesi, and Mark A. Shayman, _Hessenberg varieties_ , Trans. Amer. Math. Soc. 332 (1992), no. 2, 529–534. MR 1043857
  * [10] William Fulton, _Young tableaux with applications to representation theory and geometry_ , London Mathematical Society Student Texts, vol. 35, Cambridge University Press, 1997.
  * [11] Rebecca Goldin and Julliana Tymoczko, _Which Hessenberg varieties are GKM?_ , arXiv:2301.09741, 2023.
  * [12] Mark Goresky, Robert Kottwitz, and Robert MacPherson, _Equivariant cohomology, Koszul duality, and the localization theorem_ , Invent. Math. 131 (1998), no. 1, 25–83. MR 1489894
  * [13] Mathieu Guay-Paquet, _A second proof of the Shareshian–Wachs conjecture, by way of a new Hopf algebra_ , 2016.
  * [14] Victor Guillemin and Catalin Zara, _1-skeleta, Betti numbers, and equivariant cohomology_ , Duke Math. J. 107 (2001), no. 2, 283–349. MR 1823050
  * [15] Megumi Harada and Martha Precup, _Torus fixed point sets of Hessenberg Schubert varieties in regular semisimple Hessenberg varieties_ , Osaka Journal of Mathematics 60 (2023), no. 3, 637 – 652.
  * [16] Bertram Kostant, _Flag manifold quantum cohomology, the Toda lattice, and the representation with highest weight $\rho$_, Selecta Math. (N.S.) 2 (1996), no. 1, 43–91. MR 1403352
  * [17] V. Lakshmibai and B. Sandhya, _Criterion for smoothness of Schubert varieties in ${\rm Sl}(n)/B$_, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), no. 1, 45–52.
  * [18] Julianna S. Tymoczko, _Permutation actions on equivariant cohomology of flag varieties_ , Toric topology, Contemp. Math., vol. 460, Amer. Math. Soc., Providence, RI, 2008, pp. 365–384.