# Coloring hypergraphs with excluded minors

Raphael Steiner

###### Abstract.

Hadwiger’s conjecture, among the most famous open problems in graph theory,
states that every graph that does not contain $K_{t}$ as a minor is properly
$(t-1)$-colorable.

The purpose of this work is to demonstrate that a natural extension of
Hadwiger’s problem to hypergraph coloring exists, and to derive some first
partial results and applications.

Generalizing ordinary graph minors to hypergraphs, we say that a hypergraph
$H_{1}$ is a minor of a hypergraph $H_{2}$, if a hypergraph isomorphic to
$H_{1}$ can be obtained from $H_{2}$ via a finite sequence of the following
operations:

  * •

deleting vertices and hyperedges,

  * •

contracting a hyperedge (i.e., merging the vertices of the hyperedge into a
single vertex).

First we show that a weak extension of Hadwiger’s conjecture to hypergraphs
holds true: For every $t\geq 1$, there exists a finite (smallest) integer
$h(t)$ such that every hypergraph with no $K_{t}$-minor is $h(t)$-colorable,
and we prove

$\left\lceil\frac{3}{2}(t-1)\right\rceil\leq h(t)\leq 2g(t)$

where $g(t)$ denotes the maximum chromatic number of graphs with no
$K_{t}$-minor. Using the recent result by Delcourt and Postle that
$g(t)=O(t\log\log t)$, this yields $h(t)=O(t\log\log t)$.

We further conjecture that $h(t)=\left\lceil\frac{3}{2}(t-1)\right\rceil$,
i.e., that every hypergraph with no $K_{t}$-minor is
$\left\lceil\frac{3}{2}(t-1)\right\rceil$-colorable for all $t\geq 1$, and
prove this conjecture for all hypergraphs with independence number at most
$2$.

By considering special classes of hypergraphs, the above additionally has some
interesting applications for ordinary graph coloring, such as:

  * •

every graph $G$ is $O(kt\log\log t)$-colorable or contains a $K_{t}$-minor
model all whose branch-sets are $k$-edge-connected,

  * •

every graph $G$ is $O(qt\log\log t)$-colorable or contains a $K_{t}$-minor
model all whose branch-sets are modulo-$q$-connected (i.e., every pair of
vertices in the same branch-set has a connecting path of prescribed length
modulo $q$),

  * •

by considering cycle hypergraphs of digraphs, we obtain known results on
strong minors in digraphs with large dichromatic number as special cases. We
also construct digraphs with dichromatic number
$\left\lceil\frac{3}{2}(t-1)\right\rceil$ not containing the complete digraph
on $t$ vertices as a strong minor, thus answering a question by Mészáros and
the author in the negative.

Department of Computer Science, Institute of Theoretical Computer Science, ETH
Zürich, Switzerland<EMAIL_ADDRESS>The author was
supported by an ETH Zurich Postdoctoral Fellowship.

##  1\. Preliminaries

In this short first section we introduce essential terminology and notation
used throughout the paper. The reader familiar with hypergraphs may want to
skip this technical section and consult it at a later stage should there be
any unclarities.

A _hypergraph_ is a tuple $(V,E)$ consisting of a finite set $V$ of vertices
and a set $E\subseteq 2^{V}\setminus\\{\emptyset\\}$ of hyperedges. Throughout
this paper, all hypergraphs and graphs considered are assumed to have only
hyperedges of size at least $2$, i.e., they are loopless. We refer to a
hyperedge $e\in E$ as a _graph edge_ if it is of size $2$.

We denote $V(H):=V$, $E(H):=E$ for the vertex- and edge-set of a hypergraph.
Given two hypergraphs $H_{1}$ and $H_{2}$, we say that $H_{1}$ is a
_subhypergraph of $H_{2}$_, in symbols, $H_{1}\subseteq H_{2}$, if
$V(H_{1})\subseteq V(H_{2})$ and $E(H_{1})\subseteq E(H_{2})$. We further say
that $H_{1}$ is a _proper_ subhypergraph if at least one of the two inclusions
above is strict.

Given a hypergraph $H$ and a set $W\subseteq V(H)$, we denote by $H[W]$ the
_subhypergraph of $H$ induced by $W$_, whose vertex-set is $W$ and whose edge-
set is $\\{e\in E(H)|e\subseteq W\\}$. For a hypergraph $H$ and an edge $e\in
E(H)$ we write $H-e:=(V(H),E(H)\setminus\\{e\\})$ for the subhypergraph
obtained by deleting $e$. Similarly, for a vertex $v\in V(H)$ we denote by
$H-v:=H[V(H)\setminus\\{v\\}]$ the induced subhypergraph obtained by deleting
$v$ and all the hyperedges containing $v$. For deleting sets $W\subseteq V(H)$
of vertices or $F\subseteq E(H)$ of hyperedges we use the analogous notation
$H-W:=H[V(H)\setminus W],H-F:=(V(H),E(H)\setminus F)$.

We say that a vertex subset $W$ is _independent_ in $H$, if $H[W]$ contains no
hyperedges, and we denote by $\alpha(H)$ the maximum size of an independent
set in $H$.

A hypergraph $H$ is _connected_ if for every partition of its vertex-set into
non-empty subsets $X$ and $Y$, there exists a hyperedge $e$ in $H$ with $e\cap
X\neq\emptyset\neq e\cap Y$. Equivalently, $H$ is connected if for every pair
$x,y$ of distinct vertices there exists $k\geq 2$, a sequence of vertices
$x_{1},\ldots,x_{k}$ in $H$ and a sequence $e_{1},\ldots,e_{k-1}$ of
hyperedges in $H$ such that $x=x_{1},y=x_{k}$ and $x_{i},x_{i+1}\in e_{i}$ for
all $i\in[k-1]$. We say that a subset $W$ of $V(H)$ is _connected_ in $H$ if
the induced subhypergraph $H[W]$ is connected.

In this manuscript, as usual, a _proper coloring_ of a hypergraph with a
color-set $S$ is defined as a mapping $c:V(H)\rightarrow S$ such that for any
$s\in S$ the color-class $c^{-1}(s)$ is independent in $H$. In other words, we
assign colors from $S$ to the vertices of $H$ such that no hyperedge is
monochromatic. The _chromatic number_ $\chi(H)$ is the minimum possible size
of a color-set that can be used for a proper coloring of $H$. Note that
$\chi(H)$ coincides with the ordinary chromatic number when $H$ is a graph.
For an integer $k$, a hypergraph $H$ is called _$k$ -color-critical_ if
$\chi(H)=k$ but $\chi(H^{\prime})<\chi(H)$ for every proper subhypergraph
$H^{\prime}$ of $H$.

A _fractional coloring_ of a hypergraph $H$ is an assignment of real-valued
weights $w(I)\geq 0$ to all independent vertex sets $I$ in $H$ such that
$\sum_{v\in I}{w(I)}\geq 1$ holds for every $v\in V(H)$. The _weight_ of a
fractional coloring is defined to be the total weight $\sum{w(I)}$, where the
sum is taken over all independent sets in $H$. Finally, the _fractional
chromatic number_ of a hypergraph $H$, denoted by $\chi_{f}(H)$, is the
smallest total weight a fractional coloring of $H$ can achieve (this infimum
is always attained). We refer to [2] for an example of previous usage of the
fractional chromatic number of hypergraphs.

A hypergraph is called _Sperner_ if it does not contain distinct hyperedges
$e,f$ such that $e\subset f$. Given a hypergraph $H$, we denote by
$\text{min}(H)$ the subhypergraph on the same vertex-set as $H$, whose
hyperedges are exactly the inclusion-wise minimal hyperedges of $H$, i.e.,
$e\in E(\text{min}(H))$ if and only if $e\in E(H)$ and there exists no
hyperedge $f\in E(H)\setminus\\{e\\}$ with $f\subset e$. It is easy to check
that a set of vertices is independent in $H$ if and only if it is independent
in $\text{min}(H)$. Also, it is clear by definition that $\text{min}(H)$ is
Sperner. This immediately implies the following.

######  Observation 1.

For every hypergraph $H$, the subhypergraph $\text{min}(H)\subseteq H$ is
Sperner and satisfies $\alpha(H)=\alpha(\text{min}(H))$,
$\chi(H)=\chi(\text{min}(H))$ and $\chi_{f}(H)=\chi_{f}(\text{min}(H))$.

##  2\. Introduction

Recall that given a graph $G_{1}$, another graph $G_{2}$ is a _minor_ of
$G_{1}$ if $G_{2}$ is isomorphic to at least one graph that can be obtained
from $G_{1}$ through a finite sequence of the following operations:

  * •

moving to a subgraph,

  * •

contracting an edge (i.e., identifying its endpoints into a common vertex, and
identifying parallel edges created by this process afterwards).

Maybe the most important open problem in graph coloring remains Hadwiger’s
conjecture, claiming the following relationship between minor-containment and
the chromatic number:

######  Conjecture 1 (Hadwiger 1943 [14]).

For every integer $t\geq 2$, if $G$ is a graph which does not contain $K_{t}$
as a minor, then $\chi(G)\leq t-1$.

In this paper, we develop and study a hypergraph analogue of Hadwiger’s
conjecture. For this purpose, we generalize the definition of a graph minor to
hypergraph minors in (what seems to the author) the most straightforward way
as follows:

######  Definition 1.

Let $H_{1}$ and $H_{2}$ be hypergraphs. We say that $H_{2}$ is a _minor_ of
$H_{1}$ if $H_{2}$ is isomorphic to at least one hypergraph that can be
obtained from $H_{1}$ via a finite sequence of the following operations:

  * •

moving to a subhypergraph,

  * •

contracting a hyperedge (i.e., identifying all vertices contained in the
hyperedge and removing loops or parallel hyperedges created by this process
afterwards).

To avoid confusion, let us give a more formal description of a hyperedge-
contraction in the following: Let a hypergraph $H$ and $e\in E(H)$ be given.
Let $v\notin V(H)$ be a “new” vertex, which will serve as the contraction
vertex for $e$. Define a map $\phi:V(H)\rightarrow(V(H)\setminus
e)\cup\\{v\\}$ as follows: $\phi(x):=x$ for every $x\in V(H)\setminus e$, and
$\phi(x):=v$ for every $x\in e$. We may now define the new hypergraph $H/e$
obtained by contracting $e$ as having vertex-set $V(H/e):=(V(H)\setminus
e)\cup\\{v\\}$ and edge-set $E(H/e):=\\{\phi(f)|f\in E(H),f\not\subseteq
e\\}$. Note that, if we start from a hypergraph $H$ which is Sperner, the
contracted hypergraph $H/e$ may no longer be Sperner.

We remark that various other definitions of minors for hypergraphs and
simplicial complexes have been considered in the literature that are not
addressed here, see for instance [1, 6, 17, 26].

For some of our proofs, it will be convenient to take a slightly different
view of graph and hypergraph minors using so-called _branch-sets_ and _minor
models_. We extend these notions (which are well-established in graph minor
theory) to hypergraphs as follows:

######  Definition 2.

Let $H_{1}$ and $H_{2}$ be hypergraphs. An _$H_{2}$ -minor model_ in $H_{1}$
is a collection $(B_{h})_{h\in V(H_{2})}$ of disjoint non-empty sets of
vertices in $H_{1}$, such that:

  * •

for every $h\in V(H_{2})$, the set $B_{h}$ is connected in $H_{1}$, and

  * •

for every hyperedge $f\in E(H_{2})$, there is a hyperedge $e\in E(H_{1})$ such
that $e\subseteq\bigcup_{h\in f}{B_{h}}$ and $e\cap B_{h}\neq\emptyset$ for
every $h\in f$.

The sets $B_{h},h\in V(H_{2})$ are called the _branch-sets_ of the
$H_{2}$-minor model.

It is easy to see from the definition that if a hypergraph $H_{1}$ contains an
$H_{2}$-minor model, then by contracting in $H_{1}$ all the edges within the
connected branch-sets (in arbitrary order) and potentially deleting some
superfluous edges and vertices afterwards, we obtain $H_{2}$ as a minor of
$H_{1}$. Similarly, it is not hard to see and left for the reader to verify
that if $H_{1}$ contains $H_{2}$ as a minor, then $H_{1}$ contains an
$H_{2}$-minor model.

#### New results.

The main insight of this paper is that the above notion of hypergraph minors
harmonizes well with the established notion of the hypergraph chromatic number
$\chi(H)$, and allows for extending known partial results for Hadwiger’s
conjecture to hypergraph coloring. To discuss these statements more formally,
we use the following notation: Given an integer $t\geq 2$, we denote by $g(t)$
the maximum chromatic number of a graph not containing $K_{t}$ as a minor, and
similarly we denote by $h(t)$ the largest chromatic number of a hypergraph not
containing $K_{t}$ as a minor. Note that at first glance it is far from
obvious why the function $h(t)$ should be well-defined for every value of $t$.
In our first main result below, we show that $h(t)$ exists for every $t\geq 2$
and, quite surprisingly, is tied to the graph function $g(t)$ by a factor of
at most $2$.

######  Theorem 1.

Every $K_{t}$-minor free hypergraph is $2g(t)$-colorable. Equivalently,
$h(t)\leq 2g(t)$.

The same proof idea as for Theorem 1 also works for fractional coloring,
yielding the following analogous result.

######  Proposition 1.

Let $t\geq 2$ be an integer, and let $g_{f}(t)$ be the supremum of the
fractional chromatic numbers taken over all $K_{t}$-minor free graphs. Then
every $K_{t}$-minor free hypergraph $H$ satisfies $\chi_{f}(H)\leq 2g_{f}(t)$.

Hadwiger’s conjecture has been proved for $t\leq 6$, the case $t=6$ was
settled by Robertson, Seymour and Thomas [21]. Thus, $g(t)=t-1$ for $t\leq 6$.
Asymptotically, the best known bound is that $g(t)=O(t\log\log t)$ as proved
by Delcourt and Postle [9]. Finally, it was proved by Reed and Seymour [20]
that $g_{f}(t)\leq 2(t-1)$. Combining these known partial results for
Hadwiger’s conjecture with Theorem 1 and Proposition 1, we get the following
set of immediate consequences.

######  Corollary 2.

Let $t\geq 2$ be an integer, and let $H$ be a hypergraph without a
$K_{t}$-minor. Then the following hold.

  * •

if $t\in\\{2,3,4,5,6\\}$, then $\chi(H)\leq 2t-2$.

  * •

for $t\geq 3$, we have $\chi(H)\leq Ct\log\log t$, where $C>0$ is some
absolute constant.

  * •

$\chi_{f}(H)\leq 4t-4$.

Given that $h(t)$ exists for every integer $t\geq 2$, it is tempting to hope
or conjecture that Hadwiger’s conjecture generalizes one-to-one to
hypergraphs, in the sense that $h(t)=t-1$ for every $t\geq 2$. However, a more
careful thought shows that this is not the case, and that in fact
$h(t)\geq\left\lceil\frac{3}{2}(t-1)\right\rceil$ for every integer $t\geq 2$.

######  Observation 2.

For $t\geq 2$ the complete $3$-uniform hypergraph $H=K_{3(t-1)}^{(3)}$ does
not contain $K_{t}$ as a minor and has chromatic number
$\chi(H)=\left\lceil\frac{3}{2}(t-1)\right\rceil$. Thus,
$h(t)\geq\left\lceil\frac{3}{2}(t-1)\right\rceil$.

###### Proof.

A set of vertices is independent in $H$ if and only if it has size at most
$2$, which immediately yields
$\chi(H)=\left\lceil\frac{3}{2}(t-1)\right\rceil$. Next suppose towards a
contradiction that $H$ contains $K_{t}$ as a minor. Then $H$ must contain a
$K_{t}$-minor model consisting of $t$ disjoint and connected branch-sets
$(B_{i})_{i=1}^{t}$, such that for every distinct $i,j\in[t]$ there is a
hyperedge $e$ of $H$ contained in $B_{i}\cup B_{j}$ with $e\cap
B_{i}\neq\emptyset\neq e\cap B_{j}$. Note that no branch-set $B_{i}$ can be of
size $2$, since no such set is connected in $H$. Furthermore, there can be at
most one branch-set of size $1$: If there were distinct $i,j$ with
$|B_{i}|=|B_{j}|=1$, then $B_{i}\cup B_{j}$ would be too small to host a
hyperedge of $H$. Consequently

$3(t-1)=|V(H)|\geq\sum_{i=1}^{t}{|B_{i}|}\geq 3(t-1)+1,$

a contradiction, and this concludes the proof. ∎

Despite a significant effort, we were not able to find examples providing
better lower bounds on $h(t)$ than the one given by the previous proposition.
This finally leads us towards a hypergraph analogue of Hadwiger’s conjecture
as follows:

######  Conjecture 2.

For every integer $t\geq 2$ we have
$h(t)=\left\lceil\frac{3}{2}(t-1)\right\rceil$. In other words, if a
hypergraph $H$ does not contain $K_{t}$ as a minor, then
$\chi(H)\leq\left\lceil\frac{3}{2}(t-1)\right\rceil$.

Intriguingly,Conjecture 2 remains open even for $K_{3}$-minor-free
hypergraphs. The best upper bound on the chromatic number of $K_{3}$-minor
free hypergraphs we are aware of is $4$, provided by Corollary 2.

######  Problem 1.

Is every $K_{3}$-minor-free hypergraph $3$-colorable?

We remark that independently of our work, van der Zypen [24] has stated an
extension of Hadwiger’s conjecture to hypergraphs. However, his alternative
conjecture uses a much less restricted version of hypergraph minors, hence
leading to a more restricted class of hypergraphs with no $K_{t}$-minor. For
instance, according to the definition in [24], every hypergraph consisting of
a single hyperedge on $t$ vertices would contain $K_{t}$ as a minor. An
argument outlined in [25] shows that for _finite_ values of $t$ van der
Zypen’s conjecture is a consequence of the ordinary Hadwiger’s conjecture for
graphs. Since our focus in this paper is on finite hypergraphs, we will not
discuss this variant in more detail here.

As additional evidence for our Conjecture 2 we verify it for all hypergraphs
without $3$-vertex independent sets. This is a natural special case to look
at, due to the considerable attention that the special case of Hadwiger’s
conjecture for graphs with independence number $2$ has received in the past,
see e.g. [4, 5, 8, 10, 11, 15, 19].

######  Theorem 3.

Let $t\geq 2$ be an integer, and let $H$ be a hypergraph such that
$\alpha(H)\leq 2$. If $H$ does not contain $K_{t}$ as a minor, then
$\chi(H)\leq\left\lceil\frac{3}{2}(t-1)\right\rceil$.

#### Applications.

We present three simple examples of how our bounds for coloring $K_{t}$-minor
free hypergraphs can be applied to produce new or recover known results for
coloring graphs and directed graphs with excluded minor-like substructures. We
believe that more applications of a similar flavour will be found in the
future.

Our first two applications address the following natural question. While
Hadwiger’s conjecture guarantees the existence of a $K_{t}$-minor model with
connected branch-sets in graphs with high chromatic number, in principle these
are not very dense structures, as every branch-set could span a tree only.
However, intuitively, graphs of high chromatic number should also contain
$K_{t}$-minor models with “richer” branch-sets (i.e., denser, of higher
connectivity, etc). Our first result in this direction confirms this intuition
by proving that a very moderate bound on the chromatic number suffices to
guarantee high edge-connectivity in the branch-sets.

######  Theorem 4.

There exists an absolute constant $C>0$ such that for every pair of integers
$k\geq 1,t\geq 3$ every graph $G$ satisfying $\chi(G)>Ckt\log\log t$ contains
a $K_{t}$-minor model with branch-sets $(B_{i})_{i=1}^{t}$, such that for each
$i\in[t]$ the induced subgraph $G[B_{i}]$ is $k$-edge-connected. Furthermore,
for any distinct $i,j\in[t]$ there are $k$ distinct edges in $G$ connecting
$B_{i}$ and $B_{j}$.

In our next application of Theorem 1 we consider another way of strengthening
the connectivity requirement for the branch-sets of a complete minor, by
requiring that distinct vertices in the same branch-set can be connected by a
path of any desired length modulo $q$. For $q=2$, this is somewhat reminiscent
of (but not equivalent to) the recently popular notion of _odd minors_. The
interested reader may consult e.g. [12] for a definition and background.

######  Definition 3.

Let $q\geq 2$ be an integer and $G$ a graph. We say that $G$ is _modulo
$q$-connected_ if for every pair of distinct vertices $u,v\in V(G)$ and every
residue $r\in\\{0,1,\ldots,q-1\\}$ there exists a path $P$ in $G$ with
endpoints $u,v$ and length $\ell(P)\equiv_{q}r$.

######  Theorem 5.

There exists an absolute constant $c>0$ such that for every pair of integers
$q\geq 2$, $t\geq 3$ every graph $G$ satisfying $\chi(G)>Cqt\log\log t$
contains a $K_{t}$-minor model with branch-sets $(B_{i})_{i=1}^{t}$, such that
for each $i\in\\{1,\ldots,t\\}$ the induced subgraph $G[B_{i}]$ is
modulo-$q$-connected.

In our third and last application, we give a short reproof of the main result
from [16] on coloring digraphs with excluded strong complete minors. The
research on this topic was initiated by Axenovich, Girão, Snyder and Weber
[3], and then further addressed by Mészáros and the author [16]. To state the
result, we adopt the following terminology from [3, 16]:

For digraphs $D$ and $F$, we say that _$D$ contains $F$ as a strong minor_, if
there exist disjoint non-empty subsets $(B_{f})_{f\in V(F)}$ of $V(D)$ such
that $B_{f}$ induces a strongly connected subdigraph of $D$ for every $f\in
V(F)$ and for every arc $(f_{1},f_{2})$ in $F$, there is an arc from
$B_{f_{1}}$ to $B_{f_{2}}$ in $D$. The _dichromatic number_ $\vec{\chi}(D)$ of
a digraph $D$ is the smallest number of colors that can be used to color the
vertices of $D$ such that every color class spans an acyclic subdigraph of
$D$.

The following is a main result from [16]. By considering _cycle hypergraphs_
of digraphs, we will show that it is an immediate consequence of Theorem 1.
For $t\geq 1$ we denote by
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$ the complete digraph of
order $t$ (containing all possible $t(t-1)$ arcs).

######  Theorem 6.

If $D$ is a digraph, $t\geq 2$ an integer, and $D$ does not contain
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$ as a strong minor, then
$D$ has dichromatic number at most $h(t)\leq 2g(t)$.

It was raised as an open problem in [16] whether or not every digraph $D$ with
no $\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$ strong minor has
dichromatic number at most $t$. Inspired by our lower bound on $h(t)$ from
Proposition 2, we will actually show that this is _not_ the case:

######  Proposition 2.

For every $t\geq 2$ there is a digraph $D$ with no strong
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$-minor and dichromatic
number at least $\left\lceil\frac{3}{2}(t-1)\right\rceil$.

#### Structure of the paper.

In Section 3 we give the proofs of our main results, including Theorem 1,
Proposition 1 and Theorem 3. In Section 4 we give the formal proofs of the
three applications of these main results to graph and hypergraph coloring,
including the proofs of Theorem 4, Theorem 5, Theorem 6 and Proposition 2.

##  3\. Proofs of Theorem 1, Proposition 1 and Theorem 3

We start by giving the (joint111We decided to merge the proofs of these
results into one, since they are based on largely the same idea.) proof of
Theorem 1 and Proposition 1. The idea of the proof is to decompose the
hypergraph into connected and $2$-colorable pieces and derive a graph from
that partition.

###### Proof of Theorem 1 and Proposition 1.

Let $t\geq 2$ be an integer, and $H$ be a hypergraph with no $K_{t}$-minor.
Our goal is to show that $\chi(H)\leq 2g(t)$, and $\chi_{f}(H)\leq 2g_{f}(t)$.

W.l.o.g. we may assume that $H$ is Sperner, for if not then by Observation 1
the subhypergraph $\text{min}(H)$ is Sperner, also contains no $K_{t}$-minor
and has the same chromatic and fractional chromatic number as $H$.

Let us inductively construct a partition of the vertex-set $V(H)$ into non-
empty sets $(X_{i})_{i=1}^{n}$ for some number $n$ as follows: For $i\geq 1$,
as long as $X_{1}\cup\cdots\cup X_{i-1}\neq V(H)$, pick $X_{i}$ as a subset of
$V(H)\setminus(X_{1}\cup\cdots\cup X_{i-1})$, such that $X_{i}$ is inclusion-
wise maximal with respect to the following two properties:

  * •

$H[X_{i}]$ is connected, and

  * •

$\chi(H[X_{i}])\leq 2$.

Note that such a set always exists, since any singleton set in
$V(H)\setminus(X_{1}\cup\cdots\cup X_{i-1})$ satisfies both of the above
properties. We now define a graph $G$ by $V(G):=[n]$ and

$E(G):=\Set{\\{i,j\\}\in\binom{[n]}{2}\>}{\>\text{there exists }e\in
E(H)\text{ with }e\subseteq X_{i}\cup X_{j}\text{ and }e\cap
X_{i}\neq\emptyset\neq e\cap X_{j}}.$

Since $H[X_{i}]$ is connected for $i=1,\ldots,n$, by contracting (in arbitrary
order) all hyperedges of $H$ contained in $H[X_{i}]$ for some $i\in[n]$, we
obtain a hypergraph $\tilde{H}$ on $n$ vertices. It now follows directly from
the definition of $G$ that for every edge $\\{i,j\\}\in E(G)$, the pair
consisting of the two contraction vertices of $X_{i}$ and $X_{j}$ forms a
hyperedge in $\tilde{H}$. Hence, after deleting all edges in $\tilde{H}$ which
are not such pairs, we obtain a graph isomorphic to $G$. Thus, $G$ is a minor
of $H$. Since $H$ does not contain $K_{t}$ as a minor, the same must be true
for $G$, and it follows that $\chi(G)\leq g(t)$ and $\chi_{f}(G)\leq
g_{f}(t)$.

Claim 1. Let $e\in E(H)$. If $I(e):=\\{i\in[n]|e\cap X_{i}\neq\emptyset\\}$
forms an independent set in $G$, then there exists $j\in[n]$ such that
$e\subseteq X_{j}$.

###### Proof.

Suppose towards a contradiction that the claim is wrong, and let $e\in E(H)$
be chosen such that $|I(e)|$ is minimized among all hyperedges for which the
claim fails.

Let $j:=\min I(e)$ be the (index-wise) smallest element of $I(e)$. Since $e$
does not satisfy the claim, we have $e\not\subseteq X_{j}$ and hence
$Y:=e\setminus X_{j}\neq\emptyset$. By minimality of $j$ we have $Y\subseteq
X_{j+1}\cup\cdots\cup X_{n}$. If $I(e)=\\{j,j^{\prime}\\}$ for some
$j^{\prime}>j$, then by definition of $I(e)$ we have $e\subseteq X_{j}\cup
X_{j^{\prime}}$ and $e\cap X_{j}\neq\emptyset\neq e\cap X_{j^{\prime}}$. The
definition of $G$ now yields $\\{j,j^{\prime}\\}\in E(G)$, contradicting the
fact that $I(e)$ is an independent set in $G$. Moving on, we may therefore
assume that $|I(e)|\geq 3$. Let $I_{1},I_{2}$ be two non-empty disjoint sets
such that $I(e)\setminus\\{j\\}=I_{1}\cup I_{2}$. By definition, $X_{j}$ is
inclusion-wise maximal among the subsets $X$ of
$V(H)\setminus(X_{1}\cup\cdots\cup X_{j-1})$ for which $H[X]$ is connected and
$\chi(H[X])\leq 2$. We will now show that the strict superset $X_{j}\cup Y$ of
$X_{j}$ also satisfies these two properties, a contradiction which then
concludes the proof of Claim 1.

It remains to show that $H[X_{j}\cup Y]$ is also connected and $2$-colorable.
The connectivity follows directly from the facts that $H[X_{j}]$ is connected,
$Y=e\setminus X_{j}$ and $e\cap X_{j}\neq\emptyset$. Let now
$c:X_{j}\rightarrow\\{1,2\\}$ be a proper $2$-coloring of $H[X_{j}]$, and
extend $c$ to a $2$-coloring $c^{\prime}$ of $H[X_{j}\cup Y]$ by putting
$c^{\prime}(y):=1$ for every $y\in Y$ such that $y\in X_{i}$ for some $i\in
I_{1}$, and $c^{\prime}(y):=2$ for every $y\in Y$ such that $y\in X_{i}$ for
some $i\in I_{2}$. Towards a contradiction, suppose that there is a
monochromatic hyperedge $f$ in $H[X_{j}\cup Y]$ with respect to $c^{\prime}$.
Then since $f$ is monochromatic and $f\subseteq X_{j}\cup Y$, we conclude that
$I(f)\subseteq\\{j\\}\cup I_{1}$ or $I(f)\subseteq\\{j\\}\cup I_{2}$. In each
case, $I(f)\subsetneq I(e)$, and thus $I(f)$ is independent in $G$ and
strictly smaller than $I(e)$. Now our initial assumption on the minimality of
$|I(e)|$ tells us that $f$ satisfies the statement of Claim 1. We know however
that this is not the case: $f\subseteq X_{j}$ would imply that $f$ is a
monochromatic edge in the proper $2$-coloring $c$ of $H[X_{j}]$, which is
impossible, and similarly $f\subseteq X_{i}$ for some
$i\in[n]\setminus\\{j\\}$ would imply that $f\subseteq Y=e\setminus X_{j}$, a
contradiction since $H$ is Sperner. All in all, this concludes the argument
that $H[X_{j}\cup Y]$ is both connected and $2$-colorable, concluding the
proof of Claim 1. ∎

We can now argue that $\chi(H)\leq 2\chi(G)\leq 2g(t)$ and $\chi_{f}(H)\leq
2\chi_{f}(G)\leq 2g_{f}(t)$, completing the proof of Theorem 1.

To do so, for every $i\in[n]$, fix a proper $2$-coloring
$c_{i}:X_{i}\rightarrow\\{1,2\\}$ of $H[X_{i}]$.

To verify $\chi(H)\leq 2\chi(G)$, consider a proper coloring
$c_{G}:V(G)\rightarrow[\chi(G)]$ of $G$. Let
$c_{H}:V(H)\rightarrow[\chi(G)]\times\\{1,2\\}$ be defined as
$c_{H}(x):=(c_{G}(i),c_{i}(x))$ for every $x\in X_{i}$, $i\in[n]$. We claim
that $c_{H}$ defines a proper coloring of $H$. Suppose not, then there exists
$e\in E(H)$ (w.l.o.g. inclusion-wise minimal) such that all vertices in $e$
receive the same color under $c_{H}$, say $c_{H}(x)=(\alpha,\beta)$ for every
$x\in e$. This shows that for every $i\in[n]$ such that $e\cap
X_{i}\neq\emptyset$, we have $c_{G}(i)=\alpha$. Since $c_{G}$ is a proper
coloring of $G$, this means that (with the notation from Claim 1) the set
$I(e):=\\{i\in[n]|e\cap X_{i}\neq\emptyset\\}$ is independent in $G$. Hence,
we may apply Claim 1 to $e$, which yields that there exists $j\in[n]$ such
that $e\subseteq X_{j}$. We then have $c_{j}(x)=\beta$ for every $x\in e$,
contradicting the facts that $e$ is a hyperedge of $H[X_{j}]$ and that $c_{j}$
was chosen as a proper coloring of $H[X_{j}]$. This contradiction shows that
$c_{H}$ is indeed a proper coloring of $H$, yielding $\chi(H)\leq 2\chi(G)\leq
2g(t)$, as claimed.

To verify $\chi_{f}(H)\leq 2\chi_{f}(H)$, we proceed similarly. Denote by
$\mathcal{I}(G)$, $\mathcal{I}(H)$ the collections of independent sets in $G$
and $H$, and let $(w_{G}(I))_{I\in\mathcal{I}(G)}$ be a non-negative weight
assignment such that $\sum_{i\in I\in\mathcal{I}(G)}{w_{G}(I)}\geq 1$ for
every $i\in[n]$ and $\sum_{I\in\mathcal{I}(G)}{w_{G}(I)}=\chi_{f}(G)$. Note
that for every $i\in[n]$, the subsets $c_{i}^{-1}(1),c_{i}^{-1}(2)$ of $X_{i}$
are independent in $H$. Using Claim 1 this implies that for every
$I\in\mathcal{I}(G)$, and any string $s\in\\{1,2\\}^{I}$, the set

$J(I,s):=\bigcup_{i\in I}{c_{i}^{-1}(s_{i})}$

is independent in $H$.

We now define a weight assignment $w_{H}$ for $\mathcal{I}(H)$ by putting
$w_{H}(J(I,s)):=2^{1-|I|}w_{G}(I)$ for every $I\in\mathcal{I}(G)$ and
$s\in\\{1,2\\}^{I}$, and assigning weight $0$ to all remaining independent
sets in $H$. We then have for every $i\in[n]$ and $v\in X_{i}$:

$\sum_{v\in J\in\mathcal{I}(H)}{w_{H}(J)}=\sum_{i\in
I\in\mathcal{I}(G)}\sum_{\begin{subarray}{c}s\in\\{1,2\\}^{I}:\\\
s_{i}=c_{i}(v)\end{subarray}}{2^{1-|I|}w_{G}(I)}$ $=\sum_{i\in
I\in\mathcal{I}(G)}{2^{|I|-1}(2^{1-|I|}w_{G}(I))}=\sum_{i\in
I\in\mathcal{I}(G)}{w_{G}(I)}\geq 1.$

Therefore, $w_{H}$ is a legal weight assignment for $H$, and it follows that

$\chi_{f}(H)\leq\sum_{J\in\mathcal{I}(H)}{w_{H}(J)}=\sum_{I\in\mathcal{I}(G)}{2^{|I|}(2^{1-|I|}w_{G}(I))}=2\sum_{I\in\mathcal{I}(G)}{w_{G}(I)}=2\chi_{f}(G),$

as desired. ∎

We proceed by preparing the proof of Theorem 3. A crucial ingredient to that
proof is the following lemma. We note that its statement restricted to graphs
is well-known (compare [10]), and that our proof follows similar lines as the
one in the case of graphs.

######  Lemma 7.

Let $H$ be a hypergraph on $n$ vertices satisfying $\alpha(H)\leq 2$. Then $H$
contains $K_{\lceil n/3\rceil}$ as a minor.

###### Proof.

For every hypergraph $H$ with $\alpha(H)\leq 2$ we may instead consider
$\text{min}(H)$. By Observation 1 this subhypergraph satisfies
$\alpha(\text{min}(H))=\alpha(H)\leq 2$, is Sperner, and if it contains
$K_{\lceil n/3\rceil}$ as a minor then the same is true for $H$. So in the
remainder, we assume w.l.o.g. that $H$ is Sperner. Note that this implies that
$H$ contains no $r$-edges for any $r>3$, since if it were to contain an
$r$-edge $e$, removing any vertex $x\in e$ would result in the independent set
$e\setminus\\{x\\}$ of size $r-1>2$ in $H$, which is impossible.

In the following let us call a subset $X\subseteq V(H)$ of exactly $3$
vertices _nice_ if the induced subhypergraph $H[X]$ contains as hyperedges
either exactly one hyperedge of size $3$ or exactly two graph edges. Let
$\mathcal{X}$ be a maximal collection of pairwise disjoint nice sets in $H$
(here we allow $\mathcal{X}=\emptyset$). Let $U:=\bigcup\mathcal{X}$ denote
the set of vertices contained in a member of $\mathcal{X}$. Then by maximality
$V(H)\setminus U$ does not contain a nice set. This in particular means that
$H-U$ does not contain any hyperedges of size more than $2$, so it is a graph,
and also no induced $3$-vertex path. It is well-known (and not hard to verify)
that the only graphs with no induced $3$-vertex paths are disjoint unions of
complete graphs. Since $\alpha(H-U)\leq\alpha(H)\leq 2$, this means that $H-U$
is the disjoint union of at most $2$ complete graphs. Let us write $n=a+b$,
where $a:=|U|$ and $b:=|V(H)\setminus U|$. From the above we find that there
exists a subset $C\subseteq V(H)\setminus U$ of size
$|C|\geq\frac{b}{2}\geq\frac{b}{3}$ such that $H[C]$ is a complete graph. We
now claim that the members of $\mathcal{X}$ together with the singletons in
$C$ form the branch-sets of a minor model for a $K_{t}$ of order
$t:=|\mathcal{X}|+|C|\geq\frac{a}{3}+\frac{b}{3}=\frac{n}{3}$ in $H$, which
will conclude the proof.

To see this, note that every member of $\mathcal{X}$ (and trivially every
singleton in $C$) induces a connected subhypergraph of $H$. Furthermore, for
every nice set $X\in\mathcal{X}$ and every vertex $y$ of $H$ outside $X$,
there exists an edge $e\in E(H)$ with $e\subseteq X\cup\\{y\\}$ and $y\in e$.
Indeed, if such an edge would not exist, then it is easy to see that an
independent set of size $2$ in $H[X]$ (which exists since $X$ is nice) joined
by $y$ would form an independent set of size $3$ in $H$, a contradiction.

The above implies that for any two distinct members $X,Y\in\mathcal{X}$ there
exists a hyperedge in their union intersecting both $X$ and $Y$, and also that
for every $X\in\mathcal{X}$ and $c\in C$ there is a hyperedge contained in
$X\cup\\{c\\}$ intersecting both $X$ and $\\{c\\}$. Since additionally $C$ is
a clique, this confirms our above claim that $\mathcal{X}$ together with
$\\{c\\}_{c\in C}$ yields a complete minor in $H$.

∎

To prove Theorem 3, we additionally need a structural result about small
color-critical hypergraphs established by Stiebitz, Storch and Toft in [22].
We adopt the following terminology from their paper:

######  Definition 4.

Given two hypergraphs $H_{1}=(V_{1},E_{1})$ and $H_{2}=(V_{2},E_{2})$ with
disjoint vertex-sets $V_{1}$ and $V_{2}$, their _Dirac-sum_ $H_{1}+H_{2}$ is
the hypergraph with the vertex-set $V=V_{1}\cup V_{2}$ and the edge-set
$E=E_{1}\cup E_{2}\cup\\{\\{x,y\\}|x\in V_{1},y\in V_{2}\\}$.

We may now state their result as follows.

######  Theorem 8 (Stiebitz, Storch and Toft [22], Theorem 1).

Let $H$ be a $k$-color critical hypergraph on at most $2k-2$ vertices. Then
there exist two non-empty disjoint subhypergraphs $H_{1}$ and $H_{2}$ of $H$
such that $H=H_{1}+H_{2}$.

We remark the following simple property of the Dirac sum for later use:

######  Observation 3.

$\chi(H_{1}+H_{2})=\chi(H_{1})+\chi(H_{2})$ for all hypergraphs $H_{1},H_{2}$
on disjoint vertex-sets.

We are now sufficiently prepared for the proof of Theorem 3.

###### Proof of Theorem 3.

Towards a contradiction, suppose the claim is false and let $t\geq 2$ be the
smallest integer for which there exists a counterexample. Let $H$ be a non-
trivial hypergraph with $|V(H)|+|E(H)|$ minimum such that:

  * •

$\alpha(H)\leq 2$

  * •

$H$ does not contain $K_{t}$ as a minor, and

  * •

$\chi(H)>\left\lceil\frac{3}{2}(t-1)\right\rceil$.

We start with a few observations about $H$.

Claim 1. $H$ is Sperner.

###### Subproof..

If $H$ is not Sperner, then $\text{min}(H)$ is a proper subhypergraph of $H$,
which by Observation 1 has the same chromatic and independence number as $H$,
and clearly also does not contain $K_{t}$ as a minor. This is a contradiction
to our minimality assumption on $H$. ∎

Claim 2. $H$ is $k$-color-critical, with
$k:=\left\lceil\frac{3}{2}(t-1)\right\rceil+1$.

###### Subproof.

By our assumptions on $H$ we have $\chi(H)\geq k$. Thus the claim follows if
we can show that for every proper subhypergraph $H^{\prime}\subsetneq H$ we
have $\chi(H^{\prime})\leq k-1=\left\lceil\frac{3}{2}(t-1)\right\rceil$.
Clearly, this is equivalent to showing that $H-v$ and $H-e$ for every choice
of $v\in V(H)$ and $e\in E(H)$ are
$\left\lceil\frac{3}{2}(t-1)\right\rceil$-colorable. Note for every $v\in
V(H)$ that $H-v$ is an induced subhypergraph of $H$, which directly implies
that $\alpha(H-v)\leq 2$. Trivially, also $H-v$ does not contain $K_{t}$ as a
minor, which means that we must have
$\chi(H-v)\leq\left\lceil\frac{3}{2}(t-1)\right\rceil$, for otherwise $H-v$
would be a counterexample to the claim of the theorem with
$|V(H-v)|+|E(H-v)|<|V(H)|+|E(H)|$, contradicting the minimality of $H$.

Let now $e\in E(H)$ be arbitrary. To argue that $H-e$ is
$\left\lceil\frac{3}{2}(t-1)\right\rceil$-colorable, we have to be a bit more
careful: Deleting the hyperedge $e$ could increase the independence number,
such that $H-e$ may fall out of the class of hypergraphs with independence
number $2$. We avoid this obstacle by instead considering the hypergraph
$H^{\prime}:=H/e$, obtained from $H$ by contracting $e$. Then it is not hard
to see that $\alpha(H^{\prime})\leq\alpha(H)=2$. Further note that
$H^{\prime}$ as a minor of $H$ cannot contain $K_{t}$ as a minor. Now the
minimality of $H$ as a counterexample and the fact
$|V(H^{\prime})|+|E(H^{\prime})|<|V(H)|+|E(H)|$ imply that
$\chi(H^{\prime})\leq\left\lceil\frac{3}{2}(t-1)\right\rceil$. Thus there
exists a proper coloring
$c^{\prime}:V(H^{\prime})\rightarrow\\{1,\ldots,\left\lceil\frac{3}{2}(t-1)\right\rceil\\}$
of $H^{\prime}$. Let
$c:V(H)\rightarrow\\{1,\ldots,\left\lceil\frac{3}{2}(t-1)\right\rceil\\}$ be
the coloring defined by $c(x):=c^{\prime}(\phi(x))$ for every $x\in V(H)$,
where $\phi:V(H)\rightarrow V(H/e)$ denotes the “contraction map” as defined
in the preliminaries. We claim that $c$ is a proper coloring of the hypergraph
$H\setminus e$. Indeed, consider any edge $f\in E(H)\setminus\\{e\\}$. Then by
Claim 1, we cannot have $f\subseteq e$, and hence the image $\phi(f)$ (by
definition of $H/e$) forms a hyperedge in $H/e$. If $f$ were to be
monochromatic with respect to the coloring $c$, then its image $\phi(f)$ would
be monochromatic with respect to the coloring $c^{\prime}$ of $H^{\prime}$.
Since this is impossible, we conclude that indeed $H\setminus e$ is properly
colored by $c$, proving that $\chi(H\setminus
e)\leq\left\lceil\frac{3}{2}(t-1)\right\rceil=k-1$ for every $e\in E(H)$. This
concludes the proof of Claim 2. ∎

In the following denote $n:=|V(H)|$. By Lemma 7 applied to $H$, we find that
$H$ contains $K_{\lceil n/3\rceil}$ as a minor, which by our assumptions on
$H$ implies that $t\geq\left\lceil\frac{n}{3}\right\rceil+1$. This yields
$n\leq 3(t-1)=2\cdot\frac{3}{2}(t-1)\leq 2(k-1)=2k-2$. Since by Claim 2 $H$ is
$k$-color-critical, we may apply Theorem 8 to $H$. This yields the existence
of a pair $(H_{1},H_{2})$ of non-empty disjoint subhypergraphs of $H$ such
that $H=H_{1}+H_{2}$.

In the following, let us denote by $t_{1}$ and $t_{2}$ the largest integers
such that $H_{1}$ contains $K_{t_{1}}$ as a minor, and such that $H_{2}$
contains $K_{t_{2}}$ as a minor, respectively. It is easy to see that any
sequence of deletions and contractions resulting in the minor of $K_{t_{1}}$
of $H_{1}$ and $K_{t_{2}}$ of $H_{2}$ can be concatenated to yield a sequence
of deletions and contractions in $H$. Performing this sequence of operations
is then easily seen to result in the minor
$K_{t_{1}}+K_{t_{2}}=K_{t_{1}+t_{2}}$ of $H$. By our assumptions on $H$, this
implies that $t_{1}+t_{2}\leq t-1$.

Since $H_{1}$ and $H_{2}$ are induced subhypergraphs of $H$, they satisfy
$\alpha(H_{1}),\alpha(H_{2})\leq\alpha(H)\leq 2$.

Hence, by our minimality assumption on $t$ at the beginning of this proof,
since $t_{i}+1\leq t_{1}+t_{2}<t$ for $i=1,2$, and since $H_{i}$ does not
contain $K_{t_{i}+1}$ as a minor for $i=1,2$, we find that
$\chi(H_{i})\leq\left\lceil\frac{3((t_{i}+1)-1)}{2}\right\rceil=\left\lceil\frac{3t_{i}}{2}\right\rceil$
for $i=1,2$.

Now pick (arbitrarily) a pair of vertices $x\in V(H_{1})$ and $y\in V(H_{2})$.
We distinguish two cases depending on the behaviour of the largest clique
minors in $H_{1}-x$ and $H_{2}-y$.

#### Case 1.

$H_{1}-x$ contains $K_{t_{1}}$ as a minor, and $H_{2}-y$ contains $K_{t_{2}}$
as a minor.

Then, repeating the argument from above, we find that
$(H_{1}-x)+(H_{2}-y)=H-\\{x,y\\}$ contains
$K_{t_{1}}+K_{t_{2}}=K_{t_{1}+t_{2}}$ as a minor. Also note that every vertex
in $H$ is connected by a graph edge to either $x$ or $y$. Therefore,
contracting the edge $\\{x,y\\}$, and then successively performing the
deletions and contractions that transform $H-\\{x,y\\}$ into
$K_{t_{1}+t_{2}}$, yields the complete graph $K_{t_{1}+t_{2}+1}$ as a minor of
$H$. Since we assumed that $H$ does not contain $K_{t}$ as a minor, this
implies that $t_{1}+t_{2}+1\leq t-1$. We may now use this to bound the
chromatic number of $H$ as follows:

$\chi(H)=\chi(H_{1})+\chi(H_{2})\leq\left\lceil\frac{3t_{1}}{2}\right\rceil+\left\lceil\frac{3t_{2}}{2}\right\rceil\leq\left(\frac{3t_{1}}{2}+\frac{1}{2}\right)+\left(\frac{3t_{2}}{2}+\frac{1}{2}\right)$
$=\frac{3(t_{1}+t_{2}+1)-1}{2}<\frac{3(t_{1}+t_{2}+1)}{2}\leq\frac{3(t-1)}{2}\leq\left\lceil\frac{3(t-1)}{2}\right\rceil,$

which is a contradiction to our initial assumption
$\chi(H)>\left\lceil\frac{3(t-1)}{2}\right\rceil$ on $H$. Hence, we obtain the
desired contradiction, which concludes the proof of the theorem in Case 1.

#### Case 2.

$H_{1}-x$ does not contain $K_{t_{1}}$ as a minor, or $H_{2}-y$ does not
contain $K_{t_{2}}$ as a minor. Due to symmetry, in the following we may
assume without loss of generality that $H_{1}-x$ does not contain $K_{t_{1}}$
as a minor.

Then we can obtain a better estimate on the chromatic number of $H_{1}$: Since
$H_{1}-x$ does not contain $K_{t_{1}}$ as a minor and since
$\alpha(H_{1}-x)\leq\alpha(H_{1})\leq 2$, by minimality of $t$ we obtain
$\chi(H_{1}-x)\leq\left\lceil\frac{3(t_{1}-1)}{2}\right\rceil$. Since the
deletion of a vertex can lower the chromatic number of a hypergraph by at most
one, we conclude:

$\chi(H)=\chi(H_{1})+\chi(H_{2})\leq(\chi(H_{1}-x)+1)+\chi(H_{2})$
$\leq\left\lceil\frac{3(t_{1}-1)}{2}\right\rceil+\left\lceil\frac{3t_{2}}{2}\right\rceil+1$

Consider first the case that both $t_{1}$ and $t_{2}$ are odd numbers, meaning
that both $3t_{1}$ and $3t_{2}$ are odd, and both $3(t_{1}-1)$ and
$3(t_{2}-1)$ are even. Then we may estimate, using the above:

$\chi(H)\leq\frac{3(t_{1}-1)}{2}+\frac{3t_{2}+1}{2}+1$
$=\frac{3(t_{1}+t_{2})}{2}\leq\frac{3(t-1)}{2}\leq\left\lceil\frac{3(t-1)}{2}\right\rceil.$

Again, this yields a contradiction to the assumption
$\chi(H)>\left\lceil\frac{3(t-1)}{2}\right\rceil$ and concludes the proof in
this case.

Finally, assume that at least one of $t_{1}$ and $t_{2}$ is even. Then we may
estimate:

$\chi(H)=\chi(H_{1})+\chi(H_{2})\leq\left\lceil\frac{3t_{1}}{2}\right\rceil+\left\lceil\frac{3t_{2}}{2}\right\rceil\leq\frac{3t_{1}}{2}+\frac{3t_{2}}{2}+\frac{1}{2}=\frac{3(t_{1}+t_{2})}{2}+\frac{1}{2}$
$\leq\frac{3(t-1)}{2}+\frac{1}{2}<\frac{3(t-1)}{2}+1\leq\left\lceil\frac{3(t-1)}{2}\right\rceil+1.$

This is a contradiction, since our initial assumption on $H$ means that
$\chi(H)\geq\left\lceil\frac{3(t-1)}{2}\right\rceil+1$.

This concludes the proof of the theorem also in Case 2. ∎

##  4\. Applications

###  4.1. Complete minors with branch-sets of high edge-connectivity

As a first simple application of Theorem 1 (or, rather Corollary 2), we want
to use it to give a short proof of Theorem 4. To reach this goal, we associate
with every graph $G$ and every integer $k\geq 1$ a hypergraph
$H_{\text{conn}}(G,k)$ as follows: Its vertex-set is $V(G)$, and a subset of
vertices $e\subseteq V(G)$ of size at least $2$ forms a hyperedge of
$H_{\text{conn}}(G,k)$ if and only if the induced subgraph $G[e]$ is $k$-edge-
connected. The next lemma collects simple but important properties of this
hypergraph.

######  Lemma 9.

Let $G$ be a graph and $k\geq 1$. Then

  1. (1)

If $W\subseteq V(G)$ is connected in $H_{\text{conn}}(G,k)$, then $G[W]$ is
$k$-edge-connected.

  2. (2)

If $\chi(G)>k$ then $H_{\text{conn}}(G,k)$ contains at least one hyperedge.

  3. (3)

$\chi(G)\leq k\chi(H_{\text{conn}}(G,k))$.

###### Proof.

For the proof, we abbreviate $H:=H_{\text{conn}}(G,k)$.

  1. (1)

Let $W\subseteq V(G)$ be such that $H[W]$ is connected. Suppose towards a
contradiction that $G[W]$ is not $k$-edge connected. Then there exists a set
$F$ of at most $k-1$ edges in $G[W]$ such that $G[W]-F$ is disconnected. Let
$X$ denote the vertex-set of a connected component in $G[W]-F$ and let
$Y:=W\setminus X$. Then both $X$ and $Y$ are non-empty, and there are at most
$k-1$ edges in $G[W]$ with endpoints in $X$ and $Y$. Since $H[W]$ is
connected, there has to exist a hyperedge $e$ in $H$ with $e\subseteq W=X\cup
Y$ such that $e\cap X\neq\emptyset\neq e\cap Y$. Then $G[e]$ is a $k$-edge
connected induced subgraph of $G[W]$ containing vertices of both $X$ and $Y$.
However, since $X$ and $Y$ can be separated in $G[W]$ by deleting at most
$k-1$ edges, the same is true for $G[e]$, a contradiction to the fact that
$G[e]$ is $k$-edge connected. This contradiction proves the claim, $G[W]$ must
indeed also be $k$-edge connected.

  2. (2)

Suppose $\chi(G)>k$. Let $G^{\prime}\subseteq G$ be a minimal subgraph of $G$
with chromatic number greater than $k$. Then clearly $G^{\prime}$ is
$(k+1)$-color critical. It is a well-known result, compare e.g. [23], that
every $(k+1)$-color-critical graph is $k$-edge-connected. Hence, $G^{\prime}$
is $k$-edge-connected. Denoting by $e:=V(G^{\prime})$ its vertex-set, we
easily see that also $G[e]$ must be $k$-edge-connected, that is, $e$ forms a
hyperedge of $H$.

  3. (3)

Let $c:V(H)\rightarrow S$ be a proper coloring of $H$ for some color-set $S$
of size $\chi(H)$. Then for every $s\in S$ the color-class $c^{-1}(s)$ forms
an independent set in $H$. In other words,
$H[c^{-1}(s)]=H_{\text{conn}}(G[c^{-1}(s)],k)$ contains no hyperedges. Using
item (2), this implies that $\chi(G[c^{-1}(s)])\leq k$ for every $s\in S$.
Thus,

$\chi(G)\leq\sum_{s\in S}{\chi(G[c^{-1}(s)])}\leq k|S|=k\chi(H),$

as desired.

∎

Using Lemma 9, Theorem 4 now falls out as an immediate consequence of our
hypergraph result Corollary 2.

###### Proof of Theorem 4.

By Corollary 2 there exists a constant $c>0$ such that $h(t)\leq ct\log\log t$
for $t\geq 3$. Let now $G$ be any given graph, $k\geq 1$ and $t\geq 3$
integers.

Let $C:=c$ and suppose $\chi(G)>Ckt\log\log t$. Then by Lemma 9
$\chi(H_{\text{conn}}(G,k))\geq\frac{1}{k}\chi(G)>ct\log\log t\geq h(t)$. This
means that $H_{\text{conn}}(G,k)$ contains $K_{t}$ as a minor, i.e., there is
a $K_{t}$-minor model in $H_{\text{conn}}(G,k)$ with branch-sets
$(B_{i})_{i=1}^{t}$. Then for every $i\in[t]$, the set $B_{i}$ is connected in
$H_{\text{conn}}(G,k)$ and thus $G[B_{i}]$ is $k$-edge-connected by Lemma 9,
(1). Now consider distinct $i,j\in[k]$. Then by definition of a minor model
there exists a hyperedge $e\subseteq B_{i}\cup B_{j}$ of
$H_{\text{conn}}(G,k)$ such that $e\cap B_{i}\neq\emptyset\neq e\cap B_{j}$.
But then, since $G[e]$ is a $k$-edge-connected graph, at least $k$ edges must
be spanned between $B_{i}$ and $B_{j}$ in $G$, and this proves the claim of
the theorem. ∎

###  4.2. Complete minors with modulo $q$-connected branch-sets

To derive Theorem 5, we use the following definition of a hypergraph. For any
graph $G$ and any number $q\geq 2$, we denote by $H_{\text{mod}}(G,q)$ the
hypergraph with vertex-set $V(G)$ and in which a subset $e\subseteq V(G)$ of
size at least $2$ is a hyperedge if and only if $G[e]$ is a modulo
$q$-connected graph. Similar to Lemma 9 from the previous section, the
following lemma relates the coloring and connectivity properties of
$H_{\text{mod}}(G,q)$ and $G$.

######  Lemma 10.

Let $G$ be a graph and $q\geq 2$. Then

  1. (1)

If $W\subseteq V(G)$ is connected in $H_{\text{mod}}(G,q)$, then $G[W]$ is
modulo $q$-connected.

  2. (2)

If $\chi(G)>315q$ then $H_{\text{mod}}(G,q)$ contains at least one hyperedge.

  3. (3)

$\chi(G)\leq 315q\cdot\chi(H_{\text{conn}}(G))$.

In the proof of the above Lemma, we need two statements from the literature,
the first relating chromatic number and vertex-connectivity, and the second
relating vertex-connectivity and modulo $q$-connectivity of graphs.

######  Theorem 11 (Girão and Narayanan [13]).

Let $k\geq 1$ be an integer. Every graph $G$ with $\chi(G)>7k$ contains a
subgraph $G^{\prime}$ such that $\chi(G^{\prime})\geq k$ and $G^{\prime}$ is
$k$-vertex-connected.

We remark that the constant in the previous theorem was recently improved from
$7$ to $3+\frac{1}{16}$ by Nguyen [18]. For simplicity, we stick with the
constant $7$ here.

######  Theorem 12 (Chen, Chen, Gao and Hu [7]).

Let $k$ and $m_{1},\ldots,m_{k}$ be positive integers, and let $G$ be a
$45(m_{1}+\ldots+m_{k})$-vertex-connected graph. Then at least one of the
following holds:

  * •

There exists a vertex-set $X\subseteq V(G)$ of size $|X|\leq 4k-2$ such that
$G-X$ is bipartite, or

  * •

for every choice of pairwise distinct vertices
$x_{1},\ldots,x_{k},y_{1},\ldots,y_{k}$ in $G$ and for every choice of
integers $d_{1},\ldots,d_{k}$ there exist $k$ disjoint paths
$P_{1},\ldots,P_{k}$ in $G$ such that $P_{i}$ has endpoints $x_{i}$ and
$y_{i}$, and its length is congruent to $d_{i}$ modulo $2m_{i}$.

Setting $k:=1$ in Theorem 12, we obtain the following special case.

######  Corollary 13.

Let $q\geq 2$ be an integer. Then every $45q$-vertex-connected graph $G$
contains a set $X$ of at most $2$ vertices such that $G-X$ is bipartite, or
$G$ is modulo $2q$-connected (and thus also modulo $q$-connected).

We are now prepared for the proof of Lemma 10.

###### Proof.

During the proof we use the abbreviation $H=H_{\text{mod}}(G,q)$.

  1. (1)

Let $W\subseteq V(G)$ be connected in $H_{\text{mod}}(H,q)$. Let a pair of
distinct vertices $x,y\in W$ as well as a residue $r\in\\{0,1,\ldots,q-1\\}$
be given to us. We have to show that there exists a path in $G[W]$ with
endpoints $x,y$ and whose length is congruent to $r$ modulo $q$. Since $H[W]$
is connected, for some $k\geq 2$ there exists a sequence
$x=x_{1},x_{2},\ldots,x_{k}=y$ of vertices in $W$ and hyperedges
$e_{1},\ldots,e_{k-1}$ of $H[W]$ such that $x_{i},x_{i+1}\in e_{i}$ for all
$i\in[k-1]$. We can further assume that $k\geq 2$ is chosen minimal such that
a sequence as above exists. If $k=2$, then $x$ and $y$ are distinct vertices
in the modulo $q$-connected induced subgraph $G[e_{1}]$ of $G[W]$, and thus
can be connected by a path of length $r$ modulo $q$, as desired. So assume
$k\geq 3$. Then our minimality assumption on $k$ implies that $x_{1}\notin
e_{2}\cup\cdots\cup e_{k-1}$. Note that $H[e_{2}\cup\cdots\cup e_{k-1}]$ forms
a connected subhypergraph of $H$, and hence we may apply Lemma 9, (1), to find
that $G[e_{2}\cup\cdots\cup e_{k-1}]$ is a connected subgraph of $G[W]$. Let
$Q$ be a shortest path in $G[e_{2}\cup\cdots\cup e_{k-1}]$ that connects
$y=x_{k}$ to a vertex in $e_{1}$ (such a path exists, since $x_{2}\in
e_{1}\cap e_{2}$). Let $z$ denote the other endpoint of $Q$. Then we have
$V(Q)\cap e_{1}=\\{z\\}$ since $Q$ is shortest. Furthermore, $x\neq z$, since
$x\notin e_{2}\cup\cdots\cup e_{k-1}$. Let $r^{\prime}\in\\{0,1,\ldots,q-1\\}$
be such that $r^{\prime}+\ell(Q)\equiv_{q}r$. Then we find a path $R$ in
$G[e_{1}]$ connecting $x$ and $z$ of length congruent to $r^{\prime}$ modulo
$q$. It is now apparent that $R\cup Q$ forms a path in $G[W]$ connecting $x$
and $y$ of length $\ell(R)+\ell(Q)\equiv_{q}r^{\prime}+\ell(Q)\equiv_{q}r$.
This concludes the proof that $G[W]$ is modulo $q$-connected.

  2. (2)

Since $\chi(G)>315q=7\cdot 45q$, we may apply Theorem 11 and find a
$45q$-vertex-connected subgraph $G^{\prime}$ of $G$ with $\chi(G^{\prime})\geq
45q$. W.l.o.g. we may assume that $G^{\prime}$ is an induced subgraph of $G$.
Applying Corollary 13, we find that there is a set $X$ of at most $2$ vertices
such that $G^{\prime}-X$ is bipartite, or $G^{\prime}$ is modulo
$q$-connected. However, the first option is not feasible, since
$\chi(G^{\prime}-X)\geq\chi(G^{\prime})-|X|\geq 45q-2>2$ for every set
$X\subseteq V(G^{\prime})$ of size $2$. Hence, $V(G^{\prime})$ forms a
hyperedge in $H_{\text{mod}}(G,q)$, proving the assertion.

  3. (3)

The proof is analogous to the proof of item (3) of Lemma 9, and is thus left
out.

∎

Similar as in the previous subsection, we can now derive Theorem 5 as a direct
consequence of Corollary 2.

###### Proof of Theorem 5.

Let $c>0$ be as guaranteed by Corollary 2 such that $h(t)\leq ct\log\log t$
for $t\geq 3$. Let $G$ be any given graph, $q\geq 2$ and $t\geq 3$ integers.
Define $C:=315c$ and suppose that $\chi(G)>Cqt\log\log t$. Then by Lemma 9
$\chi(H_{\text{mod}}(G,q))\geq\frac{1}{315q}\chi(G)>ct\log\log t\geq h(t)$.
Therefore $H_{\text{mod}}(G,q)$ contains $K_{t}$ as a minor. Let
$(B_{i})_{i=1}^{t}$ be corresponding branch-sets of a minor model, then for
every $i\in[t]$ the set $B_{i}$ is connected in $H_{\text{mod}}(G,q)$ and thus
$G[B_{i}]$ is modulo $q$-connected by Lemma 10, (1). For distinct $i,j\in[k]$
we have by definition of a minor model that there is a hyperedge $e\subseteq
B_{i}\cup B_{j}$ with $e\cap B_{i}\neq\emptyset\neq e\cap B_{j}$. Since $G[e]$
is connected, this means there is at least one edge in $G$ between $B_{i}$ and
$B_{j}$, and hence the set collection $(B_{i})_{i=1}^{t}$ indeed describes a
$K_{t}$-minor model in $G$, as desired. ∎

###  4.3. Strong complete minors in digraphs

To prove Theorem 6, it will be crucial to relate strong minors in digraphs
with the complete minors in their _cycle hypergraphs_. Given a digraph $D$,
its _cycle hypergraph_ $\mathcal{C}(D)$ has the same vertex-set $V(D)$ as $D$,
and a set $e\subseteq V(D)$ forms a hyperedge of $\mathcal{C}(D)$ if and only
if there exists a directed cycle $C$ in $D$ whose vertex-set equals $e$. It is
clear by definition that a set $W$ of vertices is independent in
$\mathcal{C}(D)$ if and only if $D[W]$ is acyclic. This directly yields that
$\vec{\chi}(D)=\chi(\mathcal{C}(D))$ for every digraph $D$. The next lemma
shows that complete minors in $\mathcal{C}(D)$ induce strong complete minors
in $D$.

######  Lemma 14.

Let $t\geq 1$ be an integer. If $\mathcal{C}(D)$ contains $K_{t}$ as a minor,
then $D$ contains $\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$ as a
strong minor.

###### Proof.

Let $(B_{i})_{i=1}^{t}$ be the branch-sets of a $K_{t}$-minor model in
$\mathcal{C}(D)$. Then for every $i\in[t]$, the subhypergraph
$\mathcal{C}(D)[B_{i}]$ is connected. We claim this means that $D[B_{i}]$ is
strongly connected. Indeed, if not then there is a partition of $B_{i}$ into
non-empty sets $X,Y$ such that no arc in $D$ starts in $X$ and ends in $Y$.
But then no directed cycle in $D[B_{i}]$ can intersect both $X$ and $Y$,
contradicting the connectivity of $\mathcal{C}(D)[B_{i}]$.

Next we claim that for every distinct $i,j\in[t]$ there is an arc from $B_{i}$
to $B_{j}$, and an arc from $B_{j}$ to $B_{i}$ in $D$. Indeed, there exists a
hyperedge $e$ in $\mathcal{C}(D)$ such that $e\subseteq B_{i}\cup B_{j}$ and
$e\cap B_{i}\neq\emptyset\neq e\cap B_{j}$. Then there is a directed cycle $C$
in $D$ with $V(C)=e$, and hence $C$ must traverse an arc starting in $B_{i}$
and ending in $B_{j}$, and vice versa.

With the above observations we see that $(B_{i})_{i=1}^{t}$ certify the
existence of a strong
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$-minor of $D$, as desired.
∎

The proof of Theorem 6 is now immediate using Theorem 1.

###### Proof of Theorem 6.

Let $D$ be a digraph with no strong
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$-minor. By Lemma 14 the
cycle hypergraph $\mathcal{C}(D)$ is $K_{t}$-minor free, and Theorem 1 implies
$\vec{\chi}(D)=\chi(\mathcal{C}(D))\leq h(t)\leq 2g(t)$. ∎

We conclude this section with the lower-bound construction for the dichromatic
number of digraphs with no strong
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$-minor.

###### Proof of Proposition 2.

Let $t\geq 2$ be given. Let $A,B,C$ be $3$ vertex-disjoint sets of size $t-1$,
and let $D$ be the digraph on the vertex-set $A\cup B\cup C$ with the
following arcs: For every pair of distinct vertices $u,v$ that are contained
together in one of $A$, $B$ or $C$, we add both the arcs $(u,v)$ and $(v,u)$.
Finally, we add all arcs from $A$ to $B$, from $B$ to $C$ and from $C$ to $A$.

For $\vec{\chi}(D)\geq\left\lceil\frac{3}{2}(t-1)\right\rceil$ it suffices to
note that every set of more than $2$ vertices spans a directed cycle in $D$,
and hence at least $\frac{3(t-1)}{2}$ colors are needed in any coloring with
acyclic color classes.

Next, suppose towards a contradiction that $D$ contains
$\overset{\text{\tiny$\longleftrightarrow$}}{K_{t}}$ as a strong minor. Then
there are disjoint non-empty sets $(B_{i})_{i=1}^{t}$ such that each of
$D[B_{i}],i\in[t]$ is strongly connected and such between any two sets
$B_{i},B_{j}$ there exist arcs in both directions. These conditions imply that
each $B_{i}$ is either contained in one of $A,B,C$ or intersects each of $A,B$
and $C$ in at least one vertex (and thus has size at least $3$ in this case).
Since $D$ contains $3(t-1)<3t$ vertices, at least one of the sets has to be
fully contained in either $A,B$ or $C$. W.l.o.g. assume that $B_{1}\subseteq
A$. Since $|A|=t-1$, there must exist $i\geq 2$ such that $B_{i}\cap
A=\emptyset$. Then by the above we have $B_{i}\subseteq B$ or $B_{i}\subseteq
C$. But then $B_{1}$ and $B_{i}$ are not connected by arcs in both directions,
a contradiction. This concludes the proof. ∎

## References

  * [1] I. Adler, T. Gavenčiak and T. Klimošová. Hypertree-depth and minors in hypergraphs. _Theoretical Computer Science_ , 463: 84–95 (2012).
  * [2] G. Araujo-Pardo, J. C. Díaz-Patiño, L. Montejano and D. Oliveros. The $(p,q)$-extremal problem and the fractional chromatic number of Kneser hypergraphs. _Discrete Mathematics_ , 339: 2819–2825 (2016).
  * [3] M. Axenovich, A. Girão, R. Snyder, L. Weber. Strong complete minors in digraphs. _Combinatorics, Probability and Computing_ , 31: 489–506 (2022).
  * [4] J. Blasiak. A special case of Hadwiger’s conjecture. _Journal of Combinatorial Theory, Series B_ , 97: 1056–1073 (2007).
  * [5] C. Bosse. A note on Hadwiger’s conjecture for $W_{5}$-free graphs with independence number two. _Discrete Mathematics_ , 342(12), 111595 (2019).
  * [6] J. Carmesin. Embedding simply connected $2$-complexes in $3$-space. I. A Kuratowski-type characterisation. _arXiv preprint_ , arXiv:1709.04642 (2019).
  * [7] G. Chen, Y. Chen, S. Gao and Z. Hu. Linked graphs with restricted lengths. _Journal of Combinatorial Theory, Series B_ , 98: 735–751 (2008).
  * [8] M. Chudnovsky and P. Seymour. Packing seagulls. _Combinatorica_ , 32: 251–282 (2012).
  * [9] M. Delcourt and L. Postle. Reducing linear Hadwiger’s conjecture to coloring small graphs. _arXiv preprint_ , arXiv:2108.01633 (2021-22).
  * [10] P. Duchet and H. Meyniel. On Hadwiger’s number and the stability number. _Annals of Discrete Mathematics_ , 13: 71–74 (1982).
  * [11] Z. Füredi, A. Gyárfás and G. Simonyi. Connected matchings and Hadwiger’s conjecture. _Combinatorics, Probability and Computing_ , 14:435–438 (2005).
  * [12] J. Geelen, B. Gerards, B. Reed, P. Seymour and A. Vetta. On the odd-minor variant of Hadwiger’s conjecture. _Journal of Combinatorial Theory, Series B_ , 99:20–29 (2009).
  * [13] A. Girão and B. Narayanan. Subgraphs of large connectivity and chromatic number. _Bulletin of the London Mathematical Society_ , https://doi.org/10.1112/blms.12569 (2022).
  * [14] H. Hadwiger. Über eine Klassifikation der Streckenkomplexe. _Vierteljahrsschrift Naturforschende Gesellschaft Zürich_ , 88: 133–143 (1943).
  * [15] M. Kriesell. On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs. _Discrete Mathematics_ , 310: 2714–2724 (2010).
  * [16] T. Mészáros and R. Steiner. Complete directed minors and chromatic number. _Journal of Graph Theory_ , https://doi.org/10.1002/jgt.22844 (2022).
  * [17] E. Nevo. Higher minors and van Kampen’s obstruction. _Mathematica Scandinavica_ , 101: 161–176 (2007).
  * [18] T. H. Nguyen. Highly connected subgraphs with large chromatic number. _arXiv preprint_ , arXiv:2206.00561 (2022).
  * [19] M. D. Plummer, M. Stiebitz and B. Toft. On a special case of Hadwiger’s conjecture. _Discussiones Mathematicae Graph Theory_ , 23: 333–363 (2003).
  * [20] B. Reed and P. Seymour. Fractional colouring and Hadwiger’s conjecture. _Journal of Combinatorial Theory, Series B_ , 74: 147–152 (1998).
  * [21] N. Robertson, P. Seymour and R. Thomas. Hadwiger’s conjecture for $K_{6}$-free graphs. _Combinatorica_ , 13: 279–361 (1993).
  * [22] M. Stiebitz, P. Storch and B. Toft. Decomposable and indecomposable critical hypergraphs. _Journal of Combinatorics_ , 7: 423–451 (2016).
  * [23] B. Toft. Colour-critical graphs and hypergraphs. _Journal of Combinatorial Theory, Series B_ , 16:145–161, 1974.
  * [24] D. van der Zypen. Hadwiger’s conjecture for hypergraphs. Unpublished manuscript,
https://raw.githubusercontent.com/dominiczypen/graph/main/hadwiger_hypergraph.pdf,
2021.

  * [25] D. van der Zypen. Conjecture on connected hypergraphs. _Math overflow post_ ,
https://mathoverflow.net/questions/419867/conjecture-on-connected-
hypergraphs?noredirect=1&lq=1, 2022.

  * [26] U. Wagner. Minors, embeddability, and extremal problems for hypergraphs. In _Thirty Essays on Geometric Graph Theory, J. Pach (eds.)_ , Springer, New York, https://doi.org/10.1007/978-1-4614-0110-0_31 (2013).


# BERT Embeddings for Automatic Readability Assessment

Joseph Marvin Imperial
National University
Manila, Philippines
<EMAIL_ADDRESS>

###### Abstract

Automatic readability assessment (ARA) is the task of evaluating the level of
ease or difficulty of text documents for a target audience. For researchers,
one of the many open problems in the field is to make such models trained for
the task show efficacy even for low-resource languages. In this study, we
propose an alternative way of utilizing the information-rich embeddings of
BERT models with handcrafted linguistic features through a combined method for
readability assessment. Results show that the proposed method outperforms
classical approaches in readability assessment using English and Filipino
datasets—obtaining as high as 12.4% increase in F1 performance. We also show
that the general information encoded in BERT embeddings can be used as a
substitute feature set for low-resource languages like Filipino with limited
semantic and syntactic NLP tools to explicitly extract feature values for the
task.

##  1 Introduction

Automatic readability assessment is the task of evaluating the level of ease
or difficulty of text documents such as web articles, story and picture books,
test materials, and medical prescriptions. Often readability levels can be
expressed in many forms: discrete values with grade and age levels such as in
the Common European Framework of Reference for Languages
(CEFR)111https://www.cambridgeenglish.org/exams-and-tests/cefr/, or with
continuous values from a given range such as in the famous Lexile Reading
Framework222https://lexile.com/. In machine learning setting, this task is
most often viewed as a classification task where an annotated set of corpora
is trained with its corresponding gold-standard labels evaluated by an expert
as mostly done in previous works Vajjala (2021); Chatzipanagiotidis et al.
(2021); Weiß and Meurers (2018); Xia et al. (2016); Reynolds (2016); Hancke et
al. (2012); Vajjala and Meurers (2012). Recent works have tried testing
unexplored resources by utilizing large pre-trained language models such as
Bidirectional Encoder Representations or BERT Devlin et al. (2019) which is
based on the attention-driven Transformer architecture by Vaswani et al.
(2017) by (a) directly processing the data to the network Martinc et al.
(2021); Tseng et al. (2019) or by (b) using the discrete output of the network
via transfer learning Deutsch et al. (2020) as an additional feature. For
these methods, however, evidence of efficacy are only seen in high-resources
readability datasets in English. Thus, we propose an alternative way of
incorporating the knowledge of large language models such as BERT by combining
its information-rich sentence embeddings as a separate feature set for
traditional machine learning algorithms with handcrafted linguistic features.
We argue that this method is not only low-resource friendly but also preserves
the semantic and syntactic information encoded by the attention heads of BERT
since the embeddings itself will be used. We show that such information can
act as a substitute for languages with limited tools for explicitly extracting
semantic and syntactic features where results describe non-significance in
difference of performances between models using semantic and syntactic
features versus models using BERT embeddings.

##  2 Previous Work

The first generation of readability formulas and indices date as early as
1920-1940s with the works of Thorndike (1921), Dale and Chall (1948), and
Flesch (1948) primarily using surface-based variables such as raw frequencies
and average values of sentences and words per document. The process for using
such indices requires manual computation and plugging of values to formulas
which can be tedious as the length of a document increases. Likewise, experts
argue that considering narrow, surface-based features do not entirely capture
the linguistic complexity of a given text Macahilig (2015); Collins-Thompson
and Callan (2004); Si and Callan (2001). Thus, incorporation of deeper,
linguistic variables such as a language’s semantics, syntax, morphology, and
discourse properties are imperative and worth exploring for the task. To
answer this call, the use of handcrafted linguistic features remained the most
popular type of input for training readability assessment models through the
years. Handcrafted linguistic features are often represented as real-valued
numbers serving as potential predictors of the difficulty of reading
materials. These features span on a wide range of linguistically motivated
factors that base on syntax, semantics, morphology, cohesion, and cognition to
name a few. These features also serve as the input in the form of vectors for
conventional readability assessment setups using traditional classification-
based algorithms. To note, not all linguistic features can be applied or
extracted for all languages as some have limited NLP tools suitable for use
especially for low-resource languages. Notable works in various languages such
as Greek Chatzipanagiotidis et al. (2021), German Weiss and Meurers (2019);
Weiß and Meurers (2018); Hancke et al. (2012), Bangla Sinha et al. (2012), and
Filipino Imperial and Ong (2021a, 2020) have used this approach in combination
with traditional machine learning algorithms such as Logistic Regression and
Support Vector Machines. Likewise, another reason why studies have resorted to
the classical approach of model building is that deep neural models are not
practical for the task without a large amount of training data.

The advent of large and complex pre-trained language models such as BERT and
its variations spawned a handful of studies on how these models fare with the
readability assessment tasks. The work of Martinc et al. (2021) on the
supervised experiment setup explored directly using English benchmark corpus
such as Weebit and OneStopEnglish as input for BERT via transfer learning
while Deutsch et al. (2020) explored using the final discrete output of BERT
as a feature for the same datasets. Results from both studies show
effectiveness of BERT for English data as direct input while no significant
improvement is seen when the discrete output itself is used as a feature.
While these results are remarkable, BERT’s effectiveness remain a gray area
for low-resource languages.

##  3 Task Definition

We define our task at hand as a supervised learning setup. Given a text
document $d$ where a feature vector $x=[x_{1},x_{2}\ldots,x_{n}]$ is
extracted, a model $M$ is trained using said collection of features $X$ along
with the gold label $Y$ or expert-identified readability level. The label is
relative in form (discrete or continuous) based on how readability levels are
categorized for each corpus.

Data | Doc Count | Sent Count | Vocab
---|---|---|---
OSE | 567 | 4,890 | 17,818
CCE | 168 | 20,945 | 78,965
Adarna House | 265 | 10,018 | 16,058
Table 1:  Data distribution for English and Filipino corpus.

##  4 Corpus

We describe each corpus used in the study below as well as the statistics and
breakdown in Table 1

OneStopEnglish. The OSE corpus is a collection of 567 texts in three different
reading levels (beginner, intermediate, and advanced) for adult ESL learners
from the MacMillan Education website333https://www.onestopenglish.com/. This
corpus was first used in the work of Vajjala and Lučić (2018) and has become
one of the most-used benchmark datasets for readability assessment and text
simplification in English.

Common Core Exemplars. The CCE dataset contains 168 prose texts from the
Appendix B of the Common Core State Standards Initiative
(CCSS)444http://www.corestandards.org/assets/Appendix_B.pdf for English
Language studies and first used by Flor et al. (2013) for readability
assessment. The initiative was a project of the National Governors Association
and the Council of Chief State School Officers in USA555http://www.ccsso.org.
The dataset is divided into three age-range categories: 2-5, 6-7, and 9-12.

Adarna House. The Adarna House corpus is a collection of 265 story books for
grades 1-3 from Adarna House Inc.666https://adarna.com.ph/, the largest
children’s literature publisher in the Philippines. This corpus has been used
by Imperial et al. (2019); Imperial and Ong (2020, 2021a) for readability
assessment in Filipino777Filipino is considered as a low-resource language
Cruz et al. (2020a, b).

Figure 1: The proposed combined training approach using sentence embeddings
from BERT model and extracted handcrafted linguistic feature sets.

##  5 BERT Embeddings + Handcrafted Linguistic Features

BERT’s efficacy on a wide range of NLP tasks stems from its implicit
capability to encode linguistic knowledge such as hierarchical parse trees
Hewitt and Manning (2019), parts of speech and syntactic chunks Liu et al.
(2019); Tenney et al. (2019), semantic roles Ettinger (2019) as well as entity
types and relations Tenney et al. (2019) to name a few. In view with this, we
find such amount of knowledge an extremely valuable resource which can
potentially improve performances of readability assessment models especially
for low-resource languages if used correctly. Thus, to maximize the potential
of BERT for low-resource readability assessment, we propose a combined
training of its raw embeddings with handcrafted linguistic feature sets
through a concatenation process and feeding them to traditional machine
learning algorithms. The embeddings of BERT generated by the multi-head
attention layers are information-rich, specifically on semantic and syntactic
knowledge Rogers et al. (2020), due to the nature of its training. We describe
our proposed architecture in Figure 1 with a sample Filipino sentence for
context.

##  6 Experiment Setup

For the OSE and CCE corpus in English, we extracted over 155 linguistic
features covering lexical diversity and density features, syntactic features
based on parse trees, morphosyntactic properties of lemmas, and word-level
psycholinguistic features. For the Adarna House corpus in Filipino, we
extracted over 54 linguistic features covering traditional surface-based
features, lexical features based on POS tags, language model features,
morphology based on verb inflection, and orthographic features based on
syllable pattern. The size of the BERT embeddings for all datasets remain
equal with a fixed dimension of $H$ = 768 since the base version of BERT for
English Devlin et al. (2019) and Filipino Cruz et al. (2020c); Cruz and Cheng
(2020, 2019) were used. The embeddings and extracted linguistic feature sets
were concatenated, for a total of 923 dimensions for combined features for
both English datasets and 823 for the Filipino dataset. Recipes for feature
extraction were obtained from the studies of Vajjala and Meurers (2016, 2014)
for English and Imperial and Ong (2020, 2021a, 2021b) for Filipino. We used
the sentence-transformers library by Reimers and Gurevych (2019) with mean
pooling option to extract BERT embedding representations for the readability
corpora888We release the script for extracting BERT embeddings at
https://github.com/imperialite/BERT-Embeddings-For-ARA.

For the traditional machine learning algorithms, we used three of the commonly
utilized in previous works: Logistic Regression, Support Vector Machines, and
Random Forest. Models for each dataset were trained on a 5-fold cross
validation procedure. We used weighted F1 as the overall metric for
performance evaluation.

##  7 Results

###  7.1 Ablation

We compared performances of models on three different setups, (a) linguistic
features only, (b) BERT sentence embeddings only, and (c) combined training of
the two feature embeddings to gauge the efficacy of the proposed framework.

Method | OSE | CCE | Adarna
---|---|---|---
Linguistic Features | 0.676 | 0.774 | 0.389
BERT Embeddings | 0.620 | 0.747 | 0.505
Combined Features (Ling + BERT) | 0.732 | 0.778 | 0.554
(a) Logistic Regression

Method | OSE | CCE | Adarna
---|---|---|---
Linguistic Features | 0.691 | 0.732 | 0.414
BERT Embeddings | 0.611 | 0.826 | 0.487
Combined Features (Ling + BERT) | 0.704 | 0.893 | 0.571
(b) Support Vector Machines

Method | OSE | CCE | Adarna
---|---|---|---
Linguistic Features | 0.683 | 0.842 | 0.423
BERT Embeddings | 0.439 | 0.770 | 0.504
Combined Features (Ling + BERT) | 0.690 | 0.861 | 0.467
(c) Random Forest

Table 2: F1 performance via training with (a) Logistic Regression, (b) Support
Vector Machines, and (c) Random Forest using handcrafted linguistic features,
BERT sentence embeddings, and combined training of both.

As described in Table 2, generally speaking, models trained using the proposed
combined training of handcrafted linguistic feature sets with contexual BERT
embeddings outperform both performances of only using each exclusively on
English and Filipino datasets. On average, we note an increase of performance
of 2.63% for OSE, 6.23% for CCE, and 12.4% in weighted F1 score for Adarna
House across all algorithms. From this, we infer that extracting and
incorporating the information-rich embeddings of any readability dataset using
BERT to commonly-used linguistic feature sets can substantially improve model
performance.

Interestingly, there are a few notable cases reported in Table 2 where BERT
embeddings alone outperformed the traditional method of using handcrafted
linguistic feature sets as primary input. These cases are evident in the all
models utilizing the Adarna House dataset in Filipino with an average increase
of 9.5% weighted F1 scores. From this, we infer that the general semantic and
syntactic knowledge implicitly encoded in BERT embeddings as detailed in
probing tasks from previous works Rogers et al. (2020); Hewitt and Manning
(2019); Liu et al. (2019); Tenney et al. (2019) may be significantly more
informative than the traditional handcrafted linguistic features for
discriminating reading difficulty. Consequently, this poses as a probable and
alternative solution for low-resource languages with little to no NLP tools
such as a good part-of-speech tagger, stemmer, syntactic parse tree extractor,
and morphological analyzer to name a few for manually extracting linguistic
information from documents. Since BERT models are trained in an self-
supervised manner, the overhead of developing these tools from scratch can be
disregarded, at least for readability assessment. We discuss further
experiments on this inference in the next section.

Model w/ Removed Features | OSE | CCE | Adarna
---|---|---|---
Logistic Regression | 0.744 | 0.865 | 0.492
Support Vector Machines | 0.615 | 0.869 | 0.507
Random Forest | 0.669 | 0.791 | 0.431
Full Model (Ling + BERT) | 0.732 | 0.893 | 0.571
Table 3: Performances of models via F1 score after retraining with semantic
and syntactic handcrafed linguistic features removed to test if information-
rich BERT embeddings can act as substitution for such features. Best
performing model utilizing combined features from Table 2 appended for
comparison.

Figure 2: Decomposing large feature sets on a 25%, 50%, 75%, 95%, and 100%
(full) variance percentages using PCA for Logistic Regression, Support Vector
Machines, and Random Forest (left to right).

###  7.2 Substituting Semantic and Syntactic Features for BERT Embeddings

To empirically test if BERT embeddings can act as substitute for semantic and
syntactic linguistic features for readability assessment, we removed features
from the three datasets that assume semantic and syntactic knowledge. For OSE
and CCE, we removed 56 features covering part-of-speech densities, lexical
richness, type-token densities, and general parse-tree based features. For
Adarna, we removed 22 features covering part-of-speech densities, type-token
densities, and verb inflection densities. There are no parse-tree based
features for Adarna House as there are currently no NLP tools for extracting
such feature set for Filipino. The rest of the linguistic features from the
datasets denoting other aspects of reading difficulty measurement such as
frequency-based features and syllable patterns remain unchanged. Models were
retrained using the three selected machine learning algorithms for comparison.

Results of substitution experiments can be found in Table 3. Generally
speaking, it is evident that models trained using the combined method still
outperforms models using the reduced feature set on the account of CCE and
Adarna data. However, we note the 1.2% increase in F1 score on the OSE data.
Stemming from this observation, we also note small differences in performances
of using the combined features against decreased features. In the CCE corpus,
the highest performing model using decreased features obtained 86.9% F1 score
which is less 2.4% than using the model with combined features. For the Adarna
data, the difference is 6.4%.

To identify if such difference is significant, we used a two-tailed test of
difference via Mann-Whitney U using the performance scores of models with
combined features and models with decreased features for all datasets. We
arrived at a $p$-value of 0.522 ($p>$0.5), meaning that the difference of the
scores between two groups is not significant999The distribution of the two
groups are of equal variances with $p$-value of 0.619.. Thus, we conclude that
BERT embeddings can be fully used as a substitute for semantic and syntactic
features if such information cannot be explicitly extracted from readability
data due to the lack of NLP tools and low-resourceness of other languages. To
add, since BERT models are trained in an self-supervised manner and there are
over 3,000 pretrained models from online
repositories101010https://huggingface.co/models, these resources and the
proposed combined training method as a viable option.

###  7.3 Feature Decomposition for Performance Boost

In extending the effort to improve the performance of BERT-enriched
readability assessment models and reduce feature size or dimensionality, we
resorted to the use of feature decomposition to the large feature vector sizes
(BERT + linguistic features) via Principal Components Analysis (PCA). PCA
works by projecting the overall feature set (often large) to a lower
dimensional property while preserving quality and information of features
Hotelling (1933). We experimented on differing values of variance percentages:
25, 50, 75, 95, and 100 (full, no feature removed). Results of feature
decomposition via PCA for each machine learning model are described in Figure
2.

For SVM and Random Forest, all datasets have the highest performances if all
features are retained (100 variance percentage). While for Logistic
Regression, 75 variance percentage obtained the highest performance with 82.7
F1 score for OSE, 95 variance percentage obtained the highest performance with
83.8% F1 score for CCE, and 100% or full features for Adarna. Thus, we infer
that there is no need to perform feature decomposition to find the principal
components as the highest-performing models for OSE, CCE, and Adarna use 100%
of the combined feature set (BERT + linguistic features).

##  8 Conclusion

In this study, we proposed an alternative way of combining information-rich
BERT embeddings with handcrafted linguistic features for the readability
assessment task. Results from our experiments showed that the method
outperforms classical, vanilla approaches in readability assessment using
English (OSE and CCE) and Filipino (Adarna) datasets in various machine
learning algorithms such as Logistic Regression, Support Vector Machines, and
Random Forest. We also demonstrated that the knowledge implicitly encoded in
BERT embeddings (semantic and syntactic information) can be used as a full
substitute feature set for low-resource languages like Filipino with limited
NLP tools to explicitly extract feature values for the task. We are looking
forward to the application of our proposed method to other languages
struggling with the extraction deep linguistic features to trained readability
assessment models. Future directions of the study include deeper exploration
of BERT such as isolating extracted embeddings for each of the twelve
attention layers.

##  9 Acknowledgments

We would like to thank Dr. Ani Almario from Adarna House, Dr. Sowmya Vajjala
from the National Research Council of Canada, and Dr. Michael Flor from ETS
for providing the Adarna, OSE, and CCE datasets respectively.

##  10 Ethical Considerations

We report that there are no major ethical concerns in the study as it involves
no human subjects nor discriminate any identifiable group of people. As for
the dataset, for Adarna House, permission was obtained from the publishing
house while for the OSE and CCE datasets, it remains open-sourced. As for
energy consumption, the study only uses pre-trained BERT models and the
authors did not actually perform the pre-training phase itself.

## References

  * Chatzipanagiotidis et al. (2021) Savvas Chatzipanagiotidis, Maria Giagkou, and Detmar Meurers. 2021.  Broad linguistic complexity analysis for Greek readability classification.  In _Proceedings of the 16th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 48–58, Online. Association for Computational Linguistics.
  * Collins-Thompson and Callan (2004) Kevyn Collins-Thompson and James P. Callan. 2004.  A language modeling approach to predicting reading difficulty.  In _Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004_ , pages 193–200, Boston, Massachusetts, USA. Association for Computational Linguistics.
  * Cruz et al. (2020a) Hilaria Cruz, Antonios Anastasopoulos, and Gregory Stump. 2020a.  A resource for studying chatino verbal morphology.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 2827–2831, Marseille, France. European Language Resources Association.
  * Cruz and Cheng (2019) Jan Christian Blaise Cruz and Charibeth Cheng. 2019.  Evaluating language model finetuning techniques for low-resource languages.  _arXiv preprint arXiv:1907.00409_.
  * Cruz and Cheng (2020) Jan Christian Blaise Cruz and Charibeth Cheng. 2020.  Establishing baselines for text classification in low-resource languages.  _arXiv preprint arXiv:2005.02068_.
  * Cruz et al. (2020b) Jan Christian Blaise Cruz, Julianne Agatha Tan, and Charibeth Cheng. 2020b.  Localization of fake news detection via multitask transfer learning.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 2596–2604, Marseille, France. European Language Resources Association.
  * Cruz et al. (2020c) Jan Christian Blaise Cruz, Julianne Agatha Tan, and Charibeth Cheng. 2020c.  Localization of Fake News Detection via Multitask Transfer Learning.  In _Proceedings of The 12th Language Resources and Evaluation Conference_ , pages 2589–2597.
  * Dale and Chall (1948) Edgar Dale and Jeanne S Chall. 1948.  A formula for predicting readability: Instructions.  _Educational research bulletin_ , pages 37–54.
  * Deutsch et al. (2020) Tovly Deutsch, Masoud Jasbi, and Stuart Shieber. 2020.  Linguistic features for readability assessment.  In _Proceedings of the Fifteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 1–17, Seattle, WA, USA → Online. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Ettinger (2019) Allyson Ettinger. 2019.  What BERT is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _CoRR_ , abs/1907.13528.
  * Flesch (1948) Rudolph Flesch. 1948.  A new readability yardstick.  _Journal of applied psychology_ , 32(3):221.
  * Flor et al. (2013) Michael Flor, Beata Beigman Klebanov, and Kathleen M. Sheehan. 2013.  Lexical tightness and text complexity.  In _Proceedings of the Workshop on Natural Language Processing for Improving Textual Accessibility_ , pages 29–38, Atlanta, Georgia. Association for Computational Linguistics.
  * Hancke et al. (2012) Julia Hancke, Sowmya Vajjala, and Detmar Meurers. 2012.  Readability classification for German using lexical, syntactic, and morphological features.  In _Proceedings of COLING 2012_ , pages 1063–1080, Mumbai, India. The COLING 2012 Organizing Committee.
  * Hewitt and Manning (2019) John Hewitt and Christopher D. Manning. 2019.  A structural probe for finding syntax in word representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4129–4138, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Hotelling (1933) H. Hotelling. 1933.  Analysis of a complex of statistical variables into principal components.  _Journal of Educational Psychology_ , 24:498–520.
  * Imperial and Ong (2020) Joseph Marvin Imperial and Ethel Ong. 2020.  Exploring hybrid linguistic feature sets to measure filipino text readability.  In _2020 International Conference on Asian Language Processing (IALP)_ , pages 175–180. IEEE.
  * Imperial and Ong (2021a) Joseph Marvin Imperial and Ethel Ong. 2021a.  Application of lexical features towards improvement of filipino readability identification of children’s literature.  _arXiv preprint arXiv:2101.10537_.
  * Imperial and Ong (2021b) Joseph Marvin Imperial and Ethel Ong. 2021b.  A simple post-processing technique for improving readability assessment of texts using word mover’s distance.  _CoRR_ , abs/2103.07277.
  * Imperial et al. (2019) Joseph Marvin Imperial, Rachel Edita Roxas, Erica Mae Campos, Jemelee Oandasan, Reyniel Caraballo, Ferry Winsley Sabdani, and Ani Rosa Almaroi. 2019.  Developing a machine learning-based grade level classifier for filipino children’s literature.  In _2019 International Conference on Asian Language Processing (IALP)_ , pages 413–418. IEEE.
  * Liu et al. (2019) Nelson F. Liu, Matt Gardner, Yonatan Belinkov, Matthew E. Peters, and Noah A. Smith. 2019.  Linguistic knowledge and transferability of contextual representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 1073–1094, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Macahilig (2015) Heidi B. Macahilig. 2015.  A content-based readability formula for Filipino texts.  _The Normal Lights_ , 8(1).
  * Martinc et al. (2021) Matej Martinc, Senja Pollak, and Marko Robnik-Šikonja. 2021.  Supervised and unsupervised neural approaches to text readability.  _Computational Linguistics_ , 47(1):141–179.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Reynolds (2016) Robert Reynolds. 2016.  Insights from Russian second language readability classification: complexity-dependent training requirements, and feature evaluation of multiple categories.  In _Proceedings of the 11th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 289–300, San Diego, CA. Association for Computational Linguistics.
  * Rogers et al. (2020) Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020.  A primer in BERTology: What we know about how BERT works.  _Transactions of the Association for Computational Linguistics_ , 8:842–866.
  * Si and Callan (2001) Luo Si and Jamie Callan. 2001.  A statistical model for scientific readability.  In _Proceedings of the Tenth International Conference on Information and Knowledge Management_ , CIKM ’01, page 574–576, New York, NY, USA. Association for Computing Machinery.
  * Sinha et al. (2012) Manjira Sinha, Sakshi Sharma, Tirthankar Dasgupta, and Anupam Basu. 2012.  New readability measures for Bangla and Hindi texts.  In _Proceedings of COLING 2012: Posters_ , pages 1141–1150, Mumbai, India. The COLING 2012 Organizing Committee.
  * Tenney et al. (2019) Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R. Thomas McCoy, Najoung Kim, Benjamin Van Durme, Samuel R. Bowman, Dipanjan Das, and Ellie Pavlick. 2019.  What do you learn from context? probing for sentence structure in contextualized word representations.  _CoRR_ , abs/1905.06316.
  * Thorndike (1921) Edward L Thorndike. 1921.  The teacher’s word book.
  * Tseng et al. (2019) Hou-Chiang Tseng, Hsueh-Chih Chen, Kuo-En Chang, Yao-Ting Sung, and Berlin Chen. 2019.  An innovative bert-based readability model.  In _International Conference on Innovative Technologies and Learning_ , pages 301–308. Springer.
  * Vajjala (2021) Sowmya Vajjala. 2021.  Trends, limitations and open challenges in automatic readability assessment research.  _CoRR_ , abs/2105.00973.
  * Vajjala and Lučić (2018) Sowmya Vajjala and Ivana Lučić. 2018.  OneStopEnglish corpus: A new corpus for automatic readability assessment and text simplification.  In _Proceedings of the Thirteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 297–304, New Orleans, Louisiana. Association for Computational Linguistics.
  * Vajjala and Meurers (2012) Sowmya Vajjala and Detmar Meurers. 2012.  On improving the accuracy of readability classification using insights from second language acquisition.  In _Proceedings of the Seventh Workshop on Building Educational Applications Using NLP_ , pages 163–173, Montréal, Canada. Association for Computational Linguistics.
  * Vajjala and Meurers (2016) Sowmya Vajjala and Detmar Meurers. 2016.  Readability-based sentence ranking for evaluating text simplification.  _CoRR_ , abs/1603.06009.
  * Vajjala and Meurers (2014) Sowmya Vajjala and Walt Detmar Meurers. 2014.  Readability assessment for text simplification: From analysing documents to identifying sentential simplifications.  _ITL – International Journal of Applied Linguistics_ , 165:194–222.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Weiß and Meurers (2018) Zarah Weiß and Detmar Meurers. 2018.  Modeling the readability of German targeting adults and children: An empirically broad analysis and its cross-corpus validation.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 303–317, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Weiss and Meurers (2019) Zarah Weiss and Detmar Meurers. 2019.  Analyzing linguistic complexity and accuracy in academic language development of German across elementary and secondary school.  In _Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 380–393, Florence, Italy. Association for Computational Linguistics.
  * Xia et al. (2016) Menglin Xia, Ekaterina Kochmar, and Ted Briscoe. 2016.  Text readability assessment for second language learners.  In _Proceedings of the 11th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 12–22, San Diego, CA. Association for Computational Linguistics.