# Rational Angle Sets and Tight T-Designs

Benjamin Nasmith

###### Abstract.

Given a finite subset of a sphere or projective space, known as a design, we
can compute the strength and angle set of that design. When the strength and
angle set meet certain bounds, the design is called tight. Hoggar sought to
prove that, aside from certain known cases, the angle sets of tight projective
designs must be rational. Lyubich found a counter-example and provided a
repair for Hoggar’s proof but excluded the exceptional octonion projective
cases. This note extends Lyubich’s repair of Hoggar’s proof to the remaining
projective cases and extends the proof to all spherical cases. It does so by
using Jordan algebra primitive idempotents to treat all of the cases
simultaneously. We thereby confirm that tight spherical and projective designs
have rational angle sets except in specific cases.

###### Key words and phrases:

Tight t-designs, Jordan algebras

Combinatorial $t$-designs were generalized to spherical $t$-designs in [DGS77]
and to projective spaces in [Neu81] (see also [Sei90]). Given a finite subset
$X$ of a sphere or projective space we can evaluate both the angle set $A(X)$
and strength $t$ of that subset. For a given strength $t$ there exists an
absolute lower bound on the cardinality $|X|$ such that $X$ is a $t$-design.
Likewise, for a given cardinality $s$, there is an absolute upper bound on the
cardinality $|X|$ such that $|A(X)|=s$. Furthermore, $t$ is bounded by $s$
according to the inequality $t\leq 2s-\varepsilon$ where
$\varepsilon=|A\cap\\{0\\}|$. These three bounds are satisfied simultaneously
if any one of them is met. When a set $X$ meets these absolute bounds, $X$ is
called a tight t-design.

The full classification of tight $t$-designs is incomplete, but various
theorems place upper bounds on the value of $t$ for different geometries
(e.g., [Hog89], [BH89]). In the case of projective geometries, many of these
theorems constraining $t$ depend on a result given in [Hog84] that, except for
the real projective line, the angle set $A(X)$ must be rational. However, a
counter-example exists in the case of the complex projective line: a subset
corresponding to the vertices of an icosahedron. This counter-example is
examined in [Lyu09], which attempts to repair the defective proof in [Hog84].
Unfortunately, the repair in [Lyu09] is restricted to the real, complex, and
quaternion projective cases. It neglects the octonion projective case and the
spherical cases. The aim of this note is to complete the repair in [Lyu09] by
including the remaining octonion and spherical cases. This also generalizes
the attempted proof in [Hog84] to the full family of spherical cases. In order
to treat all possible cases at once, we will work with the primitive
idempotents of simple Euclidean Jordan algebras. This allows us to treat the
spherical, projective, and octonion cases in a unified way.

##  1\. Jordan Algebras and T-Designs

This section reviews simple Euclidean Jordan algebras and the concepts
required to identify and describe tight $t$-designs. In addition to the real
numbers $\mathbb{R}$, the classification of simple Euclidean Jordan algebras
consists of four infinite families and one exception. The first infinite
family has rank $\rho=2$ and degree $d\geq 1$. The second, third, and fourth
family respectively have degree $d=1,2,4$ and rank $\rho\geq 3$. The
exceptional Euclidean Jordan algebra has rank $\rho=3$ and degree $d=8$. Each
Euclidean Jordan algebra has a well defined trace that we can use to define a
Euclidean inner product,

$\displaystyle\langle x,y\rangle=\mathrm{Tr}(x\circ y).$

Here $\circ$ denotes the Jordan product. Let $V$ be a simple Euclidean Jordan
algebra of rank $\rho$ and degree $d$. We denote by $\mathcal{J}(V)$ the
manifold of primitive idempotents of $V$. The rank $\rho=2$ family has
manifolds of primitive idempotents isometric to spheres. The degrees $d=1,2,4$
families have manifolds of primitive idempotents respectively isometric to
real, complex, and quaternionic projective spaces. Finally, the rank $\rho=3$,
degree $d=8$ exceptional case has a manifold of primitive idempotents
isometric to the octonion projective plane. This means we can use simple
Euclidean Jordan algebras and their manifolds of primitive idempotents to
model the following geometries for $d\geq 1$ and $\rho\geq 3$:

$\displaystyle\Omega_{d+1},\quad\mathbb{RP}^{\rho-1},\quad\mathbb{CP}^{\rho-1},\quad\mathbb{HP}^{\rho-1},\quad\mathbb{OP}^{2}.$

More details about simple Euclidean Jordan algebras can be found in [FK94].

Let $X$ be a finite subset of $\mathcal{J}(V)$, the manifold of primitive
idempotents of simple Euclidean Jordan algebra $V$. Then $X$ is an $A$-code
where $A$ is defined as,

$\displaystyle A(X)=\left\\{\langle x,y\rangle\mid x\neq y\in
X\subset\mathcal{J}(V)\right\\},$

and $X$ is also a $t$-design where $t$ is the largest integer such that $X$
satisfies,

$\displaystyle\sum_{x\in X}\sum_{y\in X}Q_{k}^{0}(\langle x,y\rangle)=0,\quad
k=1,2,\ldots,t.$

Here we use renormalized Jacobi functions $Q_{k}^{\varepsilon}(x)$ with
$\varepsilon=0,1$ in terms of the rank $\rho$ and degree $d$ of $V$ as follows
(recall that $\Omega_{d+1}$ has rank $2$ and degree $d$):

$\displaystyle Q_{k}^{\varepsilon}(x)=\left(\frac{\frac{1}{2}\rho
d+2k+\varepsilon-1}{\frac{1}{2}\rho
d+k+\varepsilon-1}\right)\frac{(\frac{1}{2}\rho
d)_{k+\varepsilon}}{(\frac{1}{2}d)_{k+\varepsilon}}P_{k}^{(\frac{1}{2}d(\rho-1)-1,\frac{1}{2}d-1+\varepsilon)}(2x-1).$

Here and below we use the Pochhammer symbol for non-negative integer $n$,
which can also be defined in terms of the usual $\Gamma$ function:

$\displaystyle(x)_{n}=x(x+1)\cdots(x+n-1)=\frac{\Gamma(x+n)}{\Gamma(x)}.$

Some of the polynomials that we will use are given below, with
$N=\frac{1}{2}\rho d$ and $m=\frac{1}{2}d$. The $N,m$ notation is more common
in the literature about projective designs.

$\displaystyle Q_{0}^{0}(x)$ $\displaystyle=1,$ $\displaystyle Q_{0}^{1}(x)$
$\displaystyle=\frac{N}{m},$ $\displaystyle Q_{1}^{0}(x)$
$\displaystyle=\left(N+1\right)\left(\frac{N}{m}x-1\right),$ $\displaystyle
Q_{2}^{0}(x)$
$\displaystyle=\left(\frac{N(N+3)}{2m(m+1)}\right)\left((N(N+3)+2)x^{2}-2(N+1)(m+1)x+m(m+1)\right).$

Next we construct the annihilator polynomial of $X$ [Hog82, 242]:

$\displaystyle\mathrm{ann}(x)=\frac{|X|}{\prod_{\alpha\in
A}(1-\alpha)}\prod_{\alpha\in A}(x-\alpha).$

By construction, we have $\mathrm{ann}(1)=|X|$ and $\mathrm{ann}(\alpha)=0$
for each angle $\alpha\in A$. The polynomial $\mathrm{ann}(x)$ has degree
$|A|=s$, and can be written as a linear combination of our renormalized Jacobi
functions (which depend on the rank and degree of the Jordan algebra
containing $X$):

$\displaystyle\mathrm{ann}(x)=\sum_{i=0}^{s}a_{i}Q_{i}^{0}(x).$

The coefficients $a_{0},a_{1},\ldots,a_{s}$ are known as the indicator
coefficients of $X$. To summarize, given a finite subset
$X\subset\mathcal{J}(V)$ we can determine the values of $A$ and $t$ needed to
describe $X$ as an $A$-code and $t$-design. We can also compute the
annihilator polynomial $\mathrm{ann}(x)$ and indicator coefficients
$a_{0},a_{1},\ldots,a_{s}$.

A tight $(2s-\varepsilon)$-design is a finite subset $X\subset\mathcal{J}(V)$
where the annihilator polynomial, as defined above, obtains the following
value:

$\displaystyle\mathrm{ann}(x)=x^{\varepsilon}R_{s-\varepsilon}^{\varepsilon}(x),\quad
R_{s-\varepsilon}^{\varepsilon}(x)=\sum_{i=0}^{s-\varepsilon}Q_{i}^{\varepsilon}(x).$

As the inner products of primitive idempotents in a Euclidean Jordan algebra,
the elements of $\alpha\in A(X)$ are all real-valued in the range
$0\leq\alpha<1$. We are interested in whether a tight $t$-design will have
only rational elements in angle set $A(X)$. This note proves the following
theorem, which generalizes the theorems of [Hog84] and [Lyu09]:

######  Theorem 1.1.

Let $V$ be a simple Euclidean Jordan algebra of rank $\rho$ and degree $d$
with manifold of primitive idempotents $\mathcal{J}(V)$. Let $X$ be a finite
subset of $\mathcal{J}(V)$ forming a tight $(2s-\varepsilon)$-design, namely
with $\mathrm{ann}(x)=x^{\varepsilon}R_{s-\varepsilon}^{\varepsilon}(x)$. Then
the roots of $\mathrm{ann}(x)$, which form the angle set $A(x)$, are rational
with exceptions when $(\rho,d)=(2,1)$ with $t\neq 1,2,3,5$ and when
$(\rho,d)=(2,2)$ with $t=5$.

##  2\. Bose-Mesner Algebras and the Idempotent Basis

We now review the faulty proof given in [Hog84], which was intended for the
degree $d=1,2,4,8$ cases only (i.e., the projective cases). The notation here
is not necessarily the same as that in [Hog84] or [Lyu09]. The problem with
the faulty proof in [Hog84] is that the matrices $E_{i}$ identified in that
paper are not in fact the idempotent basis for the Bose-Mesner algebra that
they are assumed to be. The burden of [Lyu09] is to replace $E_{i}$ with the
correct idempotents $L_{i}$ and complete the remainder of the proof, in the
case of degrees $d=1,2,4$. We do the same here for any rank and degree.

First, a tight $(2s-\varepsilon)$-design has the property that $t\geq 2s-2$,
which ensures that $X$ defines an association scheme. We can describe an
association scheme in terms of the Gram matrix of the elements of $X$ with
respect to the Jordan inner product $\langle x,y\rangle=\mathrm{Tr}(x\circ y)$
given above. That is, the elements of $G$, a $|X|\times|X|$ matrix, are given
by:

$\displaystyle(G)_{x,y}=\langle x,y\rangle.$

We can write this Gram matrix as a linear combination of adjacency matrices as
follows:

$\displaystyle G=I+\sum_{\alpha\in A(X)}\alpha D_{\alpha}.$

Here $D_{\alpha}$ is the adjacency matrix of the graph on $X$ where an edge
exists between any $x,y$ in $X$ with $\langle x,y\rangle=\alpha$. In this
notation, we can write $I=D_{1}$ since $\langle x,x\rangle=1$ for all $x$ in
$X$. Specifically, for $t\geq 2s-2$ (which is satisfied for tight
$t$-designs), the $D_{\alpha}$ for $\alpha$ in $A(X)$ define the $s=|A(X)|$
classes of an association scheme.

The matrices $D_{\alpha}$ and $I$ form the basis for a commutative matrix
algebra of dimension $s+1$ known as the Bose-Mesner algebra of $X$ (or rather
of the association scheme defined on $X$ via its Gram matrix). The Bose-Mesner
algebra consists of all $\mathbb{C}$-linear combinations of the commuting
basis given by the adjacency matrices and the identity matrix,

$\displaystyle\\{D_{\alpha}\mid\alpha\in A(X)\\}\cup\\{I\\}$

The simultaneous eigenvectors of these commuting diagonal matrices can be used
to construct a unique orthogonal idempotent basis for the Bose-Mesner algebra
[CVL91, pp. 201-204]:

$\displaystyle\\{L_{i}\mid i=0,1,\ldots,s\\},\quad
L_{i}L_{j}=\delta_{i,j}L_{i}.$

We denote by $q_{i}(\alpha)/|X|$ the coefficients of the $L_{i}$ elements in
the $D_{\alpha}$ basis, such that:

$\displaystyle|X|L_{i}=q_{i}(1)I+\sum_{\alpha\in
A(X)}q_{i}(\alpha)D_{\alpha}.$

That is, we define the entries of $L_{i}$ as follows:

$\displaystyle(L_{i})_{x,y}=\frac{1}{|X|}q_{i}(\langle x,y\rangle),\quad
i=0,1,\ldots,s.$

The faulty proof in [Hog84] assumes that $q_{i}(\alpha)=Q_{i}^{0}(\alpha)$ for
$X$ any tight $(2s-\varepsilon)$-design. Indeed, [Hog84] uses matrices $E_{i}$
instead of $L_{i}$:

$\displaystyle(E_{i})_{x,y}=\frac{1}{|X|}Q_{i}^{0}(\langle x,y\rangle),\quad
i=0,1,\ldots,s.$

The matrices $E_{0},E_{1},\ldots,E_{s-\varepsilon}$ are orthogonal
idempotents. The problem, as described in [Lyu09], is that for $\varepsilon=1$
the matrix $E_{s}$ is not necessarily idempotent, so we cannot assume that
$L_{s}=E_{s}$, where $s=|A(X)|$. To see why, note that the orthogonal basis of
$s+1$ idempotents $L_{0},L_{1},\ldots,L_{s}$ must satisfy,

$\displaystyle I=\sum_{i=0}^{s}L_{i}.$

The components of this matrix equation are given by,

$\displaystyle\delta_{x,y}=\frac{1}{|X|}\sum_{i=0}^{s}q_{i}(\langle
x,y\rangle).$

For a tight $t$-design we also have,

$\displaystyle\delta_{x,y}=\frac{1}{|X|}\mathrm{ann}(\langle
x,y\rangle)=\frac{1}{|X|}\langle
x,y\rangle^{\varepsilon}R_{s-\varepsilon}^{\varepsilon}(\langle
x,y\rangle)=\frac{1}{|X|}\langle
x,y\rangle^{\varepsilon}\sum_{i=0}^{s-\varepsilon}Q_{i}^{\varepsilon}(\langle
x,y\rangle).$

This means that we require,

$\displaystyle\sum_{i=0}^{s}q_{i}(\langle x,y\rangle)=\langle
x,y\rangle^{\varepsilon}\sum_{i=0}^{s-\varepsilon}Q_{i}^{\varepsilon}(\langle
x,y\rangle).$

When $\varepsilon=0$, this constraint is satisfied by setting $q_{i}(\langle
x,y\rangle)=Q_{i}^{0}(\langle x,y\rangle)$. When $\varepsilon=1$ we need to
select $q_{s}(\langle x,y\rangle)$ more carefully.

To find $L_{s}$ we begin with,

$\displaystyle L_{s}=I-\sum_{i=0}^{s-1}L_{i}.$

Since the $E_{i}$ are idempotent for $i\neq s$ we set $L_{i}=E_{i}$ for $i\neq
s$. This yields the following components of $L_{s}$:

$\displaystyle(L_{s})_{x,y}=\delta_{x,y}-\frac{1}{|X|}\sum_{i=0}^{s-1}Q_{i}^{0}(\langle
x,y\rangle).$

The first term is equal to $\mathrm{ann}(\langle x,y\rangle)/|X|$ and the sum
in the second term is equal to $R_{s-1}^{0}(\langle x,y\rangle)$. This
provides us with a general expression for $L_{s}$, regardless of whether
$\varepsilon$ equals $0$ or $1$:

$\displaystyle(L_{s})_{x,y}=\frac{1}{|X|}\left(\mathrm{ann}(\langle
x,y\rangle)-R_{s-1}^{0}(\langle x,y\rangle)\right).$

When $\varepsilon=0$ we have $\mathrm{ann}(\langle
x,y\rangle)=R^{0}_{s}(\langle x,y\rangle)$ which ensures that $L_{s}=E_{s}$.
However, when for $\varepsilon=1$ we have $L_{s}\neq E_{s}$.

##  3\. Idempotent Ranks and Complex Automorphisms

Having replaced the faulty $E_{i}$ with a proper $L_{i}$ idempotent basis, as
described in [Lyu09], we return to the proof in [Hog84]. Hoggar’s proof
involves the so-called wild automorphisms of $\mathbb{C}$. If we admit the
axiom of choice, then the automorphisms of $\mathbb{C}$ include wild
automorphisms, namely automorphisms of $\mathbb{C}$ that map $\mathbb{R}$ to a
dense subset of $\mathbb{C}$ [Yal66]. The only complex numbers that are fixed
by all wild automorphisms are the rationals $\mathbb{Q}$. We use this property
of $\mathbb{Q}$ below, assuming the axiom of choice.

Let $\sigma$ be an automorphism of $\mathbb{C}$, potentially among the wild
automorphisms. The map $\sigma$ acts as an automorphism of the the Bose-Mesner
algebra by acting on all matrix coefficients. Even so, $\sigma$ leaves the
basis matrices $I$ and $D_{\alpha}$ fixed, since they only have $0$ and $1$
for entries. Since each $L_{i}$ is a $\mathbb{C}$-linear combination of the
$D_{\alpha}$ matrices, and since the orthogonal idempotent basis is unique,
the action of $\sigma$ on $\\{L_{0},L_{1},\ldots,L_{s}\\}$ must permute these
idempotent matrices. It must also preserve matrix rank, so that
$\mathrm{rank}~{}L_{i}=\mathrm{rank}~{}\sigma(L_{i})$.

######  Lemma 3.1.

[Hog84] If the idempotent matrices $\\{L_{0},L_{1},\ldots,L_{s}\\}$ have
distinct ranks then $\langle x,y\rangle$ is rational for all $x,y$ in tight
$t$-design $X$.

###### Proof.

If the matrices $\\{L_{0},L_{1},\ldots,L_{s}\\}$ have distinct ranks then any
field automorphism of $\mathbb{C}$ must fix these matrices, so that
$\sigma(L_{i})=L_{i}$. This ensures that the $L_{i}$ are matrices with
rational entries. Specifically, each $L_{i}$ is of the form
$|X|(L_{i})_{x,y}=q_{i}(\langle x,y\rangle)$. If $\sigma(L_{i})=L_{i}$ then we
also have $\sigma q_{i}(\langle x,y\rangle)=q_{i}(\langle x,y\rangle)$. If
$q_{i}(\langle x,y\rangle)$ is fixed by all $\sigma$ then it is rational. In
the case of $i=1$ we have,

$\displaystyle(L_{1})_{x,y}=Q_{1}^{0}(\langle
x,y\rangle)=\left(\frac{1}{2}\rho d+1\right)\left(\rho\langle
x,y\rangle-1\right),$

This means that $\langle x,y\rangle$ is rational.

∎

The next task is to compute the ranks of the $L_{i}$ idempotent matrices. The
ranks found here are the same as those calculated in [Lyu09], but presented in
a slightly different form.

######  Lemma 3.2.

Let $X$ be a tight $(2s-\varepsilon)$-design. Then the orthogonal idempotents
of the Bose-Mesner algebra have the following ranks:

$\displaystyle\mathrm{rank}~{}L_{i}=\left\\{\begin{array}[]{c
l}Q_{i}^{0}(1),&i=0,1,\ldots,s-1\\\
R_{s-\varepsilon}^{\varepsilon}(1)-R_{s-1}^{0}(1),&i=s\end{array}\right.$

Here we have,

$\displaystyle Q_{i}^{0}(1)$ $\displaystyle=\left(\frac{\frac{1}{2}\rho
d+2i-1}{\frac{1}{2}\rho d+i-1}\right)\frac{(\frac{1}{2}\rho
d)_{i}(\frac{1}{2}\rho d-\frac{1}{2}d)_{i}}{(\frac{1}{2}d)_{i}i!}.$

For $\varepsilon=0$ we have $R_{s}^{0}(1)-R_{s-1}^{0}(1)=Q_{s}^{0}(1)$. For
$\varepsilon=1$ we have,

$\displaystyle R_{s-1}^{1}(1)-R_{s-1}^{0}(1)=\frac{s}{\frac{1}{2}\rho
d+2s-1}Q_{s}^{0}(1).$

###### Proof.

The rank of an idempotent matrix is equal to its trace. For $L_{i}$ with
$i\neq s$ we have,

$\displaystyle\mathrm{rank}~{}L_{i}=\mathrm{Tr}~{}L_{i}=\sum_{x\in
X}(L_{i})_{x,x}=\sum_{x\in X}\frac{Q_{i}^{0}(1)}{|X|}=Q_{i}^{0}(1).$

For $L_{s}$ we have,

$\displaystyle\mathrm{rank}~{}L_{s}=\mathrm{Tr}~{}L_{s}=\sum_{x\in
X}(L_{s})_{x,x}=\sum_{x\in
X}\frac{1}{|X|}\left(\mathrm{ann}(1)-R_{s-1}^{0}(1)\right).$

Since $\mathrm{ann}(1)=1^{\varepsilon}R_{s-\varepsilon}^{\varepsilon}(1)$ we
have,

$\displaystyle\mathrm{rank}~{}L_{s}=R_{s-\varepsilon}^{\varepsilon}(1)-R_{s-1}^{0}(1).$

The specific expression for $Q_{i}^{0}(1)$ given above is obtained from the
expression for $Q_{k}^{\varepsilon}(x)$ given earlier and the property
$P_{k}^{(\alpha,\beta)}=\binom{\alpha+k}{k}=\frac{(\alpha+1)_{k}}{k!}$. Next
we use the following expression from [Lyu09]:

$\displaystyle R_{s-\varepsilon}^{\varepsilon}(1)=\frac{(\frac{1}{2}\rho
d)_{s}(\frac{1}{2}\rho
d-\frac{1}{2}d+1)_{s-\varepsilon}}{(\frac{1}{2}d)_{s}(s-\varepsilon)!}=\frac{(\frac{1}{2}\rho
d)_{s}}{(\frac{1}{2}d)_{s}}\binom{\frac{1}{2}d(\rho-1)+s-\varepsilon}{s-\varepsilon}$

By construction $R_{s}^{0}(1)-R_{s-1}^{0}(1)=Q_{s}^{0}(1)$. When
$\varepsilon=1$ we instead have,

$\displaystyle R_{s-1}^{1}(1)-R_{s-1}^{0}(1)$
$\displaystyle=\left(\frac{(\frac{1}{2}\rho
d)_{s}}{(\frac{1}{2}d)_{s}}-\frac{(\frac{1}{2}\rho
d)_{s-1}}{(\frac{1}{2}d)_{s-1}}\right)\binom{\frac{1}{2}d(\rho-1)+s-1}{s-1}.$

Using $\binom{a}{b-1}=\frac{b}{a-b+1}\binom{a}{b}$ and then
$\binom{a+b}{b}=\frac{(a+1)_{b}}{b!}$ we have,

$\displaystyle R_{s-1}^{1}(1)-R_{s-1}^{0}(1)$
$\displaystyle=\frac{(\frac{1}{2}\rho
d)_{s}}{(\frac{1}{2}d)_{s}}\left(1-\frac{\frac{1}{2}d+s-1}{\frac{1}{2}\rho
d+s-1}\right)\frac{s}{\frac{1}{2}d(\rho-1)}\binom{\frac{1}{2}d(\rho-1)+s-1}{s}$
$\displaystyle=\frac{s}{\frac{1}{2}\rho d+s-1}\frac{(\frac{1}{2}\rho
d)_{s}(\frac{1}{2}\rho d-\frac{1}{2}d)_{s}}{(\frac{1}{2}d)_{s}s!}$
$\displaystyle=\frac{s}{\frac{1}{2}\rho d+2s-1}Q_{s}^{0}(1).$

∎

The exceptional case of the unit circle, $\Omega_{2}\cong\mathbb{RP}^{1}$,
deserves specific attention. We examine it before proceeding with the
remainder of the proof.

######  Lemma 3.3.

When rank $\rho=2$ and degree $d=1$, the case of
$\Omega_{2}\cong\mathbb{RP}^{1}$, we have

$\displaystyle\mathrm{rank}~{}L_{0}=1,~{}\mathrm{rank}~{}L_{i}=2,\quad
i=1,\ldots,s-\varepsilon.$

When $\varepsilon=1$, we have $\mathrm{rank}~{}L_{s}=1$.

###### Proof.

We evaluate $Q_{i}^{0}(1)$ for $\rho=2$ and $d=1$. First, $Q_{0}^{0}(x)=1$ so
we have $\mathrm{rank}~{}L_{0}=Q_{0}^{0}(1)=1$. In what follows we assume
$i>0$. The following expression simplifies to $2$:

$\displaystyle Q_{i}^{0}(1)$
$\displaystyle=\left(\frac{1+2i-1}{1+i-1}\right)\frac{(1)_{i}(1-\frac{1}{2})_{i}}{(\frac{1}{2})_{i}i!}=2.$

When $\varepsilon=1$ we have,

$\displaystyle\mathrm{rank}~{}L_{s}=R_{s-1}^{1}(1)-R_{s-1}^{0}(1)=\frac{s}{1+2s-1}Q_{s}^{0}(1)=\frac{2}{2}=1.$

∎

The remaining cases satisfy the following lemma:

######  Lemma 3.4.

[Lyu09] For any tight $(2s-\varepsilon)$-design, not in
$\Omega_{2}\cong\mathbb{RP}^{1}$, the idempotent basis matrices satisfy,

$\displaystyle\mathrm{rank}~{}L_{0}<\mathrm{rank}~{}L_{1}<\cdots<\mathrm{rank}~{}L_{s-\varepsilon}.$

###### Proof.

This is equivalent to
$Q_{0}^{0}(1)<Q_{1}^{0}(1)<\cdots<Q_{s-\varepsilon}^{0}(1)$. We can compute
the following expression:

$\displaystyle Q_{i+1}^{0}(1)$ $\displaystyle=\left(\frac{\frac{1}{2}\rho
d+2i+1}{\frac{1}{2}\rho
d+2i-1}\right)\left(\frac{\frac{1}{2}d(\rho-1)+i}{\frac{1}{2}d+i}\right)\left(\frac{\frac{1}{2}\rho
d+i-1}{i+1}\right)Q_{i}^{0}(1)$

The first factor is always greater than one. The second factor is always
greater than or equal to one. The third factor is greater than or equal to one
when $\rho d\geq 4$. This leaves the $(\rho,d)=(3,1)$ case to check, which
yields
$Q_{i+1}^{0}(1)=\left(2i+\frac{5}{2}\right)/\left(2i+\frac{1}{2}\right)Q_{i}^{0}(1)$.
Therefore, for $(\rho,d)\neq(2,1)$ we have $Q_{i}^{0}(1)<Q_{i+1}^{0}(1)$ for
all $i\geq 0$. ∎

##  4\. Completing the Proof

To complete the proof of Theorem 1.1 we need to apply Lemma 3.1 to all the
relevant cases. However, since $\Omega_{2}\cong\mathbb{RP}^{1}$ generally
involves idempotent basis matrices of equal rank, we cannot use Lemma 3.1 for
this exceptional case. This case is examined carefully for completeness in
[Lyu09] and we address it in the following theorem.

######  Theorem 4.1.

[Lyu09] A tight $t$-design in $\Omega_{2}\cong\mathbb{RP}^{1}$ has a rational
angle set if and only if $t=1,2,3,5$.

###### Proof.

A tight $t$-design in $\Omega_{2}\cong\mathbb{RP}^{1}$ always exists and is
given by the corners of a regular $(t+1)$-gon. The angle between any pair of
design points on the unit circle is $\theta=2m\pi/(t+1)$ for some integer $m$.
The corresponding Jordan inner product is $\langle
x,y\rangle=\cos^{2}\left(\frac{\theta}{2}\right)=\frac{1}{2}+\frac{1}{2}\cos\theta$.
This means that $\langle x,y\rangle$ is rational if and only if $\cos\theta$
is rational. The only values of $t$ for which $\cos\theta$ is rational are
known to be $t=1,2,3,5$. ∎

We now examine the remaining cases with $(\rho,d)\neq(2,1)$, i.e., distinct
from the unit circle. The simplest to deal with, using Lemma 3.1, is the case
where $t=2s$ is even.

######  Theorem 4.2.

A tight $(2s)$-design, not in $\Omega_{2}\cong\mathbb{RP}^{1}$, has a rational
angle set.

###### Proof.

According to Lemma 3.4, the idempotent basis matrices $L_{i}$ each have
distinct rank. Therefore, by Lemma 3.1, the angle set is rational. ∎

We now examine cases with odd $t=2s-1$.

######  Lemma 4.3.

Let $(\rho,d)\neq(2,1)$. If $L_{s}$ and $L_{1}$ have distinct ranks then the
angle set is rational.

###### Proof.

According to Lemma 3.4, the ranks of all $L_{i}$ are distinct except possibly
for $L_{s}$ when $\varepsilon=1$. Therefore no field automorphism of
$\mathbb{C}$ interchanges $L_{1}$ with any $L_{i}$ other than possibly
$L_{s}$. If $L_{s}$ and $L_{1}$ have distinct ranks, then $L_{1}$ is fixed by
all field automorphisms of $\mathbb{C}$ and therefore is a matrix with
rational entries $Q_{1}^{0}(\alpha)/|X|$. As described in the proof of Lemma
3.1, it follows from the rationality of $Q_{1}^{0}(\alpha)$ that $\alpha$ is
rational. ∎

The simplest odd $t=2s-1$ case is for $s=1$, corresponding to a tight
$1$-design. A tight $1$-design exists in each $\Omega_{d+1}$ and
$\mathbb{FP}^{\rho-1}$ and is also known as a Jordan frame, or full rank set
of orthogonal primitive idempotents. The annihilator polynomial is
$\mathrm{ann}(x)=\rho x$, so the angle set is $A=\\{0\\}$, which is clearly
rational. Since this case is fully understood, we will assume $s>1$ in what
follows.

We now address the remaining spherical cases.

######  Theorem 4.4.

A tight $(2s-1)$-design in $\Omega_{d+1}$ with $d>1$ has a rational angle set
except when $d=2$ and $s=3$.

###### Proof.

In the spherical cases we have $\rho=2$ and can simplify $Q_{i}^{0}(1)$ to the
following:

$\displaystyle Q_{i}^{0}(1)$
$\displaystyle=\left(\frac{d+2i-1}{d+i-1}\right)\frac{(d)_{i}}{i!}.$

This means that,

$\displaystyle\mathrm{rank}~{}L_{1}=Q_{1}^{0}(1)$ $\displaystyle=d+1.$

Likewise,

$\displaystyle\mathrm{rank}~{}L_{s}$
$\displaystyle=R_{s-1}^{1}(1)-R_{s-1}^{0}(1)=\frac{s}{d+2s-1}Q_{s}^{0}(1)=\binom{d+s-2}{s-1}.$

For $s=2$, we always have $\mathrm{rank}~{}L_{s}-\mathrm{rank}~{}L_{1}=-1$. By
Lemma 3.1, a tight spherical $3$-design must therefore have rational angle
set. For $s>2$, $\mathrm{rank}~{}L_{s}-\mathrm{rank}~{}L_{1}\geq 0$ with the
equality achieved only when $d=2$ and $s=3$. Aside from this exception, Lemma
3.1 ensures a rational angle set. Therefore, the only case where
$\mathrm{rank}~{}L_{s}=\mathrm{rank}~{}L_{1}$ is for $d=2$ and $s=3$. A tight
$5$-design exists in this case and is known to be the vertices of a regular
icosahedron in $\Omega_{3}$. ∎

######  Remark 4.5.

In contrast to Lyubich, who only deals with projective cases of degree
$d=1,2,4$, we have dealt here with all spherical ($\rho=2$) cases
simultaneously. This provides slightly different approach to identifying
Lyubich’s exception in $\Omega_{3}\cong\mathbb{CP}^{1}$, namely as spherical
design rather than as a projective design.

We will call a design with $\rho>2$ a strictly projective design. All
remaining cases are strictly projective. In what follows we will therefore
require that $\rho>2$.

######  Theorem 4.6.

A strictly projective tight $(2s-1)$-design, i.e., with $\rho>2$, has a
rational angle set.

###### Proof.

The proof method shown here is equivalent to the method used in [Lyu09], but
the parameters are allowed to extend to the octonion case ($d=8$) yet
restricted to the strictly projective $\rho>2$ cases. We need to verify that
$\mathrm{rank}~{}L_{s}\neq\mathrm{rank}~{}L_{1}$. In the cases below we use
that fact that,

$\displaystyle\mathrm{rank}~{}L_{s}\geq\frac{2}{\frac{1}{2}\rho
d+3}Q_{2}^{0}(1)$

Specifically, as a function of $s$ the expression
$sQ_{s}^{0}(1)/(\frac{1}{2}\rho d+2s-1)$ decreases as the value of $s$
decreases. We can confirm this fact using the expression given in the proof of
Lemma 3.4. We will therefore assume that $\mathrm{rank}~{}L_{s}$ is greater
than or equal to the same expression evaluated at $s=2$. This ensures that,

$\displaystyle\mathrm{rank}~{}L_{s}-\mathrm{rank}~{}L_{1}\geq\frac{2}{\frac{1}{2}\rho
d+3}Q_{2}^{0}(1)-Q_{1}^{0}(1).$

Writing the expression on the right hand side explicitly, in simplified form,
we have,

$\displaystyle\mathrm{rank}~{}L_{s}-\mathrm{rank}~{}L_{1}\geq\frac{1}{2}\left(\frac{d(\rho-1)}{d(d+2)}\right)\left(\rho^{2}d^{2}-2\rho
d^{2}-2d-4\right)$

Whenever the right hand side of the inequality is greater than zero, we have
confirmed by Lemma 3.1 that $\mathrm{rank}~{}L_{s}\neq\mathrm{rank}~{}L_{1}$
and therefore that the angle set is rational. We define,

$\displaystyle f_{d}(\rho)=\rho^{2}d^{2}-2\rho d^{2}-2d-4.$

If $f_{d}(\rho)>0$ then the corresponding tight projective $(2s-1)$-design has
a rational angle set.

### Real Projective Case

Set $d=1$ and $\rho>2$. Then we have,

$\displaystyle f_{1}(\rho)=\rho^{2}-2\rho-6.$

The only integer value of $\rho>2$ with $f_{1}(\rho)\leq 0$ is $\rho=3$. This
means that the real projective case of $\rho=3$ and $d=1$ is a possible case
for $\mathrm{rank}~{}L_{s}=\mathrm{rank}~{}L_{1}$. We must examine this
possibility more closely.

Let $d=1$ and $\rho=3$. If $s=2$, for a tight $3$-design, then we know that
$\mathrm{rank}~{}L_{s}\neq\mathrm{rank}~{}L_{1}$ by the fact that
$f_{1}(3)\neq 0$, as shown above. We need to also ensure
$\mathrm{rank}~{}L_{s}\neq\mathrm{rank}~{}L_{1}$ for $s>2$. To do so, we
repeat the argument given above except instead we use,

$\displaystyle\mathrm{rank}~{}L_{s}\geq\frac{3}{\frac{1}{2}\rho
d+5}Q_{3}^{0}(1).$

For $d=1$ and $\rho=3$ we have,

$\displaystyle\mathrm{rank}~{}L_{s}-\mathrm{rank}~{}L_{1}\geq\frac{6}{13}Q_{3}^{0}(1)-Q_{1}^{0}(1)=1.$

Therefore all real tight strictly projective designs have rational angle set.

### Complex Projective Cases

Let $\rho\geq 3$ and $d=2$. Then the second factor in the inequality above
simplifies to,

$\displaystyle f_{2}(\rho)=4\rho^{2}-8\rho-8.$

All integer values of $\rho>2$ satisfy $f_{2}(\rho)>0$. This means that
$\mathrm{rank}~{}L_{s}>\mathrm{rank}~{}L_{1}$ for all of the complex
projective cases.

### Quaternion Projective Cases

Let $\rho\geq 3$ and $d=4$. Then the second factor in the inequality above
simplifies to,

$\displaystyle f_{4}(\rho)=16\rho^{2}-32\rho-12.$

All integer values of $\rho>2$ satisfy $f_{4}(\rho)>0$. This means that
$\mathrm{rank}~{}L_{s}>\mathrm{rank}~{}L_{1}$ for all of the quaternion
projective cases.

### Exceptional Octonion Projective Case

Let $\rho=3$ and $d=8$. Then the second factor in the inequality above
simplifies to,

$\displaystyle f_{8}(3)=172.$

This means that $\mathrm{rank}~{}L_{s}>\mathrm{rank}~{}L_{1}$ for the
exceptional case. Having checked all the cases, we have distinct ranks for all
idempotent basis matrices $L_{i}$ and by Lemma 3.1 the angle sets of a
strictly projective tight $(2s-1)$-design must be rational. ∎

##  5\. Conclusion

We have extended the result of [Hog84] for $d=1,2,4,8$, which is corrected by
[Lyu09] for $d=1,2,4$, to the full range of possible values of rank $\rho$ and
degree $d$, proving Theorem 1.1. This clarifies the full conditions under
which a tight $t$-design—whether spherical or projective—has rational angle
set. The only examples of irrational angles sets exist on the unit circle
$\Omega_{2}\cong\mathbb{RP}^{1}$ for $t\neq 2,3,4,5$ and on the unit sphere
$\Omega_{3}\cong\mathbb{CP}^{1}$ for $t=5$.

## References

  * [BH89] Eiichi Bannai and Stuart G. Hoggar, _Tight t-designs and squarefree integers_ , European Journal of Combinatorics 10 (1989), no. 2, 113–135, Publisher: Academic Press.
  * [CVL91] Peter Jephson Cameron and Jacobus Hendricus Van Lint, _Designs, graphs, codes and their links_ , vol. 3, Cambridge University Press, Cambridge, 1991.
  * [DGS77] P Delsarte, J M Goethals, and J J Seidel, _Spherical codes and designs_ , Geometriae Dedicata 6 (1977), 363–388 (en).
  * [FK94] Jacques Faraut and Adam Koranyi, _Analysis on Symmetric Cones_ , Clarendon Press, 1994 (en).
  * [Hog82] Stuart G. Hoggar, _t-Designs in projective spaces_ , European Journal of Combinatorics 3 (1982), no. 3, 233–254.
  * [Hog84] by same author, _Tight t-designs and octonions_ , Mitt. Math. Sem. Giessen 165 (1984), 1–16.
  * [Hog89] by same author, _Tight 4 and 5-designs in projective spaces_ , Graphs and Combinatorics 5 (1989), no. 1, 87–94.
  * [Lyu09] Yu. I. Lyubich, _On tight projective designs_ , Designs, Codes and Cryptography 51 (2009), no. 1, 21–31 (en).
  * [Neu81] Arnold Neumaier, _Combinatorial Configurations in terms of distances_ , 1981\.
  * [Sei90] J. J. Seidel, _Designs and approximation_ , Contemp. Math 111 (1990), 179–186.
  * [Yal66] Paul B. Yale, _Automorphisms of the complex numbers_ , Mathematics Magazine 39 (1966), no. 3, 135–141, Publisher: Taylor & Francis.


$\mathsf{type}((G[F_{t}],\iota))=\tau$.

Intuitively, we think of $S$ as the intersection of a fixed optimal solution
with $X_{t}$ and we look for a maximum-weight induced $\ell$-boundaried
subgraph of $G_{t}$ with boundary $S$ and type $\tau$. If there is no subset
$F_{t}$ satisfying the conditions above, we will have
$\mathsf{Tab}_{t}[S,\iota,\tau]=-\infty$. Clearly, having computed all entries
of $\mathsf{Tab}_{\cdot}[\cdot]$, the weight of the sought-for optimal
solution is

$\max_{\tau}\mathsf{Tab}_{\mathsf{root}(T)}[\emptyset,\emptyset,\tau],\text{
over all }\tau\in\mathsf{Types}[\phi].$

Let us now describe how we compute the entries $\mathsf{Tab}_{t}[\cdot]$ for a
node $t$ of $T$. The exact way depends on the type of $x$.

##### Case: $t$ is a leaf node.

Note that in this case $G_{t}$ has no vertices, and thus the values of
$\mathsf{Tab}_{t}[\cdot]$ can be extracted from the information that is hard-
coded in the algorithm.

##### Case: $t$ is an introduce node.

Let $t^{\prime}$ be the child of $t$ in $T$, and let $v$ be the unique vertex
in $X_{t}\setminus X_{t^{\prime}}$. Clearly, if $v\notin S$, then
$\mathsf{Tab}_{t}[S,\iota,\tau]=\mathsf{Tab}_{t^{\prime}}[S,\iota,\tau]$.

So let $v\in S$, let $S^{\prime}=S\setminus\\{v\\}$, and let
$\iota^{\prime}=\iota|_{S^{\prime}}$. Let $G_{S}$ be the subgraph of $X_{t}$
induced by $S$. As $|S|\leqslant\ell$, the value
$\tau_{S}\coloneqq\mathsf{type}((G_{S},\iota))$ is hard-coded in our
algorithm. Now we set

$\mathsf{Tab}_{t}[S,\iota,\tau]=\max_{\tau^{\prime}}\mathsf{Tab}_{t^{\prime}}[S^{\prime},\iota^{\prime},\tau^{\prime}],$

where the maximum is taken over all $\tau^{\prime}$ such that
$\tau_{S}\oplus\tau^{\prime}=\tau$.

##### Case: $t$ is a forget node.

Let $t^{\prime}$ be the child of $t$ in $\mathcal{T}$, and let $v$ be the
unique vertex in $X_{t^{\prime}}\setminus X_{t}$. Intuitively, partial
solutions at $t$ correspond to partial solutions at $t^{\prime}$ with the
label of $v$ (if any) forgotten. Thus

$\mathsf{Tab}_{t}[S,\iota,\tau]=\max\left(\mathsf{Tab}_{t^{\prime}}[S,\iota,\tau],\max_{\iota^{\prime},\tau^{\prime}}\mathsf{Tab}_{t^{\prime}}[S\cup\\{v\\},\iota^{\prime},\tau^{\prime}]\right),$

where the second term only appears if $|S|<\ell$. The maximum in the second
term is computed over all pairs $\iota^{\prime},\tau^{\prime}$, such that
$\iota^{\prime}|_{S}=\iota$ and $\tau^{\prime}_{\neg\iota^{\prime}(v)}=\tau$.

##### Case: $t$ is a join node.

Let $t^{\prime},t^{\prime\prime}$ be the children of $t$. Thus

$\mathsf{Tab}_{t}[S,\iota,\tau]=\max_{\tau^{\prime},\tau^{\prime\prime}}\mathsf{Tab}_{t^{\prime}}[S,\iota,\tau^{\prime}]+\mathsf{Tab}_{t^{\prime\prime}}[S,\iota,\tau^{\prime\prime}]-\mathfrak{w}(S),$

where the maximum is taken over all $\tau^{\prime},\tau^{\prime\prime}$ such
that $\tau^{\prime}\oplus\tau^{\prime\prime}=\tau$. Note that we subtract the
weight of $S$, as it is counted both for $t^{\prime}$ and for
$t^{\prime\prime}$.

The correctness of the procedure above follows directly from the properties of
nice tree decompositions and Proposition 6.1.

For each node $t$ of $T$, the number of states is at most
$|X_{t}|^{\ell}\cdot\ell!\cdot|\mathsf{Types}|$. Each entry of
$\mathsf{Tab}_{\cdot}[\cdot]$ can be computed in time proportional to the
number of states for each node (here we use that $k,r,\phi$ are fixed). We
conclude that the running time is
$f(k,r,\psi)\cdot|V(G)|^{\mathcal{O}(\textsf{Ramsey}(k+1,r+1))}|V(T)|$ for
some function $f$ depending on $k,r$, and $\psi$. ∎

We remark that one can easily obtain a variant of Theorem 6.2 in which a tree
decomposition with small independence number is not needed in the input.
Indeed, combining Theorem 6.2 with Theorem 3.2 yields Theorem 6.3 (with
$g(k,r)=\mathcal{O}(\textsf{Ramsey}(8k+1,r+1))$).

######  Theorem 6.3.

For every $k$, $r$, and a $\mathsf{CMSO}_{2}$ formula $\psi$ there exist
positive integers $f(k,r,\psi)$ and $g(k,r)$ such that the following holds.
Let $G$ be a graph with $\mathsf{tree}\textnormal{-}\alpha(G)\leqslant k$, and
let $\mathfrak{w}\colon V(G)\to\mathbb{Q}_{+}$ be a weight function. Then in
time $f(k,r,\psi)\cdot|V(G)|^{g(k,r)}$ we can find a set $F\subseteq V(G)$,
such that

  1. 1.

$G[F]\models\psi$,

  2. 2.

$\omega(G[F])\leqslant r$,

  3. 3.

$F$ is of maximum weight subject to the conditions above,

or conclude that no such set exists.

###  6.3 A generalization

Theorem 6.3 can be slightly generalized so that we can maximize the weight of
some carefully chosen subset of the solution. The formula $\psi$ uses this set
as a free variable.

######  Theorem 6.4.

For every $k$, $r$, and a $\mathsf{CMSO}_{2}$ formula $\psi$ with one free
vertex-set variable, there exist positive integers $f(k,r,\psi)$ and $g(k,r)$
such that the following holds. Let $G$ be a graph with
$\mathsf{tree}\textnormal{-}\alpha(G)\leqslant k$, and let $\mathfrak{w}\colon
V(G)\to\mathbb{Q}_{+}$ be a weight function. Then in time
$f(k,r,\psi)\cdot|V(G)|^{g(k,r)}$ we can find sets $X\subseteq F\subseteq
V(G)$, such that:

  1. 1.

$(G[F],X)\models\psi$,

  2. 2.

$\omega(G[F])\leqslant r$,

  3. 3.

$X$ is of maximum possible weight, subject to conditions above,

or conclude that no such set exists.

###### Proof sketch.

The proof follows by a simple trick used by Gartland et al. [38, Theorem 38].
We just sketch the argument here and refer the reader to [38] for more
details.

For a graph $G$ and a subset $M\subseteq V(G)$, by $\breve{G}$ we denote the
_forked version of_ $(G,M)$, which is obtained as follows. We start the
construction with a copy of $G$. For every vertex $v$ of $G$ we introduce to
$\breve{G}^{M}$ three vertices of degree 1, each adjacent only to $v$. For
every vertex $v$ of $M$ we introduce to $\breve{G}^{M}$ a two-edge path, whose
one endvertex is identified with $v$. If $G$ is equipped with weights
$\mathfrak{w}$, we set the weights $\breve{\mathfrak{w}}$ of all vertices of
$\breve{G}^{M}$ to 0, with the exception that the value of $\mathfrak{w}(v)$
for $v\in M$ is transferred to the other endvertex of the two-edge path
attached to $v$.

Note that if $F^{\prime}$ is a forked version of some $(F,M)$, then $F$ and
$M$ can be uniquely decoded from $F^{\prime}$. Indeed, $F$ is the subgraph of
$F^{\prime}$ induced by vertices of degree at least four, and vertices of $M$
are those vertices of $F$ that are adjacent (in $F^{\prime}$) to a vertex of
degree 2. Furthermore, $\omega(F^{\prime})\leqslant\max(\omega(F),2)$.

We apply the algorithm of Theorem 3.2 to compute in time
$|V(G)|^{\mathcal{O}(k)}$ a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of $G$ with independence number at
most $8k$. Moreover, observe that, given the tree decomposition $\mathcal{T}$,
we can easily obtain a tree decomposition
$\breve{\mathcal{T}}=(\breve{T},\\{\breve{X}_{t}\\}_{t\in V(\breve{T})})$ of
$\breve{G}^{V(G)}$ with
$\alpha(\breve{\mathcal{T}})\leqslant\alpha(\mathcal{T})$. The idea is to call
the algorithm from Theorem 6.2 on $\breve{G}^{V(G)}$ and a formula
$\breve{\psi}$ that for a graph $F^{\prime}$ ensures that

  * •

if $F^{\prime}$ is a forked version of some $(F,M)$, then
$F^{\prime}\models\breve{\psi}$ if and only if $(F,M)\models\psi$,

  * •

otherwise $F^{\prime}\not\models\breve{\psi}$.

Such a formula can be easily constructed in $\mathsf{CMSO}_{2}$ [38]. We
observe that the solution found by the algorithm satisfies the conditions
stated in the theorem; again, see [38, Theorem 38] for details. ∎

###  6.4 Algorithmic applications and limitations

Using the framework of Theorem 6.3 we can solve several well-studied problems
for graphs of bounded tree-independence number:

  * •

Max Weight Independent Set,

  * •

Max Weight Induced Forest, which is equivalent by complementation to Min
Weight Feedback Vertex Set,

  * •

Max Weight Induced Bipartite Subgraph, which is equivalent by complementation
to Min Weight Odd Cycle Transversal,

  * •

Max Weight Induced Odd Cactus, which is equivalent by complementation to Min
Weight Even Cycle Transversal (see e.g. [12]),

  * •

Max Weight Induced Planar Subgraph, which is equivalent to Planarization (see
e.g. [61]),

  * •

Defective Coloring, where we ask for a vertex coloring using
$\chi_{\textrm{d}}$ colors in which each color class induced a subgraph of
maximum degree bounded by $\Delta^{*}$, where both $\chi_{\textrm{d}}$ and
$\Delta^{*}$ are fixed (see, e.g., [10]), and

  * •

Max $k$-Dependent Set, that is, maximum set of vertices inducing a subgraph of
maximum degree at most $k$ (see, e.g., [42]), which is equivalent by
complementation to Bounded-Degree Vertex Deletion.

In particular, these results generalize Theorems 23 and 25 from [10], giving
polynomial-time algorithms for Defective Coloring for fixed
$\chi_{\textrm{d}}$ and $\Delta^{*}$ in graphs of bounded treewidth and
chordal graphs, respectively. They also solve an open problem from [42]
regarding the complexity of Max $k$-Dependent Set on interval graphs (see [42,
Table 2]).

Using the extension from Theorem 6.4 we can solve some other problems, for
example:

  * •

find the maximum number of pairwise independent induced cycles.

Note that the difference is that we maximize the _number_ of cycles, and not
their _total size_ (or weight), as we could do using Theorem 6.3. On other
other hand, the number of induced cycles in a graph might be very large, so
this problem cannot be solved using Theorem 5.6 (or Theorem 5.15). However, we
can solve our problem by calling Theorem 6.4 with the following parameters:

  * •

$r=3$,

  * •

$\psi$ is the formula saying that $G[F]$ is 2-regular (i.e., each component of
$G[F]$ is a cycle) and each vertex from $X$ must be in a distinct connected
component of $G[F]$, and

  * •

the weight of each vertex is 1.

In conclusion, let us point out that in Theorems 6.3, 6.2 and 6.4 we need to
assume that the clique number of the solution is bounded by a constant.
Indeed, the property of being a clique can be easily expressed by a
$\mathsf{CMSO}_{2}$ formula as follows (here $x,y$ are vertex variables and
$e$ is an edge variable):

$\phi_{\textrm{clique}}\coloneqq\forall_{x,y}\left(x\neq
y\to\exists_{e}\left(\textsf{inc}(e,x)\land\textsf{inc}(e,y)\right)\right).$

However, Max Clique is NP-hard on graphs with independence number 2, and thus
of tree-independence number at most 2. Indeed, this follows from the fact that
Max Independent Set is NP-hard on triangle-free graphs [62], by complementing
the input graph.

##  7 Complexity of computing induced matching treewidth and bounds

In this section, we collect some basic complexity and algorithmic observations
about induced matching treewidth, establish its close relation to treewidth
for graphs with bounded degree, and give constructions of two families of
graphs with unbounded degree and unbounded induced matching treewidth.

###  7.1 Remarks on complexity of computing induced matching treewidth

Proposition 3.1 together with known hardness results on the tree-independence
number from [32, 29] and on the independence number from [73] imply the
following hardness results for induced matching treewidth.

######  Theorem 7.1.

The following lower bounds hold.

  1. 1.

For every constant $k\geqslant 4$, it is NP-complete to decide whether
$\mathsf{tree}\textnormal{-}\mu(G)\leqslant k$ for a graph $G$.

  2. 2.

For every $\varepsilon>0$, there is no polynomial-time algorithm for
approximating induced matching treewidth of an $n$-vertex graph to within a
factor of $n^{1-\varepsilon}$ unless $\textsf{P}=\textsf{NP}$.

  3. 3.

There is no constant-factor FPT-approximation algorithm for induced matching
treewidth, unless $\textsf{FPT}=\textsf{W[1]}$.

  4. 4.

For any computable functions $f,g$, there is no $g(k)$-approximation algorithm
for computing induced matching treewidth in time $f(k)\cdot n^{o(k)}$, unless
the Gap-ETH fails.555Gap-ETH states that for some constant $\epsilon>0$,
distinguishing between a satisfiable 3-SAT formula and one that is not even
$(1-\epsilon)$-satisfiable requires exponential time (see [52, 33]).

###### Proof.

Fix an integer $k\geqslant 4$. Clearly, the problem of testing if
$\mathsf{tree}\textnormal{-}\mu(G)\leqslant k$ for a given graph $G$ belongs
to NP. To establish NP-hardness, we make a reduction from the problem of
testing if a given graph $G$ satisfies
$\mathsf{tree}\textnormal{-}\alpha(G)\leqslant k$. As shown by Dallard et al.
[29], this problem is NP-complete. By Proposition 3.1,
$\mathsf{tree}\textnormal{-}\alpha(G)=\mathsf{tree}\textnormal{-}\mu(G\circ
K_{1})$ and hence $\mathsf{tree}\textnormal{-}\alpha(G)\leqslant k$ if and
only if $\mathsf{tree}\textnormal{-}\mu(G\circ K_{1})\leqslant k$. Since
computing the corona of $G$ can be done in polynomial time, hardness follows.

To obtain the inapproximability result, let us recall the original reduction
establishing NP-hardness of the problem of computing the tree-independence
number due to Dallard et al. [32]. The reduction was from the independent set
problem and was based on the fact that for any graph $G$, if $G^{\prime}$ is
the graph obtained from two disjoint copies of $G$ by adding all possible
edges between them, then
$\alpha(G)=\mathsf{tree}\textnormal{-}\alpha(G^{\prime})$. Combining this
result with Proposition 3.1, we obtain that
$\alpha(G)=\mathsf{tree}\textnormal{-}\alpha(G^{\prime})=\mathsf{tree}\textnormal{-}\mu(G^{\prime}\circ
K_{1})$. Given an $n$-vertex graph $G$, the graph $G^{\prime}\circ K_{1}$ can
be computed in polynomial time from $G$ and has $4n$ vertices. Now,
approximately computing the induced matching treewidth of the transformed
graph would imply an equally good approximation to the independence number of
$G$.

Thus statements 2., 3., 4. follow from analogous hardness results for
approximating Max Independent Set, shown by, respectively, Zuckerman [73], Lin
[50], and Chalersmook et al. [26]. ∎

Let us remark that Theorem 7.1 does not leave much space for improvements to
Theorem 3.3. First, it implies that we cannot _exactly_ compute induce
matching treewidth, even for small values (at least 4). Second, we cannot hope
for a nontrivial approximation in polynomial time. Finally, the running time
of the approximation algorithm cannot be improved to $f(k)\cdot
n^{\mathcal{O}(1)}$ and even $f(k)\cdot n^{o(k)}$, under standard complexity
assumptions.

Theorem 7.1 establishes NP-completeness of recognizing graphs with induced
matching width at most $k$, for every integer $k\geqslant 4$. The complexity
of recognizing graphs with induced matching treewidth at most $k$ is open for
$k\in\\{2,3\\}$, but solvable in polynomial time for $k\leqslant 1$, as we
discuss next. Before doing that, let us show a nice property of induced
matching treewidth that is also satisfied by tree-independence number (see
[32]) and by _sim-width_ , a graph parameter introduced in 2017 by Kang, Kwon,
Strømme, and Telle (see [44]): the parameter is monotone under induced minors.
Given two graphs $G$ and $H$, we say that $H$ is an _induced minor_ of $G$ if
a graph isomorphic to $H$ can be obtained from $G$ by a sequence of vertex
deletions and edge contractions.

######  Proposition 7.2.

Let $G$ be a graph and let $H$ be an induced minor of $G$. Then
$\mathsf{tree}\textnormal{-}\mu(H)\leqslant\mathsf{tree}\textnormal{-}\mu(G)$.

###### Proof.

We show how to modify any tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ of $G$ into a tree decomposition $\mathcal{T}^{\prime}$ of $H$ such
that the induced matching treewidths of the two decompositions are related as
follows: $\mu_{H}(\mathcal{T}^{\prime})\leqslant\mu_{G}(\mathcal{T})$. This
will imply the desired inequality
$\mathsf{tree}\textnormal{-}\mu(H)\leqslant\mathsf{tree}\textnormal{-}\mu(G)$.

Clearly, it suffices to consider the case when $H$ is obtained from $G$ either
by a single vertex deletion or by a single edge contraction.

Consider first the case when $H$ is the graph obtained from $G$ by deleting
some vertex, say $v\in V(G)$. Then deleting $v$ from all the bags of
$\mathcal{T}$ that contain $v$ results in a tree decomposition
$\mathcal{T}^{\prime}$ of $H$. Furthermore, since every induced matching in
$H$ is also an induced matching in $G$, it holds that
$\mu_{G}(\mathcal{T})\geqslant\mu_{H}(\mathcal{T}^{\prime})$, as claimed.

Next, consider the case when $H$ is the graph obtained from $G$ by contracting
an edge $uv\in E(G)$ into a single vertex $z$. In this case, it is not
difficult to see that replacing each bag $X_{t}$ of $\mathcal{T}$ that
contains either $u$ or $v$ (or both) with the bag
$X_{t}^{\prime}\coloneqq(X_{t}\setminus\\{u,v\\})\cup\\{z\\}$ results in a
tree decomposition $\mathcal{T}^{\prime}$ of $H$. We show that
$\mu_{G}(\mathcal{T})\geqslant\mu_{H}(\mathcal{T}^{\prime})$ by verifying that
for every node $t\in V(T)$ and every induced matching $M^{\prime}$ in $H$ that
touches the bag $X_{t}^{\prime}$, there exists an induced matching $M$ in $G$
that touches the bag $X_{t}$ and such that $|M|=|M^{\prime}|$. This will
indeed suffice, since taking $M^{\prime}$ to be a maximum induced matching in
$H^{\prime}$ that touches some bag, say $X_{t}^{\prime}$, of
$\mathcal{T}^{\prime}$, then the corresponding induced matching $M$ in $G$
that touches the bag $X_{t}$ will imply that
$\mu_{G}(\mathcal{T})\geqslant|M|=|M^{\prime}|=\mu_{H}(\mathcal{T}^{\prime})$.

So, let $t\in V(T)$ be a node of $T$ and let $M^{\prime}$ be an induced
matching in $H$ that touches the bag $X_{t}^{\prime}$. We consider two cases
depending on whether the vertex $z$ is an endpoint of an edge in $M^{\prime}$
or not.

Suppose first that the vertex $z$ is not an endpoint of any edge in
$M^{\prime}$. Since the graph $H-z$ is an induced subgraph of $G$, the
matching $M^{\prime}$ is also an induced matching in $G$. Furthermore, since
the matching $M^{\prime}$ touches the bag $X_{t}^{\prime}$ in vertices
different from $z$, the fact that $X_{t}^{\prime}\setminus\\{z\\}\subseteq
X_{t}$ implies that $M^{\prime}$ also touches the bag $X_{t}$. Hence we can
take $M=M^{\prime}$ in this case.

Suppose next that the vertex $z$ is an endpoint of an edge in $M^{\prime}$. In
this case there is a unique edge $e\in M^{\prime}$ such that $z$ is an
endpoint of $e$. We consider two further subcases depending on whether $z$
belongs to the bag $X_{t}^{\prime}$ or not. Suppose first that $z\in
X_{t}^{\prime}$. In this case,
$X_{t}^{\prime}=(X_{t}\setminus\\{u,v\\})\cup\\{z\\}$ and the set
$M\coloneqq(M^{\prime}\setminus\\{e\\})\cup\\{uv\\}$ is an induced matching in
$G$ such that $|M|=|M^{\prime}|$. Furthermore, since the matching
$M\setminus\\{uv\\}=M^{\prime}\setminus\\{e\\}$ touches the set
$X_{t}\setminus\\{u,v\\}=X_{t}^{\prime}\setminus\\{z\\}$ and the edge $uv$
touches $X_{t}$ (since $z\in X_{t}^{\prime}$), we infer that $M$ touches
$X_{t}$.

Finally, suppose that $z\not\in X_{t}^{\prime}$. Then $X_{t}^{\prime}=X_{t}$.
Let $y$ be the endpoint of $e$ other than $z$. Since the edge $e$ touches the
bag $X_{t}$ and $z\not\in X_{t}^{\prime}$, we have $y\in X_{t}$. Moreover, $y$
is a vertex of $G$ such that $uy\in E(G)$ or $vy\in E(G)$. We may assume
without loss of generality that $uy\in E(G)$. Then, the set
$M\coloneqq(M^{\prime}\setminus\\{e\\})\cup\\{uy\\}$ is an induced matching in
$G$ such that $|M|=|M^{\prime}|$. Furthermore, since the matching
$M\setminus\\{uy\\}=M^{\prime}\setminus\\{e\\}$ touches the set
$X_{t}=X_{t}^{\prime}$ and the edge $uy$ touches $X_{t}$, we infer that $M$
touches $X_{t}$. This completes the proof. ∎

Proposition 7.2 implies the following. For an integer $k\geqslant 0$, let
$\mathcal{F}_{k}$ denote the family of all _forbidden induced minors_ for the
class of graphs with induced matching treewidth at most $k$, that is,
$\mathcal{F}_{k}$ consists precisely of the graphs $G$ such that
$\mathsf{tree}\textnormal{-}\mu(G)>k$ but every proper induced minor $H$ of
$G$ satisfies $\mathsf{tree}\textnormal{-}\mu(H)\leqslant k$. Then, by
Proposition 7.2, a graph $G$ has induced matching treewidth at most $k$ if and
only if $G$ does not have any graph from $\mathcal{F}_{k}$ as an induced
minor.

It is not difficult to see that the only graphs with induced matching
treewidth equal to $0$ are exactly the edgeless graphs; hence
$\mathcal{F}_{0}=\\{K_{2}\\}$. To characterize graphs with induced matching
treewidth at most $1$, we will need the following result due to Scheidweiler
and Wiederrecht [67, Theorem 3.6]. We denote by $C_{k}$ the $k$-vertex cycle
graph.

######  Theorem 7.3.

There exists a finite set $\mathcal{F}$ of graphs such that for every graph
$G$, the graph $L^{2}(G)$ is chordal if and only if $G$ does not contain any
graph from the set $\mathcal{F}\cup\\{C_{k}:k\geqslant 6\\}$ as an induced
subgraph.

We now have everything ready to prove the following.

######  Proposition 7.4.

The class of graphs with induced matching treewidth at most $1$ is
characterized by finitely many forbidden induced minors and admits a
polynomial-time recognition algorithm.

###### Proof.

By Proposition 3.1, for every graph $G$, it holds that
$\mathsf{tree}\textnormal{-}\mu(G)=\mathsf{tree}\textnormal{-}\alpha(L^{2}(G))$.
Recall also that a graph $G$ is chordal if and only if
$\mathsf{tree}\textnormal{-}\alpha(G)\leqslant 1$. It follows that a graph $G$
has induced matching treewidth at most $1$ if and only if the square of its
line graph is chordal. By Theorem 7.3, the class of graphs with this property
is characterized by a family of forbidden induced subgraphs consisting of all
cycles of length at least $6$ and a family $\mathcal{F}$ of finitely many
other graphs. Since each forbidden induced minor is also a forbidden induced
subgraph, the family of forbidden induced minors is a subfamily of
$\mathcal{F}\cup\\{C_{k}:k\geqslant 6\\}$. Using also the fact that the
$6$-cycle is an induced minor of any longer cycle, we infer that the set
$\mathcal{F}_{1}$ of forbidden induced minors for the class of graphs with
induced matching treewidth at most $1$ consists of the cycle $C_{6}$ and a
subfamily of $\mathcal{F}$; in particular, it is finite.

Given a graph $G$, testing if the square of its line graph is chordal can be
done in polynomial time (using, e.g., [66]). Therefore, graphs with induced
matching treewidth at most $1$ can be recognized in polynomial time. ∎

###  7.2 Induced matching treewidth in graphs with bounded degree

Recall that the tree-independence number of a graph is an upper bound on its
induced matching treewidth, hence, any graph class with unbounded induced
matching treewidth is necessarily of unbounded tree-independence number. On
the other hand, large tree-independence number does not necessarily imply
large induced matching treewidth, as shown, for example, by the family of
complete bipartite graphs. The balanced complete bipartite graphs $K_{n,n}$
satisfy $\mathsf{tree}\textnormal{-}\alpha(K_{n,n})=n$ (see [32]) and
$\mathsf{tree}\textnormal{-}\mu(K_{n,n})=1$, as witnessed by the trivial tree
decomposition having a unique bag equal to the entire vertex set.

Interestingly, in the absence of complete bipartite graphs as subgraphs,
bounded induced matching treewidth implies bounded tree-independence number
and even bounded treewidth. This follows from a result of Brettell et al. [24,
Proposition 18] who proved a related result for sim-width. Brettell et al.
showed that for any two integers $k,t\in\mathbb{N}$ there exists an integer
$r$ such that each graph with sim-width at most $k$ and no subgraph isomorphic
to $K_{t,t}$ has treewidth at most $r$. It is known that bounded induced
matching treewidth implies bounded sim-width. This is explicitly shown in [14,
Theorem 24] (see also [15]) but in fact the argument boils down to the proof
of [44, Proposition 3.1]. The formal statement of the result for induced
matching treewidth is as follows.

######  Theorem 7.5.

For any two integers $k,t\in\mathbb{N}$ there exists an integer $r$ such that
each graph with induced matching treewidth at most $k$ and no subgraph
isomorphic to $K_{t,t}$ has treewidth at most $r$.

Note that graphs with maximum degree less than $t$ have no subgraph isomorphic
to $K_{t,t}$. Hence, Theorem 7.5 implies that any class of graphs with bounded
degree and unbounded treewidth has unbounded induced matching treewidth. This
includes, for example, the classes of (subdivided) square or hexagonal grids
(also known as _walls_) and their line graphs.

An equivalent formulation is that in classes of graphs with bounded induced
matching treewidth, bounded degree implies bounded treewidth. This implication
(that bounded degree implies bounded treewidth) was recently established by
Abrishami, Chudnovsky, and Vušković [4] for the class of even-hole-free
graphs, and by Korhonen [46] for any class of graphs excluding some fixed grid
(or equivalently, some fixed planar graph) as an induced minor, as well as for
any class of graphs excluding all sufficiently large walls and their line
graphs as induced subgraphs.

The proof of Theorem 7.5 via [24] is based on Ramsey-type arguments and the
binding function is quite large (in particular, it is exponential in $t$). We
now give a simple argument showing that for graphs with bounded degree, the
resulting bound on treewidth is linear in $k$ and polynomial in the maximum
degree. We first show that for graphs with bounded degree, induced matching
treewidth is linearly related to the tree-independence number. As usual, for a
graph $G$, we denote by $\Delta(G)$ the maximum degree of a vertex in $G$.

######  Theorem 7.6.

For every graph $G$ with at least one edge, it holds that
$\mathsf{tree}\textnormal{-}\alpha(G)\leqslant
2\mathsf{tree}\textnormal{-}\mu(G)\cdot\Delta(G)^{2}$.

###### Proof.

Let $G$ be a graph with at least one edge. If $G$ has an isolated vertex, we
can delete it without changing the value of any of the three parameters
$\mathsf{tree}\textnormal{-}\alpha(G)$, $\mathsf{tree}\textnormal{-}\mu(G)$,
and $\Delta(G)$, since they are all strictly positive. We may therefore assume
that $G$ has no isolated vertices. To shorten the notation we will denote
$\Delta\coloneqq\Delta(G)$. Let $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ be a
tree decomposition of $G$ witnessing $\mathsf{tree}\textnormal{-}\mu(G)$. For
all $t\in V(T)$, let $X^{\prime}_{t}=N[X_{t}]$ and let
$\mathcal{T}^{\prime}=(T,\\{X^{\prime}_{t}\\}_{t\in V(T)})$. It is
straightforward to verify that $\mathcal{T}^{\prime}$ is a tree decomposition
of $G$. We want to argue that the independence number of each bag of
$\mathcal{T}^{\prime}$ is at most
$2\mathsf{tree}\textnormal{-}\mu(G)\cdot\Delta^{2}$.

Consider a bag $X^{\prime}_{t}$ of $\mathcal{T}^{\prime}$. It consists of
$X_{t}$ and $Y=N(X_{t})$. Let $I$ be a largest independent set in
$G[X^{\prime}_{t}]$ and let $k$ be its size. We iteratively construct an
induced matching $M$ in $G$ whose every edge intersects $X_{t}$ and
$|M|\geqslant k/(2\Delta^{2})$. As
$|M|\leqslant\mathsf{tree}\textnormal{-}\mu(G)$, this will give
$|I|=k\leqslant\mathsf{tree}\textnormal{-}\mu(G)\cdot 2\Delta^{2}$.

At the beginning, the matching $M$ is empty. In each step of the procedure we
add one edge to $M$ and discard some set of vertices. The procedure stops when
all the vertices in $I$ are discarded. At each step of the procedure we want
to preserve the following properties:

  1. 1.

Each $v\in I$ that is not discarded has a non-discarded neighbor in
$X^{\prime}_{t}$.

  2. 2.

Each $v\in I\cap Y$ that is not discarded has a non-discarded neighbor in
$X_{t}$.

Clearly the above properties are satisfied at the beginning, before any vertex
is discarded, as the graph has no isolated vertices and every vertex from
$I\cap Y$ has a neighbor in $X_{t}$.

Now pick any vertex $v$ in $I$ that was not discarded yet. By properties 1.
and 2. $v$ has a non-discarded neighbor $w$, and if $v\in Y$, then $w$ can be
chosen to be in $X_{t}$. We then include the edge $vw$ in the induced matching
$M$.

Next, we discard the following vertices from $X^{\prime}_{t}$:

  * •

$v$ and $w$,

  * •

every non-discarded neighbor of $v$ or $w$, and

  * •

every non-discarded vertex in $I$ that is at distance 2 from $\\{v,w\\}$ in
$G[X^{\prime}_{t}]$.

Notice that since we removed $N[\\{u,v\\}]\cap X^{\prime}_{t}$, the edges
chosen in every subsequent iteration will indeed form an induced matching. In
each iteration we discard at most $2\Delta^{2}$ vertices from $I$, so,
provided that properties 1. and 2. are preserved, the number of iterations we
perform to build an induced matching $M$ of the desired size is at most
$k/(2\Delta^{2})$. Note also that every edge of $M$ intersects $X_{t}$.

Finally, we prove that at each step of the procedure properties 1. and 2.
hold. To this end, it suffices to show that for each $u\in I$ that is not
discarded, its entire neighborhood in $X^{\prime}_{t}$ is not discarded.
Suppose for a contradiction that there exists some vertex $u^{\prime}\in
N(u)\cap X^{\prime}_{t}$ that is discarded. Clearly $u^{\prime}\notin I$, so
$u^{\prime}$ must be equal or adjacent to $v$ or $w$. However, this means that
$u$ is at distance at most 2 from $\\{v,w\\}$ in $X^{\prime}_{t}$, so $u$ got
discarded, a contradiction. ∎

######  Corollary 7.7.

For every graph $G$ with at least one edge, it holds that

$\mathrm{tw}(G)\leqslant
2\mathsf{tree}\textnormal{-}\mu(G)\cdot\Delta(G)^{2}(\Delta(G)+1)\,.$

###### Proof.

Let $G$ be a graph with at least one edge, let $\Delta$ be its maximum degree
and let $k$ be its induced matching treewidth. By Theorem 7.6, $G$ admits a
tree decomposition in which each bag induces a subgraph with independence
number at most $2k\Delta^{2}$. Since the maximum degree of any such subgraph
is at most $\Delta$, its chromatic number is at most $\Delta+1$. Consequently,
every bag has at most $2k\Delta^{2}(\Delta+1)$ vertices. ∎

###  7.3 Two graph families with unbounded induced matching treewidth

We conclude this section by identifying two graph families with unbounded
maximum degree and unbounded induced matching treewidth. For the proofs, we
need the following well-known property of tree decompositions (see, e.g.,
[32]).

######  Lemma 7.8.

For every graph $G$ and every tree decomposition $\mathcal{T}$ of $G$, there
exists a vertex $v\in V$ such that $N[v]$ is contained in some bag of
$\mathcal{T}$.

For a positive integer $n$, the _$n$ -dimensional hypercube graph_ is the
graph $Q_{n}$ with vertex set $\\{0,1\\}^{n}$ in which two vertices
$x=(x_{1},\ldots,x_{n})$ and $y=(y_{1},\ldots,y_{n})$ are adjacent if and only
if there exists a unique $i\in\\{1,\ldots,n\\}$ such that $x_{i}\neq y_{i}$.

######  Proposition 7.9.

The $n$-dimensional hypercube graph $Q_{n}$ has
$\mathsf{tree}\textnormal{-}\mu(Q_{n})\geqslant\lfloor\frac{n}{2}\rfloor$.

###### Proof.

Consider an arbitrary tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ of $Q_{n}$. By Lemma 7.8, there exists a bag $X_{t}$ that contains
$N[v]$ for some $v\in V(Q_{n})=\\{0,1\\}^{n}$. By the symmetry of $Q_{n}$, we
may assume without loss of generality that $v=(0,\ldots,0)$.

Let $v_{i}$ denote the vertex whose only non-zero entry is at the $i$-th
position and let $w_{i,j}$ denote the vertex whose only non-zero entries are
the $i$-th and $j$-th position.

An induced matching $M$ touching $N[v]$ (and thus touching the bag) of size
$\lfloor\frac{n}{2}\rfloor$ is as follows

$M=\left\\{v_{2i}w_{2i,2i-1}\large\mid
i\in\left\lfloor\frac{n}{2}\right\rfloor\right\\}.$

This implies that $\mu(\mathcal{T})$ is at least $\lfloor\frac{n}{2}\rfloor$.
Since $\mathcal{T}$ was arbitrary, we infer that
$\mathsf{tree}\textnormal{-}\mu(Q_{n})\geqslant\lfloor\frac{n}{2}\rfloor$. ∎

Our final result gives a simple construction of a family of $P_{4}$-free
graphs with unbounded induced matching number. Recall that for a positive
integer $n$, we denote by $nK_{2}$ the disjoint union of $n$ copies of
$K_{2}$.

######  Proposition 7.10.

Let $n$ be a positive integer and let $G_{n}$ denote the graph obtained from
two disjoint copies of the graph $nK_{2}$ by adding all possible edges between
them. Then $\mathsf{tree}\textnormal{-}\mu(G_{n})\geqslant n$.

###### Proof.

Let $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ be an arbitrary tree
decomposition of $G_{n}$. By Lemma 7.8, there exists some bag $X_{t}$
containing $N[v]$ for some $v\in V(G_{n})$. By definition of $G_{n}$, the bag
$X_{t}$ contains all the vertices of one of the copies of $nK_{2}$, which form
an induced matching of size $n$. ∎

##  8 Conclusion

The obvious direction for further research is to show 1.2. A somewhat easier,
but still very interesting problem, would be to show the following result,
which is a significant common generalization of both Theorem 2.1 and Corollary
2.4.

######  Conjecture 8.1.

Let $k,r\in\mathbb{N}$ be fixed. Let $G$ be a graph with induced matching
treewidth at most $k$, equipped with a weight function $\mathfrak{w}\colon
V(G)\to\mathbb{Q}_{+}$. In polynomial time we can find a maximum-weight
induced subgraph of $G$ with treewidth at most $r$.

We believe that the right way of approaching 8.1 is to prove an analogue of
Theorem 3.4 and Lemma 4.1: for each node of a tree decomposition of bounded
induced matching treewidth, there is only a polynomial number of states of the
natural dynamic programming algorithm (developed for bounded-treewidth graphs
[20]) that represent an inclusion-maximal induced subgraph of treewidth at
most $r$. However, the space of states in these algorithms is quite
complicated (much more complicated than when finding a largest induced forest)
and it is far from obvious how to re-interpret it in the current setting.

Another interesting question is to try to find a “better parameter” than
induced matching width. If we think of a parameter useful for solving MWIS, it
is natural to expect that for a simple graph such that $K_{n,n}\odot K_{1}$,
i.e., a biclique with additional pending edge added to each vertex, such a
parameter would be bounded. However, by Proposition 3.1, we have
${\mathsf{tree}\textnormal{-}\mu(K_{n,n}\odot
K_{1})}=\mathsf{tree}\textnormal{-}\alpha(K_{n,n})=n$.

Recently, Bergougnoux et al. [15] introduced _one-sided mim-width_ (or _o-mim-
width_), which can be seen as a unification of tree-independence number and
_mim-width_ , which is another well-established graph width parameter useful
in solving MWIS and many other problems [13]. Just like the definition of
induced matching treewidth, the definitions of mim-width and one-sided mim-
width are also based on the size of a maximum induced matching in certain
subgraphs of the graph (however, instead of tree decompositions they are based
on branch decompositions). While induced matching treewidth lower-bounds the
tree-independence number, it turns out that it is incomparable with one-sided
mim-width (and mim-width). Bergougnoux et al. [15] proved a result analogous
to Theorem 2.1 for graphs given with a decomposition with bounded one-sided
mim-width.

Another interesting parameter based on induced matchings and that in fact
captures all these notions (o-mim-width, mim-width, tree-independence number,
and induced matching treewidth) is sim-width. As already mentioned, bounded
induced matching treewidth implies bounded sim-width, but not vice versa; for
example, the graphs from Proposition 7.10, which have unbounded induced
matching treewidth, have bounded sim-width (see, e.g., [44, Proposition 3.6]).
One of the main open problems related to sim-width, first asked in [44], is
whether MWIS is solvable in polynomial time for graphs with bounded sim-width.
If the answer is positive, then results from [55, 24] imply that the same is
true for Max Weight Distance-$d$ Packing for all even $d$. The drawback
however is that a branch decomposition of small sim-width is needed in input,
as it is another open problem to determine whether such decompositions can be
obtained in polynomial time.

The relationships between all these parameters and some others are summarized
in Figure 2.

Figure 2: Relations between some graph width parameters.

Recall that classes of bounded tree-independence number are
$(\mathrm{tw},\omega)$-bounded, i.e., treewidth is bounded by a function of
the clique number [31]. By Theorem 7.5 we know that this is also the case for
classes of bounded induced matching treewidth that additionally exclude some
fixed biclique as a subgraph. Furthermore, excluding bicliques is necessary,
as $\mathrm{tw}(K_{n,n})=n$ and $\mathsf{tree}\textnormal{-}\mu(K_{n,n})=1$.
We believe that the following result, which is a common generalization of
Theorems 7.6 and 7.5, could also hold.

######  Conjecture 8.2.

For any two integers $k,t\in\mathbb{N}$ there exists an integer $r$ such that
each graph with induced matching treewidth at most $k$ and no induced subgraph
isomorphic to $K_{t,t}$ has tree-independence number at most $r$.

The notion of $(\mathrm{tw},\omega)$-boundedness can be seen as a variant of
the extensively studied _$\chi$ -boundedness_, where we ask for which classes
the chromatic number is upper-bounded by a function of the clique number [68].
We believe that graphs of bounded induced matching treewidth are
$\chi$-bounded.

######  Conjecture 8.3.

For any two integers $k,c\in\mathbb{N}$ there exists an integer $r$ such that
each graph with induced matching treewidth at most $k$ and clique number at
most $c$ has chromatic number at most $r$.

Finally, we believe that it would be interesting to explore for what natural
classes of graphs induced matching treewidth is bounded. We remark that such
results are known for the closely related tree-independence number [1, 30].

## References

  * [1] T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl, and K. Vušković.  Tree independence number for (even hole, diamond, pyramid)-free graphs.  CoRR, abs/2305.16258, 2023.
  * [2] T. Abrishami, M. Chudnovsky, S. Hajebi, and S. Spirkl.  Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth.  Advances in Combinatorics, 2022:6:1–29, 2022.
  * [3] T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzążewski, and P. D. Seymour.  Induced subgraphs of bounded treewidth and the container method.  In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1948–1964. SIAM, 2021.
  * [4] T. Abrishami, M. Chudnovsky, and K. Vušković.  Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree.  J. Combin. Theory Ser. B, 157:144–175, 2022.
  * [5] I. Adler.  Width functions for hypertree decompositions.  PhD thesis, Albert-Ludwigs-Universität Freiburg im Breisgau, 2006.
  * [6] B. Ahat, T. Ekim, and Z. C. Taşkın.  Integer programming formulations and benders decomposition for the maximum induced matching problem.  INFORMS J. Comput., 30(1):43–56, 2018.
  * [7] V. E. Alekseev.  An upper bound for the number of maximal independent sets in a graph.  Discrete Mathematics and Applications, 17(4):355–359, 2007.
  * [8] S. Arnborg, D. G. Corneil, and A. Proskurowski.  Complexity of finding embeddings in a $k$-tree.  SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, Apr. 1987.
  * [9] R. Balakrishnan and P. Paulraja.  Powers of chordal graphs.  J. Austral. Math. Soc. Ser. A, 35(2):211–217, 1983.
  * [10] R. Belmonte, M. Lampis, and V. Mitsou.  Defective coloring on classes of perfect graphs.  Discrete Math. Theor. Comput. Sci., 24(1):18, 2022.  Id/No 1.
  * [11] W. Ben-Ameur, M.-A. Mohamed-Sidi, and J. Neto.  The $k$-separator problem: polyhedra, complexity and approximation results.  J. Comb. Optim., 29(1):276–307, 2015.
  * [12] B. Bergougnoux, É. Bonnet, N. Brettell, and O. Kwon.  Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth.  In Y. Cao and M. Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 3:1–3:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [13] B. Bergougnoux, J. Dreier, and L. Jaffke.  A logic-based algorithmic meta-theorem for mim-width.  In N. Bansal and V. Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3282–3304. SIAM, 2023.
  * [14] B. Bergougnoux, T. Korhonen, and I. Razgon.  New width parameters for independent set: One-sided-mim-width and neighbor-depth.  CoRR, abs/2302.10643, 2023.
  * [15] B. Bergougnoux, T. Korhonen, and I. Razgon.  New width parameters for independent set: one-sided-mim-width and neighbor-depth.  In Graph-theoretic concepts in computer science, volume 14093 of Lecture Notes in Comput. Sci., pages 72–85. Springer, Cham, 2023.
  * [16] U. Bertele and F. Brioschi.  Nonserial dynamic programming.  Academic Press, 1972.
  * [17] H. L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.
  * [18] H. L. Bodlaender, É. Bonnet, L. Jaffke, D. Knop, P. T. Lima, M. Milanic, S. Ordyniak, S. Pandey, and O. Suchý.  Treewidth is NP-complete on cubic graphs (and related results).  CoRR, abs/2301.10031, 2023.
  * [19] H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk.  A $c^{k}n$ 5-approximation algorithm for treewidth.  SIAM J. Comput., 45(2):317–378, 2016.
  * [20] H. L. Bodlaender and T. Kloks.  Efficient and constructive algorithms for the pathwidth and treewidth of graphs.  J. Algorithms, 21(2):358–402, 1996.
  * [21] M. Bonamy, E. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire, S. Thomassé, and A. Wesolek.  Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.  In N. Bansal and V. Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3006–3028. SIAM, 2023.
  * [22] R. B. Borie, R. G. Parker, and C. A. Tovey.  Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families.  Algorithmica, 7(5&6):555–581, 1992.
  * [23] V. Bouchitté and I. Todinca.  Treewidth and minimum fill-in: Grouping the minimal separators.  SIAM J. Comput., 31(1):212–232, 2001.
  * [24] N. Brettell, A. Munaro, D. Paulusma, and S. Yang.  Comparing width parameters on graph classes.  CoRR, abs/2308.05817, 2023.
  * [25] K. Cameron and P. Hell.  Independent packings in structured graphs.  Math. Program., 105(2-3, Ser. B):201–213, 2006.
  * [26] P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, and L. Trevisan.  From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.  SIAM J. Comput., 49(4):772–810, 2020.
  * [27] B. Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.
  * [28] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms.  Springer, Cham, 2015.
  * [29] C. Dallard, F. V. Fomin, P. A. Golovach, T. Korhonen, and M. Milanič.  Computing tree decompositions with small independence number.  CoRR, abs/2207.09993, 2022.
  * [30] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. III. tree-independence number of graphs with a forbidden structure.  CoRR, abs/2206.15092, 2022.
  * [31] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. I. Graph classes with a forbidden structure.  SIAM J. Discrete Math., 35(4):2618–2646, 2021.
  * [32] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. II. Tree-independence number.  J. Combin. Theory Ser. B, 164:404–442, 2024.
  * [33] I. Dinur.  Mildly exponential reduction from gap 3sat to polynomial-gap label-cover.  Electron. Colloquium Comput. Complex., TR16-128, 2016.
  * [34] P. Duchet.  Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs.  In Topics on perfect graphs, volume 88 of North-Holland Math. Stud., pages 67–96. North-Holland, Amsterdam, 1984.
  * [35] H. Eto, F. Guo, and E. Miyano.  Distance-$d$ independent set problems for bipartite and chordal graphs.  J. Comb. Optim., 27(1):88–99, 2014.
  * [36] F. V. Fomin, I. Todinca, and Y. Villanger.  Large induced subgraphs via triangulations and CMSO.  SIAM J. Comput., 44(1):54–87, 2015.
  * [37] P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski.  Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 330–341. ACM, 2021.
  * [38] P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski.  Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time.  CoRR, abs/2007.11402v3, 2021.
  * [39] M. Grohe and S. Kreutzer.  Methods for algorithmic meta theorems.  In Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Washington, DC, USA, January 5-8, 2009, volume 558 of Contemporary Mathematics, pages 181–206. American Mathematical Society, 2009.
  * [40] A. Grzesik, T. Klimošová, M. Pilipczuk, and M. Pilipczuk.  Polynomial-time algorithm for Maximum Weight Independent Set on $P_{6}$-free graphs.  ACM Trans. Algorithms, 18(1):4:1–4:57, jan 2022.
  * [41] R. Halin.  S-functions for graphs.  Journal of Geometry, 8(1):171–186, 1976.
  * [42] F. Havet, R. J. Kang, and J.-S. Sereni.  Improper coloring of unit disk graphs.  Networks, 54(3):150–164, 2009.
  * [43] B. M. P. Jansen, D. Lokshtanov, and S. Saurabh.  A near-optimal planarization algorithm.  In C. Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802–1811. SIAM, 2014.
  * [44] D. Y. Kang, O.-j. Kwon, T. J. F. Strømme, and J. A. Telle.  A width parameter useful for chordal and co-comparability graphs.  Theoret. Comput. Sci., 704:1–17, 2017.
  * [45] T. Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 184–192. IEEE, 2021.
  * [46] T. Korhonen.  Grid induced minor theorem for graphs of small degree.  J. Combin. Theory Ser. B, 160:206–214, 2023.
  * [47] T. Korhonen and D. Lokshtanov.  An improved parameterized algorithm for treewidth.  In B. Saha and R. A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 528–541. ACM, 2023.
  * [48] E. Lee.  Partitioning a graph into small pieces with applications to path transversal.  In P. N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1546–1558. SIAM, 2017.
  * [49] E. Lee.  Partitioning a graph into small pieces with applications to path transversal.  Math. Program., 177(1-2, Ser. A):1–19, 2019.
  * [50] B. Lin.  Constant approximating k-clique is W[1]-hard.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1749–1756. ACM, 2021.
  * [51] D. Lokshantov, M. Vatshelle, and Y. Villanger.  Independent set in $P_{5}$-free graphs in polynomial time.  In C. Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 570–581. SIAM, 2014.
  * [52] P. Manurangsi and P. Raghavendra.  A birthday repetition theorem and complexity of approximating dense CSPs.  In I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 78:1–78:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017\.
  * [53] D. Marx.  Tractable hypergraph properties for constraint satisfaction and conjunctive queries.  J. ACM, 60(6):42:1–42:51, 2013.
  * [54] P. Misra, V. Raman, M. S. Ramanujan, and S. Saurabh.  Parameterized algorithms for even cycle transversal.  In M. C. Golumbic, M. Stern, A. Levy, and G. Morgenstern, editors, Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers, volume 7551 of Lecture Notes in Computer Science, pages 172–183. Springer, 2012.
  * [55] A. Munaro and S. Yang.  On algorithmic applications of sim-width and mim-width of $(H_{1},H_{2})$-free graphs.  Theoret. Comput. Sci., 955:Paper No. 113825, 20, 2023.
  * [56] J. Nešetřil and P. O. de Mendez.  Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics.  Springer, 2012.
  * [57] S. D. Nikolopoulos and L. Palios.  Minimal separators in $P_{4}$-sparse graphs.  Discrete Math., 306(3):381–392, 2006.
  * [58] Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, and F. Werner.  The complexity of dissociation set problems in graphs.  Discrete Appl. Math., 159(13):1352–1366, 2011.
  * [59] G. Paesani, D. Paulusma, and P. Rzążewski.  Feedback Vertex Set and Even Cycle Transversal for $H$-free graphs: Finding large block graphs.  SIAM J. Discret. Math., 36(4):2453–2472, 2022.
  * [60] B. S. Panda, A. Pandey, J. Chaudhary, P. Dane, and M. Kashyap.  Maximum weight induced matching in some subclasses of bipartite graphs.  J. Comb. Optim., 40(3):713–732, 2020.
  * [61] M. Pilipczuk.  A tight lower bound for Vertex Planarization on graphs of bounded treewidth.  Discret. Appl. Math., 231:211–216, 2017.
  * [62] S. Poljak.  A note on stable sets and colorings of graphs.  Commentationes Mathematicae Universitatis Carolinae, 15:307–309, 1974.
  * [63] F. P. Ramsey.  On a problem of formal logic.  Proc. London Math. Soc. (2), 30:264–286, 1929.
  * [64] N. Robertson and P. D. Seymour.  Graph minors. III. Planar tree-width.  J. Comb. Theory, Ser. B, 36(1):49–64, 1984.
  * [65] N. Robertson and P. D. Seymour.  Graph Minors .XIII. The Disjoint Paths Problem.  J. Comb. Theory, Ser. B, 63(1):65–110, 1995.
  * [66] D. J. Rose, R. E. Tarjan, and G. S. Lueker.  Algorithmic aspects of vertex elimination on graphs.  SIAM Journal on Computing, 5(2):266–283, 1976.
  * [67] R. Scheidweiler and S. Wiederrecht.  On chordal graph and line graph squares.  Discrete Appl. Math., 243:239–247, 2018.
  * [68] A. Scott and P. D. Seymour.  A survey of $\chi$-boundedness.  J. Graph Theory, 95(3):473–504, 2020.
  * [69] S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa.  A new algorithm for generating all the maximal independent sets.  SIAM J. Comput., 6(3):505–517, 1977.
  * [70] M. Yannakakis.  Node-deletion problems on bipartite graphs.  SIAM J. Comput., 10(2):310–327, 1981.
  * [71] N. Yolov.  Minor-matching hypertree width.  In A. Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 219–233. SIAM, 2018.
  * [72] J. You, J. Wang, and Y. Cao.  Approximate association via dissociation.  In Graph-theoretic Concepts in Computer Science, volume 9941 of Lecture Notes in Comput. Sci., pages 13–24. Springer, Berlin, 2016.
  * [73] D. Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  Theory Comput., 3:103–128, 2007.