# On the matching arrangement of a graph and properties of its characteristic
polynomial

A.I.Bolotnikov111Job: Moscow State University, e-mail<EMAIL_ADDRESS>
###### Abstract

This paper considers a hyperplane arrangement constructed with a subset of a
set of all simple paths in a graph. A connection of the constructed
arrangement to the maximum matching problem is established. Moreover, the
problem of finding the characteristic polynomial is reduced to the case of a
connected initial graph. The formula of the characteristic polynomial was also
found for the case, when the initial graph is a tree.

Keywords: hyperplane arrangement, graphical arrangement, partially ordered
set, matroid, maximum matching problem.

## Introduction

The number of regions of a hyperplane arrangement can be calculated with its
characteristic polynomial [1]. This result is useful in solving problems of
enumerative combinatorics. For example, in [2], [3], [4] a special hyperplane
arrangement with several related geometric constructions was introduced in
order to estimate the number of threshold functions.

In the paper [5] the connection between the chromatic polynomial of a graph
and the number of acyclic orientations of that graph is depicted as a property
of a specific hyperplane arrangement. This arrangement is called a graphical
arrangement, and the set of all edges of the initial graph is used for its
construction. The characteristic polynomial of the graphical arrangement is
equal to the chromatic polynomial of the initial graph, and the number of
regions of the graphical arrangement is equal to the number of acyclic
orientations in the initial graph.

The first part of this paper contains basic theory on hyperplane arrangements
and partially ordered sets. Papers [6], [7],[8] include an extensive number of
results on hyperplane arrangements and partially ordered sets, and in
particular they contain definitions and assertions from the first part.

In the second part a subset of a set of all simple paths in a graph is used to
construct a new hyperplane arrangement called the matching arrangement. It is
shown that the matching arrangement is connected to a maximum matching
problem, and the possibility that two non-isomorphic graphs have the same
matching arrangements is also been explored.

The third part contains several results on the characteristic polynomial of
the matching arrangement. The first result is that the characteristic
polynomial of the matching arrangement is a graph invariant. The second result
is that the characteristic polynomial of an unconnected graph is equal to a
product of characteristic polynomials of that graph’s connected components.
The third result describes specific sets of non-isomorphic graphs with equal
characteristic polynomials of matching arrangements. Specifically, for a case
when the initial graph is a tree, a formula for the characteristic polynomial
is obtained.

## Basic theory on hyperplane arrangements

######  Definition 1.

A hyperplane arrangement is a finite set of affine hyperplanes in some vector
space V. In this paper $V=R^{n}$.

######  Definition 2.

If all hyperplanes intersect in one point, an arrangement is called central .

######  Definition 3.

A region of an arrangement is a connected component of the complement of the
union of hyperplanes.

######  Definition 4.

A rank of an arrangement is the dimension of the space spanned by the normal
vectors to the hyperplanes in that arrangement.

######  Definition 5.

For a hyperplane arrangement A a partially ordered set (or poset) $L(A)$ is
defined the following way: elements of L(A) are all nonempty intersections of
hyperplanes in A, and $x\leq y$ in L(A), if $x\supseteq y$.

Each element x of the set L(A) is an affine subspace V. Its dimension will be
denoted as dim(x).

######  Definition 6.

Möbius function on a partially ordered set P is defined by following
conditions:

  1. 1.

$\mu(x,x)=1$ $\forall x\in P$

  2. 2.

$\mu(x,y)=-\sum_{x\leq z<y}\mu(x,z)$ $\forall x<y\in P$

  3. 3.

$\mu(x,y)=0$, if x and y are not comparable

.

If P have a minimal element $\hat{0}$, then $\mu(x)$ is a denotion for
$\mu(\hat{0},x)$.

######  Definition 7.

A direct product of posets P and Q is defined the following way:

$P\times Q=\\{(s,t):s\in P,t\in Q\\}$, where
$(s,t)\leq(\dot{s},\dot{t})\Leftrightarrow s\leq\dot{s}$ and $t\leq\dot{t}$

######  Assertion 1.

$\mu_{P\times
Q}((s,t),(\dot{s},\dot{t}))=\mu_{P}(s,\dot{s})\cdot\mu_{Q}(t,\dot{t})$

######  Definition 8.

Two posets are isomorphic, if there is an order-preserving bijection between
them whose inverse is also order-preserving.

######  Definition 9.

A characteristic polynomial of a hyperplane arrangement A is defined by the
following formula:

$\chi_{A}(t)=\sum_{x\in L(A)}\mu(x)t^{dim(x)}$

.

######  Definition 10.

A matroid is a pair $M=(S,J)$, where S is a finite set and J is a collection
of subsets of S, satisfying the following axioms:

  1. 1.

J is not empty, and if $K\in J,N\subset K$, then $N\in J$

  2. 2.

$\forall T\subset S$ the maximal elements of $J\cap 2^{T}$ have the same
cardinality.

######  Definition 11.

Two matroids $M=(S,J)$ and $\hat{M}=(\hat{S},\hat{J})$ are isomorphic, if
there is a bijection $f:S\rightarrow\hat{S}$ , such that
$\\{x_{1},x_{2},...,x_{k}\\}\in
J\Leftrightarrow\\{f(x_{1}),f(x_{2}),...f(x_{k})\\}\in\hat{J}$

######  Definition 12.

Let T be a subset of S. The rank of T is defined by: $rk(T)=max(|I|:I\in
J,I\subseteq S)$. The rank of a matroid M(S,J) is the rank of S.

######  Definition 13.

A k-flat of a matroid is a maximal subset of rank k.

######  Definition 14.

For a matroid M define L(M) to be the poset of flats of M, ordered by
inclusion. The characteristic polynomial of a matroid m is defined by

$\chi_{M}(t)=\sum_{x\in L(M)}\mu(x)t^{r-rk(x)}$

, where r is a rank of M.

######  Definition 15.

A matroid M is simple, if it does not contain elements x, such that
$rk(\\{x\\})=0$ (loops) and it does not contain elements x,y, such that
$rk(\\{x,y\\})=1$ (parallel points).

######  Assertion 2.

Let $M_{1}$ and $M_{2}$ be simple matroids. Matroids $M_{1}$ and $M_{2}$ are
isomorphic, if and only if posets $L(M_{1})$ and $L(M_{2})$ are isomorphic.

######  Definition 16.

For a hyperplane arrangement A the matroid $M_{A}(S,J)$ can be defined the
following way: S is a set of normal vectors to hyperplanes from A, with each
hyperplane having exactly one normal vector in S, and elements of J are sets
of linearly independent vectors from S.

######  Assertion 3.

If A is central, then $M_{A}(S,J)$ is simple, and $L(M)\cong L(A)$. As a
corollary, $\chi_{A}(t)=t^{n-r(A)}\cdot\chi_{M_{A}}(t)$, where r(A) is the
rank of A, and n is the dimension of the linear space that contains A.

######  Definition 17.

A proper coloring of a graph G(V,E) on [n] is a map $C:V\rightarrow[n]$, such
that if vertices $v_{1}$ and $v_{2}$ are adjacent, then $c(e_{1})\neq
c(e_{2})$.

######  Definition 18.

The chromatic polynomial $\chi_{G}$ is a polynomial with the following
property: for each natural n $\chi_{G}(n)$ is equal to the number of proper
colorings on [n].

######  Definition 19.

An orientation of a graph is an assignment of a direction to each edge of that
graph. An orientation is called acyclic, if it does not contain any directed
cycles.

######  Definition 20.

A graphical arrangement of a graph G(V,E) with —V— = n in space $R^{n}$ is a
hyperplane arrangement with a hyperplane $x_{i}-x_{j}=0$ for every edge
$(v_{i},v_{j})$ .

######  Assertion 4.

A graphical arrangement has the following properties:

  1. 1.

Its characteristic polynomial is equal to the chromatic polynomial of the
initial graph.

  2. 2.

Every acyclic orientation of a graph bijectively corresponds to a region of
the graphical arrangement.

## Definition of an arrangement MA(G,N) and its properties

######  Definition 21.

Let G(V,E), —E—=n be a graph without loops and parallel edges, let
$N:E\rightarrow\\{1,2,..,n\\}$ be a numeration of edges in G. Let P be a
sequence of edges $(r_{1},r_{2},r_{3},...,r_{n})$ that form a simple path or a
simple cycle with even number of edges in graph G. A hyperplane that
corresponds to sequence P is a hyperplane with an equation
$x_{1}-x_{2}+x_{3}-...x_{n}=0$. Let F be a set of all sequences of edges in G
that form a simple path or a simple cycle with even number of edges in G. Then
matching arrangement is a set of all hyperplanes that correspond to elements
of F. A matching arrangement will be denoted as MA(G,N).

######  Definition 22.

Every hyperplane arrangement corresponds to the set of all equations of its
hyperplanes. If there are two hyperplane arrangements with identical sets of
equations, then such arrangements will be call identical.

######  Theorem 1.

Let $G_{1}$, $G_{2}$ be two connected graphs without loops, parallel edges and
isolated vertices, and there are a numeration of edges $N_{1}$ in $G_{1}$ and
a numeration of edges $N_{2}$ in $G_{2}$, such that $MA(G_{1},N_{1})$ and
$MA(G_{2},N_{2})$ are identical. Then $G_{1}$ and $G_{2}$ are isomorphic,
except the case when one of the graphs is isomorphic to $K_{3}$, and another
is isomorphic to $K_{1,3}$.

###### Proof.

An arrangement MA(G,N) contains all hyperplanes that correspond to sequences
of length 2. An equation of such hyperplane is $x_{i}-x_{j}=0$, and if there
is a hyperplane with this equation in MA(G,N),then $e_{i}$ and $e_{j}$ are
adjacent in G (and visa versa, if there is no corresponding hyperplane in
MA(G,N) for $e_{i}$ and $e_{j}$, then these edges are not adjacent).
Therefore, an edge graph of an initial graph G can be reconstructed from
MA(G,N) the following way. The number of vertices of the edge graph can be
deduced from the dimension of a vector space that contains MA(G,N). Let
$\\{v_{1},..,v_{n}\\}$ be a set of vertices of the edge graph of G. Then
$v_{i}$ and $v_{j}$ are connected if and only if a hyperplane $x_{i}-x_{j}=0$
is an element of MA(G,N).

Therefore, if $MA(G_{1},N_{1})$ and $MA(G_{2},N_{2})$ are identical, then edge
graphs of $G_{1}$ and $G_{2}$ are isomorphic. According to Whitney theorem[9],
if two graphs have edge graphs that are isomorphic, then initial graphs are
isomorphic as well. The only exception is when one graph is isomorphic to
$K_{3}$, and another is isomorphic to $K_{1,3}$.

If $G_{1}\cong K_{3}$ and $G_{2}\cong K_{1,3}$, then the sets of hyperplane
equations for both $MA(G_{1},N_{1})$ and $MA(G_{2},N_{2})$ consist of
equations $x_{1}=0$, $x_{2}=0$, $x_{3}=0$, $x_{1}-x_{2}=0$, $x_{2}-x_{3}=0$,
$x_{3}-x_{1}=0$, therefore $MA(G_{1},N_{1})$ and $MA(G_{2},N_{2})$ are
identical. ∎

######  Remark 1.

The result on theorem 1 can be expanded to cover the case of non-connected
graphs the following way. Any two edges $e_{i}$ and $e_{j}$ of a graph G are
in the same connected component, if and only if there is a hyperplane in
MA(G,N), whose equation contains both $x_{i}$ and $x_{j}$. Let $G_{1}$ and
$G_{2}$ be two non-connected graphs with identical arrangements
$MA(G_{1},N_{1})$ and $MA(G_{2},N_{2})$. Then equations of hyperplanes of
$MA(G_{1},N_{1})$ and $MA(G_{2},N_{2})$ can be divided into groups that
correspond to connected components of the initial graphs, and then theorem 1
can be applied two each group independently. Let $G_{1}$ contain p connected
components that are isomorphic to $K_{3}$, and q components that are
isomorphic to $K_{1,3}$. Let $G_{2}$ contain s and r components of the same
types respectively. Let $p+q=s+r$, $p\neq s$, $q\neq r$, and for every other
component A of $G_{1}$ there is one and only one component B in $G_{2}$, such
that A isomorphic to B. Then there are numerations $N_{1}$ and $N_{2}$, such
that $MA(G_{1},N_{1})$ and $MA(G_{2},N_{2})$ are identical, but $G_{1}$ is not
isomorphic to $G_{2}$. However, if graphs $G_{1}$ and $G_{2}$ don’t contain
components that are isomorphic to $K_{3}$ or $K_{1,3}$, and $MA(G_{1},N_{1})$
and $MA(G_{2},N_{2})$ are identical,then $G_{1}$ and $G_{2}$ are isomorphic.

######  Theorem 2.

Let G(V,E), —E—=n be a graph without loops and parallel edges. Let D be a
region of an arrangement $MA(G,N)$, and let $a=(a_{1},..,a_{n})$ and
$b=(b_{1},...b_{n})$ be two vectors from D. Let $\Pi_{1}$ be a matching with
the greatest sum of weights of its edges if a weight of an edge $e_{i}$ is
equal to $a_{i}$. Let $\Pi_{2}$ be a matching with the greatest sum of weights
of its edges if a weight of an edge $e_{i}$ is equal to $b_{i}$. Then
$\Pi_{1}=\Pi_{2}$.

###### Proof.

By contradiction.Assume that for two vectors a,b from the same region D of
MA(G,N) the corresponding maximum matchings are different. Let
$H=\Pi_{1}\triangle\Pi_{2}$ be a symmetric difference of $\Pi_{1}$ and
$\Pi_{2}$. If there is a vertex with degree more then 2 in H, then there are
two adjacent edges from the same matching, which contradicts the definition of
a matching. Therefore, all vertices in H have degree less or equal to 2, and
each of the connected components of H is either a simple path or a simple
cycle. Edges from the same matching can’t be adjacent, so edges belong to
$\Pi_{1}$ and to $\Pi_{2}$ in rotation in each component of H. Therefore, a
component of H can’t be a simple cycle with odd number of edges. Let C be one
of the components of H and let $x_{i_{1}}-x_{i_{2}}+...x_{i_{m}}$ be the
corresponding expression. Assume that values of this expression on a and b
have the same sign. Without loss of generality, let’s assume, that these
values are negative. Without loss of generality, let $\Pi_{1}$ be the matching
that contains edges $x_{i_{1}},x_{i_{3}},...$, and let a be a vector of
weights, for which $\Pi_{1}$ is supposed to be the maximum matching. Then the
matching $\Pi_{3}$, obtained by replacing edges $x_{i_{1}},x_{i_{3}},...$ with
edges $x_{i_{2}},x_{i_{4}},...$ in $\Pi_{1}$,has greater total weight, then
$\Pi_{1}$, with a as a vector of weights. This contradicts the initial
assumption that $\Pi_{1}$ is a maximum matching. Therefore, the value of the
expression $x_{i_{1}}-x_{i_{2}}+...x_{i_{m}}$ is positive in one of the
vectors a and b, an negative in another. This means that a hyperplane with the
equation $x_{i_{1}}-x_{i_{2}}+...x_{i_{m}}=0$ divides a and b, therefore a and
b belong to different regions of the arrangement. This contradicts the
condition that a and b both belong to D. ∎

## Characteristic polynomial of the arrangement MA(G,N)

######  Theorem 3.

(On characteristic polynomial as a graph invariant): Let $MA(G,N_{1})$ and
$MA(G,N_{2})$ be two hyperplane arrangements constructed from two different
numerations of a graph G. Then $\chi_{MA(G,N_{1})}(t)=\chi_{MA(G,N_{2})}(t)$.

###### Proof.

For the arrangement $MA(G,N_{1})$ elements of its matroid will be chosen the
following way. If a hyperplane’s equation is $x_{i}=0$, then $e_{i}$ will be
chosen as a normal vector to this hyperplane, where
$\\{e_{1},e_{2},...,e_{n}\\}$ is a standard basis. For every other hyperplane
with an equation $x_{i_{1}}-x_{i_{2}}+x_{i_{3}}-x_{i_{4}}...=0$ one of two
vectors that can be written as $e_{i_{1}}-e_{i_{2}}+e_{i_{3}}-e_{i_{4}}+...$
will be chosen arbitrarily. For the arrangement $MA(G,N_{2})$ elements of its
matroid will be chosen the following way. If a hyperplane’s equation is
$x^{i}=0$, then $e^{i}$ will be chosen as a normal vector to this hyperplane,
where $\\{e^{1},e^{2},...,e^{n}\\}$ -is a standard basis. Otherwise let a
hyperplane H in $MA(G,N_{2})$ with an equation
$x^{i_{1}}-x^{i_{2}}+x^{i_{3}}-x^{i_{4}}...=0$ correspond to a simple path
$(r_{1},r_{2},r_{3},...r_{k}),r_{i}\in E$ in G, and let $H^{\prime}$ in
$MA(G,N_{1})$ correspond to the same path.If vector
$e_{N_{1}(r_{i_{1}})}-e_{N_{1}(r_{i_{2}})}+e_{N_{1}(r_{i_{3}})}-e_{N_{1}(r_{i_{4}})}+...$
was chosen as a normal vector to H’, then vector
$e^{N_{2}(r_{i_{1}})}-e^{N_{2}(r_{i_{2}})}+e^{N_{2}(r_{i_{3}})}-e^{N_{2}(r_{i_{4}})}+...$
will be chosen as a normal vector to H.

Let $M_{1}(S_{1},J_{1})$ be a matroid of the arrangement $MA(G,N_{1})$ and
$M_{2}(S_{2},J_{2})$ be a matroid of the arrangement $MA(G,N_{2})$.
$MA(G,N_{1})$ and $MA(G,N_{2})$ are central, therefore posets of $MA(G,N_{1})$
and $MA(G,N_{2})$ are isomorphic to posets of $M_{1}$ and $M_{2}$
respectively.

Let $U:R^{n}\rightarrow R^{n}$ be a linear operator, such that
$U(e_{i})=e^{j}$ if and only if $N_{1}(x)=i$, $N_{2}(x)=j$ for some edge x in
G. Each element $y\in S_{1}$ can be expressed as
$y=e_{i_{1}}-e_{i_{2}}+...e_{i_{k}}$, so
$U(y)=e^{j_{1}}-e^{j_{2}}+...e^{j_{k}}$. Both y and U(y) correspond to the
same edge sequence in G, therefore U defines a bijection between $S_{1}$ and
$S_{2}$. Since U is an invertible linear operator, this bijection between
$S_{1}$ and $S_{2}$ is and isomorphism between $M_{1}$ and $M_{2}$.

Since matroids $M_{1}$ and $M_{2}$ are isomorphic, posets $L(M_{1})$ and
$L(M_{2})$ are isomorphic. Since these posets are isomorphic, posets of the
initial arrangements are also isomorphic. The isomorphism of posets
$L(MA(G,N_{1}))$ and $L(MA(G,N_{2}))$ will be denoted as V. According to
definition, $\chi_{MA(G,N_{1})}(t)=\sum_{x\in
L(MA(G,N_{1}))}\mu_{L(MA(G,N_{1}))}(x)t^{dim(x)}$. Since $L(MA(G,N_{1}))$ and
$L(MA(G,N_{2}))$ are isomorphic, $\chi_{MA(G,N_{2})}(t)=\sum_{x\in
L(MA(G,N_{1}))}\mu_{L(MA(G,N_{2}))}(V(x))t^{dim(V(x))}$. $\mu(x)=\mu(V(x))$,
because V is an isomorphism. $dim(x)=dim(V(x))$, because $L(MA(G,N_{1}))$ and
$L(MA(G,N_{2}))$ are isomorphic and both arrangements belong to linear spaces
of the same dimension. Therefore, every member of the sum in
$\chi_{MA(G,N_{1})}(t)$ is equal to its corresponding member of the sum in
$\chi_{MA(G,N_{2})}(t)$, so $\chi_{MA(G,N_{1})}(t)=\chi_{MA(G,N_{2})}(t)$.

∎

######  Theorem 4.

(On a characteristic polynomial for a non-connected graph): Let $G(V,E)$ have
the following property: there are set $V_{1},V_{2}$, such that $V=V_{1}\cup
V_{2}$, $V_{1}\cap V_{2}=\emptyset$ , and there is no edge $e=(v_{1},v_{2})$
that connects a vertex from $V_{1}$ and a vertex from $V_{2}$. Let
$G_{1}(V_{1},E_{1}),G_{2}(V_{2},E_{2})$ be subgraphs of G, $E=E_{1}\cup
E_{2}$. Then
$\chi_{MA(G,N)}(t)=\chi_{MA(G_{1},N_{1})}(t)\cdot\chi_{MA(G_{2},N_{2})}(t)$.

###### Proof.

Let $|E_{1}|=k,|E_{2}|=m,|E|=k+m$. The arrangements MA(G,N),$MA(G_{1},N_{1})$,
$MA(G_{2},N_{2})$ belong to a linear spaces $R^{k+m}$, $R^{k}$, $R^{m}$
respectively. Let $e_{1},e_{2},...,e_{k}$ be a basis of $R^{k}$, let
$e^{1},e^{2},....,e^{m}$ be a basis $R^{m}$. Each vector $e_{i}$ corresponds
to an edge in $G_{1}$, and each vector $e^{i}$ corresponds to an edge in
$G_{2}$. Each vector of the basis of $R^{k+m}$ corresponds to an edge in G,
which means it corresponds either to a edge in $G_{1}$ or to an edge in
$G_{2}$. In the first case this vector will be denoted as $f(e_{i})$, where
$e_{i}$ is a vector that corresponds to the same edge, and in the second case
it will be denoted as $g(e^{i})$, where $e^{i}$ is a vector that corresponds
to the same edge. Therefore, the basis in $R^{n+m}$ will be denoted as
$\\{f(e_{1}),f(e_{2}),...,f(e_{k}),g(e^{1}),g(e^{2}),...,g(e^{m})\\}$.

Let $M(S,J),M_{1}(S_{1},J_{1}),M_{2}(S_{2},J_{2})$ be matroids of the
arrangements $MA(G,N),MA(G_{1},N_{1}),MA(G_{2},N_{2})$. Elements of these
matroids are chosen the following way. For an arrangement with an equation
$x_{i}=0$ from $MA(G_{1},N_{1})$ vector $e_{i}$ is chosen as a normal vector.
For every other hyperplane $MA(G_{1},N_{1})$ one of two vectors that can be
written as $e_{i_{1}}-e_{i_{2}}+...$ is chosen arbitrarily.This is how all
elements of $S_{1}$ are chosen. Elements of $S_{2}$ are chosen in a similar
way. Let H be an arrangement in $MA(G,N)$ that corresponds to a simple path
$(r_{1},..,r_{k}),r_{i}\in E$ in G, such that all $r_{i}$ belong to $G_{1}$,
and let H’ be a hyperplane from $MA(G_{1},N_{1})$ that corresponds to the same
path. Then if vector $e_{N_{1}(r_{1})}-e_{N_{1}(r_{2})}+e_{N_{1}(r_{3})}....$
was chosen for H’, then vector
$f(e_{N_{1}(r_{1})})-f(e_{N_{1}(r_{2})})+f(e_{N_{1}(r_{3})})....$ is chosen
for H.

The partially ordered sets of arrangements
$MA(G,N),MA(G_{1},N_{1}),MA(G_{2},N_{2})$ are isomorphic to the partially
ordered sets of matroids $M(S,J),M_{1}(S_{1},J_{1}),M_{2}(S_{2},J_{2})$
respectively. Vectors $e_{1},e_{2},...,e_{k}$ belong to $S_{1}$, vectors
$e^{1},e^{2},....,e^{m}$ belong to $S_{2}$, vectors
$\\{f(e_{1}),f(e_{2}),...,f(e_{k}),g(e^{1}),g(e^{2}),...,g(e^{m})\\}$ belong
to S, which means that $rk(M_{1})=k,rk(M_{2})=m,rk(M)=k+m$. Each element of
$S_{1}$ is normal to a hyperplane from $MA(G_{1},N_{1})$, it corresponds to a
simple path in $G_{1}$ and is equal to $e_{i_{1}}-e_{i_{2}}+e_{i_{3}}-...$ for
a certain set of vectors $e_{i_{1}},e_{i_{2}},e_{i_{3}},...$. In the same way
each element of $S_{2}$ is normal to a hyperplane from $MA(G_{2},N_{2})$, it
corresponds to a simple path in $G_{2}$ and is equal to
$e^{i_{1}}-e^{i_{2}}+e^{i_{3}}-...$ for a certain set of vectors
$e^{i_{1}},e^{i_{2}},e^{i_{3}}...$.Each element of S is normal to a hyperplane
from $MA(G,N)$, it corresponds to a simple path $G$, which means it
corresponds to a simple path in either $G_{1}$ or $G_{2}$. Then it is equal to
either $f(e_{i_{1}})-f(e_{i_{2}})+f(e_{i_{3}})-...$ or
$g(e^{i_{1}})-g(e^{i_{2}})+g(e^{i_{3}})-...$ and it also corresponds to an
element of either $S_{1}$ or $S_{2}$.The last two correspondences will now be
defined more accurately. Let x =
$\alpha_{1}e_{1}+\alpha_{2}e_{2}+...+\alpha_{k}e_{k}$ be an element of
$S_{1}$. Then a corresponding element in $R^{k+m}$ is
$\alpha_{1}f(e_{1})+\alpha_{2}(e_{2})+...+\alpha_{k}f(e_{k})$. Correspondence
for elements of $S_{2}$ is defined in a similar way.

The next step is to prove that the partially ordered set P of the matroid M is
isomorphic to a direct product of partially ordered sets $P_{1},P_{2}$ of
matroids $M_{1}$ and $M_{2}$. It will be proven by construction of an
isomorphism from $P_{1}\times P_{2}$ to P. Let $B=\\{x_{1},x_{2},...,x_{p}\\}$
be an n-facet in $M_{1}$, and let $C=\\{x^{1},x^{2},...,x^{q}\\}$ be an
l-facet in $M_{2}$. Then an element $(B,C)\in P_{1}\times P_{2}$ corresponds
to a set
$O=\\{f(x_{1}),f(x_{2}),...,f(x_{p}),g(x^{1}),g(x^{2}),...,g(x^{q})\\}$.
Without loss of generality, let $\\{x_{1},x_{2},...,x_{n}\\}$ be a set of n
linearly independent vectors from B, and let $\\{x^{1},x^{2},...,x^{l}\\}$ be
a set of l independent vectors from C. Let $\sum_{i}\alpha_{i}\cdot
f(x_{i})+\sum_{j}\beta_{j}\cdot g(x^{j})$ be a non-trivial linear combination
of vectors $\\{f(x_{1}),f(x_{2}),...,f(x_{n})\\}$ and
$\\{g(x^{1}),g(x^{2}),...,g(x^{l})\\}$. $\\\ sum_{i}\alpha_{i}\cdot f(x_{i})$
can be written as a linear combination of $f(e_{i})$, and
$\sum_{j}\beta_{j}\cdot g(x^{j})$ can be written as a linear combination of
$g(e^{j})$. Since
$\\{f(e_{1}),f(e_{2}),...,f(e_{k}),g(e^{1}),g(e^{2}),...,g(e^{m})\\}$ is a
basis of space $R^{k+m}$ the sum of these two combinations is equal to 0, if
and only if each of these two combinations is equal to 0. And since
$\\{f(x_{1}),f(x_{2}),...,f(x_{n})\\}$ and
$\\{g(x^{1}),g(x^{2}),...,g(x^{l})\\}$ are two sets of linear independent
vectors, then each combination is equal to 0, if and only if all coefficients
are equal to 0. Therefore, the union of sets
$\\{f(x_{1}),f(x_{2}),...,f(x_{n})\\}$ and
$\\{g(x^{1}),g(x^{2}),...,g(x^{l})\\}$ is a set of n+l linearly independent
vectors. Lastly, every element of O can be written as a linear combination of
these vectors, so the rank of the set O is equal to n+l.

Now suppose that S contains an element x that can be written as a linear
combination of these (n+l) vectors, but it does not belong to O. Element x can
be a linear combination of either only vectors $f(e_{i})$, or only vectors
$g(e^{j})$,so it can be a linear combination of either only
$\\{f(x_{1}),f(x_{2}),...,f(x_{n})\\}$, or only
$\\{g(x^{1}),g(x^{2}),...,g(x^{l})\\}$. Therefore, there is an element in
either $S_{1}$ or $S_{2}$, that can be written as a linear combination of
$\\{x_{1},x_{2},...,x_{n}\\}$ (or $\\{x^{1},x^{2},...,x^{l}\\}$, respectively)
but does not belong to B (or C, respectively). This means that either B is not
a facet of $M_{1}$,or C is not a facet of$M_{2}$, which is a contradiction.
Therefore, O is a (n+l)-facet of M.

The constructed function will be denoted as F. For example, $O=F((B,C))$. F
matches elements of $P_{1}\times P_{2}$ with elements of $P$. F is injective,
because f and g are injective, and because elements of any set from P can be
divided in a unique way into elements like $f(x_{i})$ and elements like
$g(x^{j})$. The next step is to prove, that F is surjective. Let O be an
element of P,which means that O is an n-facet in and a set of vectors
$\\{f(x_{1}),f(x_{2}),...,f(x_{p}),g(x^{1}),g(x^{2}),...,g(x^{q})\\}$. Let B
be $\\{x_{1},x_{2},...,x_{p}\\}$, and let C be $\\{x^{1},x^{2},...,x^{q}\\}$.
If B is not a facet in $M_{1}$, then there is an element x in $S_{1}$, that
can be written as a linear combination of $x_{1},x_{2},...,x_{p}$, but does
not belong to B. Therefore, the element f(x) can be written as a linear
combination of $\\{f(x_{1}),f(x_{2}),...,f(x_{p})\\}$, but does not belong to
O. This means that O is not a facet of M, which is contradiction. In turn,
this means that B is a facet of $M_{1}$. In the same way C is a facet of
$M_{2}$. By definition of F, $F((B,C))=O)$. This concludes the proof that F is
surjective.

As a result, F is a bijection between $P_{1}\times P_{2}$ and P.
$(B_{1},C_{1})\leq(B_{2},C_{2})$, if and only if each element of $B_{1}$ is an
element of $B_{2}$,and each element of $C_{1}$ is an element of $C_{2}$. On
the other hand, $O_{1}=F((B_{1},C_{1}))\leq F((B_{2},C_{2}))=O_{2}$ ,if and
only if each element of $O_{1}$ is an element of $O_{2}$. Each element of
$O_{2}$ can be written either as $f(x),x\in B_{2}$, or as $g(y),y\in
C_{2}$,and each element of $O_{1}$ can be written either as $f(x),x\in B_{1}$,
or as $g(y),y\in C_{1}$ All elements of type $f(x),x\in B_{1}$ of the set
$O_{1}$ belong to $O_{2}$, if and only if all elements of $B_{1}$ belong to
$B_{2}$, and all elements of type $g(y),y\in C_{1}$ of the set $O_{1}$ belong
$O_{2}$, if and only if all elements of $C_{1}$ belong to $C_{2}$. Therefore,
$(B_{1},C_{1})\leq(B_{2},C_{2})$ is equivalent to $F((B_{1},C_{1}))\leq
F((B_{2},C_{2}))$, which means that F preserves order in partially ordered
sets. As a result, F is an isomorphism of partially ordered sets.

The characteristic polynomial of M can now be transformed the following way.

$\chi_{M}(t)=\sum_{x\in L(M)}\mu(x)t^{rk(M)-rk(x)}=\sum_{x=F((B\times
C))}\mu(x)t^{rk(M)-rk(x)}$ $=\sum_{x=F((B\times C))}\mu(B)\cdot\mu(C)\cdot
t^{rk(M_{1})+rk(M_{2})-rk(B)-rk(C)}$ $=\sum_{x=F((B\times C))}\mu(B)\cdot
t^{rk(M_{1})-rk(B)}\cdot\mu(C)\cdot t^{rk(M_{2})-rk(C)}$ $=\sum_{B\in
L(M_{1})}\mu(B)t^{rk(M_{1})-rk(B)}\cdot\sum_{C\in
L(M_{2})}\mu(C)t^{rk(M_{2})-rk(C)}=\chi_{M_{1}}(t)\cdot\chi_{M_{2}}(t)$

Since the dimensions of linear spaces that contain normal vectors to
arrangements of hyperplanes $MA(G,N),MA(G_{1},N_{1}),MA(G_{2},N_{2})$ are
equal to the dimensions of spaces that contain
$MA(G,N),MA(G_{1},N_{1}),MA(G_{2},N_{2})$, then
$\chi_{MA(G,N)}(t)=\chi_{M}(t),\chi_{MA(G_{1},N_{1})}(t)=\chi_{M_{1}}(t),\chi_{MA(G_{2},N_{2})}(t)=\chi_{M_{2}}(t)$,
therefore
$\chi_{MA(G,N)}(t)=\chi_{MA(G_{1},N_{1})}(t)\cdot\chi_{MA(G_{2},N_{2})}(t)$. ∎

######  Corollary 1.

Let G be a graph without loops, parallel edges and isolated vertices, and let
$G_{1},G_{2},...,G_{k}$ be the connected components of G.

Then
$\chi_{MA(G,N)}(t)=\chi_{MA(G_{1},N_{1})}\cdot\chi_{MA(G_{2},N_{2})}\cdot...\cdot\chi_{MA(G_{k})}$

######  Theorem 5.

(On the characteristic polynomial in the tree case): Let graph G(V,E), —E—=n
be a tree. Then the characteristic polynomial of MA(G,N) is equal to
$\chi_{MA(G,N)}(t)=(t-1)(t-2)...(t-n)$.

###### Proof.

Since G is a tree, it has n+1 vertices. Let $K_{n+1}$ be a complete graph with
n+1 vertices and let vertices of $K_{n+1}$ and G have a one-to-one
correspondence between each other, specifically let a vertex $v_{i}$ of G
correspond to a vertex $v^{i}$ of $K_{n+1}$.

Let $M_{G}(S_{G},J_{G})$ be a matroid of $MA(G,N)$.Elements of $M_{G}$ are
chosen in s way similar to one in the beginning of theorem 1. The partially
ordered set of $MA(G,N)$ is isomorphic to the partially ordered set of
$M_{G}$. Let $e_{1},e_{2},..e_{n}$ be the basis of the space $R^{n}$ that
contains $MA(G,N)$, such that each vector $e_{i}$ corresponds to an edge
$r_{i}$ in G. Each element of $S_{G}$ is a normal vector to a hyperplane from
$MA(G,N)$, and it can be written as
$e_{i_{1}}-e_{i_{2}}+e_{i_{3}}...+e_{i_{m}}$, where
$e_{i_{1}},e_{i_{2}},...,e_{i_{k}}$ is as sequence of vectors, such that
$r_{i_{1}},r_{i_{2}},...,r_{i_{k}}$ is a simple path in G.

Let $\\{e^{1},e^{2},...,e^{n+1}\\}$ be the standard basis in the space that
contains $A_{K}$. The following step is to construct a linear operator with a
following property. This operator will convert elements of $S_{G}$ into
elements of $R^{n+1}$, such that an element corresponding to a simple path in
G that connects vertices $v_{i}$ and $v_{j}$ will be converted to an a normal
vector of a hyperplane that corresponds to an edge in $K_{n+1}$ that is
incident to $v^{i}$ and $v^{j}$. This property will further be referred to as
Property 1.

Each vector from $\\{e_{1},e_{2},e_{3},...,e_{n}\\}$ corresponds to a simple
path of length 1 in G ,i.e. and edge in G. Let all vertices of G be coloured
in black and white, such that adjacent vertices are coloured in different
colours. Since G is a tree, such colouring is possible. The following is the
definition of the function $F:\\{e_{1},e_{2},e_{3},...,e_{n}\\}\rightarrow
R^{n+1}$. If $e_{i}$ corresponds to an edge that is incident to vertices
$v_{i}$ and $v_{j}$,where $v_{i}$ is black, and $v_{j}$ is white , then
$F(e_{i})=e^{i}-e^{j}$.

Let $v_{i_{1}},v_{i_{2}},v_{i_{3}},...v_{i_{t+1}}$ be a sequence of vertices
of an arbitrary simple path in G, an let
$r_{i_{1}},r_{i_{2}},r_{i_{3}},...r_{i_{t}}$ be a sequence of edges of the
same path. Let vertex $v_{i_{1}}$ be a black vertex. The following is the
proof by induction that
$F(e_{i_{1}})-F(e_{i_{2}})+F(e_{i_{3}})-F(e_{i_{4}})+...F(e{i_{t+1}}))=e^{i_{1}}-e^{i_{t+1}}$.

Base case: t=1. $F(e_{i_{1}})=e^{i_{1}}-e^{i_{t}+1}$ by definition of F.

Inductive step. Let
$F(e_{i_{1}})-F(e_{i_{2}})+F(e_{i_{3}})-F(e_{i_{4}})+...F(e{i_{k}})=e^{i_{1}}-e^{i_{k+1}}$
stand for every simple path of length k in G. To prove that
$F(e_{i_{1}})-F(e_{i_{2}})+F(e_{i_{3}})-F(e_{i_{4}})+...F(e{i_{k+1}})=e^{i_{1}}-e^{i_{k+2}}$.
stands for every simple path of length k+1, the only two possible cases are
considered:

  1. 1.

k+1 is odd and $v_{i_{k+1}}$ is black. Then by induction hypothesis
$F(e_{i_{1}})-F(e_{i_{2}})+F(e_{i_{3}})-F(e_{i_{4}})+...-F(e_{i_{k}})+F(e_{i_{k+1}})=e^{i_{1}}-e^{i_{k+1}}+e^{i_{k+1}}-e^{i_{k+2}}=e^{i_{1}}-e^{i_{k+2}}$

  2. 2.

k+1 is even and $v_{i_{k+1}}$ is white. Then by induction hypothesis
$e_{i_{1}}-e_{i_{2}}+e_{i_{3}}-e_{i_{4}}+...+e_{i_{k}}-e_{i_{k+1}}=e^{i_{1}}-e^{i_{k+1}}-(e^{i_{k+2}}-e^{i_{k+1}})=e^{i_{1}}-e^{i_{k+2}}$.

Inductive step is proved. The similar proof works for the case when
$F(e_{i_{1}})$ is white. This result allows to redefine F as linear operator
that converts $R^{n}$ into the subset of $R^{n+1}$, such that it has the
Property 1.

A subgraph of $K_{n+1}$ that consists of edges corresponding to
$\\{F(e_{1}),F(e_{2}),F(e_{3}),...,F(e_{n})\\}$ and graph G are isomorphic,
because an edge $(v^{j},v^{k})$ corresponds to $F(e_{i})$ if and only if a
path that connects $v_{j}$ and $v_{k}$ corresponds to $e_{i}$, and paths that
correspond to vectors $e_{i}$ are edges. Now assume that there is a non-
trivial linear combination of vectors
$\\{F(e_{1}),F(e_{2}),F(e_{3}),...,F(e_{n})\\}$ that is equal to 0. Let
$W\subseteq\\{F(e_{1}),F(e_{2}),F(e_{3}),...,F(e_{n})\\}$ be a set of vectors
that have non-zero coefficients in such combination. A subgraph of $K_{n+1}$
that consists of edges corresponding to elements of W is a tree, therefore it
contains a vertex $v^{i}$ of degree 1. It means that when that non-trivial
combination is written as a combination of $e^{1},e^{2},..e^{n+1}$, an element
$e^{i}$ will appear exactly once, therefore that non-trivial combination
cannot be equal to 0.

All elements of the image $F(S_{G})$ belong to a hyperplane
$H:x_{1}+x_{2}+...+x_{n+1}=0$. H is of dimension n, therefore
$\\{F(e_{1}),F(e_{2}),F(e_{3}),...,F(e_{n})\\}$ is a basis in H, which in turn
means that F is a linear isomorphism between $R^{n}$ and H, since it converts
a basis into a basis. As a result,vectors
$\\{d_{1},d_{2},d_{3},...d_{l}\\}\supseteq S_{G}$ are linear independent, if
and only if vectors $\\{F(d_{1}),F(d_{2}),F(d_{3}),...F(d_{l})\\}$ are linear
independent.

Let $M_{K}(S_{K},J_{K})$ be the matroid of $A_{K}$ such that $S_{K}$ is the
image $F(S_{G})$ .By construction F is an isomorphism between $M_{G}$ and
$M_{K}$.

Since $M_{G}$ and $M_{K}$ are isomorphic, posets $L(M_{G})$ and $L(M_{K})$ are
isomorphic. An isomorphism between $L(M_{G})$ and $L(M_{K})$ will be denoted
as $\hat{F}$

By definition,

$\chi_{M_{G}}(t)=\sum_{x\in L(M_{G})}\mu(x)t^{rk(M_{G})-rk(x)}$

,

$\chi_{M_{K}}(t)=\sum_{x\in L(M_{K})}\mu(x)t^{rk(M_{K})-rk(x)}$

.

Let x be an arbitrary element of $L(M_{G})$,and let $\hat{F}(x)$ be a
corresponding element of $L(M_{K})$. Since
$\mu(x)=\mu(\hat{F}(x)),rk(x)=rk(\hat{F}(x)),rk(M_{G})=rk(M_{K})$, elements of
the corresponding sums for x and $\hat{F}(x)$ in the corresponding formulas
are equal, therefore polynomials $\chi_{M_{G}}$ and $\chi_{M_{K}}$ are equal.

Vectors $\\{e_{1},e_{2},...,e_{n}\\}$ and
$\\{F(e_{1}),F(e_{2}),...,F(e_{n})\\}$ are basis vectors of spaces that
contain normal vectors to hyperplanes of $MA(G,N)$ and $A_{K}$ respectively,
therefore $rk(MA(G,N))=rk(A_{K})=n$. $MA(G,N)$ belongs to $R^{n}$,$A_{K}$
belongs to $R^{n+1}$, which means that
$\chi_{MA(G,N)}(t)=t^{n-r(MA(G,N))}\cdot\chi_{M_{G}}(t)=\chi_{M_{G}}(t),\chi_{A_{K}}(t)=t^{n+1-r(A_{K})}\cdot\chi_{M_{K}}(t)=t\cdot\chi_{M_{K}}(t)$,
therefore $t\cdot\chi_{A_{G}}(t)=\chi_{A_{K}}(t)$. The polynomial
$\chi_{A_{K}}(t)$is equal to the chromatic polynomial of $K_{n+1}$. Since each
two vertices of $K_{n+1}$ are adjacent,in proper colouring all vertices are
coloured in different colours. With t¿n such colouring can be performed in
$t(t-1)(t-2)...(t-n)$ ways. This formula is the chromatic polynomial of
$K_{n+1}$.Therefore,$\chi_{A_{K}}(t)=t(t-1)(t-2)...(t-n)$.As a result,
$\chi_{MA(G,N)}(t)=(t-1)(t-2)...(t-n)$. ∎

######  Lemma 1.

Let $G_{1}$ and $G_{2}$ be two trees with n+1 vertices and n edges. Let
$\\{e_{1},e_{2},...,e_{n}\\}$ be a standard basis of n-dimensional space that
contains $MA(G_{1},N_{1})$, such that vectors from this basis correspond to
edges of $G_{1}$. Set $\\{e^{1},..e^{n}\\}$ is defined for $G_{2}$ and
$MA(G_{2},N_{2})$ the same way. Let u be a vertex of $G_{1}$, and let v be a
vertex of $G_{2}$. The elements of the matroid $M_{1}$ of the arrangement
$MA(G_{1},N_{1})$ are chosen the following way. If an arrangement has an
equation $x_{i}=0$, then $e_{i}$ will be chosen as its normal vector. If an
arrangement corresponds to a path that begins in u then the vector
$e_{i_{1}}-e_{i_{2}}+e_{i_{3}}-...$, where $e_{i_{1}}$ corresponds to an edge
that is incident to u, will be chosen as its normal vector. For any other
hyperplane one of two vectors $e_{i_{1}}-e_{i_{2}}+e_{i_{3}}-...$ will be
chosen arbitrarily.

Then there is a way to choose the elements for the matroid $M_{2}$ of the
arrangement $MA(G_{2},N_{2})$, such that there is an isomorphism F between
$M_{1}$ and $M_{2}$, such that if $a\in M_{1}$ corresponds to a simple path
that begins in u, then F(a) corresponds to a simple path that begins in v.

###### Proof.

Let $c_{1},c_{2},...,c_{n}$ be the elements of $M_{1}$ that correspond to
simple paths in $G_{1}$ that begin in u, and can be written as
$e_{i_{1}}-e_{i_{2}}+e_{i_{3}}-...$, where $e_{i_{1}}$ corresponds to an
adjacent to u edge . There are exactly n of these vectors, because for each
vertex of $G_{1}$ that is different from u there is exactly one simple path
that connects it to u. Let there be a non-trivial linear combination J of
vectors $c_{1},c_{2},...,c_{n}$ that is equal to 0. Let
$c_{i_{1}},c_{i_{2}}...$ be vectors that have non-zero coefficients in this
combination . Let $\hat{G}_{1}$ be a subgraph of $G_{1}$, in which every
vertex and every edge belongs to at least one path that corresponds to one of
the vectors $c_{i_{1}},c_{i_{2}}...$. $\hat{G}_{1}$ is a tree. Let r be an
edge that is incident to a vertex of degree 1 in $\hat{G}_{1}$. Among all
paths that correspond to vectors $c_{i_{1}},c_{i_{2}}...$ there is only one
path that contains this edge. This means that if all vectors
$c_{i_{1}},c_{i_{2}}...$ are written as linear combinations of vectors
$e_{1},e_{2},...,e_{n}$, only one of vectors $c_{i_{1}},c_{i_{2}}...$ will
have a corresponding to r vector $e_{r}$ in its combination. Therefore, this
vector cannot have a non-zero coefficient in J, because if J is rewritten as a
linear combination of $e_{1},e_{2},...,e_{n}$, vector $e_{r}$ will not be
reduced. Therefore, there is a contradiction, which means that J does not
exist, and vectors $c_{1},c_{2},...,c_{n}$ are linearly independent.As a
result, vectors $c_{1},c_{2},...,c_{n}$ form a basis in $R^{n}$ Let $c_{i}$ be
a vector corresponding to a path between u and $u_{i}$, and let $c_{j}$ be a
vector corresponding to a path between u and $u_{j}$, where $u_{i}$ and
$u_{j}$ are different from u and from each other. Without loss of generality,
let
$c_{i}=e_{i_{1}}-e_{i_{2}}+...+e_{i_{k}}-e_{j_{1}}+e_{j_{2}}-...+e_{j_{m}}$,
and let
$c_{j}=e_{i_{1}}-e_{i_{2}}+...+e_{i_{k}}-e_{l_{1}}+e_{l_{2}}-...+e_{l_{p}}$.
Then
$c_{i}-c_{j}=e_{j_{m}}-e_{j_{m-1}}+...+e_{j_{2}}-e_{j_{1}}+e_{l_{1}}-e_{l_{2}}+...-e_{l_{p}}$,
which is an element of $M_{1}$ that corresponds to a path between $u_{1}$ and
$u_{2}$.

As a result, if a path in $G_{1}$ begins in u, then it corresponds to a vector
$c_{i}$ in $S_{1}$, otherwise it corresponds to a vector $c_{i}-c_{j}$. Let f
be a bijective map between vertices of $G_{1}$ and $G_{2}$, such that
$f(u)=v$. Let $c^{1},c^{2},...,c^{n}$ be normal vectors to hyperplanes from
$MA(G_{2},N_{2})$ that correspond to paths in $G_{2}$ that begin in v, with
the following properties:

  1. 1.

1) $c^{i}=e^{j_{1}}-e^{j_{2}}+e^{j_{3}}...$, where $e^{j_{1}}$ corresponds to
an edge that is incident to v.

  2. 2.

2) if $c_{i}$ corresponds to a path between u and $u_{j}$, then $c^{i}$
corresponds to a path between v and $f(u_{i})$, where $u_{j}$ is an arbitrary
vertex of $G_{1}$

Elements $M_{2}$ will be chosen the following way. All vectors $c_{i}$ will be
chosen as normal vectors to corresponding hyperplanes. Moreover, if a vector
$c_{i_{1}}-c_{i_{2}}$ is chosen for a path between $u_{1}$ and $u_{2}$ in
$G_{1}$,then a vector $c^{i_{1}}-c^{i_{2}}$ will be chosen for a path between
$f(u_{1})$ and $f(u_{2})$ in $G_{2}$.

A linear isomorphism F,such that $F(c_{i})=c^{i}$ for every i, defines the
desired isomorphism between $M_{1}$ and $M_{2}$. ∎

######  Remark 2.

In the next theorem a matrix A will be used. A is a matrix of F for bases
$e_{1},....,e_{n}$ and $e^{1},....,e^{n}$.

######  Theorem 6.

(On tails): Let $G_{1}$ and $G_{2}$ be graphs without loops and parallel
edges, such that there are subgraphs $H_{1}\subset G_{1},T_{1}\subset
G_{1},H_{2}\subset G_{2},T_{2}\subset G_{2}$ with the following properties:

  1. 1.

$G_{1}=H_{1}\cup T_{1},G_{2}=H_{2}\cup T_{2}$

  2. 2.

$H_{1}\cap T_{1}=\\{u\\},H_{2}\cap T_{2}=\\{v\\}$, where u is a vertex in
$G_{1}$,and v is a vertex in $G_{2}$

  3. 3.

there is an isomorphism F between $H_{1}$ and $H_{2}$,that maps u into v

  4. 4.

$T_{1}$ and $T_{2}$ are trees with the same number of edges, and they both
have at least one edge

Then $\chi_{MA(G_{1},N_{1})}=\chi_{MA(G_{2},N_{2})}$.

Figure 1: Graphs $G_{1}$ and $G_{2}$

###### Proof.

Let $\\{e_{1},e_{2},...e_{k},e_{k+1},...e_{n}\\}$ be a basis of space that
contains $MA(G_{1},N_{1})$, such that each $e_{i}$ corresponds to an edge in
$G_{1}$.Without loss of generality, let $e_{1},e_{2},...,e_{k}$ correspond to
edges of $H_{1}$, and let $e_{k+1},...,e_{n}$ correspond to edges of $T_{1}$.
Set $\\{e^{1},e^{2},...e^{k},e^{k+1},....e^{n}\\}$ is defined for $G_{2}$,
$H_{2}$, $T_{2}$ in the same way , but with condition that for $i<k+1$, if
$e_{i}$ corresponds to an edge r, then $e^{i}$ corresponds to an edge F(r).

Let $M_{1}(S_{1},J_{1})$ be the matroid of $MA(G_{1},N_{1})$. Elements of
$M_{1}$ are chosen the following way. For every hyperplane with an equation
$x_{i}=0$ vector $e_{i}$ will be chosen as the normal vector. For every other
hyperplane one of two vectors $e_{i_{1}}-e{i_{2}}+...$ is chosen arbitrarily.

Let A be a matrix of a linear isomorphism from lemma 3 for trees $T_{1}$ and
$T_{2}$ and vertices u and v. Let U be a linear isomorphism with the following
matrix:

Figure 2: Matrix of U

,where Id is a matrix of the identity operator, and 0 is a matrix that
consists of zeros. Since both Id and A are matrices of linear isomorphisms, U
is a linear isomorphism as well.

Let e be an element of $S_{1}$. If the corresponding to e path consists only
of edges that belong to $H_{1}$ , then by definition of U U(e) is a normal
vector to a hyperplane in $MA(G_{2},N_{2})$ that corresponds to a path in
$H_{2}$. In the same way if all edges of the corresponding to e path lie in
$T_{1}$, then by definition of U U(e) is a normal vector to a hyperplane in
$MA(G_{2},N_{2})$ that corresponds to a path in $T_{2}$. The last case is when
the corresponding path starts in $H_{1}$ and ends in $T_{1}$. Without loss of
generality, let e be equal to
$e_{i_{1}}+e_{i_{2}}-....+e_{i_{d}}-e_{i_{d+1}}+...+e{i_{m}}$, where vectors
$e_{i_{1}},...,{e_{i_{d}}}$ correspond to edges from $H_{1}$, and vectors
$e_{i_{d+1}},...,e_{i_{m}}$ correspond to edges from $T_{1}$,with $e_{i_{d}}$
and $e_{i_{d+1}}$ corresponding to edges that are incident to u. Vector
$e_{i_{1}}+e_{i_{2}}-....+e_{i_{d}}$ corresponds to a simple path in $H_{1}$,
and
$U(e_{i_{1}}+e_{i_{2}}-....+e_{i_{d}})=e^{i_{1}}+e^{i_{2}}-....+e^{i_{d}}$,
where $e^{i_{d}}$ corresponds to an edge in $H_{2}$ that is incident to v.
Vector $e_{i_{d+1}}-...-e{i_{m}}$ corresponds to a simple path in $T_{1}$, and
$U(e_{i_{d+1}}-...-e{i_{m}})=e^{j_{d+1}}-...e^{j_{p}}$, where $e^{j_{d+1}}$
corresponds to and edge in $T_{2}$ that is incident to v. This means that
$U(e_{i_{1}}+e_{i_{2}}-....+e_{i_{d}}-e_{i_{d+1}}+...+e{i_{m}})=e^{i_{1}}+e^{i_{2}}-....+e^{i_{d}}-e^{j_{d+1}}+...e^{j_{p}}$,
which is a normal vector to a hyperplane in $MA(G_{2},N_{2})$ that corresponds
to a path that begins in $H_{2}$ and ends in $T_{2}$.

Let $M_{2}$ be a matroid of $MA(G_{2},N_{2})$ whose elements are chosen the
following way: $S_{2}$ is an image of $S_{1}$ under U. Then U defines a map
between $S_{1}$ and $S_{2}$. This map is bijective, and since U is a linear
isomorphism, this map is an isomorphism of matroids $M_{1}$ and $M_{2}$. Since
$M_{1}$ and $M_{2}$ are isomorphic, posets of matroids $M_{1}$ and $M_{2}$ are
isomorphic, which in turn means that posets of arrangements $MA(G_{1},N_{1})$
and $MA(G_{2},N_{2})$ are isomorphic. Arrangements $MA(G_{1},N_{1})$ and
$MA(G_{2},N_{2})$ belong to spaces of the same dimension, so
$\chi_{MA(G_{1},N_{1})}=\chi_{MA(G_{2},N_{2})}$.

∎

Author is grateful to A.A.Irmatov for the formulation of the problem and for
valuable discussions of these results.

## References

  * [1] T. Zaslavsky, _Facing up to arrangements: face-count formulas for partitions of space by hyperplanes_. // _Memoirs of the American Mathematical Society_ ,1975, vol 1, issue 154
  * [2] A.A.Irmatov, _Arrangement of Hyperplanes and the Number of Threshold Functions_ // _Acta Applicandae Mathematicae_ , 2001,vol 68,issue 1,pages 211–226
  * [3] A.A.Irmatov, _Bounds for the the number of threshold functions_ // _Discrete Mathematics and Applications_ , 1996, vol 6, issue 6, pages 569–584
  * [4] A.A.Irmatov,_Asymptotics of the Number of Threshold Functions and the Singularity Probability of Random ±1-Matrices_ // _Doklady Mathematics_ , 2020,vol 101, pages 247–249
  * [5] C.Greene, T. Zaslavsky,_On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs._ // _Transactions of the American Mathematical Society_ , 1983,vol 280,issue 1 ,pages 97–126
  * [6] R.P.Stanley, _Enumerative Combinatorics_ ,vol 1,edition 2 // Cambridge University Press,2011
  * [7] R.P.Stanley, _An Introduction to Hyperplane Arrangements_ // _IAS/MArk City Mathematics Series_ ,2004,vol 13: Geometric Combinatorics, pages 389–497
  * [8] U.Zimmermann, _Annals of Discrete Mathematics, vol 10: Linear and Combinatorial Optimization in Ordered Algebraic Structures_ //North-Holland Publishing company,1981
  * [9] H. Whitney, _Congruent Graphs and the Connectivity of Graphs_ // _American Journal of Mathematics_ , 1932,vol 54,issue 1,pages 150–168


# Another irreducibility criterion

Jitender Singh1 Department of Mathematics, Guru Nanak Dev University,
Amritsar-143005<EMAIL_ADDRESS>and  Sanjeev Kumar2,∗ Department of
Mathematics, SGGS College, Sector-26, Chandigarh-160019,
<EMAIL_ADDRESS>
###### Abstract.

Let $f=a_{0}+a_{1}x+\cdots+a_{m}x^{m}\in\mathbb{Z}[x]$ be a primitive
polynomial. Suppose that there exists a positive real number $\alpha$ such
that $|a_{m}|\alpha^{m}>|a_{0}|+|a_{1}|\alpha+\cdots+|a_{m-1}|\alpha^{m-1}$.
We prove that if there exist natural numbers $n$ and $d$ satisfying
$n\geq\alpha+d$ for which either $|f(n)|/d$ is a prime, or $|f(n)|/d$ is a
prime-power coprime to $|f^{\prime}(n)|$, then $f$ is irreducible in
$\mathbb{Z}[x]$.

11footnotetext: Corresponding Author email<EMAIL_ADDRESS>
2010MSC: Primary 12E05; 11C08
_Keywords_ : Irreducibility of Polynomials; Integer coefficients;
Irreducibility Criterion

##  1\. Introduction.

The classical irreducibility criteria due to Schönemann (1846), Eisenstein
(1850), Dumas (1906), and Perron (1907) have become paradigm for testing
irreducibility of polynomials having rational coefficients. The demesne
revealing riveting facts about irreducibility of polynomials over prescribed
domains has always been the cradle of such baroque classical results which for
decades have witnessed cogent extensions and generalizations. Such
irreducibility criteria have exhibited a close affinity to prime numbers and
primality as is evident from the illustrious Buniakowski’s conjecture of 1854
which asserts that if $f$ is an irreducible polynomial having integer
coefficients such that the elements in the set $f(\mathbb{N})$ have no common
factors other than $\pm 1$, then the set $f(\mathbb{N})$ contains infinitely
many prime numbers. The converse of Buniakowski’s conjecture holds
affirmatively via primality.

Another classical irreducibility result due to A. Cohn [1, p. 133] states that
if a prime number can be expressed in base 10 as $\sum_{i=0}^{m}a_{i}10^{i}$
for some positive integer $m$, then the polynomial $\sum_{i=0}^{m}a_{i}x^{i}$
is irreducible in $\mathbb{Z}[x]$. Cohn’s result was then generalized to
arbitrary base by Brillhart et al. [2] and further in Bonciocat et al. [3]. In
[4], Murty provided elementary proof of Cohn’s irreducibility criterion.
Interestingly, one of the main results of Murty [4], generalized by Girstmair
[5] apprised of a strong converse of Buniakowski’s conjecture which was
further generalized in [6] and [7] for polynomials having integer
coefficients.

######  Theorem A ([6]).

Let $f=a_{0}+a_{1}x+\cdots+a_{m}x^{m}\in\mathbb{Z}[x]$ be a primitive
polynomial. Suppose there exists a positive real number $\alpha$ such that

$\displaystyle|a_{m}|\alpha^{m}>|a_{0}|+|a_{1}|\alpha+\cdots+|a_{m-1}|\alpha^{m-1}.$

If there exist natural numbers $n$ and $d$ satisfying $n\geq\alpha+d$ for
which $f(n)=\pm pd$ for a prime $p$, then $f$ is irreducible in
$\mathbb{Z}[x]$.

######  Theorem B ([7]).

Let $f=a_{0}+a_{1}x+\cdots+a_{m}x^{m}\in\mathbb{Z}[x]$ be primitive, and let

$\displaystyle H=\max_{0\leq i\leq m-1}\\{|a_{i}/a_{m}|\\}.$

Let $f^{\prime}(x)$ denote the formal derivative of $f(x)$ with respect to
$x$. If there exist natural numbers $n$, $d$, $k$, and a prime $p\nmid d$ such
that $n\geq 1+H+d$, $f(n)=\pm p^{k}d$, and for $k>1$, also $p\nmid
f^{\prime}(n)$, then $f$ is irreducible in $\mathbb{Z}[x]$.

In the present note, we generalize Theorem A to the case when $|f(n)|/d$ is a
prime-power with the mild condition of coprimality of $|f(n)|/d$ with
$|f^{\prime}(n)|$. More precisely, we have the following result.

######  Theorem 1.

Let $f=a_{0}+a_{1}x+\cdots+a_{m}x^{m}\in\mathbb{Z}[x]$ be a primitive
polynomial. Suppose that there exists a positive real number $\alpha$ such
that

$\displaystyle|a_{m}|\alpha^{m}>|a_{0}|+|a_{1}|\alpha+\cdots+|a_{m-1}|\alpha^{m-1}.$

If there exist natural numbers $n$ and $d$ satisfying $n\geq\alpha+d$ for
which $|f(n)|/d$ is prime, or $|f(n)|/d$ is a prime-power coprime to
$|f^{\prime}(n)|$, then $f$ is irreducible in $\mathbb{Z}[x]$.

######  Example 1.

For $k\geq m+2\geq 4$ and $p\geq 1+d$, the polynomial

$\displaystyle X=-p+x\pm(p^{k-m}d)x^{m}$

satisfies the hypothesis of Theorem 1 with $\alpha=1$, $a_{0}=-p$, $a_{1}=1$;
$a_{i}=0$ for $i=2,3,\ldots,m-1$; $a_{m}=\pm p^{k-m}d$; and $n=p\geq
1+d=\alpha+d$, since we have $X(p)=\pm p^{k}d$; $X^{\prime}(p)\equiv 1\mod p$
so that $\gcd(|X(p)|/d,|X^{\prime}(p)|)=1$, and

$\displaystyle|a_{m}|\alpha^{m}=p^{k-m}d\geq
p^{2}>p+1=\sum_{i=0}^{m-1}|a_{i}|\alpha^{i}.$

By Theorem 1, the polynomial $X$ is irreducible in $\mathbb{Z}[x]$.

######  Example 2.

Now consider the polynomial

$\displaystyle Y=(x-p)+(x-p)^{2}+\cdots+(x-p)^{m-1}\pm(p^{2k-1}d)x^{m}$

for $k\geq m\geq 2$ and $p\geq 1+d$. Here, $a_{i}=\sum_{j=i}^{m-1}{j\choose
i}(-p)^{j-i}$ for $i=0,1,\ldots,m-1$; $a_{m}=\pm p^{2k-1}d$, $\alpha=1$, and
$n=p\geq 1+d$. We find that $Y(p)=\pm p^{2k+m-1}d$, $Y^{\prime}(p)\equiv 1\mod
p$. These along with the fact that $p^{2}>1+p$ yield the following:

$\displaystyle|a_{m}|\alpha^{m}=\frac{p^{2k}d}{p}\geq\frac{(p^{2})^{m}d}{p}>\frac{(1+p)^{m}}{p}>(1+p)\frac{(1+p)^{m-1}-1}{1+p-1}=\sum_{i=0}^{m-1}|a_{i}|\alpha^{i}.$

Since $a_{m-1}=1$, it follows that $Y$ is a primitive polynomial. By Theorem
1, the polynomial $Y$ is irreducible in $\mathbb{Z}[x]$.

##  2\. Proof of Theorem 1.

Let $|f(n)|/d=p^{k}$ for some prime $p$ and positive integer $k$. If
$|x|\geq\alpha$, then in view of the hypothesis, we have
$|a_{m}|\alpha^{m}>\sum_{j=0}^{m-1}|a_{j}|\alpha^{j}$. Consequently, we have

$\displaystyle|f(x)|\geq|x|^{m}\Bigl{(}|a_{m}|-\sum_{i=0}^{m-1}|a_{i}||x|^{-(m-i)}\Bigr{)}\geq\alpha^{m}\Bigl{(}|a_{m}|-\sum_{i=0}^{m-1}|a_{i}|\alpha^{-(m-i)}\Bigr{)}>0,$

which shows that each zero $\theta$ of $f$ satisfies $|\theta|<\alpha$.

Now assume on the contrary that $f(x)=f_{1}(x)f_{2}(x)$ for nonconstant
polynomials $f_{1}$ and $f_{2}\in\mathbb{Z}[x]$. Since we have

$\displaystyle\pm p^{k}d=f(n)=f_{1}(n)f_{2}(n),$

at least one of $|f_{1}(n)|$ and $|f_{2}(n)|$ is divisible by $p$. Assume that
$p$ divides $|f_{2}(n)|$. Firstly, let us suppose that $p$ does not divide
$|f_{1}(n)|$. Then $p^{k}$ divides $|f_{2}(n)|$, and so, $|f_{1}(n)|$ must
divide $d$ so that we have $|f_{1}(n)|\leq d$. If $\beta~{}(\neq 0)$ is the
leading coefficient of $f_{1}$, then

$\displaystyle f_{1}(n)=\beta\prod_{\theta}(n-\theta),$

where the product runs over all zeros $\theta$ of $f_{1}$. Observe that each
such $\theta$ satisfies $|\theta|<\alpha$. Since

$\displaystyle|n-\theta|\geq n-|\theta|>n-\alpha\geq d,$

we arrive at the following:

$\displaystyle d\geq|f_{1}(n)|=|\beta|\prod_{\theta}|n-\theta|$
$\displaystyle>$ $\displaystyle|\beta|d^{\deg f_{1}}\geq|\beta|d\geq d,$

leading to a contradiction.

Now assume that $p$ divides $|f_{1}(n)|$. Since $p$ divides $|f_{2}(n)|$, we
must have $k\geq 2$. Consequently, $p$ divides
$|{f_{1}}^{\prime}(n)f_{2}(n)+f_{1}(n){f_{2}}^{\prime}(n)|$, which in view of
the fact that

$\displaystyle{f_{1}}^{\prime}(n)f_{2}(n)+f_{1}(n){f_{2}}^{\prime}(n)=f^{\prime}(n),$

shows that $p$ divides $|f^{\prime}(n)|$. This contradicts the hypothesis. So,
$f$ must be irreducible in $\mathbb{Z}[x]$. ∎

The following remark and examples serve well to make the present idea
efficaciously comprehensible rendering an advantage over the results already
known in the domain.

######  Remark.

Note that Theorem A is the special case of Theorem 1 with $k=1$. The
significance of Theorem 1 lies in the fact that whenever each one of Theorems
A, B, 1 is applicable, Theorems A, B may encounter a tedious factorization of
integers. This is demonstrated in the following explicit examples.

######  Example 3.

Consider the polynomial

$\displaystyle Z=9-x+72x^{18}.$

The smallest value of $n$ for which Theorem 1 is applicable for $Z$ is $n=9$
with $\alpha=1$, $d=8$, and $Y(9)/8=3^{38}$, whereas the smallest value of $n$
for which Theorems A and B are applicable is $n=28$ with $d=13$ and

$\displaystyle Z(28)/13=619774506599223645785433953,$

which is an 18-digit prime number.

######  Example 4.

Consider the following polynomials $Z_{d}$ as mentioned in [7]

$Z_{d}=p^{k}-x\pm(p^{k}d)x^{m},~{}2\leq d\leq p^{k}-1,~{}k\geq 2,$

where $k,m,d$ are positive integers and $p$ is a prime number. Here,
$a_{0}=p^{k}$, $a_{1}=-1$, $a_{i}=0$ for $i=2,\ldots,m-1$, and $a_{m}=\pm
p^{k}d$. Taking $\alpha=1$ and $n=p^{k}$, we have

$\displaystyle|a_{m}|\alpha^{m}=p^{k}d>p^{k}+1$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{m-1}|a_{i}|\alpha^{i};~{}n=p^{k}\geq 1+d=\alpha+d,$
$\displaystyle|Z_{d}(p^{k})|/d$ $\displaystyle=$ $\displaystyle
p^{k(1+m)};~{}{Z_{d}}^{\prime}(p^{k})\equiv-1\mod p,$

so that $|Z_{d}(p^{k})|/d$ is coprime to $|{Z_{d}}^{\prime}(p^{k})|$. Thus by
Theorem 1, the polynomial $Z_{d}$ is irreducible in $\mathbb{Z}[x]$.

Here, for the aforementioned value of $n$ and $\alpha$, $Z_{p^{k}-1}$ is
irreducible by Theorem 1, the irreducibility of which cannot be easily
concluded from Theorem A or Theorem B.

## References

  * [1] G. Pólya and G. Szegö, _Problems and Theorems in Analysis_ , vol. 2, Springer-Verlag, New York, 1976.
  * [2] J. Brillhart, M. Filaseta, and A. Odlyzko, On an irreducibility theorem of A. Cohn. _Canadian J. Math._ 33 (1981), 1055–1059.
  * [3] A. I. Bonciocat, N. C. Bonciocat, and A. Zaharescu, On the irreducibility of polynomials that take a prime power value, _Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, Nouvelle Série_ , 54(102), No. 1 (2011), 41–54.
  * [4] M. Ram Murty, Prime numbers and irreducible polynomials. _Amer. Math. Monthly._ 109:5 (2002), 452–458.
  * [5] K. Girstmair, On an irreducibility criterion of M. Ram Murty. _Amer. Math. Monthly._ 112:3 (2003), 269–270.
  * [6] A. Jakhar, A useful irreducibility result for integer polynomials. _Amer. Math. Monthly._ 126:10 (2019), 943–944.
  * [7] J. Singh and S. Kumar, A note on Girstmair’s irreducibility criterion, _Bull. Aust. Math. Soc._ 106:1 (2022), 62–66.


* Huang et al. 2017 Huang, B.; Clark, G.; Navarro-Moratalla, E.; Klein, D. R.; Cheng, R.; Seyler, K. L.; Zhong, D.; Schmidgall, E.; McGuire, M. A.; Cobden, D. H. et al. Layer-dependent ferromagnetism in a van der Waals crystal down to the monolayer limit. _Nature_ 2017, _546_ , 270
  * 13 J., L. D.; Bin, L.; Jiajun, L.; Aiming, Y.; Ramakrishna, M. H. S. S.; Matthew, G.; R., R. C. N.; P., D. V. GaS and GaSe Ultrathin Layer Transistors. _Advanced Materials_ _24_ , 3549–3554
  * Hu et al. 2012 Hu, P.; Wen, Z.; Wang, L.; Tan, P.; Xiao, K. Synthesis of Few-Layer GaSe Nanosheets for High Performance Photodetectors. _Acs Nano_ 2012, _6_ , 5988–5994
  * Dou et al. 2015 Dou, L.; Wong, A. B.; Yu, Y.; Lai, M.; Kornienko, N.; Eaton, S. W.; Fu, A.; Bischak, C. G.; Ma, J.; Ding, T. et al. Atomically thin two-dimensional organic-inorganic hybrid perovskites. _Science_ 2015, _349_ , 1518–1521
  * Ashton et al. 2017 Ashton, M.; Paul, J.; Sinnott, S. B.; Hennig, R. G. Topology-scaling identification of layered solids and stable exfoliated 2D materials. _Physical Review Letters_ 2017, _118_ , 106101
  * Cheon et al. 2017 Cheon, G.; Duerloo, K.-A. N.; Sendek, A. D.; Porter, C.; Chen, Y.; Reed, E. J. Data mining for new two-and one-dimensional weakly bonded solids and lattice-commensurate heterostructures. _Nano Letters_ 2017, _17_ , 1915–1923
  * Mounet et al. 2016 Mounet, N.; Gibertini, M.; Schwaller, P.; Merkys, A.; Castelli, I. E.; Cepellotti, A.; Pizzi, G.; Marzari, N. Novel two-dimensional materials from high-throughput computational exfoliation of experimentally known compounds. _arXiv preprint arXiv:1611.05234_ 2016,
  * Choudhary et al. 2017 Choudhary, K.; Kalish, I.; Beams, R.; Tavazza, F. High-throughput Identification and Characterization of Two-dimensional Materials using Density functional theory. _Scientific Reports_ 2017, _7_ , 5179
  * Jain et al. 2016 Jain, A.; Persson, K. A.; Ceder, G. Research Update: The materials genome initiative: Data sharing and the impact of collaborative ab initio databases. _APL Materials_ 2016, _4_ , 053102
  * Thygesen and Jacobsen 2016 Thygesen, K. S.; Jacobsen, K. W. Making the most of materials computations. _Science_ 2016, _354_ , 180–181
  * Jain et al. 2013 Jain, A.; Ong, S. P.; Hautier, G.; Chen, W.; Richards, W. D.; Dacek, S.; Cholia, S.; Gunter, D.; Skinner, D.; Ceder, G. et al. The Materials Project: A materials genome approach to accelerating materials innovation. _APL Materials_ 2013, _1_ , 011002
  * Curtarolo et al. 2012 Curtarolo, S.; Setyawan, W.; Hart, G. L.; Jahnatek, M.; Chepulskii, R. V.; Taylor, R. H.; Wang, S.; Xue, J.; Yang, K.; Levy, O. et al. AFLOW: an automatic framework for high-throughput materials discovery. _Computational Materials Science_ 2012, _58_ , 218–226
  * Saal et al. 2013 Saal, J. E.; Kirklin, S.; Aykol, M.; Meredig, B.; Wolverton, C. Materials design and discovery with high-throughput density functional theory: the open quantum materials database (OQMD). _Jom_ 2013, _65_ , 1501–1509
  * Kirklin et al. 2015 Kirklin, S.; Saal, J. E.; Meredig, B.; Thompson, A.; Doak, J. W.; Aykol, M.; Ruehl, S.; Wolverton, C. The Open Quantum Materials Database (OQMD): assessing the accuracy of DFT formation energies. _Npj Computational Materials_ 2015, _1_ , 15010
  * 26 http://nomad-repository.eu;https://nomad-coe.eu.
  * Lejaeghere et al. 2016 Lejaeghere, K.; Bihlmayer, G.; Björkman, T.; Blaha, P.; Blügel, S.; Blum, V.; Caliste, D.; Castelli, I. E.; Clark, S. J.; Dal Corso, A. et al. Reproducibility in density functional theory calculations of solids. _Science_ 2016, _351_ , aad3000
  * Hautier et al. 2010 Hautier, G.; Fischer, C. C.; Jain, A.; Mueller, T.; Ceder, G. Finding nature’s missing ternary oxide compounds using machine learning and density functional theory. _Chemistry of Materials_ 2010, _22_ , 3762–3767
  * Ghiringhelli et al. 2015 Ghiringhelli, L. M.; Vybiral, J.; Levchenko, S. V.; Draxl, C.; Scheffler, M. Big data of materials science: Critical role of the descriptor. _Physical review letters_ 2015, _114_ , 105503
  * Ward and Wolverton 2017 Ward, L.; Wolverton, C. Atomistic calculations and materials informatics: A review. _Current Opinion in Solid State and Materials Science_ 2017, _21_ , 167–176
  * Şahin et al. 2009 Şahin, H.; Cahangirov, S.; Topsakal, M.; Bekaroglu, E.; Akturk, E.; Senger, R. T.; Ciraci, S. Monolayer honeycomb structures of group-IV elements and III-V binary compounds: First-principles calculations. _Physical Review B_ 2009, _80_ , 155453
  * Ciraci and Cahangirov 2017 Ciraci, S.; Cahangirov, S. In _2D Materials: Properties and Devices_ ; Avouris, P., Heinz, T. F., Low, T., Eds.; Cambridge University Press, 2017; p 472–484
  * Ataca et al. 2012 Ataca, C.; Sahin, H.; Ciraci, S. Stable, single-layer MX2 transition-metal oxides and dichalcogenides in a honeycomb-like structure. _The Journal of Physical Chemistry C_ 2012, _116_ , 8983–8999
  * Lebègue et al. 2013 Lebègue, S.; Björkman, T.; Klintenberg, M.; Nieminen, R. M.; Eriksson, O. Two-dimensional materials from data filtering and ab initio calculations. _Physical Review X_ 2013, _3_ , 031002
  * Miro et al. 2014 Miro, P.; Audiffred, M.; Heine, T. An atlas of two-dimensional materials. _Chemical Society Reviews_ 2014, _43_ , 6537–6554
  * Rasmussen and Thygesen 2015 Rasmussen, F. A.; Thygesen, K. S. Computational 2D materials database: Electronic structure of transition-metal dichalcogenides and oxides. _The Journal of Physical Chemistry C_ 2015, _119_ , 13169–13183
  * Enkovaara et al. 2010 Enkovaara, J. e.; Rostgaard, C.; Mortensen, J. J.; Chen, J.; Dułak, M.; Ferrighi, L.; Gavnholt, J.; Glinsvad, C.; Haikola, V.; Hansen, H. et al. Electronic structure calculations with GPAW: a real-space implementation of the projectoraugmented-wave method. _Journal of Physics: Condensed Matter_ 2010, _22_ , 253202
  * Larsen et al. 2017 Larsen, A.; Mortensen, J.; Blomqvist, J.; Castelli, I.; Christensen, R.; Dulak, M.; Friis, J.; Groves, M.; Hammer, B.; Hargus, C. et al. The Atomic Simulation Environment—A Python library for working with atoms. _Journal of Physics: Condensed Matter_ 2017,
  * Cordero et al. 2008 Cordero, B.; Gomez, V.; Platero-Prats, A. E.; Reves, M.; Echeverria, J.; Cremades, E.; Barragan, F.; Alvarez, S. Covalent radii revisited. _Dalton Trans._ 2008, 2832–2838
  * Ashton et al. 2017 Ashton, M.; Paul, J.; Sinnott, S. B.; Hennig, R. G. Topology-Scaling Identification of Layered Solids and Stable Exfoliated 2D Materials. _Phys. Rev. Lett._ 2017, _118_ , 106101
  * Larsen 2017 Larsen, P. M. Structural Analysis Algorithms for Nanomaterials. Ph.D. thesis, Department of Physics, DTU, 2017
  * Özçelik et al. 2016 Özçelik, V. O.; Azadani, J. G.; Yang, C.; Koester, S. J.; Low, T. Band alignment of two-dimensional semiconductors for designing heterostructures with momentum space matching. _Physical Review B_ 2016, _94_ , 035125
  * Togo 2009 Togo, A. Spglib. 2009; https://atztogo.github.io/spglib/
  * Pandey and Jacobsen 2015 Pandey, M.; Jacobsen, K. W. Heats of formation of solids with error estimation: The mBEEF functional with and without fitted reference energies. _Phys. Rev. B_ 2015, _91_ , 235201
  * Stevanović et al. 2012 Stevanović, V.; Lany, S.; Zhang, X.; Zunger, A. Correcting density functional theory for accurate predictions of compound enthalpies of formation: Fitted elemental-phase reference energies. _Physical Review B_ 2012, _85_ , 115104
  * Anisimov and Gunnarsson 1991 Anisimov, V.; Gunnarsson, O. Density-functional calculation of effective Coulomb interactions in metals. _Physical Review B_ 1991, _43_ , 7570
  * Kuhar et al. 2017 Kuhar, K.; Crovetto, A.; Pandey, M.; Thygesen, K. S.; Seger, B.; Vesborg, P. C. K.; Hansen, O.; Chorkendorff, I.; Jacobsen, K. W. Sulfide perovskites for solar energy conversion applications: computational screening and synthesis of the selected compound LaYS3. _Energy Environ. Sci._ 2017, _10_ , 2579–2593
  * Zhou et al. 2018 Zhou, Y.; Miao, L.; Wang, P.; Zhu, F.; Jiang, W.; Jiang, S.; Zhang, Y.; Lei, B.; Chen, X.; Ding, H. et al. Antiferromagnetic Order in Epitaxial FeSe Films on SrTiO 3. _Physical Review Letters_ 2018, _120_ , 097001
  * Alfe 2009 Alfe, D. PHON: A program to calculate phonons using the small displacement method. _Computer Physics Communications_ 2009, _180_ , 2622–2633
  * Novoselov et al. 2004 Novoselov, K. S.; Geim, A. K.; Morozov, S. V.; Jiang, D.; Zhang, Y.; Dubonos, S. V.; Grigorieva, I. V.; Firsov, A. A. Electric field effect in atomically thin carbon films. _science_ 2004, _306_ , 666–669
  * Sone et al. 2014 Sone, J.; Yamagami, T.; Aoki, Y.; Nakatsuji, K.; Hirayama, H. Epitaxial growth of silicene on ultra-thin Ag (111) films. _New Journal of Physics_ 2014, _16_ , 095004
  * Dávila et al. 2014 Dávila, M.; Xian, L.; Cahangirov, S.; Rubio, A.; Le Lay, G. Germanene: a novel two-dimensional germanium allotrope akin to graphene and silicene. _New Journal of Physics_ 2014, _16_ , 095002
  * Li et al. 2014 Li, L.; Yu, Y.; Ye, G. J.; Ge, Q.; Ou, X.; Wu, H.; Feng, D.; Chen, X. H.; Zhang, Y. Black phosphorus field-effect transistors. _Nature nanotechnology_ 2014, _9_ , 372
  * Yang et al. 2017 Yang, S.; Li, W.; Ye, C.; Wang, G.; Tian, H.; Zhu, C.; He, P.; Ding, G.; Xie, X.; Liu, Y. et al. C3N—A 2D Crystalline, Hole-Free, Tunable-Narrow-Bandgap Semiconductor with Ferromagnetic Properties. _Advanced Materials_ 2017, _29_
  * Kappera et al. 2014 Kappera, R.; Voiry, D.; Yalcin, S. E.; Branch, B.; Gupta, G.; Mohite, A. D.; Chhowalla, M. Phase-engineered low-resistance contacts for ultrathin MoS 2 transistors. _Nature materials_ 2014, _13_ , 1128
  * Mak et al. 2010 Mak, K. F.; Lee, C.; Hone, J.; Shan, J.; Heinz, T. F. Atomically thin MoS 2: a new direct-gap semiconductor. _Physical review letters_ 2010, _105_ , 136805
  * Tonndorf et al. 2013 Tonndorf, P.; Schmidt, R.; Böttger, P.; Zhang, X.; Börner, J.; Liebig, A.; Albrecht, M.; Kloc, C.; Gordan, O.; Zahn, D. R. et al. Photoluminescence emission and Raman response of monolayer MoS 2, MoSe 2, and WSe 2. _Optics express_ 2013, _21_ , 4908–4916
  * Lu et al. 2017 Lu, A.-Y.; Zhu, H.; Xiao, J.; Chuu, C.-P.; Han, Y.; Chiu, M.-H.; Cheng, C.-C.; Yang, C.-W.; Wei, K.-H.; Yang, Y. et al. Janus monolayers of transition metal dichalcogenides. _Nature nanotechnology_ 2017, _12_ , 744
  * Naylor et al. 2016 Naylor, C. H.; Parkin, W. M.; Ping, J.; Gao, Z.; Zhou, Y. R.; Kim, Y.; Streller, F.; Carpick, R. W.; Rappe, A. M.; Drndic, M. et al. Monolayer single-crystal 1T-́MoTe2 grown by chemical vapor deposition exhibits weak antilocalization effect. _Nano letters_ 2016, _16_ , 4297–4304
  * Wang et al. 2017 Wang, Y.; Xiao, J.; Zhu, H.; Li, Y.; Alsaid, Y.; Fong, K. Y.; Zhou, Y.; Wang, S.; Shi, W.; Wang, Y. et al. Structural phase transition in monolayer MoTe 2 driven by electrostatic doping. _Nature_ 2017, _550_ , 487
  * Okada et al. 2014 Okada, M.; Sawazaki, T.; Watanabe, K.; Taniguch, T.; Hibino, H.; Shinohara, H.; Kitaura, R. Direct chemical vapor deposition growth of WS2 atomic layers on hexagonal boron nitride. _ACS nano_ 2014, _8_ , 8273–8277
  * Fei et al. 2017 Fei, Z.; Palomaki, T.; Wu, S.; Zhao, W.; Cai, X.; Sun, B.; Nguyen, P.; Finney, J.; Xu, X.; Cobden, D. H. Edge conduction in monolayer WTe 2. _Nature Physics_ 2017, _13_ , 677
  * Xi et al. 2015 Xi, X.; Zhao, L.; Wang, Z.; Berger, H.; Forró, L.; Shan, J.; Mak, K. F. Strongly enhanced charge-density-wave order in monolayer NbSe 2. _Nature nanotechnology_ 2015, _10_ , 765
  * Wang et al. 2017 Wang, X.; Lin, J.; Zhu, Y.; Luo, C.; Suenaga, K.; Cai, C.; Xie, L. Chemical vapor deposition of trigonal prismatic NbS 2 monolayers and 3R-polytype few-layers. _Nanoscale_ 2017, _9_ , 16607–16611
  * Zhang et al. 2015 Zhang, M.; Zhu, Y.; Wang, X.; Feng, Q.; Qiao, S.; Wen, W.; Chen, Y.; Cui, M.; Zhang, J.; Cai, C. et al. Controlled synthesis of ZrS2 monolayer and few layers on hexagonal boron nitride. _Journal of the American Chemical Society_ 2015, _137_ , 7051–7054
  * Mañas-Valero et al. 2016 Mañas-Valero, S.; García-López, V.; Cantarero, A.; Galbiati, M. Raman spectra of ZrS2 and ZrSe2 from bulk to atomically thin layers. _Applied Sciences_ 2016, _6_ , 264
  * Xu et al. 2015 Xu, K.; Wang, Z.; Wang, F.; Huang, Y.; Wang, F.; Yin, L.; Jiang, C.; He, J. Ultrasensitive Phototransistors Based on Few-Layered HfS2. _Advanced Materials_ 2015, _27_ , 7881–7887
  * Fu et al. 2016 Fu, W.; Chen, Y.; Lin, J.; Wang, X.; Zeng, Q.; Zhou, J.; Zheng, L.; Wang, H.; He, Y.; He, H. et al. Controlled synthesis of atomically thin 1T-TaS2 for tunable charge density wave phase transitions. _Chemistry of Materials_ 2016, _28_ , 7613–7618
  * Ryu et al. 2018 Ryu, H.; Chen, Y.; Kim, H.; Tsai, H.-Z.; Tang, S.; Jiang, J.; Liou, F.; Kahn, S.; Jia, C.; Omrani, A. A. et al. Persistent charge-density-wave order in single-layer TaSe2. _Nano letters_ 2018,
  * Zhao et al. 2016 Zhao, W.; Dong, B.; Guo, Z.; Su, G.; Gao, R.; Wang, W.; Cao, L. Colloidal synthesis of VSe 2 single-layer nanosheets as novel electrocatalysts for the hydrogen evolution reaction. _Chemical Communications_ 2016, _52_ , 9228–9231
  * Feng et al. 2011 Feng, J.; Sun, X.; Wu, C.; Peng, L.; Lin, C.; Hu, S.; Yang, J.; Xie, Y. Metallic few-layered VS2 ultrathin nanosheets: high two-dimensional conductivity for in-plane supercapacitors. _Journal of the American Chemical Society_ 2011, _133_ , 17832–17838
  * Wang et al. 2015 Wang, Y.; Li, L.; Yao, W.; Song, S.; Sun, J.; Pan, J.; Ren, X.; Li, C.; Okunishi, E.; Wang, Y.-Q. et al. Monolayer PtSe2, a new semiconducting transition-metal-dichalcogenide, epitaxially grown by direct selenization of Pt. _Nano letters_ 2015, _15_ , 4013–4018
  * Zhao et al. 2016 Zhao, Y.; Qiao, J.; Yu, P.; Hu, Z.; Lin, Z.; Lau, S. P.; Liu, Z.; Ji, W.; Chai, Y. Extraordinarily strong interlayer interaction in 2D layered PtS2. _Advanced Materials_ 2016, _28_ , 2399–2407
  * Wan et al. 2015 Wan, C.; Gu, X.; Dang, F.; Itoh, T.; Wang, Y.; Sasaki, H.; Kondo, M.; Koga, K.; Yabuki, K.; Snyder, G. J. et al. Flexible n-type thermoelectric materials by organic intercalation of layered transition metal dichalcogenide TiS 2. _Nature materials_ 2015, _14_ , 622
  * Shao et al. 2017 Shao, Y.; Song, S.; Wu, X.; Qi, J.; Lu, H.; Liu, C.; Zhu, S.; Liu, Z.; Wang, J.; Shi, D. et al. Epitaxial fabrication of two-dimensional NiSe2 on Ni (111) substrate. _Applied Physics Letters_ 2017, _111_ , 113107
  * Tongay et al. 2014 Tongay, S.; Sahin, H.; Ko, C.; Luce, A.; Fan, W.; Liu, K.; Zhou, J.; Huang, Y.-S.; Ho, C.-H.; Yan, J. et al. Monolayer behaviour in bulk ReS 2 due to electronic and vibrational decoupling. _Nature communications_ 2014, _5_ , 3252
  * Oyedele et al. 2017 Oyedele, A. D.; Yang, S.; Liang, L.; Puretzky, A. A.; Wang, K.; Zhang, J.; Yu, P.; Pudasaini, P. R.; Ghosh, A. W.; Liu, Z. et al. PdSe2: Pentagonal Two-Dimensional Layers with High Air Stability for Electronics. _Journal of the American Chemical Society_ 2017, _139_ , 14090–14097
  * Zheng et al. 2018 Zheng, L.; Zhou, J.; Shi, J.; Zeng, Q.; Chen, Y.; Niu, L.; Liu, F.; Yu, T.; Suenaga, K.; Liu, X. et al. InSe monolayer: synthesis, structure and ultra-high second-harmonic generation. _2D Materials_ 2018,
  * Del Pozo-Zamudio et al. 2015 Del Pozo-Zamudio, O.; Schwarz, S.; Sich, M.; Akimov, I.; Bayer, M.; Schofield, R.; Chekhovich, E.; Robinson, B.; Kay, N.; Kolosov, O. et al. Photoluminescence of two-dimensional GaTe and GaSe films. _2D Materials_ 2015, _2_ , 035010
  * Zhou et al. 2014 Zhou, Y.; Nie, Y.; Liu, Y.; Yan, K.; Hong, J.; Jin, C.; Zhou, Y.; Yin, J.; Liu, Z.; Peng, H. Epitaxy and photoresponse of two-dimensional GaSe crystals on flexible transparent mica sheets. _Acs Nano_ 2014, _8_ , 1485–1490
  * Island et al. 2014 Island, J. O.; Buscema, M.; Barawi, M.; Clamagirand, J. M.; Ares, J. R.; Sánchez, C.; Ferrer, I. J.; Steele, G. A.; van der Zant, H. S.; Castellanos-Gomez, A. Ultrahigh Photoresponse of Few-Layer TiS3 Nanoribbon Transistors. _Advanced Optical Materials_ 2014, _2_ , 641–645
  * Wang et al. 2016 Wang, Y.-Q.; Wu, X.; Ge, Y.-F.; Wang, Y.-L.; Guo, H.; Shao, Y.; Lei, T.; Liu, C.; Wang, J.-O.; Zhu, S.-Y. et al. Tunable Electronic Structures in Wrinkled 2D Transition-Metal-Trichalcogenide (TMT) HfTe3 Films. _Advanced Electronic Materials_ 2016, _2_
  * Song et al. 2011 Song, C.-L.; Wang, Y.-L.; Jiang, Y.-P.; Li, Z.; Wang, L.; He, K.; Chen, X.; Ma, X.-C.; Xue, Q.-K. Molecular-beam epitaxy and robust superconductivity of stoichiometric FeSe crystalline films on bilayer graphene. _Physical Review B_ 2011, _84_ , 020503
  * Liu et al. 2016 Liu, H.-J.; Lin, J.-C.; Fang, Y.-W.; Wang, J.-C.; Huang, B.-C.; Gao, X.; Huang, R.; Dean, P. R.; Hatton, P. D.; Chin, Y.-Y. et al. A Metal–Insulator Transition of the Buried MnO2 Monolayer in Complex Oxide Heterostructure. _Advanced Materials_ 2016, _28_ , 9142–9151
  * Cai et al. 2017 Cai, L.; McClellan, C. J.; Koh, A. L.; Li, H.; Yalon, E.; Pop, E.; Zheng, X. Rapid flame synthesis of atomically thin MoO3 down to monolayer thickness for effective hole doping of WSe2. _Nano letters_ 2017, _17_ , 3854–3861
  * Xu et al. 2015 Xu, S.; Han, Y.; Chen, X.; Wu, Z.; Wang, L.; Han, T.; Ye, W.; Lu, H.; Long, G.; Wu, Y. et al. van der Waals epitaxial growth of atomically thin Bi2Se3 and thickness-dependent topological phase transition. _Nano letters_ 2015, _15_ , 2645–2651
  * Kong et al. 2010 Kong, D.; Dang, W.; Cha, J. J.; Li, H.; Meister, S.; Peng, H.; Liu, Z.; Cui, Y. Few-layer nanoplates of Bi2Se3 and Bi2Te3 with highly tunable chemical potential. _Nano letters_ 2010, _10_ , 2245–2250
  * Mashtalir et al. 2015 Mashtalir, O.; Lukatskaya, M. R.; Zhao, M.-Q.; Barsoum, M. W.; Gogotsi, Y. Amine-assisted delamination of Nb2C MXene for Li-Ion energy storage devices. _Advanced Materials_ 2015, _27_ , 3501–3506
  * Liu et al. 2017 Liu, F.; Zhou, J.; Wang, S.; Wang, B.; Shen, C.; Wang, L.; Hu, Q.; Huang, Q.; Zhou, A. Preparation of High-Purity V2C MXene and Electrochemical Properties as Li-Ion Batteries. _Journal of The Electrochemical Society_ 2017, _164_ , A709–A713
  * Lukatskaya et al. 2013 Lukatskaya, M. R.; Mashtalir, O.; Ren, C. E.; Dall’Agnese, Y.; Rozier, P.; Taberna, P. L.; Naguib, M.; Simon, P.; Barsoum, M. W.; Gogotsi, Y. Cation intercalation and high volumetric capacitance of two-dimensional titanium carbide. _Science_ 2013, _341_ , 1502–1505
  * Melchior et al. 2018 Melchior, S. A.; Raju, K.; Ike, I. S.; Erasmus, R. M.; Kabongo, G.; Sigalas, I.; Iyuke, S. E.; Ozoemena, K. I. High-Voltage Symmetric Supercapacitor Based on 2D Titanium Carbide (MXene, Ti2CTx)/Carbon Nanosphere Composites in a Neutral Aqueous Electrolyte. _Journal of The Electrochemical Society_ 2018, _165_ , A501–A511
  * Liu et al. 2017 Liu, G.; Li, Z.; Hasan, T.; Chen, X.; Zheng, W.; Feng, W.; Jia, D.; Zhou, Y.; Hu, P. Vertically aligned two-dimensional SnS 2 nanosheets with a strong photon capturing capability for efficient photoelectrochemical water splitting. _Journal of Materials Chemistry A_ 2017, _5_ , 1989–1995
  * Li et al. 2017 Li, J.; Guan, X.; Wang, C.; Cheng, H.-C.; Ai, R.; Yao, K.; Chen, P.; Zhang, Z.; Duan, X.; Duan, X. Synthesis of 2D Layered BiI3 Nanoplates, BiI3/WSe2van der Waals Heterostructures and Their Electronic, Optoelectronic Properties. _Small_ 2017, _13_
  * Elias et al. 2009 Elias, D. C.; Nair, R. R.; Mohiuddin, T.; Morozov, S.; Blake, P.; Halsall, M.; Ferrari, A.; Boukhvalov, D.; Katsnelson, M.; Geim, A. et al. Control of grapheneś properties by reversible hydrogenation: evidence for graphane. _Science_ 2009, _323_ , 610–613
  * Nair et al. 2010 Nair, R. R.; Ren, W.; Jalil, R.; Riaz, I.; Kravets, V. G.; Britnell, L.; Blake, P.; Schedin, F.; Mayorov, A. S.; Yuan, S. et al. Fluorographene: A two-dimensional counterpart of Teflon. _small_ 2010, _6_ , 2877–2884
  * Wang et al. 2015 Wang, L.; Kutana, A.; Zou, X.; Yakobson, B. I. Electro-mechanical anisotropy of phosphorene. _Nanoscale_ 2015, _7_ , 9746–9751
  * Wang et al. 1996 Wang, X.; Wang, D. S.; Ruqian, W.; Freeman, A. J. Validity of the force theorem for magnetocrystalline anisotropy. _J. Magn. Magn. Mater._ 1996, _159_ , 337–341
  * Olsen 2016 Olsen, T. Designing in-plane heterostructures of quantum spin Hall insulators from first principles: 1 T-́ MoS 2 with adsorbates. _Physical Review B_ 2016, _94_ , 235106
  * MacDonald et al. 1979 MacDonald, A. H.; Vosko, S. H.; Coleridge, P. T. Extensions of the tetrahedron method for evaluating spectral properties of solids. _Journal of Physics C: Solid State Physics_ 1979, _12_ , 2991–3002
  * Heyd et al. 2003 Heyd, J.; Scuseria, G. E.; Ernzerhof, M. Hybrid functionals based on a screened Coulomb potential. _The Journal of Chemical Physics_ 2003, _118_ , 8207–8215
  * Kośmider and Fernández-Rossier 2013 Kośmider, K.; Fernández-Rossier, J. Electronic properties of the MoS 2-WS 2 heterojunction. _Physical Review B_ 2013, _87_ , 075451
  * Kang et al. 2013 Kang, J.; Tongay, S.; Zhou, J.; Li, J.; Wu, J. Band offsets and heterostructures of two-dimensional semiconductors. _Applied Physics Letters_ 2013, _102_ , 012111
  * Kuisma et al. 2010 Kuisma, M.; Ojanen, J.; Enkovaara, J.; Rantala, T. T. Kohn-Sham Potential with Discontinuity for Band Gap Materials. _Phys. Rev. B_ 2010, _82_ , 115106
  * Castelli et al. 2012 Castelli, I. E.; Olsen, T.; Datta, S.; Landis, D. D.; Dahl, S.; Thygesen, K. S.; Jacobsen, K. W. Computational screening of perovskite metal oxides for optimal solar light capture. _Energy & Environmental Science_ 2012, _5_ , 5814–5819
  * Baerends 2017 Baerends, E. From the Kohn–Sham band gap to the fundamental gap in solids. An integer electron approach. _Physical Chemistry Chemical Physics_ 2017, _19_ , 15639–15656
  * Hüser et al. 2013 Hüser, F.; Olsen, T.; Thygesen, K. S. Quasiparticle GW calculations for solids, molecules, and two-dimensional materials. _Phys. Rev. B_ 2013, _87_ , 235132
  * Rasmussen et al. 2016 Rasmussen, F. A.; Schmidt, P. S.; Winther, K. T.; Thygesen, K. S. Efficient many-body calculations for two-dimensional materials using exact limits for the screened potential: Band gaps of ${\mathbf{MoS}}_{2},h$-BN, and phosphorene. _Phys. Rev. B_ 2016, _94_ , 155406
  * Tiago et al. 2004 Tiago, M. L.; Ismail-Beigi, S.; Louie, S. G. Effect of semicore orbitals on the electronic band gaps of Si, Ge, and GaAs within the GW approximation. _Phys. Rev. B_ 2004, _69_ , 125212
  * Klimeš et al. 2014 Klimeš, J.; Kaltak, M.; Kresse, G. Predictive GW calculations using plane waves and pseudopotentials. _Phys. Rev. B_ 2014, _90_ , 075125
  * Sundararaman and Arias 2013 Sundararaman, R.; Arias, T. A. Regularization of the Coulomb singularity in exact exchange by Wigner-Seitz truncated interactions: Towards chemical accuracy in nontrivial systems. _Phys. Rev. B_ 2013, _87_ , 165122
  * Ismail-Beigi 2006 Ismail-Beigi, S. Truncation of periodic image interactions for confined systems. _Phys. Rev. B_ 2006, _73_ , 233103
  * Rozzi et al. 2006 Rozzi, C. A.; Varsano, D.; Marini, A.; Gross, E. K. U.; Rubio, A. Exact Coulomb cutoff technique for supercell calculations. _Phys. Rev. B_ 2006, _73_ , 205119
  * Lee et al. 2017 Lee, J.; Huang, J.; Sumpter, B. G.; Yoon, M. Strain-engineered optoelectronic properties of 2D transition metal dichalcogenide lateral heterostructures. _2D Materials_ 2017, _4_ , 021016
  * Ramasubramaniam 2012 Ramasubramaniam, A. Large excitonic effects in monolayers of molybdenum and tungsten dichalcogenides. _Phys. Rev. B_ 2012, _86_ , 115409
  * Cheiwchanchamnangij and Lambrecht 2012 Cheiwchanchamnangij, T.; Lambrecht, W. R. L. Quasiparticle band structure calculation of monolayer, bilayer, and bulk MoS2. _Phys. Rev. B_ 2012, _85_ , 205302
  * Komsa and Krasheninnikov 2012 Komsa, H.-P.; Krasheninnikov, A. V. Effects of confinement and environment on the electronic structure and exciton binding energy of MoS2 from first principles. _Phys. Rev. B_ 2012, _86_ , 241201
  * Molina-Sánchez et al. 2013 Molina-Sánchez, A.; Sangalli, D.; Hummer, K.; Marini, A.; Wirtz, L. Effect of spin-orbit interaction on the optical spectra of single-layer, double-layer, and bulk MoS2. _Phys. Rev. B_ 2013, _88_ , 045412
  * Shi et al. 2013 Shi, H.; Pan, H.; Zhang, Y.-W.; Yakobson, B. I. Quasiparticle band structures and optical properties of strained monolayer MoS2 and WS2. _Phys. Rev. B_ 2013, _87_ , 155304
  * Conley et al. 2013 Conley, H. J.; Wang, B.; Ziegler, J. I.; Haglund, R. F.; Pantelides, S. T.; Bolotin, K. I. Bandgap Engineering of Strained Monolayer and Bilayer MoS2. _Nano Lett._ 2013, _13_ , 3626–3630
  * Hüser et al. 2013 Hüser, F.; Olsen, T.; Thygesen, K. S. How dielectric screening in two-dimensional crystals affects the convergence of excited-state calculations: Monolayer MoS 2. _Physical Review B_ 2013, _88_ , 245309
  * Qiu et al. 2016 Qiu, D. Y.; Felipe, H.; Louie, S. G. Screening and many-body effects in two-dimensional crystals: Monolayer MoS 2. _Physical Review B_ 2016, _93_ , 235435
  * Shishkin and Kresse 2007 Shishkin, M.; Kresse, G. Self-consistent G W calculations for semiconductors and insulators. _Physical Review B_ 2007, _75_ , 235102
  * Schmidt et al. 2017 Schmidt, P. S.; Patrick, C. E.; Thygesen, K. S. Simple vertex correction improves G W band energies of bulk and two-dimensional crystals. _Physical Review B_ 2017, _96_ , 205206
  * Shishkin et al. 2007 Shishkin, M.; Marsman, M.; Kresse, G. Accurate quasiparticle spectra from self-consistent GW calculations with vertex corrections. _Physical review letters_ 2007, _99_ , 246403
  * Wang et al. 2015 Wang, X.; Jones, A. M.; Seyler, K. L.; Tran, V.; Jia, Y.; Zhao, H.; Wang, H.; Yang, L.; Xu, X.; Xia, F. Highly anisotropic and robust excitons in monolayer black phosphorus. _Nature nanotechnology_ 2015, _10_ , 517
  * Klimeš et al. 2014 Klimeš, J.; Kaltak, M.; Kresse, G. Predictive G W calculations using plane waves and pseudopotentials. _Physical Review B_ 2014, _90_ , 075125
  * Klots et al. 2014 Klots, A.; Newaz, A.; Wang, B.; Prasai, D.; Krzyzanowska, H.; Lin, J.; Caudel, D.; Ghimire, N.; Yan, J.; Ivanov, B. et al. Probing excitonic states in suspended two-dimensional semiconductors by photocurrent spectroscopy. _Scientific reports_ 2014, _4_
  * Ugeda et al. 2014 Ugeda, M. M.; Bradley, A. J.; Shi, S.-F.; Felipe, H.; Zhang, Y.; Qiu, D. Y.; Ruan, W.; Mo, S.-K.; Hussain, Z.; Shen, Z.-X. et al. Giant bandgap renormalization and excitonic effects in a monolayer transition metal dichalcogenide semiconductor. _Nature materials_ 2014, _13_ , 1091
  * Hill et al. 2016 Hill, H. M.; Rigosi, A. F.; Rim, K. T.; Flynn, G. W.; Heinz, T. F. Band alignment in MoS2/WS2 transition metal dichalcogenide heterostructures probed by scanning tunneling microscopy and spectroscopy. _Nano letters_ 2016, _16_ , 4831–4837
  * Kormanyos et al. 2015 Kormanyos, A.; Burkard, G.; Gmitra, M.; Fabian, J.; Zolyomi, V.; Drummond, N. D.; Falḱo, V. k.p theory for two-dimensional transition metal dichalcogenide semiconductors. _2d Materials_ 2015, _2_ , 022001
  * Van De Walle and Martin 1989 Van De Walle, C.; Martin, R. Absolute Deformation Potentials - Formulation and ab initio Calculations for Semiconductors. _Physical Review Letters_ 1989, _62_ , 2028–2031
  * Resta et al. 1990 Resta, R.; Colombo, L.; Baroni, S. Absolute Deformation Potentials in Semiconductors. _Physical Review B_ 1990, _41_ , 12358–12361
  * Wiktor and Pasquarello 2016 Wiktor, J.; Pasquarello, A. Absolute deformation potentials of two-dimensional materials. _Phys. Rev. B_ 2016, _94_ , 245411
  * Marques et al. 2006 Marques, M.; Ullrich, C.; Nogueira, F.; Rubio, A.; Gross, E. Time-Dependent Density Functional Theory. 2006,
  * Hybertsen and Louie 1987 Hybertsen, M. S.; Louie, S. G. Ab initio static dielectric matrices from the density-functional approach. I. Formulation and application to semiconductors and insulators. _Phys. Rev. B_ 1987, _35_ , 5585–5601
  * Yan et al. 2011 Yan, J.; Mortensen, J. J.; Jacobsen, K. W.; Thygesen, K. S. Linear density response function in the projector augmented wave method: Applications to solids, surfaces, and interfaces. _Phys. Rev. B_ 2011, _83_ , 245122
  * Rozzi et al. 2006 Rozzi, C. A.; Varsano, D.; Marini, A.; Gross, E. K. U.; Rubio, A. Exact Coulomb cutoff technique for supercell calculations. _Phys. Rev. B_ 2006, _73_ , 205119
  * Hüser et al. 2013 Hüser, F.; Olsen, T.; Thygesen, K. S. Quasiparticle GW calculations for solids, molecules, and two-dimensional materials. _Phys. Rev. B_ 2013, _87_ , 235132
  * Onida et al. 2002 Onida, G.; Reining, L.; Rubio, A. Electronic excitations: density-functional versus many-body Greenś-function approaches. _Rev. Mod. Phys._ 2002, _74_ , 601–659
  * Sander et al. 2015 Sander, T.; Maggio, E.; Kresse, G. Beyond the Tamm-Dancoff approximation for extended systems using exact diagonalization. _Physical Review B_ 2015, _92_ , 045209
  * Mak et al. 2010 Mak, K. F.; Lee, C.; Hone, J.; Shan, J.; Heinz, T. F. Atomically thin MoS2: A new direct-gap semiconductor. _Phys. Rev. Lett._ 2010, _105_ , 2–5
  * Hüser et al. 2013 Hüser, F.; Olsen, T.; Thygesen, K. S. How dielectric screening in two-dimensional crystals affects the convergence of excited-state calculations: Monolayer MoS2. _Phys. Rev. B_ 2013, _88_ , 245309
  * Latini et al. 2015 Latini, S.; Olsen, T.; Thygesen, K. S. Excitons in van der Waals heterostructures: The important role of dielectric screening. _Phys. Rev. B_ 2015, _92_ , 245123
  * Da Jornada et al. 2017 Da Jornada, F. H.; Qiu, D. Y.; Louie, S. G. Nonuniform sampling schemes of the Brillouin zone for many-electron perturbation-theory calculations in reduced dimensionality. _Physical Review B_ 2017, _95_
  * Drueppel et al. 2017 Drueppel, M.; Deilmann, T.; Krueger, P.; Rohlfing, M. Diversity of trion states and substrate effects in the optical properties of an MoS¡sub¿2¡/sub¿ monolayer. _Nature Communications_ 2017, _8_ , 2117
  * Mouri et al. 2017 Mouri, S.; Zhang, W.; Kozawa, D.; Miyauchi, Y.; Eda, G.; Matsuda, K. Thermal dissociation of inter-layer excitons in MoS ¡sub¿2¡/sub¿ /MoSe ¡sub¿2¡/sub¿ hetero-bilayers. _Nanoscale_ 2017, _9_ , 6674–6679
  * Chen et al. 2016 Chen, H.; Wen, X.; Zhang, J.; Wu, T.; Gong, Y.; Zhang, X.; Yuan, J.; Yi, C.; Lou, J.; Ajayan, P. M. et al. Ultrafast formation of interlayer hot excitons in atomically thin MoS 2 /WS 2 heterostructures. _Nat. Commun._ 2016, _7_ , 1–8
  * Fang et al. 2014 Fang, H.; Battaglia, C.; Carraro, C.; Nemsak, S.; Ozdol, B.; Kang, J. S.; Bechtel, H. A.; Desai, S. B.; Kronast, F.; Unal, A. A. et al. Strong interlayer coupling in van der Waals heterostructures built from single-layer chalcogenides. _Proc. Natl. Acad. Sci._ 2014, _111_ , 6198–6202
  * Wilson et al. 2017 Wilson, N. R.; Nguyen, P. V.; Seyler, K.; Rivera, P.; Marsden, A. J.; Laker, Z. P.; Constantinescu, G. C.; Kandyba, V.; Barinov, A.; Hine, N. D. et al. Determination of band offsets, hybridization, and exciton binding in 2D semiconductor heterostructures. _Sci. Adv._ 2017, _3_ , e1601832
  * Ceballos et al. 2015 Ceballos, F.; Bellus, M. Z.; Chiu, H.-Y.; Zhao, H. Probing charge transfer excitons in a MoSe2-WS2 van der Waals heterostructure. _Nanoscale_ 2015, _7_ , 17523–17528
  * Liu et al. 2014 Liu, H.; Neal, A. T.; Zhu, Z.; Luo, Z.; Xu, X.; Tománek, D.; Ye, P. D. Phosphorene: An unexplored 2D semiconductor with a high hole mobility. _ACS Nano_ 2014, _8_ , 4033–4041
  * Yang et al. 2015 Yang, J.; Xu, R.; Pei, J.; Myint, Y. W.; Wang, F.; Wang, Z.; Zhang, S.; Yu, Z.; Lu, Y. Optical tuning of exciton and trion emissions in monolayer phosphorene. _Light Sci. Appl._ 2015, _4_ , 1–7
  * Takagi et al. 1994 Takagi, S.; Toriumi, A.; Iwase, M. On the universality of inversion layer mobility in Si MOSFET’s: Part I-effects of substrate impurity concentration. _IEEE Transactions on Electron Devices_ 1994, _41_ , 2357–2362
  * Cui et al. 2015 Cui, X.; Lee, G.-H.; Kim, Y. D.; Arefe, G.; Huang, P. Y.; Lee, C.-H.; Chenet, D. A.; Zhang, X.; Wang, L.; Ye, F. et al. Multi-terminal transport measurements of MoS2 using a van der Waals heterostructure device platform. _Nature nanotechnology_ 2015, _10_ , 534–540
  * Jin et al. 2014 Jin, Z.; Li, X.; Mullen, J. T.; Kim, K. W. Intrinsic transport properties of electrons and holes in monolayer transition-metal dichalcogenides. _Phys. Rev. B_ 2014, _90_ , 045422
  * Gong et al. 2017 Gong, C.; Li, L.; Li, Z.; Ji, H.; Stern, A.; Xia, Y.; Cao, T.; Bao, W.; Wang, C.; Wang, Y. et al. Discovery of intrinsic ferromagnetism in two-dimensional van der Waals crystals. _Nature_ 2017, _546_ , 265–269
  * Bon 2018 Strong room-temperature ferromagnetism in VSe2 monolayers on van der Waals substrates. _Nat. Nanotechnol._ 2018, _13_ , 289–293
  * Huang et al. 2018 Huang, C.; Du, Y.; Wu, H.; Xiang, H.; Deng, K.; Kan, E. Prediction of Intrinsic Ferromagnetic Ferroelectricity in a Transition-Metal Halide Monolayer. _Phys. Rev. Lett._ 2018, _120_ , 147601
  * Mermin and Wagner 1966 Mermin, N. D.; Wagner, H. Absence of Ferromagnetism or Antiferromagnetism in One- or Two-Dimensional Isotropic Heisenberg Models. _Physical Review Letters_ 1966, _17_ , 1133–1136
  * Lado and Fernández-Rossier 2017 Lado, J. L.; Fernández-Rossier, J. On the origin of magnetic anisotropy in two dimensional CrI3. 2017,
  * Olsen 2017 Olsen, T. Assessing the performance of the random phase approximation for exchange and superexchange coupling constants in magnetic crystalline solids. _Phys. Rev. B_ 2017, _96_ , 125143
  * Low et al. 2017 Low, T.; Chaves, A.; Caldwell, J. D.; Kumar, A.; Fang, N. X.; Avouris, P.; Heinz, T. F.; Guinea, F.; Martin-Moreno, L.; Koppens, F. Polaritons in layered two-dimensional materials. _Nature materials_ 2017, _16_ , 182
  * Gjerding et al. 2017 Gjerding, M. N.; Petersen, R.; Pedersen, T.; Mortensen, N. A.; Thygesen, K. S. Layered van der Waals crystals with hyperbolic light dispersion. _Nature communications_ 2017, _8_ , 320
  * Chen et al. 2012 Chen, J.; Badioli, M.; Alonso-González, P.; Thongrattanasiri, S.; Huth, F.; Osmond, J.; Spasenović, M.; Centeno, A.; Pesquera, A.; Godignon, P. et al. Optical nano-imaging of gate-tunable graphene plasmons. _Nature_ 2012, _487_ , 77
  * Andersen and Thygesen 2013 Andersen, K.; Thygesen, K. S. Plasmons in metallic monolayer and bilayer transition metal dichalcogenides. _Physical Review B_ 2013, _88_ , 155128
  * Gjerding et al. 2017 Gjerding, M. N.; Pandey, M.; Thygesen, K. S. Band structure engineered layered metals for low-loss plasmonics. _Nature communications_ 2017, _8_ , 15133
  * Cudazzo et al. 2011 Cudazzo, P.; Tokatly, I. V.; Rubio, A. Dielectric screening in two-dimensional insulators: Implications for excitonic and impurity states in graphane. _Phys. Rev. B_ 2011, _84_ , 085406
  * Chernikov et al. 2014 Chernikov, A.; Berkelbach, T. C.; Hill, H. M.; Rigosi, A.; Li, Y.; Aslan, O. B.; Reichman, D. R.; Hybertsen, M. S.; Heinz, T. F. Exciton binding energy and nonhydrogenic Rydberg series in monolayer WS 2. _Physical review letters_ 2014, _113_ , 076802
  * Olsen et al. 2016 Olsen, T.; Latini, S.; Rasmussen, F.; Thygesen, K. S. Simple Screened Hydrogen Model of Excitons in Two-Dimensional Materials. _Physical review letters_ 2016, _116_ , 056401
  * Jiang et al. 2017 Jiang, Z.; Liu, Z.; Li, Y.; Duan, W. Scaling Universality between Band Gap and Exciton Binding Energy of Two-Dimensional Semiconductors. _Phys. Rev. Lett._ 2017, _118_ , 266401
  * Choi et al. 2015 Choi, J.-H.; Cui, P.; Lan, H.; Zhang, Z. Linear Scaling of the Exciton Binding Energy versus the Band Gap of Two-Dimensional Materials. _Phys. Rev. Lett._ 2015, _115_ , 066403
  * Seh et al. 2016 Seh, Z. W.; Fredrickson, K. D.; Anasori, B.; Kibsgaard, J.; Strickler, A. L.; Lukatskaya, M. R.; Gogotsi, Y.; Jaramillo, T. F.; Vojvodic, A. Two-dimensional molybdenum carbide (MXene) as an efficient electrocatalyst for hydrogen evolution. _ACS Energy Letters_ 2016, _1_ , 589–594
  * Xie et al. 2013 Xie, J.; Zhang, H.; Li, S.; Wang, R.; Sun, X.; Zhou, M.; Zhou, J.; Lou, X. W. D.; Xie, Y. Defect-rich MoS2 ultrathin nanosheets with additional active edge sites for enhanced electrocatalytic hydrogen evolution. _Advanced materials_ 2013, _25_ , 5807–5813
  * Ridolfi et al. 2015 Ridolfi, E.; Le, D.; Rahman, T.; Mucciolo, E.; Lewenkopf, C. A tight-binding model for MoS2 monolayers. _Journal of Physics: Condensed Matter_ 2015, _27_ , 365501
  * Mostofi et al. 2008 Mostofi, A. A.; Yates, J. R.; Lee, Y.-S.; Souza, I.; Vanderbilt, D.; Marzari, N. wannier90: A tool for obtaining maximally-localised Wannier functions. _Computer physics communications_ 2008, _178_ , 685–699
  * Taherinejad et al. 2014 Taherinejad, M.; Garrity, K. F.; Vanderbilt, D. Wannier center sheets in topological insulators. _Physical Review B_ 2014, _89_ , 115102
  * Bokdam et al. 2014 Bokdam, M.; Amlaki, T.; Brocks, G.; Kelly, P. J. Band gaps in incommensurable graphene on hexagonal boron nitride. _Physical Review B_ 2014, _89_ , 201404
  * Tritsaris et al. 2016 Tritsaris, G. A.; Shirodkar, S. N.; Kaxiras, E.; Cazeaux, P.; Luskin, M.; Plecháč, P.; Cancès, E. Perturbation theory for weakly coupled two-dimensional layers. _Journal of Materials Research_ 2016, _31_ , 959–966
  * Andersen et al. 2015 Andersen, K.; Latini, S.; Thygesen, K. S. Dielectric genome of van der Waals heterostructures. _Nano letters_ 2015, _15_ , 4616–4621