Humboldt-Universität zu Berlin, Germanybenjamin.scheidt@hu-
berlin.dehttps://orcid.org/0000-0003-2379-3675 Benjamin Scheidt [100]Theory of
computation Finite Model Theory [100]Mathematics of computing Hypergraphs

###### Acknowledgements.

We thank Nicole Schweikardt for helpful discussions.

# On Homomorphism Indistinguishability and Hypertree Depth

Benjamin Scheidt

###### Abstract

$\textsf{GC}^{k}$ is a logic introduced by Scheidt and Schweikardt (2023) to
express properties of hypergraphs It is similar to first-order logic with
counting quantifiers (C) adapted to the hypergraph setting. It has distinct
sets of variables for vertices and for hyperedges and requires vertex
variables to be guarded by hyperedge variables on every quantification.

We prove that two hypergraphs $G$, $H$ satisfy the same sentences in the logic
$\textsf{GC}^{k}$ with _guard depth_ at most $k$ if, and only if, they are
homomorphism indistinguishable over the class of hypergraphs of strict
hypertree depth at most $k$. This lifts the analogous result for tree depth
$\leq k$ and sentences of first-order logic with counting quantifiers of
quantifier rank at most $k$ due to Grohe (2020) from graphs to hypergraphs.
The guard depth of a formula is the quantifier rank with respect to hyperedge
variables, and strict hypertree depth is a restriction of hypertree depth as
defined by Adler, Gavenčiak and Klimošová (2012). To justify this restriction,
we show that for every $H$, the strict hypertree depth of $H$ is at most 1
larger than its hypertree depth, and we give additional evidence that strict
hypertree depth can be viewed as a reasonable generalisation of tree depth for
hypergraphs.

###### keywords:

homomorphism indistinguishability, counting logics, guarded logics,
hypergraphs, incidence graphs, tree depth, elimination forest, hypertree width

##  1 Introduction

The ($k$-dimensional) Weisfeiler-Leman algorithm describes a technique to
classify the vertices (or $k$-tuples) of a graph, by iteratively computing a
colouring (i.e., a classification) of the vertices (or $k$-tuples), which gets
refined each iteration until it stabilises. While it can be used as a way to
(imperfectly) test graphs for isomorphism, it has found many other – seemingly
very different – uses, e.g. reducing the cost of solving linear programs [14],
as graph kernels [28] or even as an architecture for graph neural networks
[29, 22, 13, 12]. For a more in-depth overview on the expressive power of the
Weisfeiler-Leman algorithm itself, consult [17] as a starting point. The
success of the Weisfeiler-Leman algorithm can in part be explained by its
simplicity, but also by the fact that it appears to capture the structure of a
graph really well. This can be explained by its connection to first-order
logic with counting quantifiers and to homomorphism counts over graphs of
bounded tree width. A classical result due to Cai, Fürer and Immerman [5] and
Immerman and Lander [16] says that two graphs are indistinguishable by the
$k$-dimensional Weisfeiler-Leman algorithm if, and only if, they satisfy the
same sentences of first-order logic with counting quantifiers (C) and $k{+}1$
variables ($\textsf{C}^{k{+}1}$).

Dvořák [9] and Dell, Grohe, Rattan [8] related the Weisfeiler-Leman algorithm
to homomorphism counts over graphs of bounded tree width (this was
subsequently generalised to relational structures of bounded tree width by
Butti and Dalmau [3]). They showed that two graphs are homomorphism
indistinguishable over the class $\mathsf{TW}_{k}$ of graphs of tree width at
most $k$ if, and only if, they are indistinguishable by the $k$-dimensional
Weisfeiler-Leman algorithm. Here, two graphs $G$ and $H$ are _homomorphism
indistinguishable_ over a class $\mathfrak{C}$ of graphs, if the number of
homomorphisms from $F$ into $G$ equals the number of homomorphisms from $F$
into $H$ for all $F\in\mathfrak{C}$. Dvořák used the previously mentioned
connection to $\textsf{C}^{k{+}1}$ and an inductive characterisation of the
graphs of bounded tree width to prove this result, while Dell et al. used
elaborate algebraic techniques on vectors containing homomorphism counts.

In recent years, a whole theory has emerged around homomorphism
indistinguishability. There are characterisations of homomorphism
indistinguishability for classes of graphs other than $\mathsf{TW}_{k}$ (cf.
[7, 10, 21, 25]), among which we would like to emphasise the following: A
classical result by Lovász [18], stating that two graphs are isomorphic if,
and only if, they are homomorphism indistinguishable over all graphs; a well-
received result by Mančinska and Roberson [20], stating that two graphs are
homomorphism indistinguishable over the class of planar graphs if, and only
if, they are quantum isomorphic; and, of importance for this paper, Grohe [11]
showed that two graphs are homomorphism indistinguishable over the graphs of
tree depth at most $m$ if, and only if, they satisfy the same sentences of C
with quantifier rank at most $m$ ($\textsf{C}_{m}$). There is also work
concerned with a more fundamental analysis of homomorphism counting from
restricted classes (cf. [2, 15, 23, 24, 27]).

Some real-world problems can be represented by hypergraphs in a much more
natural way than by graphs. The great track record of the Weisfeiler-Leman
method poses the question, whether a similar algorithm exists that works on
_hypergraphs_. A direct application of the Weisfeiler-Leman algorithm on the
incidence structure of a hypergraph is sometimes used. But Böker noted in [4],
that this approach does not capture the hypergraph structure well, since the
algorithm will mix up hyperedges and vertices. Thus, a proper variant of the
Weisfeiler-Leman algorithm that works on hypergraphs is, to the best of our
knowledge, still missing. We believe that establishing results analogous to
the ones mentioned so far can give valuable insight on how the algorithm
should operate on hypergraphs. A first step from this angle is a result by
Scheidt and Schweikardt [26], who lift Dvořák’s result to hypergraphs by
proving the following: two hypergraphs $G$, $H$ are homomorphism
indistinguishable over the class $\mathsf{GHW}_{k}$ of hypergraphs of
generalised hypertree width at most $k$ if, and only if, they satisfy the same
sentences of the logic $\textsf{GC}^{k}$. $\textsf{GC}^{k}$ is a novel logic
introduced in [26]. It has distinct variables for vertices and for hyperedges
and counting quantifiers for both variable types. The main feature of
$\textsf{GC}^{k}$ is that it bounds the number of variables for hyperedges by
$k$, and it requires that vertex variables are ?guarded by? (i.e., contained
in) hyperedge variables on every quantification.

#### Contributions

As the main contribution of this work, we show that two hypergraphs satisfy
the same sentences of the logic $\textsf{GC}^{k}$ with guard depth at most $k$
if, and only if, they are homomorphism indistinguishable over the class of
hypergraphs of strict hypertree depth at most $k$ (Theorem 6.1). The guard
depth is the quantifier depth of the hyperedge variables. This theorem follows
from an inductive characterisation of the class of hypergraphs of strict
hypertree depth $\leq k$, combined with the main technical lemmas of Scheidt
and Schweikardt [26]. We believe that this inductive characterisation is
interesting on its own, since the same technique combined with the core
lemmata in Dvořák’s work [9] can be used to give a concise proof of the
analogous result on graphs due to Grohe [11], which was independently
recognised and shown by Fluck et al. [10] recently. Strict hypertree depth is
a mild restriction of hypertree depth as defined by Adler, Gavenčiak and
Klimošová [1]. This (as it turns out only slight) deviation from hypertree
depth is surprising at first. Because of the properties and relations between
strict hypertree depth and hypertree depth we acquire in this paper, we claim
that strict hypertree depth can be viewed as a reasonable generalisation of
tree depth for hypergraphs too. In particular, we show that the strict
hypertree depth of a hypergraph is at most 1 larger than its hypertree depth
(Theorem 2.5). Moreover, we show that the distinguishing power of homomorphism
counts from hypergraphs of hypertree depth at most $k$ is different from the
distinguishing power of homomorphism counts from their respective incidence
graphs (Theorem 2.10). Compared to other hypergraph parameters, this is very
unexpected.

#### Organisation

The remainder of the paper is organised as follows. Section 2 is dedicated to
the introduction of the necessary notation and definitions. In particular, we
introduce incidence graphs as representations of hypergraphs that will be used
throughout the paper, following Böker [4] and Scheidt and Schweikardt [26].
The notions of (strict) hypertree depth are introduced in Section 2.1,
followed by Section 2.2 where we handle the differences between homomorphisms
between hypergraphs and homomorphisms between incidence graphs. In Section 3
we introduce $k$-labeled incidence graphs that were the principle tool used in
[26] to achieve their result. We utilise them in Section 4 to give an
inductive characterisation of the hypergraphs of strict hypertree depth at
most $k$ (Theorem 4.1). Section 5 is devoted to the logic $\textsf{GC}^{k}$.
In Section 6 we combine the results from Section 4 and Section 2.2 with the
results from [26] to obtain Theorem 6.1. Section 7 concludes the paper with a
summary of the results obtained in this paper, as well as an outlook on
further research directions.

##  2 Preliminaries

Since we heavily rely on the work by Scheidt and Schweikardt [26], we will
keep our notation close to theirs. We denote the set of natural numbers
_including_ 0 by ${\rm Nature}$, the set of _positive_ natural numbers by
${\rm Nature}_{\geq{}1}$, and we write $[n]$ to denote the set
$\\{1,2,\dots,n\\}$. To denote isomorphism of two objects, we use $\cong$. A
tuple is denoted using a bar, e.g. $\overline{a}$. For a given $\ell$-tuple
$\overline{a}$, we use $a_{i}$ to denote the $i$-th element of $\overline{a}$,
i.e., $\overline{a}=(a_{1},a_{2},\dots,a_{\ell})$. For any set $S$, let
$\mathcal{P}(S)$ be the set of subsets of $S$ and let $\mathcal{P}_{k}(S)$ be
the subsets of cardinality exactly $k$. If $S$ is a set of sets, let $\bigcup
S=\bigcup_{s\in S}s$.

For a finite set $S$ of cardinality $\ell\in{\rm Nature}$, a total order $<$
on $S$ and any number $d\in{\rm Nature}$, we say that $\langle
i_{d{+}1},i_{d{+}2}\dots,i_{d{+}\ell}\rangle$ is the _$ <$-enumeration of
$S$_, if $i_{d{+}1}<i_{d{+}2}<\cdots<i_{d{+}\ell}$ and
$\\{i_{d{+1}},\dots,i_{d{+}\ell}\\}=S$. If the order $<$ is clear from the
context, we simply say that $\langle
i_{d{+}1},i_{d{+}2}\dots,i_{d{+}\ell}\rangle$ is the enumeration of $S$. Note
that we usually let $d=0$, i.e., we usually write $\langle
i_{1},\dots,i_{\ell}\rangle$. Furthermore, the enumeration $\langle
i_{d{+}1},i_{d{+}2}\dots,i_{d{+}\ell}\rangle$ of $S$ is empty if, and only if,
$S$ is empty.

We denote a partial function $f$ from $A$ to $B$ by $f\colon A\rightharpoonup
B$, and we let $\operatorname{dom}(f)\coloneqq\\{a\in A\,:\,f(a)\text{ is
defined}\\}$ and $\operatorname{img}(f)\coloneqq\\{b\in B\,:\,\text{ex. }a\in
A\text{ s.t.\ }f(a)=b\\}$. We say that two functions $f$ and $g$ are
_compatible_ , if $f(x)=g(x)$ for all
$x\in\operatorname{dom}(f)\cap\operatorname{dom}(g)$. We identify a (partial)
function $f$ with the set $\\{(x,f(x))\,:\,x\in\operatorname{dom}(f)\\}$
whenever we are using set notation on functions. For example, we write
$f\subseteq g$ to indicate
$\operatorname{dom}(f)\subseteq\operatorname{dom}(g)$ and $f(x)=g(x)$ for all
$x\in\operatorname{dom}(f)$. In particular, by $f\cup g$ we denote the
function $h$ with
$\operatorname{dom}(h)=\operatorname{dom}(f)\cup\operatorname{dom}(g)$ and
$h(x)=f(x)$ for all $x\in\operatorname{dom}(f)$ and $h(x)=g(x)$ for all
$x\in\operatorname{dom}(g)\setminus\operatorname{dom}(f)$. Note that $f$ has
_precedence_ over $g$, but this only matters if $f$ and $g$ are not
compatible. For a (partial) function $f$ and a set
$S\subseteq\operatorname{dom}(f)$ we write $f(S)$ to denote $\\{f(x)\,:\,x\in
S\\}$, and we call the function $g\subseteq f$ with
$\operatorname{dom}(g)\coloneqq S$ the _restriction of $f$ to $S$_. Finally,
we define partial functions inline like this: $\\{a\to 3,b\to 2,c\to 5\\}$. In
particular, the empty set $\varnothing$ denotes a partial function with empty
domain.

#### Graphs, Trees and Forests

An (undirected) graph is a tuple $G=(V(G),E(G))$, where $V(G)$ is a finite set
and $E(G)\subseteq\mathcal{P}_{2}(V(G))$. For a set $S\subseteq V(G)$,
${G}[{S}]$ denotes the subgraph induced by $S$, i.e., $V({G}[{S}])\coloneqq S$
and $E({G}[{S}])\coloneqq E(G)\cap\mathcal{P}_{2}(S)$. A connected component
of a graph is a maximal induced subgraph that is connected. A tree is a
connected acyclic graph and a forest is a graph were each connected component
is a tree. A rooted tree $T$ is a tree with some distinguished node that we
call its _root_ , which we denote by $\omega_{T}$. A rooted forest $F$ is the
disjoint union of a collection of rooted trees. It therefore has a set of
roots denoted by $\operatorname{\Omega}_{F}$. We may omit the index if it is
clear from the context. Note that a rooted tree is also a rooted forest and
that every node $n$ in a rooted forest is contained in a unique connected
component which is a tree that we call the _tree for $n$_ and whose root is
the _root for $n$_.

For a rooted forest $F$ we let $\leq_{F}$ be the induced partial order on the
nodes, i.e., the roots are the minimal elements and $s\leq_{F}t$ if $s$ is on
the unique path from $t$ to its root in $\Omega$. By $\operatorname*{P}(s,t)$
we denote the set of nodes on the path from $s$ to $t$ (including $s$ and
$t$). In particular, if no path from $s$ to $t$ exists,
$\operatorname*{P}(s,t)=\varnothing$. By $\operatorname*{P}(s)$ we denote the
set of nodes on the path from $s$ to the root for $s$ and by
$\operatorname*{\land}(s,t)$ we denote the unique element, if it exists, where
the paths $\operatorname*{P}(s)$, $\operatorname*{P}(t)$ join, i.e.,
$\operatorname*{\land}(s,t)\coloneqq\max_{\leq_{F}}(\operatorname*{P}(s)\cap\operatorname*{P}(t))$.
Notice that $\operatorname*{\land}(s,t)$ is undefined iff $s$ and $t$ are not
in the same tree, and that $\operatorname*{\land}(s,t)=s$, iff $s\leq_{F}t$
(and conversely, $\operatorname*{\land}(s,t)=t$ iff $t\leq_{F}s$).

The subtree $T_{t}$ induced by $t\in V(F)$ is the tree ${F}[{V}]$ with root
$t$ and $V\coloneqq\\{s\in V(T)\,:\,t\leq_{F}s\\}$. The _level_ of a node
$s\in V(F)$ is defined as the number of elements on the path from $s$ to its
root, i.e., $\operatorname{level}(s)\coloneqq|\operatorname*{P}(s)|$. The
_height_ of a rooted tree $T$ is the maximal level, i.e.,
$0pt(T)\coloneqq\max\\{\operatorname{level}(t)\,:\,t\in V(T)\\}$ and the
height of a node $t\in V(T)$ is the height of its induced subtree $T_{t}$,
i.e., $0pt(t)\coloneqq 0pt(T_{t})$.

#### Hyper- and Incidence Graphs

A _hypergraph_ is a tuple $\mathcal{H}=(V,E,\beta)$, where $V$ and $E$ are
disjoint finite sets and $\beta$ is a total function from $E$ to
$\mathcal{P}(V)$ with $V=\bigcup_{e\in E}\beta(e)$. We call the elements of
$V$ _vertices_ and the elements of $E$ _hyperedges_ and for every $e\in E$, we
call $\beta(e)$ its _contents_. We denote $V$ by $V(\mathcal{H})$, $E$ by
$E(\mathcal{H})$ and $\beta$ by $\beta_{\mathcal{H}}$, though we may omit the
index if there is no ambiguity. Notice that, in general, multiple hyperedges
with the same content and hyperedges without content are allowed. We call
$\mathcal{H}$ _simple_ if $\beta$ is injective.

An _incidence graph_ is a tuple $I=(R,B,E)$ consisting of two disjoint finite
sets $R$ and $B$ of _red_ and _blue_ vertices and a relation $E\subseteq
B\times R$. We denote $R$ by $\mathcal{R}(I)$, $B$ by $\mathcal{B}(I)$ and $E$
by $E(I)$. For every $e\in\mathcal{B}(I)$, we let
$\operatorname{\upbeta}(e)\coloneqq\\{v\in\mathcal{R}(I)\,:\,(e,v)\in
E(I)\\}$. Notice that $\operatorname{\upbeta}$ is equivalent in its function
to the map $\beta$ for a hypergraph, hence we denote them similarly. We only
consider incidence graphs where for every $v\in\mathcal{R}(I)$ there is an
$e\in\mathcal{B}(I)$ such that $(e,v)\in E(I)$.

It is easy to see that we can assign an incidence graph to every hypergraph
and the other way around: For every hypergraph $\mathcal{H}$ we let
$I_{\mathcal{H}}\coloneqq(V(\mathcal{H}),E(\mathcal{H}),E)$ where
$E\coloneqq\\{(e,v)\,:\,e\in E(\mathcal{H}),v\in\beta(e)\\}$. Conversely, for
every incidence graph $I$ we let
$\mathcal{H}_{I}\coloneqq(\mathcal{R}(I),\mathcal{B}(I),\beta)$ where
$\beta(e)\coloneqq\\{v\in\mathcal{R}(I)\,:\,(e,v)\in E(I)\\}$ for all
$e\in\mathcal{B}(I)$.

For every set $S\subseteq E(\mathcal{H})$ we define the _induced
subhypergraph_ ${\mathcal{H}}[{S}]$ as
$(V^{\prime},S,\beta_{\mathcal{H}}^{\prime})$ where
$V^{\prime}\coloneqq\bigcup_{e\in S}\beta(e)$ and
$\beta_{\mathcal{H}}^{\prime}$ is the restriction of $\beta_{\mathcal{H}}$ to
$S$. We say that a hypergraph is connected if its incidence graph is
connected. An induced subhypergraph is a connected component, if its
corresponding incidence graph is a connected component.

By $\mathcal{P}_{n}$ we denote the path of $n$ hyperedges, where each
hyperedge contains 2 vertices. I.e., we let $V(\mathcal{P}_{n})=[n{+}1]$,
$E(\mathcal{P}_{n})=\\{e_{i}\,:\,i\in[n]\\}$ and $\beta(e_{i})=\\{i,i{+}1\\}$
for all $i\in[n]$. We may use different names for the vertices if it is
convenient.

$v$$w$$z$$u$$x$$y$$t$ (a) The hypergraph $\mathcal{H}$.

$v$$w$$z$$u$$x$$y$$e$$f$$g$$h$$t$ (b) The IG $I_{\mathcal{H}}$ for
$\mathcal{H}$.

$b$$c$$a$ (c) The hypergraph $\mathcal{G}$.

$b$$c$$a$$i$$j$$k$$\ell$ (d) The IG $I_{\mathcal{G}}$ for $\mathcal{G}$.

Figure 1: Examples for hypergraphs and their corresponding incidence graphs.

######  Example 2.1.

The hypergraph $\mathcal{H}$ illustrated in Figure 1(a) is defined as
$V(\mathcal{H})=\\{u,v,w,x,\allowbreak y,z,t\\}$,
$E(\mathcal{H})=\\{e,f,g,h\\}$ and
$\beta_{\mathcal{H}}=\\{e\to\\{u,v,x\\},f\to\\{v,w,z\\},g\to\\{u,w,y\\},\allowbreak
h\to\\{t,x,y,z\\}\\}$. Its incidence graph $I_{\mathcal{H}}$, depicted in
Figure 1(b), is defined by $\mathcal{R}(I_{\mathcal{H}})=V(\mathcal{H})$,
$\mathcal{B}(I_{\mathcal{H}})=E(\mathcal{H})$ and
$E(I_{\mathcal{H}})=\\{(e,u),(e,v),(e,x),(f,v),(f,w),(f,z),(g,u),(g,w),(g,y),\allowbreak(h,t),(h,x),(h,y),(h,z)\\}$.

The hypergraph $\mathcal{G}$ depicted in Figure 1(c) is defined as
$V(\mathcal{G})=\\{a,b,c\\}$, $E(\mathcal{G})=\\{i,j,k,\ell\\}$ and
$\beta_{\mathcal{G}}\coloneqq\\{i\to\\{a,b\\},j\to\\{b,c\\},k\to\\{a,c\\},\ell\to\\{a,b,c\\}\\}$.
Its incidence graph $I_{\mathcal{G}}$, depicted in Figure 1(d), is defined as
$\mathcal{R}(I_{\mathcal{G}})=V(\mathcal{G})$,
$\mathcal{B}(I_{\mathcal{G}})=E(\mathcal{G})$ and
$E(I_{\mathcal{G}})=\\{(i,a),(i,b),(j,b),(j,c),\allowbreak(k,a),(k,c),(\ell,a),(\ell,b),(\ell,c)\\}$.

###  2.1 Hypertree Depth

The following definition of _elimination forest_ and _hypertree depth_ is due
to Adler, Gavenčiak and Klimošová [1], though they refer to elimination
forests as ?decomposition forests?. We call them elimination forests, since
this reflects their conceptual similarity to elimination forests for graphs
and avoids confusion with hypertree decompositions. Further, we define this
notion in terms of incidence graphs, because we mainly work on those. Do
notice however, that this definition easily translates to hypergraphs and that
it is equivalent to the one given by Adler, Gavenčiak and Klimošová.

######  Definition 2.2 (Hypertree Depth and Elimination Forests, [1]).

Let $I$ be an incidence graph. An _elimination forest_ $(F,\Gamma)$ for $I$
consists of a forest $F$ and a mapping $\Gamma\colon V(F)\to\mathcal{B}(I)$
such that Items 1, 2 and 3 hold. We write $\widehat{\Gamma}(t)$ as shorthand
for $\operatorname{\upbeta}(\Gamma(t))$.

  1. 1.

_Completeness for vertices_ : For every red vertex $v\in\mathcal{R}(I)$, there
is a $t\in V(F)$ such that $v\in\widehat{\Gamma}(t)$.

  2. 2.

_Hyperedge-Containment_ : For every blue vertex $e\in\mathcal{B}(I)$ there are
nodes $s,t\in V(F)$ such that $s\leq_{F}t$ and
$\operatorname{\upbeta}(e)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(s,t))$.

  3. 3.

_Shared heritage_ : For all $s,t\in V(F)$, if
$\widehat{\Gamma}(s)\cap\widehat{\Gamma}(t)\neq\varnothing$, then
$\operatorname*{\land}(s,t)$ is defined and
$\widehat{\Gamma}(s)\cap\widehat{\Gamma}(t)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

The intuition behind Item 3 is that hyperedges can only share the vertices
contained in their common ancestors in the elimination forest. The height of
an elimination forest $(F,\Gamma)$ is simply the height of $F$. The _hypertree
depth of $I$_ is defined as the minimal height over all elimination forests
for $I$, and we denote it by $\operatorname{hd}(I)$. Analogously, we let
$\operatorname{hd}(\mathcal{H})\coloneqq\operatorname{hd}(I_{\mathcal{H}})$
for all hypergraphs. We write $\mathsf{IHD}_{k}$ to denote the class of
incidence graphs of hypertree depth at most $k$ and $\mathsf{HD}_{k}$ to
denote the corresponding class of hypergraphs.

We call an elimination forest $(F,\Gamma)$ _strict_ if $\Gamma$ is bijective.
It is easy to see that the first and second condition are trivially satisfied
when $\Gamma$ is bijective, thus we can redefine the notion of strict
elimination forest in a more succinct manner.

######  Definition 2.3 (Strict Elimination Forest).

Let $I$ be an incidence graph. A _strict elimination forest_ $(F,\Gamma)$ for
$I$ consists of a forest $F$ and a _bijective_ function $\Gamma\colon
V(F)\to\mathcal{B}(I)$ satisfying Item 3 of Definition 2.2. The _strict
hypertree depth of $I$_, denoted by $\operatorname{shd}(I)$, is defined as the
minimal height over all strict elimination forests for $I$. Again, we let
$\operatorname{shd}(\mathcal{H})\coloneqq\operatorname{shd}(I_{\mathcal{H}})$
for every hypergraph $\mathcal{H}$. We write $\mathsf{ISHD}_{k}$ to denote the
class of incidence graphs of strict hypertree depth at most $k$ and
$\mathsf{SHD}_{k}$ to denote the corresponding class of hypergraphs.

$\\{u,v,x\\}$$\\{t,x,y,z\\}$ $\omega$:$\\{v,w,z\\}$$\\{u,w,y\\}$ (a) A
(strict) EF for $\mathcal{H}$.

$\\{a,b,c\\}$ $\omega$:

(b) An EF for $\mathcal{G}$.

$\\{b,c\\}$$\\{a,b,c\\}$ $\omega$:$\\{a,b\\}$$\\{a,c\\}$

(c) A strict EF for $\mathcal{G}$.

$\\{8,9\\}$$\omega$:$\\{4,5\\}$$\\{2,3\\}$$\\{6,7\\}$$\\{1,2\\}$$\\{3,4\\}$$\\{5,6\\}$$\\{7,8\\}$$\\{12,13\\}$$\\{10,11\\}$$\\{14,15\\}$$\\{9,10\\}$$\\{11,12\\}$$\\{13,14\\}$$\\{15,16\\}$
(d) A (strict) elimination forest for $\mathcal{P}_{15}$.

Figure 2: Elimination forests for various (hyper)graphs.

######  Example 2.4.

Consider the hypergraphs $\mathcal{G}$ and $\mathcal{H}$ as well as their
incidence graphs $I_{\mathcal{G}}$, $I_{\mathcal{H}}$ from Example 2.1 (see
Figure 1). Let $(F_{1},\Gamma_{1})$ be defined as follows. $F_{1}$ is a tree
defined by $V(F_{1})=\\{t_{1},t_{2},t_{3},t_{4}\\}$ and
$E(F_{2})\coloneqq\\{\\{t_{1},t_{2}\\},\\{t_{1},t_{3}\\},\\{t_{1},t_{4}\\}\\}$
with root $t_{1}$. $\Gamma_{1}$ is a map defined as $\\{t_{1}\to h,t_{2}\to
e,t_{3}\to f,t_{4}\to g\\}$. $(F_{1},\Gamma_{1})$ is an elimination forest of
height $2$ for $I_{\mathcal{H}}$. It is depicted in Figure 2(a), where we
labeled the node $t_{i}$ with $\widehat{\Gamma}_{1}(t_{i})$. Notice, that
$(F_{1},\Gamma_{1})$ is strict.

Analogously, we depicted two elimination forests for $I_{\mathcal{G}}$ of
height 1 and 2 in Figures 2(c) and 2(c). Notice how the elimination forest
depicted in Figure 2(c), witnessing $\operatorname{hd}(\mathcal{G})=1$, is not
strict. It is easy to see that $\operatorname{shd}(\mathcal{G})\geq 2$ since a
bijective map implies that there are as many nodes in the forest as there are
edges. Thus, Figure 2(c) witnesses that $\operatorname{shd}(\mathcal{G})=2$.

Finally, Figure 2(d) depicts a (strict) elimination forest for
$\mathcal{P}_{15}$ witnessing $\operatorname{shd}(\mathcal{P}_{15})\leq 4$.
Recall that $\mathcal{P}_{15}$ is defined by $V(\mathcal{P}_{15})=[16]$ and
$E(\mathcal{P}_{15})=\\{\\{i,i{+}1\\}\,:\,i\in[15]\\}$.

One can show that the strict hypertree depth of a hypergraph is at most its
hypertree depth increased by one. The main idea is that we can turn every
elimination forest into a strict one, if we add a leaf for every hyperedge
that is currently not being mapped to below the path that contains it
according to Item 2 in Definition 2.2.

######  Theorem 2.5.

For all hypergraphs $\mathcal{H}$,
$\operatorname{hd}(\mathcal{H})\;\leq\;\operatorname{shd}(\mathcal{H})\;\leq\;\operatorname{hd}(\mathcal{H}){+}1$.

######  Proof 2.6.

Let $I$ be an incidence graph. Since every strict elimination forest is also
an elimination forest, $\operatorname{hd}(I)\leq\operatorname{shd}(I)$
trivially holds.

To show $\operatorname{shd}(I)\leq\operatorname{hd}(I)+1$ it suffices to show
that any elimination forest $(F,\Gamma)$ of $I$ can be turned into a strict
elimination forest $(F_{\text{s}},\Gamma_{\text{s}})$ of $I$ where
$0pt(F_{\text{s}})\leq 0pt(F)+1$. In the following we make $\Gamma$ bijective
by inserting new nodes into $F$ as children of leaves. Thus, at the end, the
height of $F_{\text{s}}$ has increased by at most 1.

But first we show that we may assume that $\Gamma$ is already injective. If it
is not, then there are distinct $s,t\in V(F)$ such that $\Gamma(s)=\Gamma(t)$
and w.l.o.g. $\operatorname{level}(s)\geq\operatorname{level}(t)$ and $s$ is
not the root. Let $S\coloneqq\widehat{\Gamma}(s)\cap\widehat{\Gamma}(t)$
($=\widehat{\Gamma}(s)=\widehat{\Gamma}(t)$). Since $(F,\Gamma)$ is an
elimination forest, $\operatorname*{\land}(s,t)$ must be defined,
$\operatorname*{\land}(s,t)\neq s$ and
$S\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$
must hold according to Item 3. If we remove the node $s$ from $F$ by
contracting the edge between $s$ and its parent $p$ (which exists since $s$
can not be the root) and assign $\Gamma(p)$ to the resulting node, the result
$(F^{\prime},\Gamma^{\prime})$ is still an elimination forest. Item 1 is still
satisfied because $\widehat{\Gamma}(s)=\widehat{\Gamma}(t)$. It can easily be
verified that Item 2 is satisfied: Let $e\in\mathcal{B}(I)$, let $u,v\in V(F)$
such that $u\leq_{F}v$ and
$\operatorname{\upbeta}(e)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(u,v))$.
Obviously,
$\operatorname{\upbeta}(e)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(u,\omega))$
where $\omega$ is the root for $u$. Since
$\widehat{\Gamma}(s)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{\land}(s,t))$
and
$\operatorname*{\land}(s,t)\in\operatorname*{P}(s,\omega)\setminus\\{s\\}$,
$\operatorname*{P}(u,\omega)\setminus\\{s\\}$ is still a path in $F^{\prime}$
and
$\operatorname{\upbeta}(e)\subseteq\bigcup\widehat{\Gamma}^{\prime}(\operatorname*{P}(u,\omega)\setminus\\{s\\})$.
Showing that Item 3 is still satisfied is not hard either: Let $u,v\in V(F)$
such that $\widehat{\Gamma}(u)\cap\widehat{\Gamma}(v)$ is not empty. If
$\operatorname*{\land}(u,v)\leq_{F}s$ or $\operatorname*{\land}(u,v)$ is not
$\leq_{F}$-comparable to $s$, then
$\widehat{\Gamma}(u)\cap\widehat{\Gamma}(v)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(u,v)))$
obviously still holds. If $s\leq_{F}\operatorname*{\land}(u,v)$, then
$s\in\operatorname*{P}(\operatorname*{\land}(u,v))$ and
$\operatorname*{\land}(s,t)\in\operatorname*{P}(\operatorname*{\land}(u,v))$.
Using the same argument as before we can show that
$\widehat{\Gamma}^{\prime}(u)\cap\widehat{\Gamma}^{\prime}(v)\subseteq\bigcup\widehat{\Gamma}^{\prime}(\operatorname*{P}(\operatorname*{\land}(u,v)))$
still holds.

In total, we get that $(F^{\prime},\Gamma^{\prime})$ is still an elimination
forest and $0pt(F^{\prime})\leq 0pt(F)$. We can repeat this procedure until
the resulting $\Gamma^{\prime}$ is injective.

Assume that $\Gamma$ is already injective. If $\Gamma$ is surjective, $\Gamma$
is also bijective. Otherwise, let
$\\{e_{1},e_{2},\dots,e_{\ell}\\}\coloneqq\mathcal{B}(I)\setminus\operatorname{img}(\Gamma)$
be the set of blue vertices that are not being mapped to. Since $(F,\Gamma)$
is an elimination forest, there exist $s_{i},t_{i}$ for every $i\in[\ell]$
such that $s_{i}\leq_{F}t_{i}$ and
$\operatorname{\upbeta}(e_{i})\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(s_{i},t_{i}))$
and where $|\operatorname*{P}(s_{i},t_{i})|$ is minimal. We insert a fresh
node $s_{i}^{\prime}$ as a child of $s_{i}$ for every $e_{i}$ and map
$s_{i}^{\prime}$ to $e_{i}$. In precise terms, we let
$F_{\text{s}}=(V(F_{\text{s}}),E(F_{\text{s}}))$ with
$V(F_{\text{s}})=V(F)\mathrel{\dot{\cup}}\\{s_{1}^{\prime},s_{2}^{\prime},\dots,s_{\ell}^{\prime}\\}$
and $E(F_{\text{s}})=E(F)\cup\\{\\{s_{i},s_{i}^{\prime}\\}\,:\,i\in[\ell]\\}$;
and $\Gamma_{\text{s}}(s_{i}^{\prime})\coloneqq e_{i}$ for all $i\in[\ell]$
and $\Gamma_{\text{s}}(t)=\Gamma(t)$ for all $t\in V(F)$.

Obviously, the height of the tree $F_{\text{s}}$ did not increase by more than
1 relative to $F$ and the resulting $\Gamma_{\text{s}}$ is bijective. Since
$\mathcal{R}(I)=\bigcup\operatorname{\upbeta}(\mathcal{B}(I))$ by definition,
Item 1 is trivially satisfied. Since $\Gamma_{\text{s}}$ is bijective, Item 2
is trivially satisfied as well. It remains to verify Item 3: Let $u,v\in
V(F_{\text{s}})$ such that
$S\coloneqq\widehat{\Gamma}_{\text{s}}(u)\cap\widehat{\Gamma}_{\text{s}}(v)$
is not empty. If $u,v\in V(F)$ then this still holds since $(F,\Gamma)$ is an
elimination forest and all $s_{i}^{\prime}$ are leaves. Thus assume w.l.o.g.
that $u=s_{i}^{\prime}$ for some $i\in[\ell]$. Let
$n_{1},\dots,n_{{\hat{\imath}}}$ be the nodes in
$\operatorname*{P}(s_{i},t_{i})$ where
$S\cap\widehat{\Gamma}_{\text{s}}(n_{j})$ is not empty.

_Case 1_ : If $v\neq s_{j}^{\prime}$ for every $j\in[\ell]$, the nodes
$\operatorname*{\land}(n_{j},v)$ must exist and
$\varnothing\neq\widehat{\Gamma}(n_{j})\cap\widehat{\Gamma}(v)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(n_{j},v)))$
holds. Thus, also $\operatorname*{\land}(u,v)$ must exist. Since $F$ is a
forest, all $\operatorname*{\land}(n_{j},v)$ must lie on a path, since
otherwise $F$ would contain a cycle. This means that for the largest
$\operatorname*{\land}(n_{j},v)$ according to $\leq_{F}$, both
$\operatorname*{\land}(n_{j},v)\leq_{F_{\text{s}}}\operatorname*{\land}(u,v)$
and
$S\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(n_{j},v)))$
hold. Thus,
$S\subseteq\bigcup\widehat{\Gamma}_{\text{s}}(\operatorname*{P}(\operatorname*{\land}(u,v)))$.

_Case 2_ : If $v=s_{j}^{\prime}$ for a $j\in[\ell]$, let
$m_{1},\dots,m_{{\hat{\jmath}}}$ be the nodes in
$\operatorname*{P}(s_{j},t_{j})$ where
$S\cap\widehat{\Gamma}_{\text{s}}(m_{j^{\prime}})$ is not empty. Consider the
set of pairs
$M\coloneqq\\{(n_{i^{\prime}},m_{j^{\prime}})\,:\,\widehat{\Gamma}(n_{i^{\prime}})\cap\widehat{\Gamma}(m_{j^{\prime}})\neq\varnothing\\}$.
Again, for all $(n_{i^{\prime}},m_{j^{\prime}})\in M$,
$\operatorname*{\land}(n_{i^{\prime}},m_{j^{\prime}})$ must exist and
$\widehat{\Gamma}(n_{i^{\prime}})\cap\widehat{\Gamma}(m_{j^{\prime}})\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(n_{i^{\prime}},m_{j^{\prime}})))$.
Again, since $F$ is a forest, they must all lie on a path and
$\operatorname*{\land}(u,v)$ must exist. For the largest
$\operatorname*{\land}(n_{\tilde{\imath}},m_{\tilde{\jmath}})$ according to
$\leq_{F}$, it therefore holds that
$\widehat{\Gamma}(n_{i^{\prime}})\cap\widehat{\Gamma}(m_{j^{\prime}})\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(n_{\tilde{\imath}},m_{\tilde{\jmath}})))$
for _all_ $(n_{i^{\prime}},m_{j^{\prime}})\in M$. Since
$\operatorname{\upbeta}(u)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(s_{i},t_{i}))$
and
$\operatorname{\upbeta}(v)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(s_{j},t_{j}))$
hold by construction, it must also hold that
$S=\bigcup_{(n_{i^{\prime}},m_{j^{\prime}})\in
M}\widehat{\Gamma}(n_{i^{\prime}})\cap\widehat{\Gamma}(m_{j^{\prime}})$, and
since
$\operatorname*{\land}(n_{\tilde{\imath}},m_{\tilde{\jmath}})\leq_{F_{\text{s}}}\operatorname*{\land}(u,v)$,
we are done.

Before closing this section, it is easy to see that, due to Item 3 (shared
heritage), every elimination forest of a connected incidence graph is also an
_elimination tree_.

######  Lemma 2.7.

Let $I$ be a connected incidence graph. For every elimination forest
$(F,\Gamma)$ of $I$, $F$ is a tree.

###  2.2 Homomorphisms

While hypergraphs and incidence graphs are conceptually close, their ?natural?
notions of homomorphisms are not the same. Since our interest lies in
hypergraphs, but we are mainly working on incidence graphs in this paper, we
have to relate these notions. Following Scheidt and Schweikardt, we use the
same definitions as Böker [4].

A homomorphism from a hypergraph $\mathcal{H}$ into another hypergraph
$\mathcal{G}$ is a pair of functions $(h_{V}\colon V(\mathcal{H})\to
V(\mathcal{G}),h_{E}\colon E(\mathcal{H})\to E(\mathcal{G}))$ such that for
every $e\in E(\mathcal{H})$ the equality $h_{V}(\beta(e))=\beta(h_{E}(e))$
holds.

A homomorphism from an incidence graph $I$ into another incidence graph $J$ is
a pair of mappings
$(h_{V}\colon\mathcal{R}(I)\to\mathcal{R}(J),h_{E}\colon\mathcal{B}(I)\to\mathcal{B}(J))$
such that $(h_{E}(e),h_{V}(v))\in E(J)$ holds for every edge $(e,v)\in E(I)$.
This is equivalent to the requirement
$h_{V}(\operatorname{\upbeta}(e))\subseteq\operatorname{\upbeta}(h_{E}(e))$.
Thus, the equality that we require for a hypergraph homomorphism is relaxed to
an inclusion for incidence graphs.

Let $A$, $B$ and $\mathfrak{C}$ be two hypergraphs and a class of hypergraphs
or two incidence graphs and a class of incidence graphs. We denote the number
of homomorphisms from $A$ to $B$ by $\hom(A,B)$, and we let
$\operatorname{Hom}(\mathfrak{C},A)$ be the ?vector? that has a row for every
$F\in\mathfrak{C}$ containing $\hom(F,A)$. We say that $A$ and $B$ are
_homomorphism indistinguishable_ over $\mathfrak{C}$
($A\equiv_{\mathfrak{C}}B$), if
$\operatorname{Hom}(\mathfrak{C},A)=\operatorname{Hom}(\mathfrak{C},B)$, i.e.,
if $\hom(F,A)=\hom(F,B)$ for all $F\in\mathfrak{C}$.

The following crucial theorem relates homomorphism indistinguishability over a
class of hypergraphs to homomorphism indistinguishability over the
corresponding class $\mathfrak{C}_{\mathsf{I}}$ of incidence graphs. As noted
in [26], this theorem is implicit in [4], consult Appendix A of the full
version of [26] for details.

######  Theorem 2.8 ([4, 26]).

Let $\mathfrak{C}$ be a class of hypergraphs and let
$\mathfrak{C}_{\mathsf{I}}$ be its corresponding class of incidence graphs. If
$\mathfrak{C}$ is closed under _pumping_ and _local merging_ , then
$\operatorname{Hom}(\mathfrak{C},\mathcal{G})=\operatorname{Hom}(\mathfrak{C},\mathcal{H})$
if, and only if,
$\operatorname{Hom}(\mathfrak{C}_{\mathsf{I}},I_{\mathcal{G}})=\operatorname{Hom}(\mathfrak{C}_{\mathsf{I}},I_{\mathcal{H}})$
for all hypergraphs $\mathcal{G}$ and $\mathcal{H}$.

$\mathfrak{C}$ is closed under pumping, if $H^{\prime}\in\mathfrak{C}$ for
every $H\in\mathfrak{C}$, where $H^{\prime}$ is created from $H$ by inserting
a new vertex into _one_ arbitrary hyperedge of $H$; and closed under local
merging, if $H^{\prime}\in\mathfrak{C}$ for every $H\in\mathfrak{C}$, where
$H^{\prime}$ is created from $H$ by choosing an arbitrary hyperedge $e$ and
then merging two vertices $u,v$ that are both contained in $e$.

It is easy to see that $\mathsf{SHD}_{k}$ is closed under both pumping and
local merging, whereas $\mathsf{HD}_{k}$ is only closed under local merging.
See Appendix A for details.

######  Proposition 2.9.

Let $k\in{\rm Nature}_{\geq{}1}$. The class $\mathsf{SHD}_{k}$ is closed under
pumping and local merging, the class $\mathsf{HD}_{k}$ is closed under local
merging but not under pumping.

The following theorem shows that homomorphism indistinguishability over
$\mathsf{HD}_{k}$ is not equal to homomorphism indistinguishability over
$\mathsf{SHD}_{k}$. Because $\mathsf{SHD}_{k}\subseteq\mathsf{HD}_{k}$,
counting homomorphisms from $\mathsf{HD}_{k}$ is more powerful in the sense
that it distinguishes more hypergraphs. But we also show that it is unequal to
homomorphism indistinguishability over $\mathsf{IHD}_{k}$, which is
unexpected. Since this prohibits us from relating $\mathsf{HD}_{k}$ to any
fragment of GC, it is conceivable that this could pose a problem in other
scenarios too. Thus, we argue that the notion of strict hypertree depth can be
viewed as a reasonable generalisation of tree depth, especially when we recall
that $\mathsf{HD}_{k-1}\subseteq\mathsf{SHD}_{k}\subseteq\mathsf{HD}_{k}$.

$\bullet$$\bullet$$\bullet$$\bullet$ (a) $\mathcal{G}_{1}$

$\bullet$$\bullet$$\bullet$$\bullet$ (b) $\mathcal{H}_{1}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ (c)
$\mathcal{G}_{1}^{\prime}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ (d)
$\mathcal{H}_{1}^{\prime}$

Figure 3: $(\mathcal{G}_{1},\mathcal{H}_{1})$,
$(\mathcal{G}_{1}^{\prime},\mathcal{H}_{1}^{\prime})$ witness Theorem 2.10 for
$k=1$. Circles denote singleton hyperedges.

######  Theorem 2.10.

For every $k\in{\rm Nature}_{\geq{}1}$ there exist pairs of hypergraphs
$(\mathcal{G}_{k},\mathcal{H}_{k})$ and
$(\mathcal{G}_{k}^{\prime},\mathcal{H}_{k}^{\prime})$, such that:

  1. 1.

$\operatorname{Hom}(\mathsf{SHD}_{k},\mathcal{G}_{k})=\operatorname{Hom}(\mathsf{SHD}_{k},\mathcal{H}_{k})$,
but
$\operatorname{Hom}(\mathsf{HD}_{k},\mathcal{G}_{k})\neq\operatorname{Hom}(\mathsf{HD}_{k},\mathcal{H}_{k})$;

  2. 2.

$\operatorname{Hom}(\mathsf{HD}_{k},\mathcal{G}_{k}^{\prime})=\operatorname{Hom}(\mathsf{HD}_{k},\mathcal{H}_{k}^{\prime})$,
but
$\operatorname{Hom}(\mathsf{IHD}_{k},I_{\mathcal{G}_{k}^{\prime}})\neq\operatorname{Hom}(\mathsf{IHD}_{k},I_{\mathcal{H}_{k}^{\prime}})$.

For $k=1$ this is easy to see: A connected hypergraph has strict hypertree
depth $1$ iff it consists of a single hyperedge, whereas a connected
hypergraph has hypertree depth $1$ if one hyperedge contains all vertices. It
is therefore not hard to see that the statement of the theorem holds for $k=1$
using the hypergraphs depicted in Figure 3. For $k\geq 2$ a similar idea for
the construction of $(\mathcal{G}_{k},\mathcal{H}_{k})$ and
$(\mathcal{G}_{k}^{\prime},\mathcal{H}_{k}^{\prime})$ works, but we defer the
details to Appendix B as keeping these (rather long) proofs in the main part
would distract from the paper’s main result.

##  3 k-Labeled Incidence Graphs

Our goal is to give an inductive characterisation of the incidence graphs of
strict hypertree depth at most $k$ (and thus also of hypergraphs of strict
hypertree depth at most $k$). The concepts presented in this section were
first defined in [26], and we adopt their notation and phrasing for the most
part. Note that the $k$-labeled incidence graphs defined here are inspired by
the concept of $k$-labeled graphs as they are used in [6, 9, 10, 19] and
elsewhere. In particular, $k$-labeled graphs are the main tool used by Dvořák
[9] to prove his result. In principle, a _$k$ -labeled incidence graph_ is an
incidence graphs that has _labels_ attached to some of its red and blue
vertices. We have an unbounded number of red labels that can be attached to
red vertices (though the number of labels actually used must always be
finite), but we only have $k$ labels that we can attach to blue vertices. We
are allowed to attach multiple labels to the same vertex, but we are not
required to use all of them. Every red label has an assigned ?guard?, which is
a blue vertex with a label on it. In practice, we will require every red
labeled vertex to be a neighbour of its guard (i.e., we want it to have a
_real_ guard, as defined in the next paragraphs), though it makes the proofs
easier if we do not enforce this in the definition itself. This idea is
formalised as follows.

A $k$-labeled incidence graph is a tuple $L=(I,r,b,g)$, where $I$ is an
incidence graph, $r\colon{\rm Nature}_{\geq{}1}\rightharpoonup\mathcal{R}(I)$,
$b\colon[k]\rightharpoonup\mathcal{B}(I)$ and $g\colon{\rm
Nature}_{\geq{}1}\rightharpoonup[k]$ are partial mappings such that
$\operatorname{dom}(r)$ is finite and
$\operatorname{dom}(g)=\operatorname{dom}(r)$. We use $I_{L}$, $r_{L}$, …to
denote the components of $L$. But to keep the indices from getting overly
complicated, we may write $I^{\prime},r^{\prime},\dots$ and
$I_{i},r_{i},\dots$ instead of $I_{L^{\prime}},r_{L^{\prime}}$ and
$I_{L_{i}},r_{L_{i}},\dots$, respectively. If it is clear from the context, we
may omit the index altogether and simply write $I,r,b,g$.

We say that $L$ _has real guards (w.r.t. $g$)_, if for every
$i\in\operatorname{dom}(r)$ we have $g(i)\in\operatorname{dom}(b)$ and
$(b(g(i)),r(i))\in E(I)$. A $k$-labeled incidence graph $L$ is _label-free_ if
$r_{L}=b_{L}=g_{L}=\varnothing$. We call $I$ the _skeleton_ of $L$. Next, we
define some operations on $k$-labeled incidence graphs. For completeness,
mathematically precise definitions can be found in Appendix C.

For any set $X_{r}\subseteq{\rm Nature}_{\geq{}1}$ of finite size $\ell$ and
any tuple
$\overline{v}=(v_{1},v_{2},\dots,v_{\ell})\in{\mathcal{R}(I_{L})}^{n}$ we
write $L[X_{r}{\to}\overline{v}]$ to denote a copy of $L$ where we modified
$r$ such that $r(i_{j})=v_{j}$ for all $j$ along the enumeration $\langle
i_{1},\dots,i_{\ell}\rangle$ of $X_{r}$, i.e., we introduce, and change the
placement of, some red labels. Similarly, for any
$X_{b}=\\{i_{1},\dots,i_{\ell}\\}\subseteq[k]$ and any
$\overline{e}=(e_{1},e_{2},\dots,e_{\ell})\in{\mathcal{B}(I_{L})}^{\ell}$ we
write $L\langle X_{b}{\to}\overline{e}\rangle$ to denote a copy of $L$ where
we modified $b$ accordingly. We write $L[X_{r}{\to}\bullet]$ ($L\langle
X_{b}{\to}\bullet\rangle$) to denote a copy of $L$ where we _removed_ the red
(blue) labels in $X_{r}$ ($X_{b}$). Note, that we remove _just_ the labels and
_not_ the vertices that carry them. Definition C.1 in Appendix C gives
mathematically precise definitions.

Intuitively, the ?product? $(L_{1}\cdot L_{2})$ or _glueing_ of two
$k$-labeled incidence graphs $L_{1}$, $L_{2}$ is the $k$-labeled incidence
graph $L$ that is created by first taking the disjoint union of $L_{1}$ and
$L_{2}$, followed by repeatedly merging pairs of red (blue) vertices, that
carry a shared red (blue) label. By merging we mean that we replace these
vertices by a single fresh vertex, which inherits their neighbourhoods and
labels. We apply this procedure until there are no more such pairs. The guard
function of $(L_{1}\cdot L_{2})$ is simply $g_{L_{1}}\cup g_{L_{2}}$, i.e., in
theory, $g_{L_{1}}$ has precedence over $g_{L_{2}}$. In practice, we will
require that $g_{L_{1}}$ and $g_{L_{2}}$ are compatible, which means the
precedence of $g_{L_{1}}$ will be irrelevant. Note that the order in which we
merge vertices does not matter, and that if a vertex carries two or more
labels, all vertices carrying any one of these labels will be replaced by a
single fresh vertex that carries _all_ those labels and inherits _all_
neighbourhoods. Finally, for $i\in[2]$ we define mappings
$\operatorname{succ}^{R}_{L_{i}}\colon\mathcal{R}(I_{L_{i}})\to\mathcal{R}(I_{L})$
and
$\operatorname{succ}^{B}_{L_{i}}\colon\mathcal{B}(I_{L_{i}})\to\mathcal{B}(I_{L})$
such that $\operatorname{succ}^{R}_{L_{i}}(v)$ is the red vertex of $I_{L}$
that corresponds to $v\in\mathcal{R}(I_{i})$, and
$\operatorname{succ}^{B}_{L_{i}}(e)$ is the blue vertex of $I_{L}$ that
corresponds to $e\in\mathcal{B}(I_{i})$. Definition C.2 in Appendix C gives
mathematically precise definitions.

######  Example 3.1.

Consider the $k$-labeled incidence graphs $L_{1}$, $L_{2}$ according to
Figures 4(a) and 4(b). In particular, we have

$\displaystyle\begin{array}[pos]{r|cccc}i&1&2&3&5\\\ \hline\cr
r_{1}(i)&u&w&v&w\\\ r_{2}(i)&u&\text{--}&v&w\end{array}$
$\displaystyle\begin{array}[pos]{r|ccc}i&1&2&3\\\ \hline\cr b_{1}(i)&f&g&h\\\
b_{2}(i)&f&g&h\end{array}$ and
$\displaystyle\begin{array}[pos]{r|cccc}i&1&2&3&5\\\ \hline\cr
g_{1}(i)&2&1&1&1\\\ g_{2}(i)&2&\text{--}&1&1\end{array}\quad.$

The product $(L_{1}\cdot L_{2})$ is depicted in Figure 4(c).

So far, we should not be allowed to remove a blue label from a vertex, if it
serves as the guard of a red label. But sometimes we want to _transition_ from
one (real) guard assignment to another (real) guard assignment. I.e., we want
to remove blue labels even if they still guard some red labels, because we
guarantee that we introduce new guards for these labels right away. We
formalise this operation as a special partial function, that assigns new
guards to existing red labels: We call $f\colon{\rm
Nature}_{\geq{}1}\rightharpoonup[k]$ a _transition for $L$ (for $g$)_, if
$\varnothing\neq\operatorname{dom}(f)\subseteq\operatorname{dom}(g)$ and for
all $i\in\operatorname{dom}(g)$ we have that if
$g(i)\in\operatorname{img}(f)$, then $i\in\operatorname{dom}(f)$. This means
that if $f$ reassigns the blue label guarding the red label $i$, then $f$
provides a new guard for $i$. Applying a transition, denoted by
$L[{\leadsto}f]$, means modifying a copy of $L$ as follows: we want to insert
fresh vertices with these blue labels, thus we must first remove all blue
labels, that are currently in use, i.e., we must first remove the labels in
the set
$X_{b}\coloneqq\operatorname{img}(f)\cap\operatorname{dom}(b_{L})\cap\operatorname{img}(g_{L})$
from $b$. Notice that we have to intersect with $\operatorname{dom}(b_{L})$
since we do not require $L$ to have real guards. After removing the labels in
$X_{b}$, we insert $|X_{b}|$ new blue vertices into $I_{L}$, each carrying one
of the blue labels in $X_{b}$, and introduce an edge between $b(f(i))$ and
$r(i)$ for all $i\in\operatorname{dom}(f)$. Finally, we redefine the guard
function as $f\cup g_{L}$.

Note that this procedure can be easily expressed as the product $(M_{f}\cdot
L\langle X_{b}{\to}\bullet\rangle)$ for a suitably defined $k$-labeled
incidence graph $M_{f}$. Definition C.4 in Appendix C gives a mathematically
precise definition.

$v^{3}$$w^{2,5}$$u^{1}$$x$$e$$f^{1}$$g^{2}$$h^{3}$$t$ (a) The $3$-labeled
incidence graph $L_{1}$.

$v^{3}$$w^{5}$$z$$u^{1}$$y$$f^{1}$$g^{2}$$h^{3}$ (b) The $3$-labeled incidence
graph $L_{2}$.

$v^{3}$$w^{2,5}$$z$$u^{1}$$x$$y$$e$$f$$g^{2}$$h^{3}$$t$ (c) An example of
glueing: $(L_{1}\cdot L_{2})$.

$v^{3}$$w^{5}$$z$$u^{1}$$y$$e^{2}$$f^{1}$$g$$h^{3}$ (d) An example of applying
a transition: $L_{1}[{\leadsto}f]$.

Figure 4: $3$-labeled incidence graphs and operations on them. Labels are
encoded as exponents and the guard function is encoded using thicker edges
between the red vertex and its guard.

######  Example 3.2.

Consider the $k$-labeled incidence graph from Example 3.1 and Figure 4(a). The
partial function $f=\\{1\to 2,3\to 2\\}$ is a transition for $L_{1}$. The
result $L_{1}[{\leadsto}f]$ of the application of $f$ on $L_{1}$ is depicted
in Figure 4(d).

We define the class $\mathsf{GLI}_{k}^{i}$ of $k$-labeled incidence graphs
that can be constructed in a way that at most $i$ blue labels are removed ?in
series?.

######  Definition 3.3.

For $k\in{\rm Nature}_{\geq{}1}$ and $i\in{\rm Nature}$ we define the set
$\mathsf{GLI}_{k}^{i}$ inductively as follows.

Base case:

$L\in\mathsf{GLI}_{k}^{0}$ for all $k$-labeled incidence graphs $L$ with
$\operatorname{dom}(r)=\mathcal{R}(I)$, $\operatorname{dom}(b)=\mathcal{B}(I)$
and real guards.

For all $i\in{\rm Nature}$, if $L\in\mathsf{GLI}_{k}^{i}$, then
$L\in\mathsf{GLI}_{k}^{i+1}$.

Glueing

Let $L_{1}\in\mathsf{GLI}_{k}^{i_{1}},\ L_{2}\in\mathsf{GLI}_{k}^{i_{2}}$ have
compatible guard functions and $L=(L_{1}\cdot L_{2})$.
Then, $L\in\mathsf{GLI}_{k}^{i}$ where $i\coloneqq\max\\{i_{1},i_{2}\\}$.

Transitioning

Let $L\in\mathsf{GLI}_{k}^{i}$, let $f$ be a transition for $L$ and
$L^{\prime}=L_{1}[{\leadsto}f]$.
Then, $L^{\prime}\in\mathsf{GLI}_{k}^{i^{\prime}}$ where $i^{\prime}\coloneqq
i+|\operatorname{img}(f)\cap\operatorname{img}(b_{L})\cap\operatorname{img}(g_{L})|$.

Label-Removal

Let $L\in\mathsf{GLI}_{k}^{i}$.

  1. (a)

For $X_{r}\subseteq\operatorname{dom}(r)$,
$L[X_{r}{\to}\bullet]\in\mathsf{GLI}_{k}^{i}$.

  2. (b)

For $X_{b}\subseteq\operatorname{dom}(b)\setminus\operatorname{img}(g)$,
$L\langle X_{b}{\to}\bullet\rangle\in\mathsf{GLI}_{k}^{i^{\prime}}$ where
$i^{\prime}\coloneqq i+|X_{b}|$.

Finally, we let $\mathsf{GLI}^{k}\coloneqq\mathsf{GLI}_{k}^{k}$ for every
$k\in{\rm Nature}$.

##  4 Characterising Hypergraphs of Strict Hypertree Depth at most k

In this section we prove that the inductively defined class $\mathsf{GLI}^{k}$
corresponds precisely to the class $\mathsf{ISHD}_{k}$.

######  Theorem 4.1.

An incidence graph $J$ has strict hypertree depth at most $k$ if, and only if,
there exists a label-free $L\in\mathsf{GLI}^{k}$ such that $I_{L}\cong J$.

In the following, we first show how to construct an incidence graph of strict
hypertree depth at most $k$ as the skeleton of a label-free $k$-labeled
incidence graph in $\mathsf{GLI}^{k}$ (Lemma 4.2). Then we show that every
label-free $L\in\mathsf{GLI}^{k}$ has strict hypertree depth at most $k$
(Lemma 4.4). Theorem 4.1 follows directly from the combination of these two
Lemmata.

For the rest of this section, let $J\in\mathsf{ISHD}_{k}$ and let $(T,\Gamma)$
be a strict elimination forest of height $\leq k$ for $J$. We can w.l.o.g.
assume that $J$ is connected and that $T$ is a tree (Lemma 2.7). Let
$\mathcal{R}(I)=\\{v_{1},v_{2},\dots,v_{m}\\}$ where $m\geq 1$.

$(T,\Gamma)$ will help us decide when to remove (i.e., eliminate) which label
from which blue vertex in the following sense. The core idea is to start with
a trivial $k$-labeled incidence graph for every path from a leaf to the root
in the elimination tree. Then we walk bottom-up along these paths and whenever
several paths join in a node, we apply red and blue vertex removals in a
suitable way on their $k$-labeled incidence graphs, such that afterwards we
can glue them together and receive a $k$-labeled incidence graph that is
isomorphic to the incidence graph induced by the union of said paths. This
idea is illustrated in Example D.1 in Appendix D.

For this we need the following notions: for a $k$-labeled incidence graph $L$,
we say that a red vertex $v\in\mathcal{R}(I_{L})$ is _unlabeled_ , if
$v\not\in\operatorname{img}(r_{L})$. Analogously, a blue vertex
$e\in\mathcal{B}(I_{L})$ is _unlabeled_ , if
$e\not\in\operatorname{img}(b_{L})$. For a node $n$ in a tree $T$, the
_subtree with stem induced by $n$_ is the tree $\dot{T}_{n}$ induced on $T$ by
the set $\operatorname*{P}(n)\cup\\{t\in V(T)\,:\,n\leq_{T}t\\}$. Recall that
$\operatorname*{P}(n)$ is the set of nodes on the path from $n$ to the root
$\omega$ (including $n$ and $\omega$), and notice that the subtree with stem
induced by the root is $T$, i.e., $T_{\omega}=T$, and for every leaf $n$ it is
the path from the root $\omega$ to $n$. For every node $n\in V(T)$ we define
the set
$\operatorname{labels}(n)\coloneqq\\{i\in[m]\,:\,v_{i}\in\widehat{\Gamma}(n)\\}$.
To avoid an overload of notation, we will write $\operatorname{labels}(N)$ to
denote the set $\bigcup_{n\in N}\operatorname{labels}(n)$ and write
${J}[{\dot{T}_{n}}]$ to abbreviate ${J}[{\widehat{\Gamma}(V(\dot{T}_{n}))}]$.

######  Lemma 4.2.

For every $n\in V(T)$ of level $d$ where $\langle t_{1},\dots,t_{d}\rangle$ is
a $\leq_{T}$-enumeration of $\operatorname*{P}(n)$ (i.e., in particular
$t_{1}=\omega$, $t_{d}=n$), there exists an $L_{n}\in\mathsf{GLI}_{k}^{k-d}$
of the form $(I,r,b,g)$ such that

  1. (A)

$\operatorname{dom}(b)=[d]$ and
$\operatorname{dom}(r)=\operatorname{labels}(\operatorname*{P}(n))$;

  2. (B)

$g(i)\coloneqq\min\\{j\in[d]\,:\,v_{i}\in\widehat{\Gamma}(t_{j})\\}$ for every
$i\in\operatorname{dom}(g)$;

  3. (C)

There exists an isomorphism $(\pi_{R},\pi_{B})$ between $I$ and
${J}[{\dot{T}_{n}}]$ such that

    1. (i)

$\pi_{R}(r(i))=v_{i}$ for all $i\in\operatorname{dom}(r)$, and

    2. (ii)

$\pi_{B}(b(j))=\Gamma(t_{j})$ for all $j\in\operatorname{dom}(b)$.

Notice that, in particular, this lemma states $J\cong I_{L_{\omega}}$ for the
root $\omega$ of $T$. But $L_{\omega}$ is not label-free, since
$\operatorname{dom}(b_{L_{\omega}})=\\{1\\}$ and
$\operatorname{dom}(r_{L_{\omega}})=\operatorname{labels}(\operatorname*{P}(\omega))=\operatorname{labels}(\omega)$.
But, the lemma also states that $L_{\omega}\in\mathsf{GLI}_{k}^{d-1}$, since
$\operatorname{level}(\omega)=1$. Thus, $J\cong I_{L^{\prime}}$ for
$L^{\prime}=L_{\omega}[\operatorname{labels}(\omega){\to}\bullet]\langle\\{1\\}{\to}\bullet\rangle$,
and in particular, $L^{\prime}\in\mathsf{GLI}_{k}^{k}$ is label-free. Thus,
this lemma shows the forward direction of Theorem 4.1.

######  Proof 4.3 (Proof of Lemma 4.2).

We prove this claim by (inverse) induction over the level of the node $n\in
V(T)$. *Base Case. Let $n$ be a leaf, then $\dot{T}_{n}$ is simply the path
from $n$ to the root $\omega$.

We let $L_{n}=({J}[{\dot{T}_{n}}],r,b,g)$ where $r(i)\coloneqq v_{i}$ and
$g(i)\coloneqq\min\\{j\in[k]\,:\,v_{i}\in\widehat{\Gamma}(t_{j})\\}$ for all
$i\in[m]$ and $b(j)\coloneqq t_{j}$ for all $j\in[d]$.
$L_{n}\in\mathsf{GLI}_{k}^{0}$ according to the base case of Definition 3.3,
and thus also $L_{n}\in\mathsf{GLI}_{k}^{k-d}$ and Items C, B and A are easily
verified. Inductive Step. Let $n\in V(T)$ be a node of level $d$ that is not a
leaf. Let $n_{1},\dots,n_{\ell}$ be the children of $n$ with $\ell\geq 1$ and
assume that for every $i\in[\ell]$ there exist
$L_{i}\in\mathsf{GLI}_{k}^{k-(d{+}1)}$ and $(\pi_{R}^{i},\pi_{B}^{i})$ such
that Items A, B and C are satisfied.

For every child $n_{i}$ let
$X_{r}^{i}\coloneqq\operatorname{labels}(n_{i})\setminus\operatorname{labels}(\operatorname*{P}(n))$
and let $L_{i}^{\prime}\coloneqq L_{i}[X_{r}^{i}{\to}\bullet]\langle
X_{b}{\to}\bullet\rangle$ with $X_{b}\coloneqq\\{d{+}1\\}$. We let
$L_{n}\coloneqq L^{\prime}_{1}\cdot L^{\prime}_{2}\cdot\cdots\cdot
L^{\prime}_{\ell}$ if $\ell\geq 2$, otherwise $L_{n}\coloneqq L_{1}$. We claim
that $L_{n}\in\mathsf{GLI}_{k}^{d}$ and that it satisfies Items A, B and C.

Let $n_{i}$ be any child of $n$. Obviously,
$L_{i}[X_{r}^{i}{\to}\bullet]\in\mathsf{GLI}_{k}^{k-(d+1)}$. Let
$j\in\operatorname{dom}(r_{i})$ such that $g_{i}(j)=d{+}1$. By induction
hypothesis, this means that $n_{i}$ is the minimal node according to
$\leq_{T}$ where $v_{j}$ appears in $\widehat{\Gamma}$. Thus,
$j\in\operatorname{labels}(n_{i})$ but
$j\not\in\operatorname{labels}(\operatorname*{P}(n))$. Therefore, $j\in
X_{r}^{i}$. Thus,
$d{+}1\not\in\operatorname{img}(g_{L_{i}[X_{r}^{i}{\to}\bullet]})$. By
Definition 3.3 this means that

$L_{i}[X_{r}^{i}{\to}\bullet]\langle
X_{b}{\to}\bullet\rangle\in\mathsf{GLI}_{k}^{k-d}.$ (1)

By induction hypothesis, we have $\operatorname{dom}(b_{i})=[d{+}1]$. Thus,
$\operatorname{dom}(b_{L_{i}^{\prime}})=[d]$.
Since $\operatorname*{P}(n)$ is a subset of $\operatorname*{P}(n_{i})$,
$\operatorname{labels}(\operatorname*{P}(n))$ is also a subset of
$\operatorname{labels}(\operatorname*{P}(n_{i}))$, which means
$\operatorname{labels}(\operatorname*{P}(n))\subseteq\operatorname{dom}(r_{i})$
by induction hypothesis. By definition of $X_{r}^{i}$,
$\operatorname{labels}(\operatorname*{P}(n))$ is also a subset of
$\operatorname{dom}(r_{L^{\prime}_{i}})$. Let
$j\in\operatorname{dom}(r_{L^{\prime}_{i}})$ be any red label in
$L_{i}^{\prime}$. Since $j\not\in X_{r}^{i}$,
$j\not\in\operatorname{labels}(n_{i})$ or
$j\in\operatorname{labels}(\operatorname*{P}(n))$. In both cases, this implies
$j\in\operatorname{labels}(\operatorname*{P}(n))$.

Since all this holds for every child and their guard functions are compatible
according to the induction hypothesis, it is easy to see that
$L_{n}\in\mathsf{GLI}_{k}^{k-d}$ and that it satisfies Item A, whereas Item B
follows directly from the induction hypothesis.

It remains to verify Item C for $n$. For the following, keep in mind that
$I_{L_{i}^{\prime}}=I_{i}$ for all $i\in[\ell]$, since the operations we
applied to create $L_{i}^{\prime}$ only changed the functions $r_{i}$,
$b_{i}$, $g_{i}$.

For every unlabeled vertex $e\in\mathcal{B}(I)$ or $v\in\mathcal{R}(I)$ we
know that there is a unique child $n_{i_{e}}$ or $n_{i_{v}}$ of $n$ and a
unique $e^{\prime}\in\mathcal{B}(I_{i_{e}})$ or
$v^{\prime}\in\mathcal{R}(I_{i_{v}})$ such that
$\operatorname{succ}^{B}_{L_{i_{e}}^{\prime}}(e^{\prime})=e$ or
$\operatorname{succ}^{R}_{L_{i_{v}}^{\prime}}(v^{\prime})=v$ and the other way
around.

Let $\pi_{R}$ and $\pi_{B}$ be defined by

$\displaystyle\pi_{B}(b(j))$ $\displaystyle=\Gamma(t_{j})\enspace$
$\displaystyle\text{for all}\ j\in\operatorname{dom}(b),\quad$
$\displaystyle\pi_{B}(e)$ $\displaystyle=\pi_{B}^{i_{e}}(e^{\prime})\enspace$
$\displaystyle\text{for all}\ e\not\in\operatorname{img}(b)\quad\text{and}$
$\displaystyle\pi_{R}(r(j))$ $\displaystyle=v_{j}\ $ $\displaystyle\text{for
all}\ j\in\operatorname{dom}(r),\;$ $\displaystyle\pi_{R}(v)$
$\displaystyle=\pi_{R}^{i_{v}}(v^{\prime})\ $ $\displaystyle\text{for all}\
v\not\in\operatorname{img}(r).$

Item C is satisfied if $(\pi_{R},\pi_{B})$ is indeed an isomorphism. We first
show that $\pi_{R}$ and $\pi_{B}$ are bijective. They clearly are total
mappings, thus we have to show that they are surjective and injective. Let
$v_{i}\in\mathcal{R}({J}[{\dot{T}_{n}}])$ be a vertex. Then
$v_{i}\in\widehat{\Gamma}(V(\dot{T}_{n}))$.

_Case 1_ : If $v_{i}\in\mathcal{R}({J}[{\Gamma(\operatorname*{P}(n))}])$, then
by definition, $i\in\operatorname{labels}(\operatorname*{P}(n))$. I.e.,
$\pi_{R}(r(i))=v_{i}$. Assume there exists another
$v^{\prime}\in\mathcal{R}(I)$ such that $r(i)\neq v^{\prime}$ but
$\pi_{R}(v^{\prime})=v_{i}$. Then there must be a unique child $n_{j}$ of $n$
such that $\pi_{R}(v^{\prime})=\pi_{R}^{j}(v^{\prime})=v_{i}$. Since
$v_{i}\in\operatorname{labels}(\operatorname*{P}(n))$, $v_{i}$ is also in
$\operatorname{labels}(\operatorname*{P}(n_{j}))$. Thus, by induction
hypothesis, $v^{\prime}\in\operatorname{img}(r_{j})$ and
$r_{j}(i)=v^{\prime}$. Since $v^{\prime}\not\in\operatorname{img}(r)$, the
label must have been removed, i.e., $i\in X_{r}^{j}$. This means
$i\in\operatorname{labels}(n_{j})\setminus\operatorname{labels}(\operatorname*{P}(n))$,
which contradicts the assumption that
$i\in\operatorname{labels}(\operatorname*{P}(n))$. Thus, $v^{\prime}$ can not
exist.

_Case 2_ : Otherwise, $v_{i}\in\mathcal{R}({J}[{\dot{T}_{n_{j}}}])$ for a
unique child $n_{j}$ of $n$. If there were more than one child containing
$v_{i}$, this would imply the first case, i.e.,
$v_{i}\in\mathcal{R}({J}[{\Gamma(\operatorname*{P}(n))}])$, because of Item 3
of Definition 2.2. By induction hypothesis, there exists a
$v^{\prime}\in\mathcal{R}(I_{j})$ such that $\pi_{R}^{j}(v^{\prime})=v_{i}$.
Since $i\not\in\operatorname{labels}(\operatorname*{P}(n))$, either
$v^{\prime}\not\in\operatorname{img}(r_{j})$ or $i\in X_{r}^{j}$. In both
cases, $v^{\prime}\not\in\operatorname{img}(r_{L_{j}^{\prime}})$. Thus, for
$v\in\mathcal{R}(I)$ such that
$\operatorname{succ}^{R}_{L_{j}^{\prime}}(v^{\prime})=v$ we get
$\pi_{R}(v)=v_{i}$. Since
$i\not\in\operatorname{labels}(\operatorname*{P}(n))$, this $v$ is unique.
Hence, in total, $\pi_{R}$ is bijective.

Analogously, it is easy to see that $\pi_{B}$ is bijective since every
$e\in\mathcal{B}({J}[{\dot{T}_{n}}])$ is either in the stem or in
$\mathcal{B}({J}[{\dot{T}_{n_{i}}}])$ for precisely one child $n_{i}$ of $n$.
It remains to show that $(e,v)\in E(I)$ iff $(\pi_{B}(e),\pi_{R}(v))\in
E({J}[{\dot{T}_{n}}])$.

$(e,v)\in E(I)$ holds, iff there is a (not necessarily unique) $j\in[\ell]$
and $e^{\prime}\in\mathcal{B}(I_{j})$, $v^{\prime}\in\mathcal{R}(I_{j})$ such
that $\operatorname{succ}^{B}_{L_{j}^{\prime}}(e^{\prime})=e$,
$\operatorname{succ}^{R}_{L_{j}^{\prime}}(v^{\prime})=v$ and
$(e^{\prime},v^{\prime})\in E(I_{j})$. By induction hypothesis, this is the
case iff $(\pi_{B}^{j}(e^{\prime}),\pi_{R}^{j}(v^{\prime}))\in
E({J}[{\dot{T}_{n_{j}}}])$. It is easy to verify that,
$(\pi_{B}^{j}(e^{\prime}),\pi_{R}^{j}(v^{\prime}))\in
E({J}[{\dot{T}_{n_{j}}}])$ if, and only if,
$(\pi_{B}(\operatorname{succ}^{B}_{L_{j}}(e^{\prime})),\pi_{R}(\operatorname{succ}^{R}_{L_{j}}(v^{\prime})))\in
E({J}[{\dot{T}_{n}}])$. Thus, $(e,v)\in E(I)\iff(\pi_{B}(e),\pi_{R}(v))\in
E({J}[{\dot{T}_{n}}])$.

The following lemma can be shown by induction. On a high level, the idea of
the proof is to only modify the elimination forest, if blue labels are
removed. At that point, we prepend a chain of new nodes to the root(s) of the
elimination forest. If we take the product of two $k$-labeled incidence
graphs, we take the union of the forests, and if we remove red labels, we do
not alter the forest at all.

######  Lemma 4.4.

For every $L\in\mathsf{GLI}_{k}^{d}$ of the form $(I,r,b,g)$ there is a tuple
$(F,\Gamma)$, where $F$ is a forest of height $\leq d$ and $\Gamma$ is a
bijective function from $V(F)$ to
$\mathcal{B}(I)\setminus\operatorname{img}(b)$ satisfying Item A. We write
$\widehat{\Gamma}(t)$ as a shorthand for $\operatorname{\upbeta}(\Gamma(t))$
and $\widetilde{\Gamma}(t)$ as a shorthand for
$\widehat{\Gamma}(t)\setminus\operatorname{img}(r)$.

  1. (A)

For all $s,t\in V(F)$, and all
$v\in\widetilde{\Gamma}(s)\cap\widetilde{\Gamma}(t)\neq\varnothing$ it holds
that:
$v\in\operatorname{\upbeta}(b(j))$ for a $j\in\operatorname{dom}(b)$ or
$\operatorname*{\land}(s,t)$ is defined and
$v\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

Notice that, if $L\in\mathsf{GLI}_{k}^{d}$ is label-free, this guarantees a
strict elimination forest $(F,\Gamma)$ of height $d$ for $I_{L}$. This shows
the backward direction of Theorem 4.1.

######  Proof 4.5 (Proof of Lemma 4.4).

We prove this by induction over the definition of $\mathsf{GLI}_{k}^{d}$.

$\vartriangleright$ Base Case

Let $L\in\mathsf{GLI}_{k}^{0}$. It is easy to see that the empty forest
together with the empty map proves the claim for $L$.

$\vartriangleright$ Inductive Step

Let $L_{1}\in\mathsf{GLI}_{k}^{d_{1}}$, $L_{2}\in\mathsf{GLI}_{k}^{d_{2}}$.
For convenience, let $L_{i}=(I_{i},r_{i},b_{i},g_{i})$.

Induction Hypothesis

There exist $(F_{i},\Gamma_{i})$ proving the lemma for $L_{i}$ with $i\in[2]$.
We assume for convenience, that $F_{1}$ and $F_{2}$ are disjoint.

Induction Claim

There exists a tuple $(F,\Gamma)$ proving the lemma for $L=(I,r,b,g)$
constructed according to the following cases.

*Case Glueing If $L=(L_{1}\cdot L_{2})$, we let $F$ be the disjoint union of $F_{1}$, $F_{2}$. For all $t\in V(F_{1})$, let $\Gamma(t)\coloneqq\operatorname{succ}^{B}_{L_{1}}(\Gamma_{1}(t))$ and for all $t\in V(F_{2})$, let $\Gamma(t)\coloneqq\operatorname{succ}^{B}_{L_{2}}(\Gamma_{2}(t))$. It is easy to see that $F$ has height at most $d=\max\\{d_{1},d_{2}\\}$ and that $\Gamma$ is a bijective map from $V(F)$ to $\mathcal{B}(I)\setminus\operatorname{img}(b)$.

It remains to _verify Item A_: Let $s,t\in V(F)$, let
$v\in\widetilde{\Gamma}(s)\cap\widetilde{\Gamma}(t)$ and let $e_{s}=\Gamma(s)$
and $e_{t}=\Gamma(t)$. If $v\in\operatorname{\upbeta}(b(j))$ for a
$j\in\operatorname{dom}(b)$, there is nothing to show. Thus, assume that all
blue neighbours of $v$ are unlabeled. Since $v\not\in\operatorname{img}(r)$,
either $\operatorname{succ}^{R}_{L_{1}}(v^{\prime})=v$ holds for a
$v^{\prime}\in\mathcal{R}(I_{1})$, or
$\operatorname{succ}^{R}_{L_{2}}(v^{\prime})=v$ holds for a
$v^{\prime}\in\mathcal{R}(I_{2})$. We assume that the first is true, i.e.,
$\operatorname{succ}^{R}_{L_{1}}(v^{\prime})=v$. The second case can be
handled analogously.

All unlabeled blue vertices $e\in\mathcal{B}(I)\setminus\operatorname{img}(b)$
that are neighbours of $v$ must have come from $L_{1}$, because since they are
unlabeled, the only way that $(e,v)\in E(I)$ can hold is that
$(e^{\prime},v^{\prime})\in E(I_{1})$ holds for $e^{\prime}$ such that
$\operatorname{succ}^{B}_{L_{1}}(e^{\prime})=e$. Thus, there exist
$e_{s}^{\prime},e_{t}^{\prime}\in\mathcal{B}(I_{1})$ such that
$\operatorname{succ}^{B}_{L_{1}}(e_{s}^{\prime})=e_{s}$ and
$\operatorname{succ}^{B}_{L_{1}}(e_{t}^{\prime})=e_{t}$. By definition of
$\Gamma$ we can infer that $\Gamma_{1}(s)=e_{s}^{\prime}$ and
$\Gamma_{1}(t)=e_{t}^{\prime}$. I.e., $s,t\in V(F_{1})$ and because of that,
according to the induction hypothesis, $\operatorname*{\land}(s,t)$ is defined
and
$v^{\prime}\in\bigcup\widetilde{\Gamma}_{1}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.
Let $p\in\operatorname*{P}(\operatorname*{\land}(s,t))$ such that
$v^{\prime}\in\widetilde{\Gamma}(p)$. This means $(e^{\prime},v^{\prime})\in
E(I_{1})$ for $e^{\prime}=\Gamma_{1}(p)$ and thus also
$(\operatorname{succ}^{B}_{L_{1}}(e^{\prime}),\operatorname{succ}^{R}_{L_{1}}(v^{\prime}))\in
E(I)$. Since by definition,
$\Gamma(p)=\operatorname{succ}^{B}_{L_{1}}(e^{\prime})$, we get that
$v\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

*Case Transitioning If $L=L_{1}[{\leadsto}f]$ where $f$ is a transition for $L_{1}$, consider the enumeration $\langle j_{1},j_{2},\dots,j_{\ell}\rangle$ of $\operatorname{img}(f)\cap\operatorname{img}(b_{1})\cap\operatorname{img}(g_{1})$. Let $F$ be the tree constructed from $F_{1}$, when we insert a chain $t_{1},\dots,t_{\ell}$ into $F_{1}$, connect all roots in $\operatorname{\Omega}_{F_{1}}$ with $t_{\ell}$ and let $\omega_{F}=t_{1}$. I.e., let $F=(V(F),E(F))$ with $V(F)\coloneqq V(F_{1})\mathrel{\dot{\cup}}\\{t_{1},t_{2},\dots,t_{\ell}\\}$, $\omega_{F}\coloneqq t_{1}$ and

$E(F)\coloneqq
E(F_{1})\;\cup\;\\{\\{t_{i},t_{i{+}1}\\}\,:\,i\in[\ell{-}1]\\}\;\cup\;\\{\\{\omega,t_{\ell}\\}\,:\,\omega\in\operatorname{\Omega}_{F_{1}}\\}.$

Let $\Gamma(t_{i})\coloneqq\operatorname{succ}^{B}_{L_{1}}(b_{1}(j_{i}))$ for
all $i\in[\ell]$ and let
$\Gamma(t)\coloneqq\operatorname{succ}^{B}_{L_{1}}(\Gamma_{1}(t))$ for all
other $t\in V(F)$ (i.e., for $t\in V(F_{1})$). It is easy to see that $F$ is a
forest of height
$d=d_{1}+|\operatorname{img}(f)\cap\operatorname{img}(b_{1})\cap\operatorname{img}(g_{1})|$.

_Verifying Item A_: Let $s,t\in V(F)$, let
$v\in\widetilde{\Gamma}(s)\cap\widetilde{\Gamma}(t)$. Let
$v^{\prime}\in\mathcal{R}(I_{1})$ such that
$\operatorname{succ}^{R}_{L_{1}}(v^{\prime})=v$. If $s=t_{i}$ for
$i\in[\ell]$, then w.l.o.g. $\operatorname*{\land}(s,t)=s$ and Item A is
trivially true. The same holds if $t=t_{i}$ for $i\in[\ell]$. Thus, it remains
to consider that $s,t\in V(F_{1})$. Let $e_{s}^{\prime}$, $e_{t}^{\prime}$ be
the blue vertices such that $\Gamma_{1}(s)=e_{s}^{\prime}$ and
$\Gamma_{1}(t)=e_{t}^{\prime}$. By construction, they are both unlabeled. If
$v\in\operatorname{\upbeta}(b(j))$ for a $j\in\operatorname{dom}(b)$ there is
nothing left to show. Thus assume that this is not the case. Because we
assumed that $v\in\widetilde{\Gamma}(s)\cap\widetilde{\Gamma}(t)$, we know
that
$(\operatorname{succ}^{B}_{L_{1}}(e_{s}^{\prime}),v),(\operatorname{succ}^{B}_{L_{1}}(e_{t}^{\prime}),v)\in
E(I)$. Hence, $(e_{s}^{\prime},v^{\prime}),(e_{t}^{\prime},v^{\prime})\in
E(I_{1})$ and according to the induction hypothesis,
$\operatorname*{\land}(s,t)$ is defined and
$v^{\prime}\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$
unless $v^{\prime}\in\operatorname{\upbeta}(b_{1}(j))$ for a
$j\in\operatorname{dom}(b_{1})$. In the first case we get that
$v\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$
by the same reasoning we used for glueing. If $v^{\prime}\in b_{1}(j)$ but
$v\not\in b(j^{\prime})$ for all $j^{\prime}\in\operatorname{dom}(b)$, then
$j\in\operatorname{img}(f)\cap\operatorname{img}(b_{1})\cap\operatorname{img}(g_{1})$.
I.e., $v^{\prime}\in\operatorname{\upbeta}(b_{1}(j_{i}))$ for some
$i\in[\ell]$. But this also means that
$v\in\operatorname{\upbeta}(\Gamma(t_{i}))$ and since by construction both
$s\leq_{F}t_{i}$ and $t\leq_{F}t_{i}$, $\operatorname*{\land}(s,t)$ is defined
and $t_{i}\in\operatorname*{P}(\operatorname*{\land}(s,t))$ and thus
$v\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

*Case Label-Removal
(a) If $L=L_{1}[X_{r}{\to}\bullet]$ for a set
$X_{r}\subseteq\operatorname{dom}(r_{1})$, let $F=F_{1}$ and let
$\Gamma(t)=\operatorname{succ}^{B}_{L_{1}}(\Gamma_{1}(t))$ for all $t\in
V(F)$.

_Verifying Item A_: Let $s,t\in V(F)$, let
$v\in\widetilde{\Gamma}(s)\cap\widetilde{\Gamma}(t)$. Remember that
$\operatorname{succ}^{R}_{L_{1}}$ is the identity in this case. If
$v\not\in\operatorname{img}(r_{1})$, then it trivially follows from the
induction hypothesis, that Item A still holds for $v$. If
$v\in\operatorname{img}(r_{1})$, then there exists an $i\in X_{r}$ such that
$r_{1}(i)=v$. Thus, $v\in\operatorname{\upbeta}(b_{1}(g_{1}(i)))$, since
$L_{1}$ has real guards. Thus, $v\in\operatorname{\upbeta}(b(j))$ for
$j=g_{1}(i)$ still holds.

(b) If $L=L_{1}\langle X_{b}{\to}\bullet\rangle$ for
$X_{b}\subseteq\operatorname{dom}(b_{1})\setminus\operatorname{img}(g_{1})$,
consider the enumeration $\langle j_{1},j_{2},\dots,j_{\ell}\rangle$ of
$X_{b}$. Let $F$ be the tree constructed from $F_{1}$, when we insert a chain
$t_{1},\dots,t_{\ell}$ into $F_{1}$, connect all roots in
$\operatorname{\Omega}_{F_{1}}$ with $t_{\ell}$ and let $\omega_{F}=t_{1}$.
I.e., let $F=(V(F),E(F))$ with $V(F)\coloneqq
V(F_{1})\mathrel{\dot{\cup}}\\{t_{1},t_{2},\dots,t_{\ell}\\}$,
$\omega_{F}\coloneqq t_{1}$ and

$E(F)\coloneqq
E(F_{1})\;\cup\;\\{\\{t_{i},t_{i{+}1}\\}\,:\,i\in[\ell{-}1]\\}\;\cup\;\\{\\{\omega,t_{\ell}\\}\,:\,\omega\in\operatorname{\Omega}_{F_{1}}\\}.$

Let $\Gamma(t_{i})\coloneqq\operatorname{succ}^{B}_{L_{1}}(b_{1}(j_{i}))$ for
all $i\in[\ell]$ and let
$\Gamma(t)\coloneqq\operatorname{succ}^{B}_{L_{1}}(\Gamma_{1}(t))$ for all
other $t\in V(F)$ (i.e., for $t\in V(F_{1})$).

_Verifying Item A_: If $s=t_{i}$ for $i\in[\ell]$, then w.l.o.g.
$\operatorname*{\land}(s,t)=s$ and Item A is trivially true. The same holds if
$t=t_{i}$ for $i\in[\ell]$. Thus, it remains to consider that $s,t\in
V(F_{1})$. Let $e_{s}^{\prime}$, $e_{t}^{\prime}$ be the blue vertices such
that $\Gamma_{1}(s)=e_{s}^{\prime}$ and $\Gamma_{1}(t)=e_{t}^{\prime}$. By
construction, they are both unlabeled. If $v\in\operatorname{\upbeta}(b(j))$
for a $j\in\operatorname{dom}(b)$ there is nothing left to show. Thus assume
that this is not the case. Because we assumed that
$v\in\widetilde{\Gamma}(s)\cap\widetilde{\Gamma}(t)$, we know that
$(\operatorname{succ}^{B}_{L_{1}}(e_{s}^{\prime}),v),(\operatorname{succ}^{B}_{L_{1}}(e_{t}^{\prime}),v)\in
E(I)$. Hence, $(e_{s}^{\prime},v^{\prime}),(e_{t}^{\prime},v^{\prime})\in
E(I_{1})$ and according to the induction hypothesis,
$\operatorname*{\land}(s,t)$ is defined and
$v^{\prime}\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$
unless $v^{\prime}\in\operatorname{\upbeta}(b_{1}(j))$ for a
$j\in\operatorname{dom}(b_{1})$. In the first case we get that
$v\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$
by the same reasoning we used for glueing. If $v^{\prime}\in b_{1}(j)$ but
$v\not\in b(j^{\prime})$ for all $j^{\prime}\in\operatorname{dom}(b)$, then
$j\in X_{b}$. I.e., $v^{\prime}\in\operatorname{\upbeta}(b_{1}(j_{i}))$ for
some $i\in[\ell]$. But this also means that
$v\in\operatorname{\upbeta}(\Gamma(t_{i}))$ and since by construction both
$s\leq_{F}t_{i}$ and $t\leq_{F}t_{i}$, $\operatorname*{\land}(s,t)$ is defined
and $t_{i}\in\operatorname*{P}(\operatorname*{\land}(s,t))$ and thus
$v\in\bigcup\widetilde{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

##  5 The Logic GCk

This section introduces the logic $\textsf{GC}^{k}$ as defined in [26] and its
restricted fragment $\textsf{GC}_{k}$, consisting of all formulas of guard
depth at most $k$. Let $k$ be a positive natural number, that is fixed for
this section.

#### Variables

$\textsf{GC}^{k}$ uses two different kinds of variables:
$\textsf{VAR}_{\mathtt{v}}\coloneqq\\{\mathtt{v}_{1},\mathtt{v}_{2},\mathtt{v}_{3}\dots\\}$
to address vertices and
$\textsf{VAR}_{\mathtt{e}}\coloneqq\\{\mathtt{e}_{1},\mathtt{e}_{2},\dots,\mathtt{e}_{k}\\}$
to address hyperedges. Notice that the number of variables for hyperedges is
bounded by $k$, but unbounded for vertices. We say that a tuple of the form
$\overline{\mathtt{v}}=(\mathtt{v}_{i_{1}},\dots,\mathtt{v}_{i_{\ell}})\in\textsf{VAR}_{\mathtt{v}}^{\ell}$
or
$\overline{\mathtt{e}}=(\mathtt{e}_{i_{1}},\dots,\mathtt{e}_{i_{\ell}})\in\textsf{VAR}_{\mathtt{e}}^{\ell}$
is a _$\mathtt{v}$ \- or $\mathtt{e}$-tuple_, if
$i_{1}<i_{2}<\cdots<i_{\ell}$. We let
$\operatorname{vars}(\overline{\mathtt{v}})\coloneqq\\{\mathtt{v}_{i_{1}},\dots,\mathtt{v}_{i_{\ell}}\\}$
and
$\operatorname{vars}(\overline{\mathtt{e}})\coloneqq\\{\mathtt{e}_{i_{1}},\dots,\mathtt{e}_{i_{\ell}}\\}$
respectively. We call $\\{i_{1},\dots,i_{\ell}\\}$ the _index set_ of
$\overline{v}$ and $\overline{e}$, respectively.

#### Logical Guards

The key idea behind $\textsf{GC}^{k}$ is that on quantification, vertex
variables must be _guarded_ by hyperedge variables. This is formalised by a
partial function $g\colon{\rm Nature}_{\geq{}1}\rightharpoonup[k]$ with finite
domain (similar to the guard function of a $k$-labeled incidence graph, cf.
Section 3) and its corresponding _logical guard_
$\Delta_{g}\coloneqq\bigwedge_{i\in\operatorname{dom}(g)}E(\mathtt{e}_{g(i)},\mathtt{v}_{i})$.
For the special partial function $g$ with empty domain, we let
$\Delta_{g}\coloneqq\top$, which is a special formula that always evaluates to
true.

######  Definition 5.1.

The logic $\textsf{GC}^{k}$ is inductively defined along with the _free vertex
variables_ , the _free hyperedge variables_ and the _guard depth_ , as
formalised by the functions

$\textstyle\operatorname*{free}_{\mathtt{v}}\colon\textsf{GC}^{k}\to\mathcal{P}(\textsf{VAR}_{\mathtt{v}})\,,\quad\textstyle\operatorname*{free}_{\mathtt{e}}\colon\textsf{GC}^{k}\to\mathcal{P}(\textsf{VAR}_{\mathtt{e}})\,,\quad\text{and}\quad\operatorname*{gd}\colon\textsf{GC}^{k}\to{\rm
Nature}.$

Atomic Formulas

For all $i,i^{\prime}\in{\rm Nature}_{\geq{}1}$ and all $j,j^{\prime}\in[k]$
the following formulas are in $\textsf{GC}^{k}$:

  * •

$\varphi\,=\,\mathtt{v}_{i}\kern 1.0pt{=}\kern 1.0pt\mathtt{v}_{i^{\prime}}$
with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\\{\mathtt{v}_{i},\mathtt{v}_{i^{\prime}}\\}$
and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\varnothing$;

  * •

$\varphi\,=\,\mathtt{e}_{j}\kern 1.0pt{=}\kern 1.0pt\mathtt{e}_{j^{\prime}}$
with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\varnothing$ and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\\{\mathtt{e}_{j},\mathtt{e}_{j^{\prime}}\\}$;

  * •

$\varphi\,=\,E(\mathtt{e}_{j},\mathtt{v}_{i})$ with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\\{\mathtt{v}_{i}\\}$
and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\\{\mathtt{e}_{j}\\}$.

In all the above cases, $\operatorname*{gd}(\varphi)\coloneqq 0$.

Inductive Rules

Let $\chi,\psi$ be formulas of $\textsf{GC}^{k}$. The following formulas are
in $\textsf{GC}^{k}$.

  * •

$\varphi\,=\,\lnot\chi$ with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{v}}(\chi)$
and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{e}}(\chi)$,
and $\operatorname*{gd}(\varphi)\coloneqq\operatorname*{gd}(\chi)$;

  * •

$\varphi\,=\,(\chi\land\psi)$ with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{v}}(\chi)\cup\textstyle\operatorname*{free}_{\mathtt{v}}(\psi)$
and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{e}}(\chi)\cup\textstyle\operatorname*{free}_{\mathtt{e}}(\psi)$,
and
$\operatorname*{gd}(\varphi)\coloneqq\max\\{\,\operatorname*{gd}(\chi),\,\operatorname*{gd}(\psi)\,\\}$.

Note that by the rules defined so far, $\operatorname*{gd}(\Delta_{g})=0$ for
all logical guards $\Delta_{g}$.

We say that _$g\colon{\rm Nature}_{\geq{}1}\rightharpoonup[k]$ is a guard
function for $\varphi$_ if
$\operatorname{dom}(g)=\\{i\,:\,\mathtt{v}_{i}\in\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\\}$.

Let $n\in{\rm Nature}_{\geq{}1}$, let $g$ be a guard function for $\psi$ and
$\chi=(\Delta_{g}\land\psi)$. The following formulas are in $\textsf{GC}^{k}$
for every $\mathtt{v}$-tuple $\overline{\mathtt{v}}$ with
$\operatorname{vars}(\overline{\mathtt{v}})\subseteq\textstyle\operatorname*{free}_{\mathtt{v}}(\chi)$
and every $\mathtt{e}$-tuple $\overline{\mathtt{e}}$ with
$\operatorname{vars}(\overline{\mathtt{e}})\subseteq\textstyle\operatorname*{free}_{\mathtt{e}}(\chi)$:

  * •

$\varphi\,=\,\exists^{\scalebox{0.6}{$\geq$}n}\overline{\mathtt{v}}\mathbin{.}\chi$
with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{v}}(\chi)\setminus\operatorname{vars}(\overline{\mathtt{v}})$
and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{e}}(\chi)$,
and $\operatorname*{gd}(\varphi)\coloneqq\operatorname*{gd}(\chi)$;

  * •

$\varphi\,=\,\exists^{\scalebox{0.6}{$\geq$}n}\overline{\mathtt{e}}\mathbin{.}\chi$
with
$\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{v}}(\chi)$
and
$\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{e}}(\chi)\setminus\operatorname{vars}(\overline{\mathtt{e}})$,
and
$\operatorname*{gd}(\varphi)\coloneqq\operatorname*{gd}(\chi)+|\operatorname{vars}(\overline{\mathtt{e}})|$.

For convenience, we let
$\textstyle\operatorname*{free}(\varphi)\coloneqq\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\cup\textstyle\operatorname*{free}_{\mathtt{e}}(\varphi)$
for all $\varphi\in\textsf{GC}^{k}$. Formulas of $\textsf{GC}^{k}$ are
evaluated over a hypergraph $\mathcal{H}$ via interpretations
$\mathcal{I}=(I_{\mathcal{H}},\nu_{\mathtt{v}},\nu_{\mathtt{e}})$ that consist
of $\mathcal{H}$’s incidence graph $I_{\mathcal{H}}$ and assignments
$\nu_{\mathtt{v}}\colon\textsf{VAR}_{\mathtt{v}}\to\mathcal{R}(I_{\mathcal{H}})$
and
$\nu_{\mathtt{e}}\colon\textsf{VAR}_{\mathtt{e}}\to\mathcal{B}(I_{\mathcal{H}})$.
The semantics of $\textsf{GC}^{k}$ are as expected and a definition can be
found in Section 6 of the full version of [26], thus we do not give one here.
A _sentence_ is a formula $\varphi\in\textsf{GC}^{k}$ that has neither free
vertex, nor free hyperedge variables, i.e.,
$\textstyle\operatorname*{free}(\varphi)=\varnothing$. By
$\textsf{GC}^{k}_{d}$ we denote the fragment
$\\{\varphi\in\textsf{GC}^{k}\,:\,\operatorname*{gd}(\varphi)\leq d\\}$, and
we let $\textsf{GC}_{k}\coloneqq\textsf{GC}^{k}_{k}$. We write
$\mathcal{G}\equiv_{\textsf{L}}\mathcal{H}$ to denote that $\mathcal{G}$ and
$\mathcal{H}$ satisfy the same sentences in the fragment
$\textsf{L}\subseteq\textsf{GC}^{k}$.

For simplicity, we omit logical guards if they are empty or equal to the
formula they are guarding. I.e., we may abbreviate subformulas of the form
$(\top\land\varphi)$ or $(\varphi\land\varphi)$ as $\varphi$. We may also omit
parentheses in the usual way. We write
$\exists^{\scalebox{0.6}{$=$}n}(\overline{\mathtt{x}})\mathbin{.}(\Delta\land\varphi)$
as shorthand for
$\exists^{\scalebox{0.6}{$\geq$}n}(\overline{\mathtt{x}})\mathbin{.}(\Delta\land\varphi)\land\lnot\exists^{\scalebox{0.6}{$\geq$}n{+}1}(\overline{\mathtt{x}})\mathbin{.}(\Delta\land\varphi)$.
Clearly, these shorthands change neither the semantics, nor the free
variables, nor the guard depth of a formula.

######  Example 5.2.

The sentence
$\varphi_{\mathcal{G}}\coloneqq\psi_{1}\land\psi_{2}\land\psi_{3}$ describes
$\mathcal{G}$ from Example 2.1 up to isomorphism, where

$\displaystyle\chi_{n}\;$ $\displaystyle\coloneqq\textstyle\bigwedge_{1\leq
i<j\leq n}\lnot\mathtt{v}_{i}\kern 1.0pt{=}\kern
1.0pt\mathtt{v}_{j}\;\land\;\lnot\exists^{\scalebox{0.6}{$\geq$}1}(\mathtt{v}_{n{+}1})\mathbin{.}\Bigl{(}E(\mathtt{e},\mathtt{v}_{n{+}1})\;\land\;\bigwedge_{i\in[n]}\lnot\mathtt{v}_{n{+}1}=\mathtt{v}_{i}\Bigr{)}\,,$
$\displaystyle\psi_{1}\,$
$\displaystyle\coloneqq\,\exists^{\scalebox{0.6}{$=$}4}(\mathtt{e})\mathbin{.}\mathtt{e}\kern
1.0pt{=}\kern 1.0pt\mathtt{e}\,,$ $\displaystyle\psi_{2}\,$
$\displaystyle\coloneqq\,\exists^{\scalebox{0.6}{$=$}1}(\mathtt{e})\mathbin{.}\exists^{\scalebox{0.6}{$\geq$}1}(\mathtt{v}_{1},\mathtt{v}_{2},\mathtt{v}_{3})\mathbin{.}\Bigl{(}\textstyle\bigwedge_{i\in[3]}E(\mathtt{e},\mathtt{v}_{i})\;\land\;\chi_{3}\;\land\;\textstyle\bigwedge_{i\in[3]}\exists^{\scalebox{0.6}{$=$}3}(\mathtt{e})\mathbin{.}E(\mathtt{e},v_{i})\Bigr{)}\,\vphantom{\Bigl{(}\Bigr{)}},$
$\displaystyle\psi_{3}\,$
$\displaystyle\coloneqq\,\exists^{\scalebox{0.6}{$=$}3}(\mathtt{e})\mathbin{.}\exists^{\scalebox{0.6}{$\geq$}1}(\mathtt{v}_{1},\mathtt{v}_{2})\mathbin{.}\Bigl{(}\textstyle\bigwedge_{i\in[2]}E(\mathtt{e},\mathtt{v}_{i})\;\land\;\chi_{2}\;\land\;\textstyle\bigwedge_{i\in[3]}\exists^{\scalebox{0.6}{$=$}3}(\mathtt{e})\mathbin{.}E(\mathtt{e},v_{i})\Bigr{)}\,.$

It is easily verified that $\varphi_{\mathcal{G}}\in\textsf{GC}^{1}_{2}$.
$\chi_{n}$ is a helper formula, describing that there are precisely $n$
vertices $\mathtt{v}_{1},\dots,\mathtt{v}_{n}$ in the hyperedge $\mathtt{e}$.
$\psi_{1}$ describes that there are precisely four hyperedges, $\psi_{2}$
describes that precisely one hyperedge contains precisely three vertices, each
being contained in precisely 3 hyperedges. Finally, $\psi_{3}$ describes that
there are exactly 3 hyperedges containing precisely 2 vertices, each being
contained in precisely 3 hyperedges. It is not hard to see that, in total,
this describes $\mathcal{G}$ up to isomorphism.

Scheidt and Schweikardt [26] prove their result only for the following
restricted variant of $\textsf{GC}^{k}$, called $\textsf{RGC}^{k}$. They
mention in the conclusion, that $\textsf{RGC}^{k}$ and $\textsf{GC}^{k}$ are
equivalent and show in the full version of the paper (Theorem 7.2) how a
formula in $\textsf{GC}^{k}$ can be translated into one in $\textsf{RGC}^{k}$.
We still need $\textsf{RGC}^{k}$ since it is used in the formulation and the
proof of the two core lemmata of [26] that we want to borrow.

######  Definition 5.3 ([26]).

The restriction $\textsf{RGC}^{k}$ is inductively defined as follows:

Atomic Formulas

$(\Delta_{g}\land\varphi)$ is in $\textsf{RGC}^{k}$ for all atomic formulas
$\varphi\in\textsf{GC}^{k}$ and all guard functions for $\varphi$, i.e., all
$g\colon{\rm Nature}_{\geq{}1}\rightharpoonup[k]$ with
$\operatorname{dom}(g)=\\{i\,:\,\mathtt{v}_{i}\in\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)\\}$.

Inductive Rules

  * •

For every formula $(\Delta_{g}\land\varphi)\in\textsf{RGC}^{k}$, the formula
$(\Delta_{g}\land\lnot\varphi)$ is also in $\textsf{RGC}^{k}$.

  * •

For $i\in[2]$ and formulas $(\Delta_{g_{i}}\land\psi_{i})\in\textsf{RGC}^{k}$,
the formula $(\Delta_{(g_{1}\cup g_{2})}\land(\psi_{1}\land\psi_{2}))$ is in
$\textsf{RGC}^{k}$, if $g_{1}$ and $g_{2}$ are compatible.

Let $n\in{\rm Nature}_{\geq{}1}$,
$(\Delta_{g}\land\varphi)\in\textsf{RGC}^{k}$.

  * •

For every $\mathtt{v}$-tuple $\overline{\mathtt{v}}$ with
$\operatorname{vars}(\overline{\mathtt{v}})\subseteq\textstyle\operatorname*{free}_{\mathtt{v}}(\varphi)$
and index set $S$, the formula $(\Delta_{\tilde{g}}\land\chi)$ is in
$\textsf{RGC}^{k}$, where

$\chi\coloneqq\exists^{\scalebox{0.6}{$\geq$}n}\overline{\mathtt{v}}\mathbin{.}(\Delta_{g}\land\varphi)\quad\text{and
$\tilde{g}$ is the restriction of $g$ to }\operatorname{dom}(g)\setminus S.$

  * •

For every $\mathtt{e}$-tuple $\overline{\mathtt{e}}$ with
$\operatorname{vars}(\overline{\mathtt{e}})\subseteq\textstyle\operatorname*{free}_{\mathtt{e}}(\Delta_{g}\land\varphi)$
and index set $S$, the formula

$(\Delta_{\tilde{g}}\land\exists^{\scalebox{0.6}{$\geq$}n}\overline{\mathtt{e}}\mathbin{.}(\Delta_{g}\land\varphi))$

is in $\textsf{RGC}^{k}$, if
$\operatorname{dom}(\tilde{g})=\operatorname{dom}(g)$ and all
$i\in\operatorname{dom}(g)$ satisfy

$\tilde{g}(i)=g(i)\quad\text{or}\quad\tilde{g}(i)\in
S\quad\text{or}\quad\tilde{g}(i)\not\in\operatorname{img}(g).$ (2)

Intuitively, formulas in $\textsf{RGC}^{k}$ always carry the information,
which hyperedge variable currently guards which vertex variable and the
logical guards are in a certain sense ?consistent? (2) along the syntax tree.

A simple inspection of the inductive proof for Theorem 7.2 in the full version
of [26] shows that the guard depth is unaffected by the translation, giving us
the following refined result.

######  Lemma 5.4.

For every formula $\varphi\in\textsf{GC}^{k}$ and every guard function $g$ for
$\varphi$, there exists a formula
$(\Delta_{g}\land\varphi_{g})\in\textsf{RGC}^{k}$ such that

  1. 1.

$(\Delta_{g}\land\varphi)\equiv(\Delta_{g}\land\varphi_{g})$,

  2. 2.

$\textstyle\operatorname*{free}(\varphi)=\textstyle\operatorname*{free}(\varphi_{g})$,
and $\operatorname*{gd}(\varphi)=\operatorname*{gd}(\varphi_{g})$.

##  6 Main Result

We are now ready to plug everything together, which yields our main result.

######  Theorem 6.1.

Let $\mathcal{G}$ and $\mathcal{H}$ be hypergraphs and let $k\in{\rm
Nature}_{\geq{}1}$.

$\displaystyle\mathcal{G}\equiv_{\textsf{GC}_{k}}\mathcal{H}$
$\displaystyle\iff\operatorname{Hom}(\mathsf{ISHD}_{k},I_{\mathcal{G}})\,$
$\displaystyle=\;\operatorname{Hom}(\mathsf{ISHD}_{k},I_{\mathcal{H}})$
$\displaystyle\iff\operatorname{Hom}(\mathsf{SHD}_{k},\mathcal{G})$
$\displaystyle=\;\operatorname{Hom}(\mathsf{SHD}_{k},\mathcal{H}).$

We use the fact that the proofs for the core Lemmata 8.1 and 8.2 in the work
by Scheidt and Schweikardt [26] actually give us the following refined
results. This is easy to see on inspection of the original proofs (consult
Appendix E in the full version of [26]), since there is a one-to-one
correspondence between the blue label $i$ and the hyperedge variable
$\mathtt{e}_{i}$ in the proofs for both lemmas: whenever a blue label $i$ is
removed, the corresponding variable $\mathtt{e}_{i}$ is quantified and vice-
versa.

For a $k$-labeled incidence graph $L$ of the form $(I,r,b,g)$, we let
$\mathcal{I}_{L}\coloneqq(I,\nu_{\mathtt{v}},\nu_{\mathtt{e}})$ be defined by
$\nu_{\mathtt{v}}(\mathtt{v}_{i})\coloneqq r(i)$ for all
$i\in\operatorname{dom}(r)$ and $\nu_{\mathtt{e}}(\mathtt{e}_{j})\coloneqq
b(j)$ for all $j\in\operatorname{dom}(b)$.

######  Lemma 6.2 (implicit in [26]).

Let $L=(I,r,b,g)\in\mathsf{GLI}_{k}^{i}$. For every $m\in{\rm Nature}$ there
is a formula $\varphi_{L,m}$ with
$(\Delta_{g}\land\varphi_{L,m})\in\textsf{RGC}^{k}$,
$\textstyle\operatorname*{free}_{\mathtt{v}}(\Delta_{g}\land\varphi_{L,m})=\\{\mathtt{v}_{i}\,:\,i\in\operatorname{dom}(r)\\}$,
$\textstyle\operatorname*{free}_{\mathtt{e}}(\Delta_{g}\land\varphi_{L,m})=\\{\mathtt{e}_{j}\,:\,j\in\operatorname{dom}(b)\\}$,
and $\operatorname*{gd}(\varphi_{L,m})\leq i$, such that for every $k$-labeled
incidence graph $L^{\prime}$ with
$\operatorname{dom}(b_{L^{\prime}})\supseteq\operatorname{dom}(b)$,
$\operatorname{dom}(r_{L^{\prime}})\supseteq\operatorname{dom}(r)$, and with
real guards w.r.t. $g$ we have: $\mathcal{I}_{L^{\prime}}\models\Delta_{g}$,
and $\hom(L,L^{\prime})=m\ \iff\
\mathcal{I}_{L^{\prime}}\models\varphi_{L,m}$.

######  Lemma 6.3 (implicit in [26]).

Let $\chi\coloneqq(\Delta_{g}\land\psi)\in\textsf{RGC}^{k}$ with
$\operatorname*{gd}(\chi)=\ell$ and let $m,d\in{\rm Nature}$ with $m\geq 1$.
There exists a linear combination $Q\coloneqq\sum_{i\in[q]}\alpha_{i}L_{i}$,
and sets
$\textup{dr}_{Q}=\\{i\,:\,\mathtt{v}_{i}\in\textstyle\operatorname*{free}_{\mathtt{v}}(\chi)\\}$
and
$\textup{db}_{Q}=\\{i\,:\,\mathtt{e}_{i}\in\textstyle\operatorname*{free}_{\mathtt{e}}(\chi)\\}$,
where for all $i\in[q]$:

$\displaystyle\alpha_{i}\in\mathbb{R},\quad
L_{i}\in\mathsf{GLI}_{k}^{\ell},\quad
g_{i}\,=\,g,\quad\operatorname{dom}(b_{i})\,=\,\textup{db}_{Q},\quad\text{and}\quad\operatorname{dom}(r_{i})\,=\,\textup{dr}_{Q};$

such that for all $k$-labeled incidence graphs $L^{\prime}$ with
$|\mathcal{B}(I^{\prime})|=m$,
$\max\\{|\operatorname{\upbeta}(e)|\,:\,e\in\mathcal{B}(I^{\prime})\\}\leq d$
and $\operatorname{dom}(b^{\prime})\supseteq\textup{db}_{Q}$,
$\operatorname{dom}(r^{\prime})\supseteq\textup{dr}_{Q}$, $g^{\prime}\supseteq
g$, and with real guards w.r.t. $g$ we have:
$\mathcal{I}_{L^{\prime}}\models\Delta_{g}$, and

$\displaystyle\sum_{i\in[q]}\alpha_{i}\cdot\hom(L_{i},L^{\prime})=\begin{cases}1,&\text{if
}\;\mathcal{I}_{L^{\prime}}\models\chi\\\ 0,&\text{if
}\;\mathcal{I}_{L^{\prime}}\not\models\chi.\end{cases}$

The proof of Theorem 6.1 works the same way as the one for Theorem 6.1 in [26,
Section 8]: the second biimplication is provided by Theorem 2.8 and
Proposition 2.9. The first biimplication is shown via contraposition, where
the contraposition of the forward direction uses Lemma 6.2 and the one for the
backward direction uses Lemma 6.3.

######  Proof 6.4 (Proof of Theorem 6.1).

Let $I=I_{\mathcal{G}}$ and $J=I_{\mathcal{H}}$. If
$|\mathcal{B}(I)|\neq|\mathcal{B}(J)|$ then
$\hom(I^{\prime},I)\neq\hom(I^{\prime},J)$ for the incidence graph
$I^{\prime}\in\mathsf{ISHD}_{1}$ that consists of a single blue vertex and no
red vertices. Similarly, $I$ and $J$ are distinguished by a suitable
$\textsf{GC}_{1}$-sentence of the form
$\exists^{\scalebox{0.6}{$\geq$}n}\mathtt{e}\mathbin{.}(\mathtt{e}\kern
1.0pt{=}\kern 1.0pt\mathtt{e})$. If $|\mathcal{B}(I)|=|\mathcal{B}(J)|$,
consider their corresponding label-free $k$-labeled incidence graphs
$L_{I}=(I,\varnothing,\varnothing,\varnothing)$ and
$L_{J}=(J,\varnothing,\varnothing,\varnothing)$.

Assume there is an $I^{\prime}\in\mathsf{ISHD}_{k}$ such that
$\hom(I^{\prime},I)=m_{1}\neq m_{2}=\hom(I^{\prime},J)$. According to Theorem
4.1, there is a label-free $L\in\mathsf{GLI}^{k}$ such that $I^{\prime}\cong
I_{L}$, which means $\hom(L,L_{I})=m_{1}\neq m_{2}=\hom(L,L_{J})$. By Lemma
6.2 there exists a formula $(\top\land\varphi_{L,m_{1}})\in\textsf{RGC}^{k}$
with $\operatorname*{gd}(\varphi_{L,m_{1}})\leq k$ such that
$\mathcal{I}_{L_{I}}\models(\top\land\varphi_{L,m_{1}})$ and
$\mathcal{I}_{L_{J}}\not\models(\top\land\varphi_{L,m_{1}})$. Hence,
$\mathcal{I}_{L_{I}}\models\varphi_{L,m_{1}}$ and
$\mathcal{I}_{L_{J}}\not\models\varphi_{L,m_{1}}$, and since
$\varphi_{L,m_{1}}\in\textsf{GC}_{k}$,
$\mathcal{G}\not\equiv_{\textsf{GC}_{k}}\mathcal{H}$.

Assume there is a sentence $\varphi\in\mathsf{GLI}_{k}$ with
$\operatorname*{gd}(\varphi)=k$ such that $\mathcal{I}_{L_{I}}\models\varphi$
and $\mathcal{I}_{L_{J}}\not\models\varphi$. By Lemma 5.4 there exists a
formula $(\top\land\psi)\in\textsf{RGC}^{k}$ with $\operatorname*{gd}(\psi)=k$
such that $\mathcal{I}_{L_{I}}\models(\top\land\psi)$ and
$\mathcal{I}_{L_{J}}\not\models(\top\land\psi)$. Let
$m\coloneqq|\mathcal{B}(I)|=|\mathcal{B}(J)|$ be the number of hyperedges and
let $n\in{\rm Nature}$ such that $|\operatorname{\upbeta}(e)|\leq n$ for all
$e\in\mathcal{B}(I)$ and all $e\in\mathcal{B}(J)$. According to Lemma 6.3
there exists a linear combination $Q=\sum_{i\in[q]}\alpha_{i}L_{i}$ such that
$\sum_{i\in[q]}\alpha_{i}\cdot\hom(L_{i},L_{I})=1$ and
$\sum_{i\in[q]}\alpha_{i}\cdot\hom(L_{i},L_{J})=0$ and
$L_{i}\in\mathsf{GLI}_{k}^{k}$ for all $i\in[q]$. This means there must be an
$i\in[q]$ such that
$\alpha_{i}\cdot\hom(L_{i},L_{I})\neq\alpha_{i}\cdot\hom(L_{i},L_{J})$, which
means $\hom(L_{i},L_{I})\neq\hom(L_{i},L_{J})$. Since
$\textup{dr}_{Q}=\textup{db}_{Q}=\varnothing$, $L_{i}$ is label-free.
According to Theorem 4.1, there exists an $I^{\prime}\in\mathsf{ISHD}_{k}$
such that $I^{\prime}\cong I_{L_{i}}$. Thus,
$\hom(I^{\prime},I)\neq\hom(I^{\prime},J)$, i.e.,
$\operatorname{Hom}(\mathsf{ISHD}_{k},I)\neq\operatorname{Hom}(\mathsf{ISHD}_{k},J)$.

This finishes the proof for the first ?iff?. The second is provided by the
combination of Theorem 2.8 and Proposition 2.9.

##  7 Final Remarks

This paper solves one of the open questions of Scheidt and Schweikardt [26],
who lift a result by Dvořák [9] from graphs to hypergraphs. Dvořák shows that
homomorphism indistinguishability over the graphs of tree width at most $k$ is
equivalent to indistinguishability over first-order logic with counting
quantifiers (C) and $k{+}1$ variables ($\textsf{C}^{k{+}1}$). Scheidt and
Schweikardt show that homomorphism indistinguishability over the class
$\mathsf{GHW}_{k}$ of hypergraphs of generalised hypertree width at most $k$
is equivalent to indistinguishability over the logic GC with $k$ guards
($\textsf{GC}^{k}$). Grohe [11] gave a result complementing Dvořák’s: C with
quantifier depth at most $m$ ($\textsf{C}_{m}$) matches homomorphism
indistinguishability over graphs of tree depth at most $m$. An obvious
expectation was that the distinguishing power of $\textsf{GC}_{m}$ would match
homomorphism indistinguishability over the class $\mathsf{HD}_{m}$ of
hypergraphs of hypertree depth at most $m$ as it is defined by Adler et al.
[1]. However, this expectation did not manifest in this exact way. Instead, we
proved that the distinguishing power of $\textsf{GC}_{m}$ matches homomorphism
indistinguishability over hypergraphs of _strict_ hypertree depth at most $m$,
which is a (mild) restriction of hypertree depth. Combining Theorem 6.1 with
the main result of [26] yields the following combined result.

######  Theorem 7.1.

For all hypergraphs $\mathcal{G}$ and $\mathcal{H}$, the following
equivalences hold:

$\displaystyle\mathcal{G}\equiv_{\textsf{GC}_{k}}\mathcal{H}$
$\displaystyle\;\iff\;\mathcal{G}\equiv_{\mathsf{SHD}_{k}}\mathcal{H}$
$\displaystyle\;\iff\;I_{\mathcal{G}}\equiv_{\mathsf{ISHD}_{k}}I_{\mathcal{H}}\quad\text{and}$
$\displaystyle\mathcal{G}\equiv_{\textsf{GC}^{k}}\mathcal{H}$
$\displaystyle\;\iff\;\mathcal{G}\equiv_{\mathsf{GHW}_{k}}\mathcal{H}$
$\displaystyle\;\iff\;I_{\mathcal{G}}\equiv_{\mathsf{IGHW}_{k}}I_{\mathcal{H}}.$

We took this unexpected mismatch between $\textsf{GC}_{k}$ and
$\mathsf{HD}_{k}$ as an opportunity to investigate the relationship between
$\mathsf{HD}_{k}$ and $\mathsf{SHD}_{k}$. In Theorem 2.5 we showed that the
strict hypertree depth of a hypergraph is at most 1 larger than its hypertree
depth. See 2.5

To show that homomorphism counts from the class $\mathsf{SHD}_{k}$ are just as
expressive as homomorphism counts from the class $\mathsf{ISHD}_{k}$, which
was necessary to prove Theorem 6.1, we used an implicit result by Böker [4],
who gives a sufficient set of properties for a class $\mathfrak{C}$ of
hypergraphs, such that homomorphism indistinguishability over $\mathfrak{C}$
is the same as homomorphism indistinguishability over the corresponding class
$\mathfrak{C}_{\mathsf{I}}$ of incidence graphs. Since $\mathsf{HD}_{k}$ does
not have these properties, Böker’s result cannot be applied with respect to
$\mathsf{HD}_{k}$ and $\mathsf{IHD}_{k}$. In fact, we showed in Theorem 2.10
that homomorphism indistinguishability over $\mathsf{HD}_{k}$ is _not_ the
same as homomorphism indistinguishability over $\mathsf{IHD}_{k}$ and
furthermore, that it is also not the same as homomorphism indistinguishability
over $\mathsf{SHD}_{k}$. See 2.10

#### Further Research

It would be very interesting to see if the result by Böker (Theorem 2.8) is
tight in the sense that closure under pumping and local merging are sufficient
_and required_ properties. I.e., whether for every class $\mathfrak{C}$ that
misses one of these properties, homomorphism counts over $\mathfrak{C}$ differ
from homomorphism counts over the corresponding class
$\mathfrak{C}_{\mathsf{I}}$ of incidence graphs in their distinguishing power.

As mentioned in the introduction, this work can be seen as one more step in
the search of a ?proper? lifting of the $k$-dimensional Weisfeiler-Leman
algorithm to hypergraphs. Given the relationship between Weisfeiler-Leman, C
and homomorphism indistinguishability on graphs [5, 7, 8, 9, 10, 11], we
believe that the proper lifting should admit a similar relationship to the
corresponding hypergraph parameters. Hence, we believe that the distinguishing
power of such an algorithm should match homomorphism indistinguishability over
the class $\mathsf{GHW}_{k}$ of hypergraphs of generalised hypertree width at
most $k$ and thus also indistinguishability by the logic $\textsf{GC}^{k}$.
Since we believe that $\textsf{GC}^{k}$ is the natural lifting of
$\textsf{C}^{k}$ in this setting, this paper adds to this picture: The
$k$-dimensional Weisfeiler-Leman algorithm restricted to $m$ iterations should
have the same distinguishing power as the intersection of the classes
$\mathsf{GHW}_{k}\cap\mathsf{SHD}_{m}$. Hence, the mismatch we uncovered in
this work might propagate to the Weisfeiler-Leman algorithm.

## References

  * [1] Isolde Adler, Tomáš Gavenčiak, and Tereza Klimošová.  Hypertree-depth and minors in hypergraphs.  Theoretical Computer Science, 463:84–95, 2012.  doi:10.1016/j.tcs.2012.09.007.
  * [2] Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan.  The Complexity of Homomorphism Indistinguishability.  In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.MFCS.2019.54.
  * [3] Silvia Butti and Víctor Dalmau.  Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem.  In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.MFCS.2021.27.
  * [4] Jan Böker.  Color Refinement, Homomorphisms, and Hypergraphs.  In Ignas Sau and Dimitrios M. Thilikos, editors, Graph-Theoretic Concepts in Computer Science, volume 11789 of Lecture Notes in Computer Science, pages 338–350. Springer, Cham, 2019.
  * [5] Jin-Yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Combinatorica, 12(4):389–410, December 1992.  doi:10.1007/BF01305232.
  * [6] Bruno Courcelle.  Graph Grammars, Monadic Second-Order Logic And The Theory Of Graph Minors.  In Neil Robertson and Paul Seymour, editors, Graph Structure Theory, number 147 in Contemporary Mathematics. American Mathematical Society, 1993.
  * [7] Anuj Dawar, Tomáš Jakl, and Luca Reggio.  Lovász-Type Theorems and Game Comonads.  In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–13, June 2021.  doi:10.1109/LICS52264.2021.9470609.
  * [8] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász meets Weisfeiler and Leman.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1–40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.ICALP.2018.40.
  * [9] Zdeněk Dvořák.  On recognizing graphs by numbers of homomorphisms.  Journal of Graph Theory, 64(4):330–342, 2010.  doi:10.1002/jgt.20461.
  * [10] Eva Fluck, Tim Seppelt, and Gian Luca Spitzer.  Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth.  In Aniello Murano and Alexandra Silva, editors, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.CSL.2024.27.
  * [11] Martin Grohe.  Counting Bounded Tree Depth Homomorphisms.  In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’20, pages 507–520, New York, NY, USA, July 2020. Association for Computing Machinery.  doi:10.1145/3373718.3394739.
  * [12] Martin Grohe.  Word2vec, Node2vec, Graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, pages 1–16. ACM, 2020.  doi:10.1145/3375395.3387641.
  * [13] Martin Grohe.  The Logic of Graph Neural Networks.  In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–17, June 2021.  doi:10.1109/LICS52264.2021.9470677.
  * [14] Martin Grohe, Kristian Kersting, Martin Mladenov, and Erkal Selman.  Dimension Reduction via Colour Refinement.  In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, Lecture Notes in Computer Science, pages 505–516, Berlin, Heidelberg, 2014. Springer.  doi:10.1007/978-3-662-44777-2_42.
  * [15] Martin Grohe, Gaurav Rattan, and Tim Seppelt.  Homomorphism Tensors and Linear Equations.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1–70:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICALP.2022.70.
  * [16] Neil Immerman and Eric Lander.  Describing Graphs: A First-Order Approach to Graph Canonization.  In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59–81. Springer, New York, NY, 1990.  doi:10.1007/978-1-4612-4478-3_5.
  * [17] Sandra Kiefer.  The Weisfeiler-Leman Algorithm: An Exploration of Its Power.  ACM SIGLOG News, 7(3):5–27, November 2020.  doi:10.1145/3436980.3436982.
  * [18] László Lovász.  Operations with structures.  Acta Mathematica Academiae Scientiarum Hungaricae, 18(3):321–328, 1967.
  * [19] László Lovász and Balázs Szegedy.  Contractors and connectors of graph algebras.  Journal of Graph Theory, 60(1):11–30, 2009.  doi:10.1002/jgt.20343.
  * [20] Laura Mančinska and David E. Roberson.  Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661–672, November 2020.  doi:10.1109/FOCS46700.2020.00067.
  * [21] Yoàv Montacute and Nihil Shah.  The Pebble-Relation Comonad in Finite Model Theory.  In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’22, pages 1–11, New York, NY, USA, August 2022. Association for Computing Machinery.  doi:10.1145/3531130.3533335.
  * [22] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.  Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):4602–4609, July 2019.  doi:10.1609/aaai.v33i01.33014602.
  * [23] Daniel Neuen.  Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width, July 2023.  arXiv:2304.07011, doi:10.48550/arXiv.2304.07011.
  * [24] Gaurav Rattan and Tim Seppelt.  Weisfeiler-Leman and Graph Spectra.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 2268–2285. Society for Industrial and Applied Mathematics, January 2023.  doi:10.1137/1.9781611977554.ch87.
  * [25] David E. Roberson.  Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, June 2022.  arXiv:2206.10321, doi:10.48550/arXiv.2206.10321.
  * [26] Benjamin Scheidt and Nicole Schweikardt.  Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation.  In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 79:1–79:15, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  Full version available at arXiv: arXiv:2303.10980 [cs.LO].  doi:10.4230/LIPIcs.MFCS.2023.79.
  * [27] Tim Seppelt.  Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors.  In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:15, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.MFCS.2023.82.
  * [28] Nino Shervashidze.  Weisfeiler-Lehman Graph Kernels.  Journal of Machine Learning Research, 12(77):2539–2561, 2011.  URL: http://jmlr.org/papers/v12/shervashidze11a.html.
  * [29] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How Powerful are Graph Neural Networks?  In International Conference on Learning Representations, September 2018.  URL: https://openreview.net/forum?id=ryGs6iA5Km.

##  Appendix A Proof of Proposition 2.9

#### Closure under Pumping

It is easy to see that a _bijective_ elimination forest stays a bijective
elimination forest, when we add a fresh vertex to the neighbourhood of a
single blue vertex, since there already exists a node in the forest that maps
to this blue vertex. Obviously Items 1 and 2 remain satisfied when the vertex
is added. And since it is only contained in this single edge, Item 3 remains
satisfied as well.

On the other hand, if the elimination forest $(F,\Gamma)$ is not bijective,
problems arise when a fresh vertex is added to a hyperedge
$e\not\in\operatorname{img}(\Gamma)$, i.e., one that $\Gamma$ does not map to.
In this case, Item 1 and Item 2 are no longer satisfied. To fix this, we have
to map to $e$ and this may mean inserting a new node into $F$, which might
increase its height. A simple example where this happens is when we add a
vertex to one of the singleton hyperedges of $\mathcal{G}_{k}$ from Theorem
2.10.

#### Closure under Local Merging

Let $I$ be an incidence graph and let $(F,\Gamma)$ be an elimination forest
for $I$. Let $u,v\in\mathcal{R}(I)$ be distinct vertices and let
$e\in\mathcal{B}(I)$ such that $u,v\in\operatorname{\upbeta}(e)$. Let
$\pi\colon\mathcal{R}(I)\to\mathcal{R}(I)$ be defined by $\pi(u)=v$ and
$\pi(w)=w$ for all $w\in\mathcal{R}(I)\setminus\\{u\\}$. Let $I^{\prime}$ be
the projection of $I$ that is defined as follows:

$\mathcal{R}(I^{\prime})=\pi(\mathcal{R}(I)),\;\mathcal{B}(I^{\prime})=\mathcal{B}(I),\quad\text{and}\quad
E(I^{\prime})=\\{(e,\pi(v))\,:\,(e,v)\in E(I)\\}.$

Now we simply have to verify that $(F,\Gamma)$ is still an elimination forest
for $I^{\prime}$. In particular, if $(F,\Gamma)$ is a strict elimination
forest, it will remain strict, since $\Gamma$ is still bijective. To avoid
confusion, we write $\operatorname{\upbeta}^{\prime}(e)$ to denote the set
$\\{v\in\mathcal{R}(I^{\prime})\,:\,(e,v)\in E(I^{\prime})\\}$ and
$\widehat{\Gamma}^{\prime}(t)$ to denote the set
$\operatorname{\upbeta}^{\prime}(\Gamma(t))$. We have to show that Items 1, 2
and 3 still hold with respect to $\operatorname{\upbeta}^{\prime}$ and
$\widehat{\Gamma}^{\prime}$.

_Verifying Item 1._ Since $\mathcal{R}(I^{\prime})\subseteq\mathcal{R}(I)$ we
know that for every $w\in\mathcal{R}(I^{\prime})$ there is a $t\in V(F)$ such
that $w\in\operatorname{\upbeta}(\Gamma(t))$. Since by construction $\pi(w)=w$
for all $w\in\mathcal{R}(I^{\prime})$, we get that $(e,w)\in E(I)$ implies
$(e,w)\in E(I^{\prime})$. Therefore,
$w\in\operatorname{\upbeta}^{\prime}(\Gamma(t))$, i.e.,
$w\in\widehat{\Gamma}^{\prime}(t)$.

_Verifying Item 2._ Notice that $\mathcal{B}(I^{\prime})=\mathcal{B}(I)$. Let
$e\in\mathcal{B}(I^{\prime})$, let $s,t\in V(F)$ be the nodes in $V(F)$ for
$e$ according to Item 2 with respect to $I$. Let
$w^{\prime}\in\operatorname{\upbeta}^{\prime}(e)$. Then there exists a
$w\in\mathcal{R}(I)$ such that $(e,\pi(w))\in E(I)$ and $\pi(w)=w^{\prime}$.
Since
$\operatorname{\upbeta}(e)\subseteq\bigcup\widehat{\Gamma}(\operatorname*{P}(s,t))$,
there exists a $p\in\operatorname*{P}(s,t)$ such that
$w\in\widehat{\Gamma}(p)$, i.e., $(\Gamma(p),w)\in E(I)$. This implies by
construction, that $(\Gamma(p),\pi(w))\in E(I^{\prime})$, i.e.,
$(\Gamma(p),w^{\prime})\in E(I^{\prime})$. Thus,
$w^{\prime}\in\widehat{\Gamma}^{\prime}(p)$, i.e.,
$w^{\prime}\in\widehat{\Gamma}^{\prime}(\operatorname*{P}(s,t))$. Since we
chose an arbitrary $w^{\prime}\in\operatorname{\upbeta}^{\prime}(e)$, this
yields
$\operatorname{\upbeta}^{\prime}(e)\subseteq\bigcup\widehat{\Gamma}^{\prime}(\operatorname*{P}(s,t))$.

_Verifying Item 3._ Again, notice that
$\mathcal{B}(I^{\prime})=\mathcal{B}(I)$. Let $s,t\in V(F)$ and let
$w^{\prime}\in\widehat{\Gamma}^{\prime}(s)\cap\widehat{\Gamma}^{\prime}(t)$.

_Case 1_ : Assume there exists a $w\in\mathcal{R}(I)$ such that
$\pi(w)=w^{\prime}$, and $(\Gamma(s),w),(\Gamma(t),w)\in E(I)$. Thus,
$w\in\widehat{\Gamma}(s)\cap\widehat{\Gamma}(t)$. Since $(F,\Gamma)$ is an
elimination forest for $I$, according to Item 3 the node
$\operatorname*{\land}(s,t)$ exists and
$w\in\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.
I.e., there is a $p\in\operatorname*{P}(\operatorname*{\land}(s,t))$ such that
$w\in\widehat{\Gamma}(p)$, i.e., $(\Gamma(p),w)\in E(I)$. Hence, by
construction, $(\Gamma(p),w^{\prime})\in E(I^{\prime})$, i.e.,
$w^{\prime}\in\widehat{\Gamma}^{\prime}(p)$, which means
$w^{\prime}\in\bigcup\widehat{\Gamma}^{\prime}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

_Case 2_ : Otherwise, $\pi(u)=w$ and $\pi(v)=w$, and $w=v$ must hold. W.l.o.g.
let $(\Gamma(s),u)\in E(I)$ and $(\Gamma(t),v)\in E(I)$. Since $u$ and $v$
appear in a common hyperedge $e\in\mathcal{B}(I)$, there are
$s^{\prime},t^{\prime}\in V(F)$ such that
$u,v\in\bigcup\widehat{\Gamma}(\operatorname*{P}(s^{\prime},t^{\prime}))$.
I.e., there are $p_{u},p_{v}\in\operatorname*{P}(s^{\prime},t^{\prime})$ such
that $u\in\widehat{\Gamma}(p_{u})$ and $v\in\widehat{\Gamma}(p_{v})$. Thus,
$u\in\widehat{\Gamma}(p_{u})\cap\widehat{\Gamma}(s)$ and
$v\in\widehat{\Gamma}(t)\cap\widehat{\Gamma}(p_{v})$. This means that
$u\in\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,p_{u})))$
and
$v\in\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(t,p_{v})))$.
Since $p_{u},p_{v}\in\operatorname*{P}(s^{\prime},t^{\prime})$, either
$p_{u}\leq_{F}p_{v}$ or $p_{v}\leq_{F}p_{u}$, and because of that also
$\operatorname*{\land}(s,p_{u})\leq_{F}\operatorname*{\land}(t,p_{v})$ or
$\operatorname*{\land}(t,p_{v})\leq_{F}\operatorname*{\land}(s,p_{u})$. Since
$F$ is a forest, this means that $\operatorname*{\land}(s,t)$ exists and
$\operatorname*{\land}(s,t)\geq_{F}\operatorname*{\land}(\operatorname*{\land}(s,p_{u}))$
or $\operatorname*{\land}(s,t)\geq_{F}\operatorname*{\land}(t,p_{v})$.
Therefore,
$u\in\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$
or
$v\in\bigcup\widehat{\Gamma}(\operatorname*{P}(\operatorname*{\land}(s,t)))$,
i.e.,
$w^{\prime}\in\bigcup\widehat{\Gamma}^{\prime}(\operatorname*{P}(\operatorname*{\land}(s,t)))$.

##  Appendix B Proof of Theorem 2.10

Let $\mathcal{H}$, $\mathcal{G}$ be graphs and let $(h_{V},h_{E})$ be a
homomorphism from $\mathcal{H}$ into $\mathcal{G}$. If $\mathcal{H}$ is
connected, then the homomorphic image of $\mathcal{H}$ in $\mathcal{G}$ is
also connected.

For every hypergraph $\mathcal{H}$ and $e\in E(\mathcal{H})$, let
$\mathcal{H}\setminus e$ be the hypergraph $\mathcal{H}^{\prime}$ with
$V(\mathcal{H}^{\prime})=V(\mathcal{H})\setminus\beta_{\mathcal{H}}(e)$,
$E(\mathcal{H}^{\prime})=E(\mathcal{H})\setminus\\{e\\}$ and let
$\beta_{\mathcal{H}^{\prime}}$ be the corresponding restriction of
$\beta_{\mathcal{H}}$.

######  Lemma B.1.

A connected hypergraph $\mathcal{H}\in\mathsf{SHD}_{k}$ cannot have a
homomorphism $(h_{V},h_{E})$ into $\mathcal{P}_{n}$ for any $n\geq 2^{k}$,
such that $h_{V}$ and $h_{E}$ are surjective.

######  Proof B.2.

Clearly this holds for $k=1$ since all connected
$\mathcal{H}\in\mathsf{SHD}_{1}$ consist of a single hyperedge, which cannot
be mapped to two hyperedges.

Assume there is a $k\geq 2$ for which the statement of the lemma does not
hold. Consider the smallest $k$, for which there is a connected hypergraph
$\mathcal{H}\in\mathsf{SHD}_{k}$ and a homomorphism $(h_{V},h_{E})$ from
$\mathcal{H}$ into $\mathcal{P}_{n}$ for $n\geq 2^{k}$. Let $(T,\Gamma)$ be a
strict elimination tree for $\mathcal{H}$ and let $\omega$ be the root of $T$.
Let $\mathcal{H}^{\prime}\coloneqq\mathcal{H}\setminus\Gamma(\omega)$. Then
the restriction $(h_{V}^{\prime},h_{E}^{\prime})$ of $(h_{V},h_{E})$ to
$V(\mathcal{H}^{\prime})$ and $E(\mathcal{H}^{\prime})$ is still a
homomorphism from $\mathcal{H}^{\prime}$ into $\mathcal{P}_{n}$, but
$h_{V}^{\prime}$ or $h_{E}^{\prime}$ (or both) may no longer be surjective and
$\operatorname{shd}(\mathcal{H}^{\prime})=k-1$.

If $\mathcal{H}^{\prime}$ is not connected, consider the connected components
$C_{1},\dots,C_{\ell}$ of $\mathcal{H}^{\prime}$. The restriction
$(h_{V}^{i},h_{E}^{i})$ of $(h_{V}^{\prime},h_{E}^{\prime})$ to $C_{i}$ is a
homomorphism from $C_{i}$ to $\mathcal{P}_{n}$ and according to Appendix B it
is connected, but since $k$ is minimal, it covers a path of at most
$2^{k{-}1}-1$ hyperedges. And since $\mathcal{H}$ was connected, these paths
must all touch $h_{E}(\Gamma(\omega))$. Thus, the number of hyperedges
$\mathcal{H}$ covered could have been at most $1+2\cdot(2^{k{-}1}-1)=2^{k}-1$,
which contradicts our assumption. Therefore, $\mathcal{H}^{\prime}$ must still
be connected.

If $h_{V}^{\prime}$ and $h_{E}^{\prime}$ are surjective, $k$ was not minimal,
i.e., $h_{V}^{\prime}$ or $h_{E}^{\prime}$ must no longer be surjective. Since
$\mathcal{H}^{\prime}$ is still connected, the homomorphic image must be as
well. Thus, $h_{E}(\Gamma(\omega))$ must be the first or the last edge. I.e.,
$\mathcal{H}^{\prime}$ has a surjective homomorphism to $\mathcal{P}_{n-1}$.
Since $\operatorname{shd}(\mathcal{H}^{\prime})=k-1$ and $n\geq 2^{k}$ and $k$
was minimal, this means that $n-1<2^{k-1}$. This is the case, iff $n=1$ and
$k=0$, which contradicts $k\geq 2$.

Notice that this lemma only holds for $\mathsf{SHD}_{k}$. If we do not require
$(T,\Gamma)$ to be strict, the proof fails since we can not be sure that the
hypertree depth of $\mathcal{H}^{\prime}$ is smaller than that of
$\mathcal{H}$. But since $\mathsf{HD}_{k}\subseteq\mathsf{SHD}_{k{+}1}$, we
get the following corollary.

######  Corollary B.3.

A connected hypergraph $\mathcal{H}\in\mathsf{HD}_{k}$ cannot have a
homomorphism $(h_{V},h_{E})$ into $\mathcal{P}_{n}$ for any $n\geq 2^{k{+}1}$,
such that $h_{V}$ and $h_{E}$ are surjective.

For the proof of Theorem 2.10, we need to tighten this result a bit further.

######  Lemma B.4.

A connected hypergraph $\mathcal{H}\in\mathsf{HD}_{k}$ cannot have a
homomorphism $(h_{V},h_{E})$ into $\mathcal{P}_{n}$ for any $n\geq
2^{k{+}1}-2$, such that $h_{V}$ and $h_{E}$ are surjective.

######  Proof B.5.

Assume for contradiction, that $\mathcal{H}\in\mathsf{HD}_{k}$ has a
homomorphism $(h_{V},h_{E})$ into $\mathcal{P}_{n}$ for $n\geq 2^{k{+}1}-2$,
such that $h_{V}$ and $h_{E}$ are surjective. Let
$E(\mathcal{P}_{n})=\\{e_{1},\dots,e_{n}\\}$ and
$V(\mathcal{P}_{n})=\\{v_{1},\dots,v_{n{+}1}\\}$.

Let $(T,\Gamma)$ be an elimination forest for $\mathcal{H}$ of height $k$.
There are $e,e^{\prime}\in E(\mathcal{H})$ and
$v\in\beta(e),v^{\prime}\in\beta(e^{\prime})$ such that $h_{E}(e)=e_{1}$,
$h_{E}(e^{\prime})=e_{n}$, and $h_{V}(v)=v_{1}$,
$h_{V}(v^{\prime})=v_{n{+}1}$. Consider the hypergraph $\mathcal{H}^{\prime}$
with $V(\mathcal{H}^{\prime})=V(\mathcal{H})\mathrel{\dot{\cup}}\\{u,w\\}$,
$E(\mathcal{H}^{\prime})=E(\mathcal{H})\mathrel{\dot{\cup}}\\{f,g\\}$ and
$\beta_{\mathcal{H}^{\prime}}=\beta_{\mathcal{H}}\cup\\{f\to\\{v,u\\},g\to\\{v^{\prime},w\\}\\}$.
It is easy to see that $(T,\Gamma)$ can be turned into a strict elimination
tree for $\mathcal{H}^{\prime}$ of height $k{+}1$: First we apply the method
presented in the proof of Theorem 2.5. Then we insert two new nodes that map
to $f$ and $g$. It is not hard to see that we can add these new nodes as
children of _inner nodes_ , which means the height does not increase any
further.

It is also not hard to see that $(h_{V}^{\prime},h_{E}^{\prime})$ is a
homomorphism from $\mathcal{H}^{\prime}$ to $\mathcal{P}_{n{+}2}$, where
$(h_{V}^{\prime},h_{E}^{\prime})$ are defined in the following way:

  * •

Let $h_{V}^{\prime}(u)=v_{1}$, $h_{V}^{\prime}(w)=v_{n{+}3}$ and for all $v\in
V(\mathcal{H})$, let $h_{V}^{\prime}(v)=v_{i{+}1}$, where $i\in[n{+}1]$ such
that $h_{V}(v)=v_{i}$.

  * •

Let $h_{E}^{\prime}(f)=e_{1}$, $h_{E}^{\prime}(g)=e_{n{+}2}$ and for all $e\in
E(\mathcal{H})$, let $h_{E}^{\prime}(e)=e_{i{+}1}$, where $i\in[n]$ such that
$h_{E}(e)=e_{i}$.

This contradicts Lemma B.1.

Inserting a hyperedge into $\mathcal{H}$, whose contents are a subset of an
already existing hyperedge does not increase the hypertree depth.

[due to [1]] For all $n\in{\rm Nature}_{\geq{}1}$,
$\operatorname{hd}(\mathcal{P}_{n})=\lfloor\log(n+2)\rfloor$.

See 2.10

######  Proof B.6.

1. For all $k\geq 2$ let $\mathcal{G}_{k}$ and $\mathcal{H}_{k}$ be the hypergraphs with

$\displaystyle V(\mathcal{G}_{k})$
$\displaystyle=V(\mathcal{H}_{k})=V(\mathcal{P}_{2^{k{+}1}+1})=\\{u_{1},u_{2},\dots\\}\,,$
$\displaystyle E(\mathcal{G}_{k})$
$\displaystyle=E(\mathcal{H}_{k})=E(\mathcal{P}_{2^{k{+}1}+1})\mathrel{\dot{\cup}}\\{e,f,g\\}\,,\quad\text{and}$
$\displaystyle\beta_{\mathcal{G}_{k}}$
$\displaystyle=\\{e\to\\{u_{2^{k{+}1}+2},u_{1}\\},f\to\\{u_{1}\\},g\to\\{u_{2^{k}+1}\\}\\}\cup\beta_{\mathcal{P}_{2^{k{+}1}+1}}\,,$
$\displaystyle\beta_{\mathcal{H}_{k}}$
$\displaystyle=\\{e\to\\{u_{2^{k{+}1}+2},u_{1}\\},f\to\\{u_{1}\\},g\to\\{u_{2^{k}+2}\\}\\}\cup\beta_{\mathcal{P}_{2^{k{+}1}+1}}\,.$

I.e., $\mathcal{G}_{k}$ and $\mathcal{H}_{k}$ both are circles of
$2^{k{+}1}+2$ edges, with two additional singleton hyperedges. The difference
is in the distance between those: There are $2^{k}$ hyperedges between them in
$\mathcal{G}_{k}$, but $2^{k}+1$ in $\mathcal{H}_{k}$.

$\mathcal{G}_{k}$ and $\mathcal{H}_{k}$ are distinguished by
$\mathcal{P}^{\prime}$ with
$V(\mathcal{P}^{\prime})=V(\mathcal{P}_{2^{k}})=\\{v_{1},v_{2},\dots\\}$,
$E(\mathcal{P}^{\prime})=E(\mathcal{P}^{\prime})\mathrel{\dot{\cup}}\\{f^{\prime},g^{\prime}\\}$
and $\beta_{\mathcal{P}^{\prime}}=\\{f^{\prime}\to v_{1},g^{\prime}\to
v_{2^{k}+1}\\}\cup\beta_{\mathcal{P}_{2^{k}}}$. Using B.5 and B we know that
$\operatorname{hd}(\mathcal{P}^{\prime})=\lfloor\log(2^{k}+2)\rfloor$ and
since $k\geq 2$, $\operatorname{hd}(\mathcal{P}^{\prime})=k$. Thus,
$\mathcal{G}_{k}$ and $\mathcal{H}_{k}$ are homomorphism distinguishable over
$\mathsf{HD}_{k}$.

To show that they are indistinguishable over $\mathsf{SHD}_{k}$ we use Lemma
B.1. Let $\mathcal{H}\in\mathsf{SHD}_{k}$. We may assume that $\mathcal{H}$ is
connected. According to Appendices B and B.1 we know that for every
homomorphism $(h_{V},h_{E})$ from $\mathcal{H}$ to $\mathcal{G}_{k}$, either
$f\not\in\operatorname{img}(h_{E})$ or $g\not\in\operatorname{img}(h_{E})$.
The same holds for the homomorphisms from $\mathcal{H}$ to $\mathcal{H}_{k}$.
It is easy to see that this means we can give a bijective mapping between the
homomorphisms into $\mathcal{G}_{k}$ and those into $\mathcal{H}_{k}$. I.e.,
$\hom(\mathcal{H},\mathcal{G}_{k})=\hom(\mathcal{H},\mathcal{H}_{k})$.

2. We use a similar construction and Lemma B.4. For all $k\geq 2$ let $\mathcal{G}_{k}^{\prime}$ and $\mathcal{H}_{k}^{\prime}$ be the hypergraphs with

$\displaystyle V(\mathcal{G}_{k}^{\prime})$
$\displaystyle=V(\mathcal{H}_{k}^{\prime})=V(\mathcal{P}_{2^{k{+}2}+1})\mathrel{\dot{\cup}}\\{v,w\\}=\\{u_{1},u_{2},\dots\\}\mathrel{\dot{\cup}}\\{v,w\\}\,,$
$\displaystyle E(\mathcal{G}_{k}^{\prime})$
$\displaystyle=E(\mathcal{H}_{k}^{\prime})=E(\mathcal{P}_{2^{k{+}2}+1})\mathrel{\dot{\cup}}\\{e,f,g\\}\,,\quad\text{and}$
$\displaystyle\beta_{\mathcal{G}_{k}}$
$\displaystyle=\\{e\to\\{u_{2^{k{+}2}+2},u_{1}\\},f\to\\{u_{1},v\\},g\to\\{u_{2^{k+1}-2},w\\}\\}\cup\beta_{\mathcal{P}_{2^{k{+}1}+1}}\,,$
$\displaystyle\beta_{\mathcal{H}_{k}}$
$\displaystyle=\\{e\to\\{u_{2^{k{+}2}+2},u_{1}\\},f\to\\{u_{1},v\\},g\to\\{u_{2^{k+1}-1},w\\}\\}\cup\beta_{\mathcal{P}_{2^{k{+}1}+1}}\,.$

I.e., $\mathcal{G}_{k}$ and $\mathcal{H}_{k}$ both are circles of
$2^{k{+}2}+2$ edges, with two additional hyperedges ?sticking out as handles?.
Again, the only difference is in the distance between those handles: There are
$2^{k{+}1}-3$ hyperedges between them in $\mathcal{G}_{k}$ and $2^{k+1}-2$ in
$\mathcal{H}_{k}$.

With the same argument as before one can see that
$\operatorname{Hom}(\mathsf{HD}_{k},\mathcal{G}_{k})=\operatorname{Hom}(\mathsf{HD}_{k},\mathcal{G}_{k})$,
because this time the handles are not included in the outer edges of the path,
rather they _are_ the outer edges of the path. Thus, the path a homomorphism
would have to map to, to distinguish $\mathcal{G}_{k}$ and $\mathcal{H}_{k}$
contains $2^{k{+}1}-3+2=2^{k{+}1}-1$ edges.

Consider $\mathcal{P}^{\prime}$ with
$V(\mathcal{P}^{\prime})=V(\mathcal{P}_{2^{k+1}-3})=\\{v_{1},v_{2},\dots\\}$,
$E(\mathcal{P}^{\prime})=E(\mathcal{P}_{2^{k+1}-3})\mathrel{\dot{\cup}}\\{f^{\prime},g^{\prime}\\}$
and $\beta_{\mathcal{P}^{\prime}}=\\{f^{\prime}\to v_{1},g^{\prime}\to
v_{2^{k}-1}\\}\cup\beta_{\mathcal{P}_{2^{k{+}1}-3}}$. Obviously,
$\operatorname{hd}(\mathcal{P}^{\prime})=\lfloor\log(2^{k+1}-3+2)\rfloor=k$
and $\mathcal{P}^{\prime}$ is ?too short? to distinguish $\mathcal{G}_{k}$ and
$\mathcal{H}_{k}$. But we can map the singleton hyperedges $f^{\prime}$ and
$g^{\prime}$ of $\mathcal{P}^{\prime}$ onto the handles if we consider
homomorphisms from $I_{\mathcal{P}^{\prime}}$. Thus,
$\hom(I_{\mathcal{P}^{\prime}},\mathcal{G}_{k})\neq\hom(I_{\mathcal{P}^{\prime}},\mathcal{H}_{k})$.

##  Appendix C Missing Definitions in Section 3

The following is taken almost verbatim from the full version of [26] to assure
that we are using the same definitions as them, so that we can also use their
proofs.

######  Definition C.1.

Let $L=(I,r,b,g)$ be a $k$-labeled incidence graph. Let $X_{r}\subseteq{\rm
Nature}_{\geq{}1}$ be finite, and let $X_{b}\subseteq[k]$.

  * •

Removing from the red vertices all the labels in $X_{r}$ is achieved by the
operation $L[X_{r}{\to}\bullet]\coloneqq(I,r^{\prime},b,g^{\prime})$ where
$r^{\prime}$ is the restriction of $r$ to $\operatorname{dom}(r)\setminus
X_{r}$ and $g^{\prime}$ is the restriction of $g$ to
$\operatorname{dom}(g)\setminus X_{r}$.

  * •

Removing from the blue vertices all the labels in $X_{b}$ is achieved by the
operation $L\langle X_{b}{\to}\bullet\rangle\coloneqq(I,r,b^{\prime},g)$ where
$b^{\prime}$ is the restriction of $b$ to $\operatorname{dom}(b)\setminus
X_{b}$.

  * •

Let $\langle i_{1},\dots,i_{\ell}\rangle$ be the enumeration of $X_{r}$. For
every $\overline{v}=(v_{1},\ldots,v_{\ell})\in{\mathcal{R}(I)}^{\ell}$ we let
$L[X_{r}{\to}\overline{v}]\coloneqq(I,r^{\prime},b,g)$ with
$\operatorname{dom}(r^{\prime})=\operatorname{dom}(r)\cup X_{r}$ and
$r^{\prime}(i_{j})=v_{j}$ for all $j\in[\ell]$ and $r^{\prime}(i)=r(i)$ for
all $i\in\operatorname{dom}(r)\setminus X_{r}$.

  * •

Let $\langle i_{1},\dots,i_{\ell}\rangle$ be the enumeration of $X_{b}$. For
every $\overline{e}=(e_{1},\ldots,e_{\ell})\in{\mathcal{B}(I)}^{\ell}$ we let
$L\langle X_{b}{\to}\overline{e}\rangle\coloneqq(I,r,b^{\prime},g)$ with
$\operatorname{dom}(b^{\prime})=\operatorname{dom}(b)\cup X_{b}$ and
$b^{\prime}(i_{j})=e_{j}$ for all $j\in[\ell]$ and $b^{\prime}(i)=b(i)$ for
all $i\in\operatorname{dom}(b)\setminus X_{b}$.

######  Definition C.2 (Glueing $k$-labeled incidence graphs).

Let $L_{i}\coloneqq(I_{i},r_{i},b_{i},g_{i})$ be a $k$-labeled incidence graph
for $i\in[2]$. The _glueing operation_ produces the $k$-labeled incidence
graph $(L_{1}\cdot L_{2})\coloneqq(I,r,b,g)$ in the following way.

Let $I^{\prime}\coloneqq I_{1}\mathrel{\dot{\cup}}I_{2}$ be the disjoint union
of $I_{1}$ and $I_{2}$. Precisely, we let

$\displaystyle\mathcal{R}(I^{\prime})$
$\displaystyle\;\;\coloneqq\;\;\textstyle\bigcup_{i\in[2]}(\mathcal{R}(I_{i})\times\\{i\\}),\quad\mathcal{B}(I^{\prime})\;\;\coloneqq\;\;\textstyle\bigcup_{i\in[2]}(\mathcal{B}(I_{i})\times\\{i\\})\quad\text{and}$
$\displaystyle E(I^{\prime})$
$\displaystyle\;\;\coloneqq\;\;\textstyle\bigcup_{i\in[2]}\\{\bigl{(}(e,i),(v,i)\bigr{)}\,:\,(e,v)\in
E(I_{i})\\}.$

Let $\sim_{R}$ be the equivalence relation on $\mathcal{R}(I^{\prime})$
obtained as the reflexive, symmetric, and transitive closure of the relation
$\\{\bigl{(}(r_{1}(j),1),(r_{2}(j),2)\bigr{)}\,:\,j\in\operatorname{dom}(r_{1})\cap\operatorname{dom}(r_{2})\\}$.
Let ${[v]}_{\sim_{R}}$ denote the equivalence class of each
$v\in\mathcal{R}(I^{\prime})$.

Let $\sim_{B}$ be the equivalence relation on $\mathcal{B}(I^{\prime})$
obtained as the reflexive, symmetric, and transitive closure of the relation
$\\{\bigl{(}(b_{1}(j),1),(b_{2}(j),2)\bigr{)}\,:\,j\in\operatorname{dom}(b_{1})\cap\operatorname{dom}(b_{2})\\}$.
Let ${[e]}_{\sim_{B}}$ denote the equivalence class of each
$e\in\mathcal{B}(I^{\prime})$.

$I$ is the incidence graph $(\mathcal{R}(I),\mathcal{B}(I),E(I))$ for

$\displaystyle\mathcal{R}(I)$
$\displaystyle\coloneqq\\{{[v]}_{\sim_{R}}\,:\,v\in\mathcal{R}(I^{\prime})\\},\quad\mathcal{B}(I)\coloneqq\\{{[e]}_{\sim_{B}}\,:\,e\in\mathcal{B}(I^{\prime})\\}\quad\text{and}$
$\displaystyle E(I)$
$\displaystyle\coloneqq\\{\bigl{(}{[(e,i)]}_{\sim_{B}}\,,\,{[(v,i)]}_{\sim_{R}}\bigr{)}\,:\,i\in[2],\
(e,v)\in E(I_{i})\\}.$

Next we define the functions $r,b,g$.

(r)

Let $r\colon{\rm Nature}_{\geq{}1}\rightharpoonup\mathcal{R}(I)$ with
$\operatorname{dom}(r)=\operatorname{dom}(r_{1})\cup\operatorname{dom}(r_{2})$
be defined by $r(j)\coloneqq{[(r_{1}(j),1)]}_{\sim_{R}}$ for all
$j\in\operatorname{dom}(r_{1})$ and $r(j)\coloneqq{[(r_{2}(j),2)]}_{\sim_{R}}$
for all $j\in\operatorname{dom}(r_{2})\setminus\operatorname{dom}(r_{1})$.

(b)

Let $b\colon[k]\rightharpoonup\mathcal{B}(I)$ with
$\operatorname{dom}(b)=\operatorname{dom}(b_{1})\cup\operatorname{dom}(b_{2})$
be defined by $b(j)\coloneqq{[(b_{1}(j),1)]}_{\sim_{B}}$ for all
$j\in\operatorname{dom}(b_{1})$ and $b(j)\coloneqq{[(b_{2}(j),2)]}_{\sim_{B}}$
for all $j\in\operatorname{dom}(b_{2})\setminus\operatorname{dom}(b_{1})$.

(g)

Let $g\coloneqq g_{1}\cup g_{2}$ (recall from Section 2 that this means that
$g(j)=g_{1}(j)$ for all $j\in\operatorname{dom}(g_{1})$ and $g(j)=g_{2}(j)$
for all $j\in\operatorname{dom}(g_{2})\setminus\operatorname{dom}(g_{1})$).

Finally, for both $i\in[2]$ we define mappings
$\operatorname{succ}^{R}_{L_{i}}\colon\mathcal{R}(I_{i})\to\mathcal{R}(I)$ and
$\operatorname{succ}^{B}_{L_{i}}\colon\mathcal{B}(I_{i})\to\mathcal{B}(I)$ by

$\displaystyle\operatorname{succ}^{R}_{L_{i}}(v)$
$\displaystyle\coloneqq{[(v,i)]}_{\sim_{R}}\quad\text{for
all}\;v\in\mathcal{R}(I_{i})\;\text{and}$