# The Weisfeiler-Leman Dimension of Existential Conjunctive Queries111Andreas
Göbel was funded by the project PAGES (project No. 467516565) of the German
Research Foundation (DFG). For the purpose of Open Access, the authors have
applied a CC BY public copyright licence to any Author Accepted Manuscript
version arising from this submission. All data is provided in full in the
results section of this paper.

Andreas Göbel
Hasso Plattner Institute
University of Potsdam
Germany  Leslie Ann Goldberg
Department of Computer Science
University of Oxford
United Kingdom  Marc Roth
Department of Computer Science
University of Oxford
United Kingdom

(29 October 2023)

###### Abstract

A graph parameter is a function $f$ on graphs with the property that, for any
pair of isomorphic graphs $G_{1}$ and $G_{2}$, $f(G_{1})=f(G_{2})$. The
Weisfeiler–Leman (WL) dimension of $f$ is the minimum $k$ such that, if
$G_{1}$ and $G_{2}$ are indistinguishable by the $k$-dimensional WL-algorithm
then $f(G_{1})=f(G_{2})$. The WL-dimension of $f$ is $\infty$ if no such $k$
exists. We study the WL-dimension of graph parameters characterised by the
number of answers from a fixed conjunctive query to the graph. Given a
conjunctive query $\varphi$, we quantify the WL-dimension of the function that
maps every graph $G$ to the number of answers of $\varphi$ in $G$.

The works of Dvorák (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP
2018), and Neuen (ArXiv 2023) have answered this question for _full_
conjunctive queries, which are conjunctive queries without existentially
quantified variables. For such queries $\varphi$, the WL-dimension is equal to
the treewidth of the Gaifman graph of $\varphi$.

In this work, we give a characterisation that applies to all conjunctive
qureies. Given any conjunctive query $\varphi$, we prove that its WL-dimension
is equal to the _semantic extension width_ $\mathsf{sew}(\varphi)$, a novel
width measure that can be thought of as a combination of the treewidth of
$\varphi$ and its _quantified star size_ , an invariant introduced by Durand
and Mengel (ICDT 2013) describing how the existentially quantified variables
of $\varphi$ are connected with the free variables. Using the recently
established equivalence between the WL-algorithm and higher-order Graph Neural
Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence
that the function counting answers to a conjunctive query $\varphi$ cannot be
computed by GNNs of order smaller than $\mathsf{sew}(\varphi)$.

The majority of the paper is concerned with establishing a lower bound of the
WL-dimension of a query. Given any conjunctive query $\varphi$ with semantic
extension width $k$, we consider a graph $F$ of treewidth $k$ obtained from
the Gaifman graph of $\varphi$ by repeatedly cloning the vertices
corresponding to existentially quantified variables. Using a recent
modification due to Roberson (ArXiv 2022) of the Cai-Fürer-Immerman
construction (Combinatorica 1992), we then obtain a pair of graphs $\chi(F)$
and $\hat{\chi}(F)$ that are indistinguishable by the $(k-1)$-dimensional WL-
algorithm since $F$ has treewidth $k$. Finally, in the technical heart of the
paper, we show that $\varphi$ has a different number of answers in $\chi(F)$
and $\hat{\chi}(F)$. Thus, $\varphi$ can distinguish two graphs that cannot be
distinguished by the $(k-1)$-dimensional WL-algorithm, so the WL-dimension of
$\varphi$ is at least $k$.

##  1 Introduction

The Weisfeiler–Leman (WL) algorithm [36] and its higher dimensional
generalisations [8] are amongst the most well-studied heuristics for graph
isomorphism. This algorithm works as follows. For each positive integer $k$,
the $k$-dimensional WL-algorithm iteratively maps the vertices of a graph to
multisets of colours. Two graphs $G$ and $G^{\prime}$ are said to be $k$-WL-
equivalent, denoted $G\cong_{k}G^{\prime}$, if this algorithm returns the same
vertex colouring for $G$ and $G^{\prime}$, up to consistently renaming the
colours. For the specific case $k=1$ the WL-algorithm is equivalent to the
colour-refinement algorithm, which is a widely used and efficiently-
implementable heuristic for graph isomorphism (see e.g. [1, 22]).

In addition to applications to graph isomorphism, recent works have shown that
the expressiveness of Graph Neural Networks (GNNs) and their higher order
generalisations is precisely characterised by the WL-algorithm [28, 37]. This
result has sparked a flurry of research with the objective of determining
which graph parameters are invariant on graphs that are indistinguishable by
the WL-algorithm [27, 11, 3, 2, 29, 24, 6]. We refer the reader to the survey
by Grohe [21] for further reading.

Over the years, surprising alternative characterisations of $k$-WL-equivalence
have been established.

  * (I)

$G\cong_{1}G^{\prime}$ if and only if $G$ and $G^{\prime}$ are fractionally
isomorphic [34, 35].

  * (II)

For each positive integer $k$, $G\cong_{k}G^{\prime}$ if and only if there is
no first-order formula with counting quantifiers that uses at most $k+1$
variables and that can distinguish $G$ and $G^{\prime}$ [23, 8].

  * (III)

For each positive integer $k$, $G\cong_{k}G^{\prime}$ if and only if, for each
graph $H$ of treewidth at most $k$, the number of graph homomorphisms from $H$
to $G$ is equal to the number of graph homomorphisms from $H$ to $G^{\prime}$
[19, 14]. This is the characterisation of $k$-WL-equivalence that will be used
in this work (see Definition 18).

The characterisation in (III) has ignited interest in studying the _WL-
dimension_ of counting graph homomorphisms and of counting related patterns
[11, 2, 29, 24, 6].

A graph parameter $f$ is a function from graphs that is invariant under
isomorphisms. The WL-dimension of a graph parameter $f$ is the minimum
positive integer $k$ such that $f$ cannot distinguish $k$-WL-equivalent graphs
(see Definition 19). Building upon the works of Dvorák [19], Dell, Grohe and
Rattan [14], Roberson [31], and Seppelt [33], it has very recently been shown
by Neuen [29] that the WL-dimension of the graph parameter that counts
homomorphisms from a fixed graph $H$ is exactly the treewidth of $H$. It is
well-known that counting homomorphisms is equivalent to counting answers to
conjunctive queries without existentially quantified variables (see e.g.
[30]); such conjunctive queries are also called _full_ conjunctive queries. In
this work, we consider all conjunctive queries including those that have
existentially quantified variables and we answer the fundamental question:
What is the WL-dimension of the graph parameter that counts answers to fixed
conjunctive queries?

To state our results, we first introduce some central concepts.

###  1.1 Conjunctive Queries and Semantic Extension Width

A _conjunctive query_ $\varphi$ consists of a set of free variables
$X=\\{x_{1},\dots,x_{k}\\}$ and a set of (existentially) quantified variables
$Y=\\{y_{1},\dots,y_{\ell}\\}$, and is of the form

$\varphi(x_{1},\dots,x_{k})=\exists y_{1},\dots,y_{\ell}\colon
A_{1}\wedge\dots\wedge A_{m},$

such that each $A_{i}$ is an atom $R(\vec{z})$ where $R$ is a relation symbol
and $\vec{z}$ is a vector of variables in $X\cup Y$. Since we focus in this
work on undirected graphs without self-loops, in our setting there is only one
binary relation symbol $E$, so all atoms are of the form $E(z_{1},z_{2})$. An
_answer_ to $\varphi$ in a graph $G$ is an assignment $a$ from the free
variables $X$ to $V(G)$ such there is an assignment $h$ from $X\cup Y$ to
$V(G)$ which agrees with $a$ on $X$ and has the property that, for each atom
$E(z_{1},z_{2})$, the image $\\{h(z_{1}),h(z_{2})\\}$ is an edge of $G$.

As is common in the literature (see e.g. [30, 9, 10, 15]), we can equivalently
express the answers of $\varphi$ in a graph $G$ as partial homomorphisms to
$G$. Let $H$ be the graph with vertex set $X\cup Y$ that has as edges the
pairs of variables in $X\cup Y$ that occur in a common atom. Then the answers
of $\varphi$ in $G$ are the mappings $a\colon X\to V(G)$ that can be extended
to a homomorphism from $H$ to $G$. For this reason, following the notation of
[15], we will from now an refer to a conjunctive query as a pair $(H,X)$ where
$H$ is a graph and $X$ is a subset of vertices of $H$ corresponding to the
free variables. We will say that $(H,X)$ is _connected_ if $H$ is a connected
graph. We will write $\mathrm{Ans}((H,X),G)$ for the set of answers of $(H,X)$
in $G$; this is made formal in Section 2.1. The WL-dimension of a conjunctive
query $(H,X)$ is the WL-dimension of the graph parameter that maps every graph
$G$ to $|\mathrm{Ans}((H,X),G)|$.

##### Semantic Extension Width

Let $(H,X)$ be a conjunctive query and let $Y=V(H)\setminus X$. The graph
$\Gamma(H,X)$ is obtained from $H$ by adding an edge between each pair of
vertices $u\neq v$ in $X$ if and only if there is a connected component in
$H[Y]$ that is adjacent to both $u$ and $v$. We then define the _extension
width_ of $(H,X)$ as the treewidth of $\Gamma(H,X)$; the definition of
treewidth can be found in Section 2.2.

The _semantic extension width_ of a conjunctive query $(H,X)$, denoted by
$\mathsf{sew}(H,X)$ is then the minimum extension width of any conjunctive
query $(H^{\prime},X^{\prime})$ that is _counting equivalent_ to $(H,X)$,
i.e., any conjunctive query $(H^{\prime},X^{\prime})$ such that, for every
graph $G$,
$|\mathrm{Ans}((H,X),G)|=|\mathrm{Ans}((H^{\prime},X^{\prime}),G)|$. A
discussion of counting equivalence and _counting minimal_ conjunctive queries
can be found in Section 2.1.

Before stating our main result, we provide an example of a conjunctive query
and its semantic extension width: Let $(S_{k},X_{k})$ be the $k$-_star query_
: $X_{k}=\\{x_{1},\dots,x_{k}\\}$ and $S_{k}$ has vertices $X_{k}\cup\\{y\\}$
and edges $\\{x_{i},y\\}$ for all $i\in[k]$. Note that the answers of
$(S_{k},X_{k})$ in a graph $G$ are precisely the assignments from $X_{k}$ to
$V(G)$ the images of which have a common neighbour. The $k$-star query is
acyclic (i.e., $S_{k}$ has treewidth $1$) and played an important role as a
base case for complexity classifications of counting answers to conjunctive
queries [9, 15]. The graph $\Gamma(S_{k},X_{k})$ is the $(k+1)$-clique which
has treewidth $k$. Since it is also minimal with respect to counting
equivalence, we have $\mathsf{sew}(S_{k},X_{k})=k$.

###  1.2 Our Contributions

We are now able to state our main result.

######  Theorem 1.

Let $(H,X)$ be a connected conjunctive query with $X\neq\emptyset$. Then the
WL-dimension of $(H,X)$ is equal to its semantic extension width
$\mathsf{sew}(H,X)$.

Theorem 1 has consequences regarding the expressiveness of conjunctive
queries. It follows from a recent result of Morris et al. [28] that Graph
Neural Networks (GNNs) of order $k$ cannot compute functions of WL-dimension
larger than $k$. Therefore, for every connected conjunctive query $(H,X)$ with
$X\neq\emptyset$, GNNs of order smaller than $\mathsf{sew}(H,X)$ cannot
compute the function that counts the answers to $(H,X)$.

As a further corollary, we establish the following alternative
characterisation of WL-equivalence.

######  Corollary 2.

For each positive integer $k$, two graphs $G$ and $G^{\prime}$ are $k$-WL-
equivalent if and only if, for each connected conjunctive query $(H,X)$ with
$X\neq\emptyset$ and $\mathsf{sew}(H,X)\leq k$,
$|\mathrm{Ans}((H,X),G)|=|\mathrm{Ans}((H,X),G^{\prime})|$.

The next consequence of our main result reveals a surprising connection
between the complexity of counting answers to conjunctive queries and their
WL-dimension. Given a class of conjunctive queries $\Psi$, the counting
problem $\\#\textsc{CQ}(\Psi)$ takes as input a pair consisting of a
conjunctive query $(H,X)\in\Psi$ and a graph $G$ and outputs
$|\mathrm{Ans}((H,X),G)|$. We say that a class of conjunctive queries has
_bounded_ WL-dimension if there is a constant $B$ that upper bounds the WL-
dimension of all queries in the class. The assumption $\mathrm{FPT}\neq W[1]$
is the central (and widely accepted) hardness assumption in parameterised
complexity theory (see e.g. [20]). Theorem 1 has the following corollary; we
say that a conjunctive query is _counting minimal_ if it is a minimal
representative with respect to counting equivalence (see Definition 8).

######  Corollary 3.

Let $\Psi$ be a recursively enumerable class of counting minimal and connected
conjunctive queries with at least one free variable. The problem
$\\#\textsc{CQ}(\Psi)$ is solvable in polynomial time if and only if the WL-
dimension of $\Psi$ is bounded; the “only if” is conditioned under the
assumption $\mathrm{FPT}\neq W[1]$.

Our main result also enables us to classify the WL-dimension of more complex
queries including unions of conjunctive queries and conjunctive queries with
disequalities and negations over the free variables. The statement of this
classification requires the consideration of finite linear combinations of
conjunctive queries (also known as _quantum queries_ ; see Definition 61). A
quantum query is of the form $Q=\sum_{i=1}^{\ell}c_{i}\cdot(H_{i},X_{i})$
where, for all $i\in[\ell]$, $c_{i}\in\mathbb{Q}\setminus\\{0\\}$. The
$(H_{i},X_{i})$ are connected and pairwise non-isomorphic conjunctive queries
where each $(H_{i},X_{i})$ is counting minimal and $X_{i}\neq\emptyset$.

It is well-known [10, 15] that unions of conjunctive queries, existential
positive queries, and conjunctive queries with disequalities and negations
over the free variables all have (unique) expressions as quantum queries, that
is, the number of answers to those more complex queries can be computed by
evaluation the respective quantum query according to the definition
$|\mathrm{Ans}(Q,G)|:=\sum_{i=1}^{\ell}c_{i}\cdot|\mathrm{Ans}((H_{i},X_{i}),G)|$.
For this reason, understanding the WL-dimension of linear combination of
conjunctive queries allows us to also understand the WL-dimension of more
complex queries.

Defining the _hereditary semantic extension width_ of a quantum query $Q$,
denoted by $\mathsf{hsew}(Q)$, as the maximum semantic extension width of its
terms, we obtain the following.

######  Corollary 4.

The WL-dimension of a quantum query $Q$ is equal to $\mathsf{hsew}(Q)$.

As a final corollary of our main result we take a look at a concrete graph
parameter, the WL-dimension of which was not known so far: the parameter that
maps each graph $G$ to the number of size-$k$ dominating sets in $G$. Here, a
dominating set of a graph $G$ is a subset of vertices $D$ of $G$ such that
each vertex of $G$ is either contained in $D$ or is adjacent to a vertex in
$D$. With an easy argument, we show that counting dominating sets of size $k$
can be expressed as a linear combination of the $k$-star queries
$(S_{k},X_{k})$. Using Theorem 1 and Corollary 4, we obtain the following
corollary.

######  Corollary 5.

For each positive integer $k$, the WL-dimension of the graph parameter that
maps each graph $G$ to the number of size-$k$ dominating sets in $G$ is equal
to $k$.

###  1.3 Discussion and Outlook

We stated and proved our result for the case of connected conjunctive queries
with at least one free variable over graphs. However, our result can easily be
extended to the following.

  * (A)

For disconnected queries, the WL-dimension will just be the maximum of the
semantic extension widths of the connected components.

  * (B)

If no variable is free, then counting answers of a conjunctive query becomes
equivalent to _deciding_ the existence of a homomorphism. The WL-dimension of
the corresponding graph parameter is equal to the treewidth of the query
modulo homomorphic equivalence, which for queries without free variables is
the same as semantic extension width. This can be proved along the lines of
the analysis of Roberson [31].

  * (C)

Barceló et al. [3], and Lanzinger and Barceló [24] have shown very recently
that the WL-algorithm (and the notions of WL-equivalence and WL-dimension)
readily extend from graphs to _knowledge graphs_ , i.e., graphs with vertex
labels and edge labels; parallel edges with distinct labels are allowed, but
self-loops are not allowed. It is not hard to see that our analysis applies to
knowledge graphs as well.

Since the technical content of this paper is already quite extensive, we
decided to defer the formal statement and proofs of (A)–(C) to a future
journal version.

Finally, extending our results from graphs to relational structures is more
tricky, since it is not known yet whether and how WL-equivalence can be
characterised via homomorphism indistinguishability from structures of higher
arity.222A characterisation for the special case of _constant_ arity $r\geq 2$
was recently established independently by Butti and Dalmau [7], and by Dawar,
Jakl, and Reggio [13]. However, recent works by Böker [5] and by Scheidt and
Schweikardt [32] provide first evidence that homomorphism counts from
hypergraphs of bounded generalised hypertreewidth might be the right answer.
We leave this for future work.

###  1.4 Organisation of the Paper

We start by introducing further necessary notation and concepts in Section 2.
Afterwards, we prove the upper bound of the WL-dimension in Section 3, and we
prove the lower bound in Section 4. Those two sections can be read
independently from each other and the majority of the conceptual and technical
work is done in Section 4. Finally, we prove Theorem 1, as well as its
consequences, in Section 5.

##  2 Preliminaries

Given a set $S$, we write $\mathsf{Bij}(S)$ for the set of all bijections from
$S$ to itself. Given a function $f:A\to B$ and a subset $X\subseteq A$, we
write $f|_{X}:X\to B$ for the restriction of $f$ on $X$. We write $\pi_{1}$
for the projection of a pair to its first component, that is,
$\pi_{1}(a,b)=a$. Given a positive integer $\ell$ we set
$[\ell]=\\{1,\dots,\ell\\}$.

All graphs in this paper are undirected and simple (without self-loops and
without parallel edges). Given a graph $G=(V,E)$, a vertex $u\in V$ and a
subset $U$ of $V$, $N(u)=\\{v\in V\mid\\{u,v\\}\in E\\}$ and $N(U)=\cup_{u\in
U}N_{u}$. We say that a connected component $C$ of a graph $H$ is _adjacent_
to a vertex $v$ of $H$ if there are vertices $u$ and $w$ in $C$ that are
adjacent to $v$. Given a subset $S$ of vertices of a graph $G$, we write
$G[S]$ for the graph induced by the vertices in $S$.

A _homomorphism_ from a graph $H$ to a graph $G$ is a function $h:V(H)\to
V(G)$ such that, for all edges $\\{u,v\\}\in E(H)$, $\\{h(u),h(v)\\}$ is an
edge of $G$. We write $\mathrm{Hom}(H,G)$ for the set of all homomorphisms
from $H$ to $G$. An _isomorphism_ from $H$ to $G$ is a bijection $b:V(H)\to
V(G)$ such that, for all $u,v\in V(H)$, $\\{u,v\\}\in E(H)$ if and only if
$\\{h(u),h(v)\\}\in E(G)$. We say that $H$ and $G$ are _isomorphic_ , denoted
by $H\cong G$, if there is an isomorphism from $H$ to $G$. An _automorphism_
of a graph $H$ is an isomorphism from $H$ to itself, and we write
$\mathrm{Aut}(H)$ for the set of all automorphisms of $H$.

###  2.1 Conjunctive Queries

As stated in the introduction, we focus on conjunctive queries on graphs. This
allows us to follow the notation of [15].

######  Definition 6.

A _conjunctive query_ is a pair $(H,X)$ where $H$ is the underlying graph and
$X$ is the set of free variables. When $H$ and $X$ are clear from context we
will use $Y$ to denote $V(H)\setminus X$. We say that a conjunctive query
$(H,X)$ is _connected_ if $H$ is connected.

It is well-known (see e.g. [9, 10, 15]) that the set of answers of a
conjunctive query in a graph $G$ is the set of assignments from the free
variables to the vertices of $G$ that can be extended to a homomorphism.

######  Definition 7.

Let $(H,X)$ be a conjunctive query and let $G$ be a graph. The set of answers
of $(H,X)$ in $G$ is given by $\mathrm{Ans}((H,X),G)=\\{a:X\to V(G)\mid\exists
h\in\mathrm{Hom}(H,G):h|_{X}=a\\}$.

We say that two conjunctive queries $(H_{1},X_{1})$ and $(H_{2},X_{2})$ are
_isomorphic_ , denoted by $(H_{1},X_{1})\cong(H_{2},X_{2})$ if there is an
isomorphism from $H_{1}$ to $H_{2}$ that maps $X_{1}$ to $X_{2}$.

Throughout this work, we will focus on _counting minimal_ conjunctive queries.

######  Definition 8 (Counting Equivalence and Counting Minimality).

We say that two conjunctive queries $(H_{1},X_{1})$ and $(H_{2},X_{2})$ are
_counting equivalent_ , denoted by $(H_{1},X_{1})\sim(H_{2},X_{2})$, if for
each graph $G$,
$|\mathrm{Ans}((H_{1},X_{1}),G)|=|\mathrm{Ans}((H_{2},X_{2}),G)|$. A
conjunctive query is said to be _counting minimal_ if it it is minimal (with
respect to taking subgraphs) in its counting equivalence class.

It is known that all counting minimal conjunctive queries within a counting
equivalence class are isomorphic [10, 15]. If a query has no existential
variables so that $X=V(H)$ then counting equivalence is the same as
isomorphism. If all variables are quantified so that $X=\emptyset$ then
counting equivalence is the same as homomorphic equivalence (also called
semantic equivalence).

###  2.2 Treewidth and Extension Width

We start by introducing tree decompositions and treewidth.

######  Definition 9.

Let $H$ be a graph. A _tree decomposition_ of $H$ is a pair consisting of a
tree $T$ and a collection of sets, called _bags_ ,
$\mathcal{B}=\\{B_{t}\\}_{t\in V(T)}$, such that the following conditions are
satisfied:

  * (T1)

For all $v\in V(H)$ there is a bag $B_{t}$ with $v\in B_{t}$.

  * (T2)

For all $v\in V(H)$ the subgraph of $T$ induced by the vertex set $\\{t\in
V(T)\mid v\in B_{t}\\}$ is connected.

  * (T3)

For all $e\in E(H)$, there is a bag $B_{t}$ with $e\subseteq B_{t}$.

The _width_ of $(T,\mathcal{B})$ is $\max_{t\in V(T)}|B_{t}|-1$ and a tree
decomposition of minimum width is called _optimal_. The _treewidth_ of $H$,
denoted by $\mathsf{tw}(H)$, is the width of an optimal tree decomposition of
$H$. The treewidth of a conjunctive query $(H,X)$, denoted by
$\mathsf{tw}(H,X)$, is the treewidth of $H$.

Next we introduce the extension width of a conjunctive query.

######  Definition 10 ($\Gamma(H,X)$ and Extension Width).

Let $(H,X)$ be a conjunctive query. The _extension_ $\Gamma(H,X)$ of $(H,X)$
is a graph with vertex set $V(H)$ and edge set $E(H)\cup E^{\prime}$, where
$E^{\prime}$ is the set of all $\\{u,v\\}$ such that $u,v\in X$, $u\neq v$,
and there is a connected component of $H[Y]$ which is adjacent to both $u$ and
$v$ in $H$. The _extension width_ of of a conjunctive query $(H,X)$ is defined
by $\mathsf{ew}(H,X):=\mathsf{tw}(\Gamma(X,H))$.

We will often restrict our analysis to counting minimal conjunctive queries.
This requires us to lift the notion of extension width as follows.

######  Definition 11 (Semantic Extension Width).

The _semantic extension width_ of a conjunctive query $(H,X)$, denoted by
$\mathsf{sew}(H,X)$, is the extension width of a counting minimal conjunctive
query $(H^{\prime},X^{\prime})$ with $(H,X)\sim(H^{\prime},X^{\prime})$.

Note that the semantic extension width is well-defined since all counting
minimal $(H^{\prime},X^{\prime})$ with $(H,X)\sim(H^{\prime},X^{\prime})$ are
isomorphic.

###  2.3 The $\ell$-copy $F_{\ell}(H,X)$

One of the most central operations on conjunctive queries invoked in this work
is a cloning operation on existentially quantified variables, defined as
follows.

######  Definition 12 ($F_{\ell}(H,X)$).

Let $(H,X)$ be a conjunctive query and let $\ell$ be a positive integer. The
$\ell$_-copy_ $F_{\ell}(H,X)$ is defined as follows. The vertex set of
$F_{\ell}(H,X)$ is $X\cup(Y\times[\ell])$. Let

$\displaystyle E_{X}$ $\displaystyle=\\{\\{u,v\\}\in E(H)\cap X^{2}\\},$
$\displaystyle E_{X,Y}$ $\displaystyle=\\{\\{u,(v,i)\\}\mid u\in X,v\in
Y,i\in[\ell],\\{u,v\\}\in E(H)\\},\textrm{ and }$ $\displaystyle E_{Y}$
$\displaystyle=\\{\\{(u,i),(v,i)\\}\mid\\{u,v\\}\in E(H)\cap
Y^{2},i\in[\ell]\\}.$

The edge set of $F_{\ell}(H,X)$ is $E_{X}\cup E_{X,Y}\cup E_{Y}$.

There is a natural homomorphism from $F_{\ell}(H,X)$ to $H$ which we denote by
$\gamma[H,X,\ell]$.

######  Definition 13.

Let $(H,X)$ be a conjunctive query and let $\ell$ be a positive integer.
Define $\gamma[H,X,\ell]\colon V(F_{\ell}(H,X))\to V(H)$ as follows:

$\gamma[H,X,\ell](u)=\begin{cases}u&u\in X\\\ \pi_{1}(u)&u\in
Y\times[\ell]\end{cases}$

We will just write $\gamma=\gamma[H,X,\ell]$ if $(H,X)$ and $\ell$ are clear
from the context.

######  Observation 14.

The function $\gamma$ is a homomorphism from $F_{\ell}(H,X)$ to $H$.

Next, we relate the treewidth of the graph $F_{\ell}(H,X)$ to the extension
width of $(H,X)$.

######  Lemma 15.

Let $(H,X)$ be a conjunctive query and let $\ell$ be a positive integer. The
treewidth of $F_{\ell}(H,X)$ is at most $\mathsf{ew}(H,X)$.

###### Proof.

Let $\Gamma=\Gamma(H,X)$ and let $C_{1},\dots,C_{m}$ be the connected
components of $H[Y]$. For each $i\in[m]$, let $\delta_{i}=N(C_{i})\cap X$ and
let $\hat{C}_{i}=C_{i}\cup\delta_{i}$. Since $\delta_{i}$ is a clique in
$\Gamma$, there is an optimal tree decomposition
$(\mathcal{T}_{i},\mathcal{B}_{i})$ of $\Gamma[\hat{C}_{i}]$ with $\delta_{i}$
as a bag. For $j\in[\ell]$, let $(\mathcal{T}_{i}^{j},\mathcal{B}_{i}^{j})$ be
a copy of $(\mathcal{T}_{i},\mathcal{B}_{i})$ where $B_{i}^{j}$ is the bag
corresponding to $\delta_{i}$.

Let $(\mathcal{T}_{X},\mathcal{B}_{X})$ be an optimal tree decomposition of
$\Gamma[X]$. Choose $(\mathcal{T}_{X},\mathcal{B}_{X})$ such that there is a
bag $B_{X,i}$ corresponding to each $\delta_{i}$.

Finally, construct a tree decomposition $(\mathcal{T},\mathcal{B})$ of
$F_{\ell}(H,X)$ by identifying $B_{X,i}$ and $B_{i}^{j}$ for each $i\in[m]$
and $j\in[\ell]$. This tree decomposition shows that
$\mathsf{tw}(F_{\ell}(H,X))\leq\mathsf{tw}(\Gamma)$. ∎

######  Lemma 16.

Let $(H,X)$ be a conjunctive query. There exists a positive integer $\ell$
such that $\mathsf{ew}(H,X)\leq\mathsf{tw}(F_{\ell}(H,X))$.

###### Proof.

Choose any $\ell>|V(H)|+1$, and let $\gamma=\gamma[H,X,\ell]$. Let
$(T,\mathcal{B})$, with $\mathcal{B}=\\{B_{t}\\}_{t\in V(T)}$ be an optimal
tree decomposition of $F_{\ell}(H,X)$. We prove the lemma by constructing a
tree decomposition $(T^{\prime},\mathcal{B}^{\prime})$ of $\Gamma(X,H)$ with
with width at most the width of $(T,\mathcal{B})$. Let $T^{\prime}=T$. For
each $t\in V(T)$, define $B^{\prime}_{t}=\\{\gamma(v)\mid\mbox{$v\in B_{t}$
and $v$ is not of the form $(v,i)$ for $i>1$}\\}$.

We claim that $(T^{\prime},\mathcal{B}^{\prime})$ is a tree-decomposition of
$\Gamma(H,X)$. This claim proves the lemma, since the width of
$(T^{\prime},\mathcal{B}^{\prime})$ is clearly at most the width of
$(T,\mathcal{B})$, and since the extension width of $(H,X)$ is, by definition,
the treewidth of $\Gamma(H,X)$. Hence it remains to prove our claim by
establishing (T1), (T2), and (T3) from Definition 9. In each case, for each
$v\in V(\Gamma(H,X))$, let $v^{\prime}=v$ if $v\in X$ and let
$v^{\prime}=(v,1)$ if $v\in Y$.

  * (T1)

Consider $v\in V(\Gamma(H,X))=V(H)$. Then $v^{\prime}\in V(F_{\ell}(H,X))$ and
thus there is a bag $B_{t}$ with $v^{\prime}\in B_{t}$. Since
$v^{\prime}\neq(v,i)$ for $i>1$ and since $\gamma(v^{\prime})=v$, $v\in
B^{\prime}_{t}$.

  * (T2)

Consider $v\in V(\Gamma(H,X))$ and let $s$ and $t$ be any pair of vertices of
$T$ such that $v\in B^{\prime}_{s}$ and $v\in B^{\prime}_{t}$. We show that
there is an $s$-$t$-path $P$ in $T$ such that $v\in B^{\prime}_{u}$ for each
$u\in P$. Since $v\in B^{\prime}_{s}$ and $v\in B^{\prime}_{t}$, we have
$v^{\prime}\in B_{s}$ and $v^{\prime}\in B_{t}$. Using that $(T,\mathcal{B})$
is a tree-decomposition, there is a path $P$ in $T$ such that $v^{\prime}\in
B_{u}$, and thus $v\in B^{\prime}_{u}$, for each $u\in P$.

  * (T3)

Consider $e=\\{v_{1},v_{2}\\}\in E(\Gamma(H,X))$. Recall from Definition 10
that $E(\Gamma(H,X))=E(H)\cup E^{\prime}$, where $E^{\prime}$ contains all
$\\{u,v\\}$ such that there is a connected component $C$ of $H[Y]$ that is
adjacent to both $u$ and $v$ in $H$.

We distinguish between two cases. For the easy case, suppose that $e\in E(H)$.
Then $e^{\prime}=\\{v^{\prime}_{1},v^{\prime}_{2}\\}\in E(F_{\ell}(H,X))$.
Thus there is a bag $B_{t}\in\mathcal{B}$ with $e^{\prime}\subseteq B_{t}$.
Consequently, $e\in B^{\prime}_{t}$.

For the more difficult case, suppose $e\in E^{\prime}$. Then $v_{1},v_{2}\in
X$ and thus $v_{1}=v^{\prime}_{1}$ and $v_{2}=v^{\prime}_{2}$. Moreover, there
is a connected component $C$ of $H[Y]$ that is adjacent to both $v_{1}$ and
$v_{2}$. Since there are $\ell$ copies of $C$ in $F_{\ell}(H,X)$, there are at
least $\ell$ vertex disjoint paths from $v_{1}$ to $v_{2}$ in $F_{\ell}(H,X)$.
Now, using known separation properties of tree decompositions (see for
instance [17, Lemma 5]), there is either a bag $B_{t}$ of $(T,\mathcal{B})$
that contains $v_{1}$ and $v_{2}$ — in this case, we are done — or there is an
edge $e=\\{s,t\\}$ of $T$ such that $S:=B_{s}\cap B_{t}$ separates $v_{1}$ and
$v_{2}$, that is, $S$ does not contain $v_{1}$ and $v_{2}$, and every
$v_{1}$-$v_{2}$-path of $F_{\ell}(H,X)$ intersects $S$. This requires
$|S|\geq\ell$ and thus $|B_{s}|\geq\ell$ (and $|B_{t}|\geq\ell$).
Consequently, using the fact that $(T,\mathcal{B})$ is optimal, the treewidth
of $F_{\ell}(H,X)$ is at least $\ell>|V(H)|+1$, which yields a contradiction,
since by Lemma 15 we have

$\mathsf{tw}(F_{\ell}(H,X))\leq\mathsf{ew}(H,X)=\mathsf{tw}(\Gamma(H,X))\leq|V(\Gamma(H,X))|=|V(H)|\,.$

Thus $v_{1}$ and $v_{2}$ must both be contained in some bag $B_{t}$, and thus
also in the bag $B^{\prime}_{t}$.

With (T1)-(T3) established, the proof is concluded. ∎

In combination, Lemmas 15 and 16 provide an alternative characterisation of
the extension width, which we will be using for the remainder of the paper.

######  Corollary 17.

Let $(H,X)$ be a conjunctive query. Then
$\mathsf{ew}(H,X)=\max\\{\mathsf{tw}(F_{\ell}(H,X))\mid\ell\in\mathbb{Z}_{>0}\\}$.

###### Proof.

The corollary follows immediately from Lemmas 15 and 16. ∎

###  2.4 Weisfeiler-Leman Equivalence, Invariance and Dimension

In order to make this work self-contained, we will use the characterisation of
Weifeiler-Leman (from now on just “WL”) equivalence via homomorphism
indistinguishability due to Dvorák [19] and Dell, Grohe and Rattan [14]. We
recommend the survey of Arvind for a short but comprehensive introduction to
the classical definition using the WL-algorithm [1].

######  Definition 18 (WL-Equivalence).

Let $k$ be a positive integer. Two graphs $G$ and $G^{\prime}$ are $k$_-WL-
equivalent_ , denoted by $G\cong_{k}G^{\prime}$, if for every graph $H$ of
treewidth at most $k$ we have
$|\mathrm{Hom}(H,G)|=|\mathrm{Hom}(H,G^{\prime})|$.

Note that WL-equivalence is monotone in the sense that $G\cong_{k}G^{\prime}$
implies that for every $k^{\prime}\leq k$, $G\cong_{k^{\prime}}G^{\prime}$. A
graph parameter $f$ is called $k$_-WL-invariant_ if, for every pair of graphs
$G,G^{\prime}$ with $G\cong_{k}G^{\prime}$, $f(G)=f(G^{\prime})$. Observe
that, for $k\geq k^{\prime}$, every $k^{\prime}$ -WL-invariant graph parameter
is also $k$-WL-invariant. Thus, following the definition of Arvind et al. [2],
we define the _WL-dimension_ of a graph parameter $f$ as the minimum $k$ for
which $f$ is $k$-WL-invariant, if such a $k$ exists, and $\infty$ otherwise.

######  Definition 19 (WL-dimension of conjunctive queries).

Let $(H,X)$ be a conjunctive query. The _WL-dimension_ of $(H,X)$ is the WL-
dimension of the function $G\mapsto|\mathrm{Ans}((H,X),G)|$.

##  3 Upper Bound on the WL-Dimension

The goal of this section is to prove the following upper bound.

######  Theorem 20.

Let $(H,X)$ be a conjunctive query. Then the WL-dimension of $(H,X)$ is at
most $\mathsf{ew}(H,X)$.

For the proof of Theorem 20 we will use the following interpolation argument.

######  Lemma 21.

Let $(H,X)$ be a conjunctive query. Let $G_{1}$ and $G_{2}$ be graphs. Suppose
that, for all positive integers $\ell$,
$|\mathrm{Hom}(F_{\ell}(H,X),G_{1})|=|\mathrm{Hom}(F_{\ell}(H,X),G_{2})|$.
Then $|\mathrm{Ans}((H,X),G_{1})|=|\mathrm{Ans}((H,X),G_{2})|$.

###### Proof.

Let $G$ be a graph and let $\sigma\colon X\to V(G)$. Define

$\mathrm{Ext}(\sigma)=\\{\rho\colon Y\to
V(G)\mid\sigma\cup\rho\in\mathrm{Hom}(H,G)\\}.$

Let $\Omega$ be the set of functions from $Y$ to $V(G)$ and consider any
$\Upsilon\subseteq\Omega$. Define

$\displaystyle H^{G}(\Upsilon)$
$\displaystyle=\\{h\in\mathrm{Ans}((H,X),G)\mid\mathrm{Ext}(h)=\Upsilon\\}$
$\displaystyle\hat{H}_{\ell}^{G}(\Upsilon)$
$\displaystyle=\\{h\in\mathrm{Hom}(F_{\ell}(H,X),G)\mid\mathrm{Ext}(h|_{X})=\Upsilon\\}$

First observe that for any $\Upsilon\subseteq\Omega$,
$|\hat{H}_{\ell}^{G}(\Upsilon)|=|H^{G}(\Upsilon)|\cdot|\Upsilon|^{\ell}$.
Moreover,

$\displaystyle|\mathrm{Ans}((H,X),G)|$
$\displaystyle=\sum_{\emptyset\neq\Upsilon\subseteq\Omega}|H^{G}(\Upsilon)|,\mbox{and}$
$\displaystyle|\mathrm{Hom}(F_{\ell}(H,X),G)|$
$\displaystyle=\sum_{\emptyset\neq\Upsilon\subseteq\Omega}|\hat{H}^{G}_{\ell}(\Upsilon)|.$

Now let $G_{1}$ and $G_{2}$ be graphs with
$|\mathrm{Hom}(F_{\ell}(H,X),G_{1})|=|\mathrm{Hom}(F_{\ell}(H,X),G_{2})|$ for
all positive integers $\ell$. Let $\Omega_{1}$ be the set of functions from
$Y$ to $V(G_{1})$ and let $\Omega_{2}$ be the set of functions from $Y$ to
$V(G_{2})$. Let $\hat{n}=\max\\{|\Omega_{1}|,|\Omega_{2}|\\}$. For every
positive integer $\ell$,

$\displaystyle|\mathrm{Hom}(F_{\ell}(H,X),G_{1})|=|\mathrm{Hom}(F_{\ell}(H,X),G_{2})|$
$\displaystyle\Leftrightarrow$
$\displaystyle\sum_{\emptyset\neq\Upsilon\subseteq\Omega_{1}}|\hat{H}^{G_{1}}_{\ell}(\Upsilon)|-\sum_{\emptyset\neq\Upsilon\subseteq\Omega_{2}}|\hat{H}^{G_{2}}_{\ell}(\Upsilon)|=0$
$\displaystyle\Leftrightarrow$
$\displaystyle\sum_{\emptyset\neq\Upsilon\subseteq\Omega_{1}}|{H}^{G_{1}}(\Upsilon)|\cdot|\Upsilon|^{\ell}-\sum_{\emptyset\neq\Upsilon\subseteq\Omega_{2})}|{H}^{G_{2}}(\Upsilon)|\cdot|\Upsilon|^{\ell}=0$
$\displaystyle\Leftrightarrow$
$\displaystyle\sum_{i=1}^{\hat{n}}i^{\ell}\cdot\Bigg{(}\sum_{\begin{subarray}{c}\Upsilon\subseteq\Omega_{1}\\\
|\Upsilon|=i\end{subarray}}|{H}^{G_{1}}(\Upsilon)|-\sum_{\begin{subarray}{c}\Upsilon\subseteq\Omega_{2}\\\
|\Upsilon|=i\end{subarray}}|{H}^{G_{2}}(\Upsilon)|\Bigg{)}=0$

Note that this yields a system of linear equations. For each positive integer
$\ell$, we have the equation $\sum_{i=1}^{\hat{n}}c_{i}\cdot i^{\ell}=0$ where

$c_{i}=\Bigg{(}\sum_{\begin{subarray}{c}\Upsilon\subseteq\Omega_{1}\\\
|\Upsilon|=i\end{subarray}}|{H}^{G_{1}}(\Upsilon)|-\sum_{\begin{subarray}{c}\Upsilon\subseteq\Omega_{2}\\\
|\Upsilon|=i\end{subarray}}|{H}^{G_{2}}(\Upsilon)|\Bigg{)}.$

The matrix corresponding to this system of equations is a Vandermonde matrix,
so it is invertible. Thus $c_{i}=0$ for all $i\in\\{1,\dots,n\\}$. Therefore

$\displaystyle|\mathrm{Ans}((H,X),G_{1})|$
$\displaystyle=\sum_{\emptyset\neq\Upsilon\subseteq\Omega_{1}}|H^{G_{1}}(\Upsilon)|=\sum_{i=1}^{\hat{n}}\sum_{\begin{subarray}{c}\Upsilon\subseteq\Omega_{1}\\\
|\Upsilon|=i\end{subarray}}|{H}^{G_{1}}(\Upsilon)|$
$\displaystyle=\sum_{i=1}^{\hat{n}}\sum_{\begin{subarray}{c}\Upsilon\subseteq\Omega_{2}\\\
|\Upsilon|=i\end{subarray}}|{H}^{G_{2}}(\Upsilon)|=\sum_{\emptyset\neq\Upsilon\subseteq\Omega_{2}}|H^{G_{2}}(\Upsilon)|=|\mathrm{Ans}((H,X),G_{2})|.$

∎

###### Proof of Theorem 20.

Let $(H,X)$ be a conjunctive query. Let $k=\mathsf{ew}(H,X)$. We wish to show
that the WL-dimension of $(H,X)$ is at most $k$ which is equivalent to showing
that the function $G\mapsto|\mathrm{Ans}((H,X),G)|$ is $k$-WL invariant. To do
this, we show that, for any pair of graphs $G$ and $G^{\prime}$ with
$G\cong_{k}G^{\prime}$,
$|\mathrm{Ans}((H,X),G)|=|\mathrm{Ans}((H,X),G^{\prime})|$.

Consider $G$ and $G^{\prime}$ with $G\cong_{k}G^{\prime}$. This implies that
for every graph $H$ with treewidth at most $k$,
$|\mathrm{Hom}(H,G)|=|\mathrm{Hom}(H,G^{\prime})|$. From the definition of
$\mathsf{ew}(H,X)$ and Corollary 17, for every positive integer $\ell$, the
treewidth of $F_{\ell}(H,X)$ is at most $k$. Thus,
$|\mathrm{Hom}(F_{\ell}(H,X),G)|=|\mathrm{Hom}(F_{\ell}(H,X),G^{\prime})|$.
The claim then follows directly by Lemma 21. ∎

##  4 Lower Bound on the WL-Dimension

The goal of this section, which is the technical heart of the paper, is the
proof of the following lower bound.

######  Theorem 22.

Let $(H,X)$ be a counting minimal conjunctive query such that $H$ is
connected, and $\emptyset\subsetneq X\subsetneq V(H)$. Then the WL-dimension
of $(H,X)$ is at least $\mathsf{ew}(H,X)$.

In order to prove Theorem 22, we will find graphs $G$ and $G^{\prime}$ such
that $G\cong_{k-1}G^{\prime}$, where $k=\mathsf{ew}(H,X)$, and
$|\mathrm{Ans}((H,X),G)|\neq|\mathrm{Ans}((H,X),G^{\prime})|$. As explained in
the introduction, we will rely on a recently developed version of the CFI
graphs of Cai, Fürer and Immerman [8]. The following subsection will provide a
concise and self-contained explanation of the construction and properties of
CFI graphs.

###  4.1 CFI Graphs

We start with a formal definition of a version of CFI graphs introduced by
Roberson [31].

######  Definition 23 (CFI graphs, $\chi(G,W)$).

Let $G$ be a graph and let $W$ be a subset of $V(G)$. For every vertex $w$ of
$G$, let $\delta_{w,W}=|\\{w\\}\cap W|$. The graph $\chi(G,W)$ is defined as
follows. The vertex set is $V(\chi(G,W)):=\\{(w,S)\mid w\in V(G),S\subseteq
N_{G}(w),\delta_{w,W}\equiv|S|\pmod{2}\\}$. The edge set is

$E(\chi(G,W)):=\\{\\{(w,S),(w^{\prime},S^{\prime})\\}\mid\mbox{$\\{w,w^{\prime}\\}\in
E(G)$ and $w^{\prime}\in S\Longleftrightarrow w\in S^{\prime}$}\\}.$

For any fixed $G$, the isomorphism class of $\chi(G,W)$ depends only on the
parity of $|W|$:

######  Lemma 24 (Lemma 3.2 in [31]).

Let $G$ be a connected graph and let $W,W^{\prime}\subseteq V(G)$. Then
$\chi(G,W)\cong\chi(G,W^{\prime})$ if and only if
$|W|\equiv|W^{\prime}|\pmod{2}$.

Neuen [29] established the following WL-equivalence result for
$\chi(G,\emptyset)$ and $\chi(G,\\{w\\})$.

######  Lemma 25 (Theorem 4.2, Lemma 4.4 and Theorem 5.1 in [29]).

Let $G$ be a graph of treewidth $t$ and let $w$ be a vertex of $G$. Then for
all $k<t$, $\chi(G,\emptyset)\cong_{k}\chi(G,\\{w\\})$.

###  4.2 Cloning Vertices in CFI Graphs

We will introduce some notions and properties of coloured graphs and of CFI
graphs due to Roberson [31]. First of all, since we will work with vertex
colourings induced by homomorphisms throughout this section, we adopt the
well-established notion of $H$-_colourings_ of graphs.

######  Definition 26.

We refer to a homomorphism from a graph $G$ to a graph $H$ as an
$H$-_colouring_ of $G$.

Recall that $\pi_{1}$ is the projection that maps a pair $(a,b)$ to the first
component $a$.

######  Observation 27 ([31]).

Let $F$ be a graph and let $W$ be a subset of $V(F)$. The function $\pi_{1}$
is a homomorphism from $\chi(F,W)$ to $F$.

Technically, to get the $F$-colouring of $\chi(F,W)$ in Observation 27, one
should restrict $\pi_{1}$ to the domain $V(\chi(F,W))$, but it will not be
important to capture this in our notation. The following is an extension of a
notion introduced in [31, Section 3.1] from CFI graphs to coloured graphs.

######  Definition 28.

Let $H$, $G$, and $F$ be graphs, let $c$ be a homomorphism from $G$ to $F$,
and let $\tau$ be a homomorphism from $H$ to $F$. We define
$\mathrm{Hom}_{\tau}(H,G,F,c)=\\{h\in\mathrm{Hom}(H,G)\mid
c(h(\cdot))=\tau\\}$.

${H}$${G}$${F}$

$\scriptstyle h$

$\scriptstyle\tau$

$\scriptstyle c$

Figure 1: Each homomorphism $h$ from $H$ to $G$ induces a homomorphism $\tau$
from $H$ to $F$ by composing $h$ with the $F$-colouring $c$ of $G$. By
partitioning $\mathrm{Hom}(H,G)$ along the induced homomorphisms to $F$, we
obtain Observation 29.

######  Observation 29.

Let $H$, $G$, and $F$ be graphs and let $c$ be a homomorphism from $G$ to $F$.
Then

$|\mathrm{Hom}(H,G)|=\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,G,F,c)|.$

######  Theorem 30 (Theorem 3.6 in [31]).

Let $H$ be a graph, let $F$ be a connected graph, let $W\subseteq V(F)$, and
let $\tau\in\mathrm{Hom}(H,F)$. Then
$|\mathrm{Hom}_{\tau}(H,\chi(F,W),F,\pi_{1})|\leq|\mathrm{Hom}_{\tau}(H,\chi(F,\emptyset),F,\pi_{1})|$.

######  Definition 31 (Cloning Colour-Blocks).

Let $G$ be a graph, let $F$ be a connected graph, and let $c$ be a
homomorphism from $G$ to $F$. Let $k$ be a positive integer, let
$\vec{v}=(v_{1},\dots,v_{k})$ be a $k$-tuple of pairwise distinct vertices of
$F$, and let $\vec{z}=(z_{1},\dots,z_{k})$ be $k$-tuple of positive integers.
The graph $\mathcal{G}(G,F,c,\vec{v},\vec{z})$ is obtained from $G$ by
cloning, for each $i\in[k]$, the colour class of $v_{i}$ under $c$ precisely
$z_{i}-1$ times. Formally, for each $v\in V(F)$, let $B_{v}=c^{-1}(v)$. The
vertices of $\mathcal{G}(G,F,c,\vec{v},\vec{z})$ are

$\bigcup_{u\in
V(F)\setminus\vec{v}}B_{u}\cup\bigcup_{i\in[k]}(B_{v_{i}}\times\\{1,\dots,z_{i}\\}).$

The vertices contained in $\bigcup_{u\in V(F)\setminus\vec{v}}B_{u}$ are
called _primal vertices_ and the vertices contained in
$\bigcup_{i\in[k]}(B_{v_{i}}\times\\{1,\dots,z_{i}\\})$ are called _cloned
vertices_. Two vertices $x$ and $y$ of $\mathcal{G}(G,F,c,\vec{v},\vec{z})$
are adjacent if and only if

  * •

$x$ and $y$ are primal vertices, and $\\{x,y\\}\in E(G)$, or

  * •

$x$ is primal, $y$ is a clone, and $\\{x,\pi_{1}(y)\\}\in E(G)$, or

  * •

$x$ is a clone, $y$ is primal, and $\\{\pi_{1}(x),y\\}\in E(G)$, or

  * •

$x$ and $y$ are clones, and $\\{\pi_{1}(x),\pi_{1}(y)\\}\in E(G)$.

We define a function $\mathcal{C}(G,F,c,\vec{v},\vec{z})\colon
V(\mathcal{G}(G,F,c,\vec{v},\vec{z})\to V(F)$ by mapping primal vertices $u$
to $c(u)$, and cloned vertices $(u,i)$ to $c(u)$. It is easy to see that
$\mathcal{C}(G,F,c,\vec{v},\vec{z})$ is a homomorphism from
$\mathcal{G}(G,F,c,\vec{v},\vec{z})$ to $F$.

######  Lemma 32.

Let $H$ and $G$ be graphs and let $F$ be a connected graph. Let $c$ be a
homomorphism from $G$ to $F$ and let $\tau$ be a homomorphism from $H$ to $F$.
Let $\vec{v}=(v_{1},\dots,v_{k})$ be a $k$-tuple of distinct vertices of $F$
and let $\vec{z}=(z_{1},\dots,z_{k})$ be a $k$-tuple of positive integers. For
all $i\in[k]$, let $d_{i}$ be the number of vertices of $H$ that are mapped by
$\tau$ to $v_{i}$, i.e., $d_{i}=|\\{u\in V(H)\mid\tau(u)=v_{i}\\}|$. Let
$G^{\prime}=\mathcal{G}(G,F,c,\vec{v},\vec{z})$ and let
$c^{\prime}=\mathcal{C}(G,F,c,\vec{v},\vec{z})$. Then

$|\mathrm{Hom}_{\tau}(H,G^{\prime},F,c^{\prime})|=|\mathrm{Hom}_{\tau}(H,G,F,c)|\cdot\prod_{i=1}^{k}z_{i}^{d_{i}}.$

###### Proof.

Let $\rho\colon V(G^{\prime})\to V(G)$ be the function that maps cloned
vertices to their original counterparts, that is

$\rho(x)=\begin{cases}x&\mbox{if $x$ is a primal vertex}\\\
\pi_{1}(x)&\mbox{otherwise}\end{cases}$

Observe that $\rho$ is a homomorphism from $G^{\prime}$ to $G$. We define an
equivalence relation on the set
$\mathrm{Hom}_{\tau}(H,G^{\prime},F,c^{\prime})$ by setting $h\sim h^{\prime}$
if and only if $\rho(h(\cdot))=\rho(h^{\prime}(\cdot))$. For every
$h\in\mathrm{Hom}_{\tau}(H,G^{\prime},F,c^{\prime})$, $\rho(h(\cdot))$ is a
homomorphism from $H$ to $G$ since it is the composition of homomorphisms from
$H$ to $G^{\prime}$ and from $G^{\prime}$ to $G$. Moreover, since
$h\in\mathrm{Hom}_{\tau}(H,G^{\prime},F,c^{\prime})$,
$c^{\prime}(h(\cdot))=\tau$. From the definitions of $\rho$ and $c^{\prime}$
it is immediate that $c(\rho(\cdot))=c^{\prime}$. Thus
$c(\rho(h(\cdot))=c^{\prime}(h(\cdot))=\tau$, proving that
$\rho(h(\cdot))\in\mathrm{Hom}_{\tau}(H,G,F,c)$; consider Figure 2 for an
illustration. Consequently, we can represent each equivalence class of $\sim$
by a homomorphism $\hat{h}\in\mathrm{Hom}_{\tau}(H,G,F,C)$.

Finally, each equivalence class has size $\prod_{i=1}^{k}z_{i}^{d_{i}}$, since
for each $i\in[k]$, there are $z_{i}$ possibilities for each of the $d_{i}$
vertices $u\in V(H)$ with $\tau(u)=v_{i}$. ∎

${H}$${G^{\prime}}$${G}$${F}$

$\scriptstyle h$

$\scriptstyle\tau$

$\scriptstyle\rho$

$\scriptstyle c^{\prime}$

$\scriptstyle c$

Figure 2: Illustration for the proof of Lemma 32:
$G^{\prime}=\mathcal{G}(G,F,c,\vec{v}\,\vec{z})$ is the graph obtained from
$G$ by cloning vertices (Definition 31), and $\rho$ is the homomorphism from
$G^{\prime}$ to $G$ that maps each cloned vertex in $G^{\prime}$ to its primal
vertex in $G$. Moreover, $c$ is the $F$-colouring of $G$ and
$c^{\prime}=\mathcal{C}(G,F,c,\vec{v},vz)$ is, by Definition 31, the
composition of $c$ and $\rho$, i.e., each cloned vertex is mapped by
$c^{\prime}$ to the colour of its primal vertex.

Next we show that cloning colour-blocks in CFI graphs preserves WL-
equivalence:

######  Lemma 33.

Let $F$ be a connected graph of treewidth $t+1$, let $W\subseteq V(F)$, let
$\vec{v}=(v_{1},\dots,v_{k})$ be a $k$-tuple of distinct vertices of $F$, and
let $\vec{z}=(z_{1},\dots,z_{k})$ be a $k$-tuple of positive integers. Then
$\mathcal{G}(\chi(F,\emptyset),F,\pi_{1},\vec{v},\vec{z})\cong_{t}\mathcal{G}(\chi(F,W),F,\pi_{1},\vec{v},\vec{z})$.

###### Proof.

Let $G_{\emptyset}=\mathcal{G}(\chi(F,\emptyset),F,\pi_{1},\vec{v},\vec{z})$
and $G_{W}=\mathcal{G}(\chi(F,W),F,\pi_{1},\vec{v},\vec{z})$. The lemma will
follow immediately by Definition of WL-equivalence (Definition 18) once we
show that, for each graph $H$ of treewidth at most $t$,
$|\mathrm{Hom}(H,G_{\emptyset})|=|\mathrm{Hom}(H,G_{W})|$. To this end, fix
any graph $H$ with treewidth at most $t$. By Lemma 25,
$\chi(F,\emptyset)\cong_{t}\chi(F,W)$ since $F$ has treewidth $t+1$. Again, by
Definition 18, we have
$|\mathrm{Hom}(H,\chi(F,\emptyset))|=|\mathrm{Hom}(H,\chi(F,W))|$. By
Observation 27, $\pi_{1}$ is a homomorphism from $\chi(F,\emptyset)$ to $F$
and from $\chi(F,W)$ to $F$. By Observation 29,

$\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,\chi(F,\emptyset),F,\pi_{1})|=\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,\chi(F,W),F,\pi_{1}).$

Combining this with Theorem 30, we find that for all
$\tau\in\mathrm{Hom}(H,F)$,

$|\mathrm{Hom}_{\tau}(H,\chi(F,\emptyset),F,\pi_{1}))|=|\mathrm{Hom}_{\tau}(H,\chi(F,W),F,\pi_{1})|.$
(1)

Therefore

$\displaystyle|\mathrm{Hom}(H,G_{\emptyset})|$
$\displaystyle=\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,G_{\emptyset},F,\pi_{1})|$
(Observation 29)
$\displaystyle=\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,\chi(F,\emptyset),F,\pi_{1})|\cdot\prod_{i=1}^{k}z_{i}^{d_{i}}$
(Lemma 32)
$\displaystyle=\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,\chi(F,W),F,\pi_{1})|\cdot\prod_{i=1}^{k}z_{i}^{d_{i}}$
(Equation (1))
$\displaystyle=\sum_{\tau\in\mathrm{Hom}(H,F)}|\mathrm{Hom}_{\tau}(H,G_{W},F,\pi_{1})|$
(Lemma 32) $\displaystyle=|\mathrm{Hom}(H,G_{W})|,$ (Observation 29)

where the quantities $d_{1},\ldots,d_{k}$ depend on $\tau$ as in Lemma 32.
This concludes the proof. ∎

###  4.3 Reduction to the Colourful Case

Throughout this section, we fix a conjunctive query $(H,X)$ such that $H$ is
connected, and with $X=\\{x_{1},\dots,x_{k}\\}$. Fix also a positive integer
$\ell$. Let $Y=V(H)\setminus X$ and $F=F_{\ell}(H,X)$.

Recall that the vertices of $F$ are $X\cup(Y\times[\ell])$. We start by
extending the partitioning result from Section 4.2 from graphs to conjunctive
queries. Moreover, recall the definition of the mapping $\gamma\colon V(F)\to
V(H)$ (Definition 13):

$\gamma(u)=\begin{cases}u&u\in X\\\ \pi_{1}(u)&u\in Y\times[\ell]\end{cases}$

Recall also that by Observation 14, the function $\gamma$ is a homomorphism
from $F$ to $H$.

######  Definition 34.

Let $G$ be a graph, let $c$ be an $H$-colouring of $G$, and let $\tau$ be a
function from $X$ to $V(H)$. Define

$\mathrm{Ans}^{\tau}((H,X),(G,c))=\\{h\in\mathrm{Ans}((H,X),G)\mid
c(h(\cdot))=\tau(\cdot)\\}\\}$

Let $\hat{c}$ be an $F$-colouring of $G$. Define

$\mathrm{Ans}^{\tau}((H,X),(G,\hat{c}))=\\{h\in\mathrm{Ans}((H,X),G)\mid\gamma(\hat{c}(h(\cdot))=\tau(\cdot)\\}\\}$

${V(F)}$${V(H)}$${X}$${V(G)}$

$\scriptstyle\gamma$

$\scriptstyle h$

$\scriptstyle\tau$

$\scriptstyle\hat{c}$

$\scriptstyle c$

Figure 3: Illustrations of the mappings used in Definition 34.

######  Observation 35.

Let $(G,c)$ be an $H$-coloured graph. Then

$|\mathrm{Ans}((H,X),G)|=\sum_{\tau:X\to
V(H)}|\mathrm{Ans}^{\tau}((H,X),(G,c))|.$

We will adapt Lemma 32 to existential conjunctive queries in the following
way.

######  Lemma 36.

Let $G$ be a graph and let $c$ be an $F$-colouring of $G$, and assume that $F$
is connected. Let $\tau\colon X\to V(H)$. Let $\vec{v}=(x_{1},\ldots,x_{k})$.
Let $\vec{z}=(z_{1},\dots,z_{k})$ be a $k$-tuple of positive integers. For all
$i\in[k]$ let $d_{i}$ be the number of vertices of $H$ that are mapped by
$\tau$ to $x_{i}$, i.e., $d_{i}:=|\\{u\in X\mid\tau(u)=x_{i}\\}|$. Let
$G^{\prime}=\mathcal{G}(G,F,c,\vec{v},\vec{z})$ and
$c^{\prime}=\mathcal{C}(G,F,c,\vec{v},\vec{z})$. Then

$|\mathrm{Ans}^{\tau}((H,X),(G^{\prime},c^{\prime})|=|\mathrm{Ans}^{\tau}((H,X),(G,c))|\cdot\prod_{i=1}^{k}z_{i}^{d_{i}}.$

###### Proof.

We encourage the reader to consider Figure 4 for keeping track of the mappings
and homomorphisms used in the proof. Let $\rho\colon V(G^{\prime})\to V(G)$ be
the function that maps cloned vertices to their original counterparts, that is

$\rho(w)=\begin{cases}w&\mbox{if $w\in Y$ }\\\
\pi_{1}(w)&\mbox{otherwise}\end{cases}$

Observe that $\rho$ is a homomorphism from $G^{\prime}$ to $G$. We define an
equivalence relation on the set
$\mathrm{Ans}^{\tau}((H,X),(G^{\prime},c^{\prime}))$ by setting $h\sim
h^{\prime}$ if and only if $\rho(h(\cdot))=\rho(h^{\prime}(\cdot))$. For every
$h\in\mathrm{Ans}^{\tau}((H,X),(G^{\prime},c^{\prime}))$, we have
$\rho(h(\cdot))\in\mathrm{Ans}((H,X),G)$.

Moreover, since $h\in\mathrm{Ans}^{\tau}((H,X),(G^{\prime},c^{\prime}))$,
$\gamma(c^{\prime}(h(\cdot)))=\tau$. From the definitions of $\rho$ and
$c^{\prime}$ it is immediate that
$\gamma(c(\rho(\cdot)))=\gamma(c^{\prime}(\cdot))$. Thus
$\gamma(c(\rho(h(\cdot)))=\gamma(c^{\prime}(h(\cdot)))=\tau$, proving that
$\rho(h(\cdot))\in\mathrm{Ans}^{\tau}((H,X),(G,c))$. Consequently, we can
represent each equivalence class of $\sim$ by a homomorphism
$\hat{h}\in\mathrm{Ans}^{\tau}((H,X),(G,c))$.

Finally, each equivalence class has size $\prod_{i=1}^{k}z_{i}^{d_{i}}$, since
for each $i\in[k]$, there are $z_{i}$ possibilities for each of the $d_{i}$
vertices $u\in V(H)$ with $\tau(u)=v_{i}$. ∎

${X}$ ${V(H)}$ ${V(F)}$${V(G)}$ ${V(G^{\prime})}$

$\scriptstyle\hat{h}$

$\scriptstyle h$

$\scriptstyle\tau$

$\scriptstyle\gamma$

$\scriptstyle c$

$\scriptstyle c^{\prime}$

$\scriptstyle\rho$

Figure 4: Overview of the mappings and homomorphisms used in the proof of
Lemma 36.

Lemma 38 is the main technical lemma in this section, which is concerned with
$\chi(F,\emptyset)$ and $\chi(F,\\{x_{1}\\})$. Recall that the projection
$\pi_{1}$ is an $F$-colouring of $\chi(F,\emptyset)$ and
$\chi(F,\\{x_{1}\\})$. Moreover $\gamma$ is a homomorphism from $F$ to $H$.
Thus:

######  Observation 37.

$\gamma(\pi_{1}(\cdot))$ is an $H$-colouring of both $\chi(F,\emptyset)$ and
$\chi(F,\\{x_{1}\\})$.

Recall that $\mathsf{Bij}(X)$ is the set of all bijections from $X$ to $X$.

######  Lemma 38.

Let $c=\gamma(\pi_{1}(\cdot))$. Let $\vec{v}=(x_{1},\ldots,x_{k})$. Suppose
that

$\sum_{\tau\in\mathsf{Bij}(X)}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|\neq
0.$

Then there is a $k$-tuple $\vec{z}=(z_{1},\dots,z_{k})$ of positive integers
such that

$|\mathrm{Ans}((H,X),\mathcal{G}(\chi(F,\emptyset),F,c,\vec{v},\vec{z}))|\neq|\mathrm{Ans}((H,X),\mathcal{G}(\chi(F,\\{x_{1}\\}),F,c,\vec{v},\vec{z}))|.$

###### Proof.

Let $G_{0}=\mathcal{G}(\chi(F,\emptyset),c,\vec{v},\vec{z}))$,
$c_{0}=\mathcal{C}(\chi(F,\emptyset),F,c,\vec{v},\vec{z}))$,
$G_{1}=\mathcal{G}(\chi(F,\\{x_{1}\\}),F,c,\vec{v},\vec{z}))$, and
$c_{1}=\mathcal{C}(\chi(F,\\{x_{1}\\}),F,c,\vec{v},\vec{z}))$,

Suppose for contradiction that, for every $k$-tuple $\vec{z}$ of positive
integers, $|\mathrm{Ans}((H,X),G_{0})|=|\mathrm{Ans}((H,X),G_{1})|$. By
Observation 35

$\sum_{\tau\colon X\to
V(H)}\Big{(}|\mathrm{Ans}^{\tau}((H,X),(G_{0},c_{0}))|-|\mathrm{Ans}^{\tau}((H,X),(G_{1},c_{1}))\Big{)}|=0.$

Let $d^{\tau}_{i}:=|\\{u\in X\mid\tau(u)=x_{i}\\}|$. Applying Lemma 36,

$\displaystyle\sum_{\tau\colon X\to
V(H)}\Big{(}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|\Big{)}\prod_{i=1}^{k}z_{i}^{d^{\tau}_{i}}=0.$
(2)

Define
$b_{\tau}:=|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|$.
Then, treating the $z_{i}$ as variables, we can define a $k$-variate
polynomial

$\displaystyle P(z_{1},\dots,z_{k}):=\sum_{\tau:X\to
V(H)}b_{\tau}\cdot\prod_{i=1}^{k}z_{i}^{d^{\tau}_{i}}\,.$

By (2), $P(z_{1},\dots,z_{k})=0$ for all $k$-tuples of positive integers
$(z_{1},\dots,z_{k})$. We wish to apply polynomial interpolation, which
requires us to collect coefficients for all monomials: To this end, observe
first that all $d^{\tau}_{i}$ are bounded from above by $k$ since $|X|=k$. Let
$\mathcal{A}_{k}$ be the set of all $k$-tuples of integers
$(a_{1},\dots,a_{k})$ with $0\leq a_{i}\leq k$ for each $i\in[k]$. Given a
$k$-tuple $\vec{a}\in\mathcal{A}_{k}$, we write $\mathsf{coeff}(\vec{a})$ for
the coefficient of the monomial $\prod_{i=1}^{k}z_{i}^{a_{i}}$, that is,

$\displaystyle
P(z_{1},\dots,z_{k})=\sum_{\vec{a}\in\mathcal{A}_{k}}\mathsf{coeff}(\vec{a})\cdot\prod_{i=1}^{k}z_{i}^{a_{i}}\,.$

By (2), $P(z_{1},\dots,z_{k})=0$ for all $k$-tuples of positive integers
$(z_{1},\dots,z_{k})$. By multivariate polynomial interpolation, only the
constant $0$ polynomial can satisfy this conditions. Concretely, we obtain
$\mathsf{coeff}(1,1,\dots,1)=0$. This yields the desired result since
$\mathsf{Bij}(X)$ is the set of functions $\tau\colon X\to V(H)$ with
$d^{\tau}_{i}=1$ for all $i\in[k]$. Thus,

$\sum_{\tau\in\mathsf{Bij}(X)}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|\\\
=\mathsf{coeff}(1,1,\dots,1)=0,$

contradicting the assumption in the statement of the lemma, and therefore
completing the proof. ∎

######  Corollary 39.

Suppose that the treewidth of $F$ is $t$ and that $F$ is connected. Let
$c=\gamma(\pi_{1}(\cdot))$. Suppose that

$\sum_{\tau\in\mathsf{Bij}(X)}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|\neq
0.$

Then the WL-dimension of $(H,X)$ is at least $t$.

###### Proof.

Let $\vec{v}=(x_{1},\ldots,x_{k})$. By Lemma 33, for every $k$-tuple of
positive integers $\vec{z}$,

$\mathcal{G}(\chi(F,\emptyset),F,\pi_{1},\vec{v},\vec{z})\cong_{(t-1)}\mathcal{G}(\chi(F,\\{x_{1}\\}),F,\pi_{1},\vec{v},\vec{z}).$

From the definition of the cloning operation (Definition 31) and the fact that
$\gamma$ is the identity on $X$ (see Definition 13),
$\mathcal{G}(\chi(F,\emptyset),F,\pi_{1},\vec{v},\vec{z})=\mathcal{G}(\chi(F,\emptyset),F,c,\vec{v},\vec{z})$.
Similarly,
$\mathcal{G}(\chi(F,\\{x_{1}\\}),F,\pi_{1},\vec{v},\vec{z})=\mathcal{G}(\chi(F,\\{x_{1}\\}),F,c,\vec{v},\vec{z})$.
So for every $k$-tuple of positive integers $\vec{z}$,
$\mathcal{G}(\chi(F,\emptyset),F,c,\vec{v},\vec{z})\cong_{(t-1)}\mathcal{G}(\chi(F,\\{x_{1}\\}),F,c,\vec{v},\vec{z})$.

However, by Lemma 38, there is a $k$-tuple $\vec{z}=(z_{1},\dots,z_{k})$ of
positive integers such that

$|\mathrm{Ans}((H,X),\mathcal{G}(\chi(F,\emptyset),F,c,\vec{v},\vec{z}))|\neq|\mathrm{Ans}((H,X),\mathcal{G}(\chi(F,\\{x_{1}\\}),F,c,\vec{v},\vec{z}))|.$

This shows that the function $G\mapsto|\mathrm{Ans}((H,X),G)|$ can distinguish
$(t-1)$-WL invariant graphs and thus the WL-dimension of $(H,X)$ at least $t$.
∎

We will consider the set of partial automorphisms of a conjunctive query,
defined as follows:

######  Definition 40 ($\mathsf{Aut}(H,X)$).

$\mathsf{Aut}(H,X):=\\{\tau:X\to X\mid\exists
a\in\mathsf{Aut}(H):a|_{X}=\tau\\}$.

Note that a mapping $\tau:X\to X$ can only be extended to an automorphism of
$H$ if it is bijective. Thus:

######  Observation 41.

$\mathsf{Aut}(H,X)\subseteq\mathsf{Bij}(X)$

The following result will be very useful for the remainder of this section; it
can be found in Corollary 54.4 in the full version [16] of [15].

######  Lemma 42 ([16, 15]).

Let $h$ be a homomosphism from $H$ to $H$ that surjectively maps $X$ onto $X$.
If $(H,X)$ is counting minimal then $h$ is an automorphism of $H$.

######  Lemma 43.

Let $G$ be a graph, let $c$ be a homomorphism from $G$ to $H$, and let
$\tau\in\mathsf{Bij}(X)\setminus\mathsf{Aut}(H,X)$. If $(H,X)$ is counting
minimal, then $|\mathrm{Ans}^{\tau}((H,X),(G,c))|=0$.

###### Proof.

Assume for contradiction that there is a homomorphism
$h\in\mathrm{Ans}^{\tau}((H,X),(G,c))$. Then there is
$\varphi\in\mathrm{Hom}(H,G)$ with $\varphi|_{X}=h$. Moreover,
$c(h(\cdot))=\tau(\cdot)$. Thus $c(\varphi(\cdot))$ is a homomorphism from $H$
to $H$ such that, for all $x\in X$, $c(\varphi(x))=\tau(x)$. Since
$\tau\in\mathsf{Bij}(X)$, $c(\varphi(\cdot))$ maps $X$ surjectively to itself.
By Lemma 42, $c(\varphi(\cdot))$ is an automorphism of $H$, and thus
$\tau\in\mathsf{Aut}(H,X)$, contradicting the assumption in the statement of
the lemma that $\tau\notin\mathsf{Aut}(H,X)$. ∎

######  Lemma 44.

Let $G$ be a graph, let $c$ be a homomorphism from $G$ to $H$, and let
$\tau\in\mathsf{Aut}(H,X)$. Then
$|\mathrm{Ans}^{\tau}((H,X),(G,c))|=|\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))|$.

###### Proof.

We will construct a bijection between $\mathrm{Ans}^{\tau}((H,X),(G,c))$ and
$\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$.

Since $\tau\in\mathsf{Aut}(H,X)$ there is an automorphism $a$ of $H$ such that
$a|_{X}=\tau$. Let $a^{-1}$ be the inverse of $a$ in the group
$\mathsf{Aut}(H)$ and observe that $\tau^{-1}=a^{-1}|_{X}$.

We first show that, for every function $h\in\mathrm{Ans}^{\tau}((H,X),(G,c))$,
the function $h(\tau^{-1}(\cdot))$ is in
$\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$. To see this, consider
$h\in\mathrm{Ans}^{\tau}((H,X),(G,c))$. From the definition of
$\mathrm{Ans}^{\tau}((H,X),(G,c))$, there is a homomorphism
$\varphi\in\mathrm{Hom}(H,G)$ with $\varphi|_{X}=h$ and that
$c(h(\cdot))=\tau$. Since $a^{-1}$ is an automorphism of $H$,
$\varphi(a^{-1}(\cdot))\in\mathrm{Hom}(H,G)$. Also, for every $x\in X$,
$\varphi(a^{-1}(x))=\varphi(\tau^{-1}(x))$. Since $\tau^{-1}(x)\in X$ and
$\varphi|_{X}=h$, $\varphi(\tau^{-1}(x))=h(\tau^{-1}(x))$. Putting these
equalities together, $\varphi(a^{-1}(x))=h(\tau^{-1}(x))$. Thus
$h(\tau^{-1}(\cdot))\in\mathrm{Ans}((H,X),G)$. Finally, since
$h\in\mathrm{Ans}^{\tau}((H,X),(G,c))$,
$c(h(\tau^{-1}(\cdot)))=\tau(\tau^{-1}(\cdot))=\mathsf{id}(\cdot)$ so
$h(\tau^{-1}(\cdot))\in\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$, as required.

Let $b$ be the function that maps every $h\in\mathrm{Ans}^{\tau}((H,X),(G,c))$
to the function $b(h):=h(\tau^{-1}(\cdot))$. We have shown that $b$ is a map
from $\mathrm{Ans}^{\tau}((H,X),(G,c))$ to
$\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$. By a symmetric argument, the
function $\hat{b}$ that maps every
$h\in\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$ to $\hat{b}(h):=h(\tau(\cdot))$
is a map from $\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$ to
$\mathrm{Ans}^{\tau}((H,X),(G,c))$.

Since $b(\hat{b}(\cdot))=\mathsf{id}$ and $\hat{b}(b(\cdot))=\mathsf{id}$, $b$
and $\hat{b}$ are bijections, completing the proof. ∎

Corollary 45 is the main tool that we will use to lower bound the WL-dimension
of conjunctive queries.

######  Corollary 45.

Suppose that $\mathsf{tw}(F)=t>1$, that $F$ is connected, and that $(H,X)$ is
counting minimal. Let $c=\gamma(\pi_{1}(\cdot))$. Suppose that
$|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\emptyset),c))|$ is not equal to
$|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\\{x_{1}\\}),c))|$. Then the WL-
dimension of $(H,X)$ is at least $t$.

###### Proof.

By Corollary 39 it suffices to establish the following.

$\sum_{\tau\in\mathsf{Bij}(X)}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|\neq
0.$

By Observation 37, $c$ is an $H$-colouring of both $\chi(F,\emptyset)$ and
$\chi(F,\\{x_{1}\\})$. Thus we can use Lemmas 43 and 44, and obtain:

$\displaystyle\leavevmode\nobreak\
\sum_{\tau\in\mathsf{Bij}(X)}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{\tau\in\mathsf{Aut}(H,X)}|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\tau}((H,X),(\chi(F,\\{x_{1}\\}),c))|$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
|\mathsf{Aut}(H,X)|\cdot\left(|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\emptyset),c))|-|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\\{x_{1}\\}),c))|\right).$

The first factor is non-zero because $\mathsf{Aut}(H,X)$ is non-empty. The
second factor is non-zero by the assumption in the statement of the corollary.
∎

###  4.4 Proving the Lower Bound

We first set up some notation, following [15].

######  Definition 46 (Colour-prescribed Homomorphisms).

Let $H$ and $G$ be graphs, let $(H,X)$ be a conjunctive query, and let $c$ be
an $H$-colouring of $G$. Define

$\displaystyle\mathsf{cpHom}(H,(G,c))$
$\displaystyle=\\{h\in\mathrm{Hom}(H,G)\mid\forall v\in
V(H),c(h(v))=v\\},\mbox{and}$ $\displaystyle\mathsf{cpAns}((H,X),(G,c))$
$\displaystyle=\\{a\colon X\to V(G)\mid\mbox{ $\exists
h\in\mathsf{cpHom}(H,(G,c))$ such that $h|_{X}=a$ }\\}.$

Homomorphisms in $\mathsf{cpHom}(H,(G,c))$ are said to be “colour-prescribed”
with respect to $c$.

######  Observation 47.

$\mathsf{cpAns}((H,X),(G,c))\subseteq\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$

Observation 47 follows directly from the definitions. Recall that
$\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))=\\{h\in\mathrm{Ans}((H,X),G)\mid\forall
v\in X,c(h(v))=v\\}\\}$. So $c(h(v))=v$ is required for all $v\in X$ in the
definition of $\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$, while for all $v\in
V(H)$ in the definition of $\mathsf{cpAns}((H,X),(G,c))$. Lemma 48 shows
equivalence for counting minimal conjunctive queries.

######  Lemma 48.

Let $(H,X)$ be a counting minimal conjunctive query, let $G$ be a graph, and
let $c$ be an $H$-colouring of $G$. Then
$\mathsf{cpAns}((H,X),(G,c))=\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$.

###### Proof.

Observation 47 proves one direction. For the other direction, consider a map
$a\in\mathrm{Ans}^{\mathsf{id}}((H,X),(G,c))$. From the definition, there is a
homomorphism $h\in\mathrm{Hom}(H,G)$ such that $h|_{X}=a$ and $c(a(x))=x$ for
all $x\in X$. From the definitions of $c$ and $h$, the function
$\varphi:=c(h(\cdot))$ is a homomorphism from $H$ to itself. Since $\varphi$
maps $X$ to $X$ and $(H,X)$ is counting minimal, Lemma 42 guarantees that
$\varphi$ is an automorphism of $H$. Let $h^{\prime}=h(\varphi^{-1}(\cdot))$.
Clearly, $h^{\prime}\in\mathrm{Hom}(H,G)$. Moreover, for each $v\in V(H)$,
$c(h^{\prime}(v))=c(h(\varphi^{-1}(v)))=\varphi(\varphi^{-1})(v)=v$. Thus
$h^{\prime}\in\mathsf{cpHom}(H,(G,c))$. Since $\varphi$ is the identity on
$X$, the same is true of $\varphi^{-1}$. Thus, for all $x\in X$,
$h^{\prime}(x)=h(\varphi^{-1}(x))=h(x)=a(x)$, implying that
$a\in\mathsf{cpAns}((H,X),(G,c))$. ∎

The following definition will be useful; it will provide a parity condition
which is both sufficient and necessary for containment in the relevant set of
answers.

######  Definition 49 (Extendable Assignments, $\mathcal{E}(X,F,W)$).

Let $(H,X)$ be a conjunctive query with $\emptyset\subsetneq
X=\\{x_{1},\ldots,x_{k}\\}\subsetneq V(H)$ and suppose that $x_{1}$ is
adjacent to at least one vertex in $Y=V(H)\setminus X$. Suppose that $H$ is
connected and let $\ell$ be an odd positive integer. Let $F=F_{\ell}(H,X)$ and
let $c=\gamma(\pi_{1}(\cdot))$. Let $C_{1},\dots,C_{m}$ be the connected
components of $H[Y]$. For each $i\in[m]$, denote the vertex sets of the $\ell$
copies of $C_{i}$ in $F$ by $V_{i}^{1},\dots,V_{i}^{\ell}$. Let $W$ be a
subset of $X$ and let $\varphi$ be an assignment from $X$ to $V(\chi(F,W))$
such that, for all $p\in[k]$, $c(\varphi(x_{p}))=x_{p}$. Define
$S_{1},\ldots,S_{k}$ such that $\varphi(x_{p})=(x_{p},S_{p})$ for all
$p\in[k]$. We say that $\varphi$ is _extendable_ if the following two
conditions hold.

  * (E1)

For every $\\{x_{a},x_{b}\\}\in E(H[X])$, $x_{a}\in S_{b}\Longleftrightarrow
x_{b}\in S_{a}$.

  * (E2)

For every $i\in[m]$ there is a $j\in[\ell]$ such that
$\sum_{p=1}^{k}|S_{p}\cap V_{i}^{j}|$ is even.

Define $\mathcal{E}(X,F,W):=\\{\varphi:X\to\chi(F,W)\mid\mbox{ $\varphi$ is
extendable and $\forall x\in X$, $c(\varphi(x))=x$}\\}$.

We will prove Lemmas 50, 51 and 52 in Section 4.4.1.

######  Lemma 50.

Let $(H,X)$ be a conjunctive query with $\emptyset\subsetneq X\subsetneq V(H)$
and suppose that $x_{1}$ is adjacent to at least one vertex in $V(H)\setminus
X$. Suppose that $H$ is connected and let $\ell$ be an odd positive integer.
Let $F=F_{\ell}(H,X)$ and let $c=\gamma(\pi_{1}(\cdot))$. Then
$|\mathcal{E}(X,F,\emptyset)|>|\mathcal{E}(X,F,\\{x_{1}\\})|$.

######  Lemma 51.

Let $(H,X)$ be a conjunctive query with $\emptyset\subsetneq
X=\\{x_{1},\ldots,x_{k}\\}\subsetneq V(H)$ and suppose that $x_{1}$ is
adjacent to at least one vertex in $V(H)\setminus X$. Suppose that $H$ is
connected and let $\ell$ be an odd positive integer. Let $F=F_{\ell}(H,X)$ and
let $c=\gamma(\pi_{1}(\cdot))$. Let $W$ be a subset of $X$ and let $\varphi$
be an assignment from $X$ to $V(\chi(F,W))$ such that, for all $p\in[k]$,
$c(\varphi(x_{p}))=x_{p}$. If $\varphi$ is not extendable, then
$\varphi\notin\mathsf{cpAns}((H,X),(\chi(F,W),c))$.

######  Lemma 52.

Let $(H,X)$ be a conjunctive query with $\emptyset\subsetneq
X=\\{x_{1},\ldots,x_{k}\\}\subsetneq V(H)$ and suppose that $x_{1}$ is
adjacent to at least one vertex in $V(H)\setminus X$. Suppose that $H$ is
connected and let $\ell$ be an odd positive integer. Let $F=F_{\ell}(H,X)$ and
let $c=\gamma(\pi_{1}(\cdot))$. Let $W$ be a subset of $X$ and let $\varphi$
be an assignment from $X$ to $V(\chi(F,W))$ such that, for all $p\in[k]$,
$c(\varphi(x_{p}))=x_{p}$. If $\varphi$ is extendable, then
$\varphi\in\mathsf{cpAns}((H,X),(\chi(F,W),c))$

######  Lemma 53.

Let $(H,X)$ be a conjunctive query with $\emptyset\subsetneq X\subsetneq V(H)$
and suppose that $x_{1}$ is adjacent to at least one vertex in $V(H)\setminus
X$. Suppose that $H$ is connected and let $\ell$ be an odd positive integer.
Let $F=F_{\ell}(H,X)$ and let $c=\gamma(\pi_{1}(\cdot))$. Let $W$ be a subset
of $X$. Then $\mathsf{cpAns}((H,X),(\chi(F,W),c))=\mathcal{E}(X,F,W)$.

###### Proof.

Let $\varphi$ be an assignment from $X$ to $V(\chi(F,W))$. If there is an
$x\in X$ such that $c(\varphi(x))\neq x$ then
$\varphi\notin\mathcal{E}(X,F,W)$ and
$\varphi\notin\mathsf{cpAns}((H,X),(\chi(F,W),c))$. Otherwise, if $\varphi$ is
not extendable then it not in $\mathcal{E}(X,F,W)$ by definition and it is not
in $\mathsf{cpAns}((H,X),(\chi(F,W),c))$ by Lemma 51. If $\varphi$ is
extendable then it is in $\mathcal{E}(X,F,W)$ by definition, Also, by Lemma
52, $\varphi$ is in $\mathsf{cpAns}((H,X),(\chi(F,W),c))$. ∎

######  Lemma 54.

Let $(H,X)$ be a conjunctive query with $\emptyset\subsetneq X\subsetneq V(H)$
and suppose that $x_{1}$ is adjacent to at least one vertex in $V(H)\setminus
X$. Suppose that $H$ is connected and let $\ell$ be an odd positive integer.
Let $F=F_{\ell}(H,X)$ and let $c=\gamma(\pi_{1}(\cdot))$. Then
$|\mathsf{cpAns}((H,X),(\chi(F,\emptyset),c))|>|\mathsf{cpAns}((H,X),(\chi(F,\\{x_{1}\\}),c))|$.

###### Proof.

The lemma follows immediately from Lemmas 50 and 53. ∎

We can now state and prove Lemma 55, the main goal of this subsection, which
will enable us to immediately infer Theorem 22.

######  Lemma 55.

Let $(H,X)$ be a counting minimal conjunctive query such that $H$ is
connected, and $\emptyset\subsetneq X\subsetneq V(H)$. Without loss of
generality, suppose that $x_{1}$ is adjacent to at least one vertex in
$V(H)\setminus X$. Let $\ell$ be an odd positive integer. Let
$F=F_{\ell}(H,X)$ and let $c=\gamma(\pi_{1}(\cdot))$. Then

$|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\emptyset),c))|>|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\\{x_{1}\\}),c))|$

###### Proof.

The lemma follows directly from Lemma 48 and lemma 54. ∎

We can now prove Theorem 22. See 22

###### Proof.

By Corollary 17,
$\mathsf{ew}(H,X)=\max\\{\mathsf{tw}(F_{\ell}(H,X))\mid\ell>0\\}$. Choose
$\ell$ large enough such that $\mathsf{ew}(H,X)=\mathsf{tw}(F_{\ell}(H,X))$.
We can assume, without loss of generality, that $\ell$ is odd: If $\ell$ is
even, choose $\ell+1$ instead and note that
$\mathsf{tw}(F_{\ell+1}(H,X))\geq\mathsf{tw}(F_{\ell}(H,X))$ since
$F_{\ell}(H,X)$ is a subgraph of $F_{\ell+1}(H,X)$ and since treewidth is
monotone under taking subgraphs.

Let $F=F_{\ell}(H,X)$ (note that $F$ is connected as $(H,X)$ is connected) and
let $c=\gamma(\pi_{1}(\cdot))$. By Corollary 45, it suffices to show that
$|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\emptyset),c))|$ is not equal to
$|\mathrm{Ans}^{\mathsf{id}}((H,X),(\chi(F,\\{x_{1}\\}),c))|$, which holds by
Lemma 55. This concludes the proof. ∎

####  4.4.1 Proofs of Lemmas 50, 51 and 52

This section will use the following combinatorial lemma, Lemma 56, which seems
to be folklore.

######  Lemma 56.

Let $G$ be a connected graph and let $S\subseteq V(G)$ be a vertex-subset of
even cardinality. Then there is an assignment $\beta:E(G)\to\\{0,1\\}$ such
that, for all $v\in V(G)$,

$\sum_{u\in N(v)}\beta(\\{u,v\\})\equiv\begin{cases}1\mod 2&\mbox{if $v\in
S$,}\\\ 0\mod 2&\mbox{if $v\notin S$.}\end{cases}$ (3)

###### Proof.

The proof is by induction on $n=|V(G)|$. If $n=1$, then $E(G)=\emptyset$ so
necessarily $S=\emptyset$. By convention, the (empty) sum is $0$ which is as
desired since $v\notin S$.

Assume for the induction hypothesis that the claim holds for $n$ and let
$G=(V,E)$ be a graph with $n+1$ vertices. Let $v$ be a vertex of $G$ such that
$G^{\prime}:=G\setminus\\{v\\}$ is connected. Let $v_{1},\dots,v_{d}$ be the
neighbours of $v$. Note that $d>0$ since $G$ is connected. We consider two
cases.

Case 1. If $v\in S$: Set $\beta^{\ast}(\\{v,v_{1}\\})=1$ and
$\beta^{\ast}(\\{v,v_{i}\\})=0$ for all $1<i\leq d$. Set
$S^{\prime}=(S\setminus v)\oplus v_{1}$. Note that $S^{\prime}$ has even
cardinality, since $S\setminus v$ has odd cardinality. We can thus apply the
induction hypothesis to $G^{\prime}$ and $S^{\prime}$ and obtain a function
$\beta^{\prime}:E(G^{\prime})\to\\{0,1\\}$ that satisfies (3) for
$G^{\prime}$. It is easy to see that $\beta^{\ast}\cup\beta^{\prime}$
satisfies (3) for $G$.

Case 2. If $v\notin S$: Set $\beta^{\ast}(\\{v,v_{i}\\})=0$ for all $i\in[d]$.
We apply the induction hypothesis to $G^{\prime}$ and $S$ and obtain a
function $\beta^{\prime}:E(G^{\prime})\to\\{0,1\\}$ that satisfies (3) in
$G^{\prime}$. It is easy to see that $\beta^{\ast}\cup\beta^{\prime}$
satisfies (3) in $G$.

∎

We finish by proving Lemmas 51, 52 and 50.

###### Proof of Lemma 51.

Let $Y=V(H)\setminus X$. Let $G=\chi(F,W)$. For all $p\in[k]$, $i\in[m]$ and
$j\in[\ell]$, define $S_{p}$, $C_{i}$, and $V_{i}^{j}$ as in Definition 49. If
(E1) is not satisfied, then $\varphi$ cannot be extended to a homomorphism
from $H$ to $G$. If (E2) is not satisfied then there is an $i\in[m]$ such
that, for all $j\in[\ell]$, $\sum_{p=1}^{k}|S_{p}\cap V_{i}^{j}|$ is odd. Fix
this $i$. Assume for contradiction that
$\varphi\in\mathsf{cpAns}((H,X),(G,c))$. Then there is a homomorphism
$h\in\mathsf{cpHom}(H,(G,c))$ with $h|_{X}=\varphi$.

Let $y_{1},\dots,y_{t}$ be the vertices of $C_{i}$. Since
$h\in\mathsf{cpHom}(H,(G,c))$, the definition of $c$ implies that for all
$v\in V(H)$, $\gamma(\pi_{1}(h(v)))=v$. Recall that the vertices of
$F=F_{\ell}(H,X)$ are $X\cup(Y\times[\ell])$ and that the vertices of
$G=\chi(F,W)$ are pairs $(w,T)$ where $w$ is a vertex of $F$ and $T\subseteq
N(w)$. So for a vertex $v=y_{s}$ of $C_{i}$, $\gamma(\pi_{1}(h(y_{s})))=y_{s}$
implies that $h(y_{s})$ is of the form $((y_{s},j),T_{s})$ for some
$j\in[\ell]$. Moreover, since $C_{i}$ is a connected component of $H[Y]$ there
is a single $j$ such that, for all $s\in[t]$, $h(y_{s})=((y_{s},j),T_{s})$.

We next define a $t$-by-$(k+t)$ matrix $M$, indexed by vertices of $F$. The
rows of $M$ are indexed by $(y_{1},j),\dots,(y_{t},j)$, and the columns of $M$
are indexed $x_{1},\dots,x_{k},(y_{1},j),\dots,(y_{t},j)$. The entries of $M$
are defined as follows. For $s\in[t]$,

$M((y_{s},j),v)=\begin{cases}1&\mbox{if $v\in T_{s}$,}\\\ 0&\mbox{if $v\notin
T_{s}$}.\end{cases}$

From the definition of $G=\chi(F,W)$, the size of $T_{s}$ is odd if
$(y_{s},j)\in W$ and even otherwise. Since $W$ is a subset of $X$, every set
$T_{s}$ has even cardinality. Thus every row of $M$ has an even number of
$1$s, and therefore $M$ has an even number of $1$s. Let $M_{X}$ be the
submatrix of $M$ containing only the columns indexed by $x_{1},\dots,x_{k}$.
Let $M_{Y}$ be the submatrix of $M$ containing only the columns indexed by
$(y_{1},j),\dots,(y_{t},j)$.

Note that $M_{Y}$ is a square matrix. We next show that it is symmetric. If
$M((y_{s},j),(y_{s^{\prime}},j))=1$, then $(y_{s^{\prime}},j)\in T_{s}$, which
implies that $(y_{s},j)$ and $(y_{s^{\prime}},j)$ are adjacent in $F$ and thus
$y_{s}$ and $y_{s^{\prime}}$ are adjacent in $H$. Suppose for contradiction
that $M((y_{s^{\prime}},j),(y_{s},j))=0$. Then $(y_{s},j)\notin
T_{s^{\prime}}$. So $((y_{s},j),T_{s})$ and
$((y_{s^{\prime}},j),T_{s^{\prime}})$ are not adjacent in $G=\chi(F,W)$,
contradicting the fact that $h$ is a homomorphism from $H$ to $G$. Thus, our
assumption was wrong, and $M_{Y}$ is symmetric. Since the diagonal of $M_{Y}$
contains only $0$s (since $H$ and $F$ do not have self-loops), the number of
$1$s in $M_{Y}$ is even.

To finish the proof we will show that, for every $p\in[k]$, the number of $1$s
in the column of $M$ indexed by $x_{p}$ is $|S_{p}\cap V_{i}^{j}|$ so the
number of $1$s in $M_{X}$ is $\sum_{p=1}^{k}|S_{p}\cap V_{i}^{j}|$, which is
odd by the choice of $i$. Thus, $M_{X}$ has an odd number of $1$s and $M_{Y}$
has an even number of $1$s, contradicting the fact that $M$ has an even number
of $1$s. We conclude that our initial assumption for contradiction, that
$\varphi\in\mathsf{cpAns}((H,X),(G,c))$, is false, proving the lemma.

So to finish, fix $p\in[k]$. We will show that the number of $1$s in the
column of $M$ indexed by $x_{p}$ is $|S_{p}\cap V_{i}^{j}|$.

Before considering the entries of this column of $M$, we establish a fact
which we will use twice — if $x_{p}$ and $(y_{s},j)$ are adjacent in $F$ then,
from the definition of $F$, $x_{p}$ and $y_{s}$ are adjacent in $H$. Since $h$
is a homomorphism from $H$ to $G$ that extends $\varphi$, from the definition
of $S_{p}$, $h(x_{p})=\varphi(x_{p})=(x_{p},S_{p})$, so it follows that
$(x_{p},S_{p})$ is adjacent to $h(y_{s})=((y_{s},j),T_{s})$ in $G$. Using this
fact, we will show that the number of $1$s in the column of $M$ indexed by
$x_{k}$ is $|S_{p}\cap V_{i}^{j}|$.

First, consider any $s$ such that that $M((y_{s},j),x_{p})=1$. From the
definition of $M$, $x_{p}\in T_{s}$ so, from the definition of $G=\chi(F,W)$,
$x_{p}$ and $(y_{s},j)$ are adjacent in $F$. From the fact, $(x_{p},S_{p})$ is
adjacent to $((y_{s},j),T_{s})$ in $G$. From the definition of $G$,
$(y_{s},j)\in S_{p}$. By construction, $(y_{s},j)\in V_{i}^{j}$, so
$(y_{s},j)\in S_{p}\cap V_{i}^{j}$.

Finally, consider any $s$ such that that $M((y_{s},j),x_{p})=0$. From the
definition of $M$, $x_{p}\notin T_{s}$. There are two cases.

Case 1: If $x_{p}$ and $(y_{s},j)$ are not adjacent in $F$ then, from the
definition of $S_{p}$, $(y_{s},j)$ is not in $S_{p}$ so it is clearly not in
$S_{p}\cap V_{i}^{j}$.

Case 2. If $x_{p}$ and $(y_{s},j)$ are adjacent in $F$ but $x_{p}\notin T_{s}$
then from the fact $(x_{p},S_{p})$ is adjacent to $((y_{s},j),T_{s})$ in $G$.
So from the definition of $G$, $(y_{s},j)\notin S_{p}$ so it is clearly not in
$S_{p}\cap V_{i}^{j}$.

As required, we thus obtain that the number of $1$s in the column of $M$
indexed by $x_{k}$ is $|S_{p}\cap V_{i}^{j}|$.

∎

###### Proof of Lemma 52.

Let $Y=V(H)\setminus X$. Let $G=\chi(F,W)$. For all $p\in[k]$, $i\in[m]$ and
$j\in[\ell]$, define $S_{p}$, $C_{i}$, and $V_{i}^{j}$ as in Definition 49.
Condition (E1) ensures that, for every $\\{x_{a},x_{b}\\}\in E(H[X])$,
$(x_{a},S_{a})$ and $(x_{b},S_{b})$ are adjacent in $G$. By (E2), for every
$i\in[m]$ there is a $j_{i}\in[\ell]$ such that $\sum_{p=1}^{k}|S_{p}\cap
V_{i}^{j_{i}}|$ is even.

To show that $\varphi\in\mathsf{cpAns}((H,X),(G,c))$, we will construct an
$h\in\mathsf{cpHom}(H,(G,c))$ with $h|_{X}=\varphi$. To do this we will choose
a value for $h(y)$ for each $y\in Y$. For every $i\in[m]$, let
$V(C_{i}):=\\{y_{i,1},\dots,y_{i,t_{i}}\\}$ be the vertices of the connected
component $C_{i}$ of $H[Y]$. Given a vertex $y_{i,s}\in V(C_{i})$, let
$N_{i}(y_{i,s})$ denote the set of its neighbours in $C_{i}$. For every
$y_{i,s}\in V(C_{i})$, let $T_{i,s,X}=\\{x_{p}\in X\mid(y_{i,s},j_{i})\in
S_{p}\\}$.

Let $\Omega_{i}=\\{y_{i,s}\>:\>\mbox{$|T_{i,s,X}|$ is odd}\\}$. We will show
that $|\Omega_{i}|$ is even. To see this, let $M_{X}$ be a matrix with rows
indexed by $(y_{i,1},j_{i}),\ldots,(y_{i,t_{i}},j_{i})$ and columns indexed by
$X$. Define $M(y_{i,s},j_{i}),x_{p})$ to be $1$ if $x_{p}\in T_{i,s,X}$ and
$0$ otherwise. By construction, the number of $1$s in the column of $M$
indexed by $x_{p}$ is the number of vertices $(y_{i,s},j_{i})\in S_{p}$ so
this is $|S_{p}\cap V_{i}^{j_{i}}|$. By the choice of $j_{i}$, the number of
$1$s in $M_{X}$ is even. So $\Omega_{i}$, which contains the indices of rows
with an odd number of $1$s, has even cardinality. Apply Lemma 56 with graph
$C_{i}$ and $S=\Omega_{i}$ to obtain an assignment $\beta\colon
E(C_{i})\to\\{0,1\\}$ such that, for all $y_{i,s}\in\Omega_{i}$,
$\sum_{y_{i,s^{\prime}}\in
N_{i}(y_{i,s})}\beta(\\{y_{i,s^{\prime}},y_{i,s}\\})$ is odd and for all
$y_{i,s}\in V(C_{i})\setminus\Omega_{i}$, this sum is even. Finally, let
$T_{i,s,Y}=\\{(y_{i,s^{\prime}},j_{i})\mid\mbox{$y_{i,s^{\prime}}\in
N_{i}(y_{i,s})$ and $\beta(\\{y_{i,s^{\prime}},y_{i,s}\\})=1$}\\}$ and let
$T_{i,s}=T_{i,s,X}\cup T_{i,s,Y}$. We then define
$h(y_{i,s})=((y_{i,s},j_{i}),T_{i,s})$. Our goal is to show that
$h\in\mathsf{cpHom}(H,(G,c))$. For this we require

  * •

Property 1: Each $h(y_{i,s})$ is a vertex of $G$.

  * •

Property 2: For all $y_{i,s}\in Y$, $c(h(y_{i,s}))=y_{i,s}$. (This follows
immediately from the definition of $h$.)

  * •

Property 3: $h$ is a homomorphism from $H$ to $G$. That is, all three of the
following hold.

    * –

Property 3a: For every edge $\\{x_{a},x_{b}\\}$ of $E(H[X])$,
$\\{h(x_{a}),h(x_{b})\\}$ is an edge of $G$ (this follows immediately from
(E1) and the definition of $G$).

    * –

Property 3b: For every edge $\\{x_{p},y_{i,s}\\}$ of $H$ with $x_{p}\in X$ and
$y_{i,s}\in C_{i}$, $\\{h(x_{p}),h(y_{i,s})\\}$ is an edge of $G$.

    * –

Property 3c: For every edge $\\{y_{i,s},y_{i,s^{\prime}}\\}$ of $C_{i}$,
$\\{h(y_{i,s}),h(y_{i,s^{\prime}})\\}$ is an edge of $G$.

We start by showing Property 1 — that each $h(y_{i,s})$ is a vertex of $G$.
For this, we need two constraints to be satisfied as follows.

  * •

Constraint 1: Every vertex of $T_{i,s}$ must be a neighbour of
$(y_{i,s},j_{i})$ in $F$.

  * •

Constraint 2: $|T_{i,s}|$ must be even (this constraint comes from the
definition of $G$ since $y_{i,s}$ is not in $W$, which is a subset of $X$).

Constraint 1 follows directly from the definition of $T_{i,s}$. To see that
every $x_{p}\in T_{i,s,X}$ is a neighbour of $(y_{i,s},j_{i})$ note that
$(y_{i,s},j_{i})\in S_{p}$ which implies that $\\{x_{p},(y_{i,s},j_{i})\\}$ is
an edge of $F$ since $(x_{p},S_{p})$ is a vertex of $G$. It is immediate from
the definition of $T_{i,s,Y}$ and $F$ that every vertex in $T_{i,s,Y}$ is a
neighbour of $(y_{i,s},j_{i})$ in $F$.

Constraint 2 is by construction. Consider any pair $(i,s)$. If $|T_{i,s,X}|$
is even then $y_{i,s}\notin\Omega_{i}$ so $|T_{i,s,Y}|$ is even. On the other
hand, if $|T_{i,s,X}|$ is odd then $Y_{i,s}\in\Omega_{i}$, so $|T_{i,s,Y}|$ is
odd.

We next consider Property 3b. Consider an edge $\\{x_{p},y_{i,s}\\}$ of $H$
with $x_{p}\in X$ and $y_{i,s}\in C_{i}$. Then $h(x_{p})=(x_{p},S_{p})$. If
$(y_{i,s},j_{i})\in S_{p}$ then $x_{p}\in T_{i,s,X}$ so $x_{p}\in T_{i,s}$ and
$h(y_{i,s})=((y_{i,s},j_{i}),T_{i,s})$ is connected to $(x_{p},S_{p})$ in $G$
by the definitions of $F$ and $G$. Similarly, if $(y_{i,s},j_{i})\notin S_{p}$
then $x_{p}\notin T_{i,s}$ so again $((y_{i,s},j_{i}),T_{i,s})$ is connected
to $(x_{p},S_{p})$ in $G$.

To finish the proof, we establish Property 3c. Consider an edge
$\\{y_{i,s},y_{i,s^{\prime}}\\}$ of $C_{i}$. Then
$h(y_{i,s})=((y_{i,s},j_{i}),T_{i,s})$ and
$h(y_{i,s^{\prime}})=((y_{i,s^{\prime}},j_{i}),T_{i,s^{\prime}})$ By
construction, $(y_{i,s^{\prime}},j_{i})\in T_{i,s}$ iff $(y_{i,s},j_{i})\in
T_{i,s^{\prime}}$. Hence $h(y_{i,s})$ and $h(y_{i,s^{\prime}})$ are connected
in $G$. ∎

###### Proof of Lemma 50.

Let $Y=V(H)\setminus X$. For $i\in[m]$ and $j\in[\ell]$, define $C_{i}$ and
$V_{i}^{j}$ as in Definition 49. For every subset $W$ of $X$ and every map
$\varphi\colon X\to V(\chi(F,W))$ that satisfies $c(\varphi(x_{p}))=x_{p}$ for
all $p\in[k]$, let $S_{1}(\varphi),\ldots,S_{k}(\varphi)$ be the sets defined
in Definition 49. For every $\varphi\in\mathcal{E}(X,F,W)$, (E2) guarantees
that for every $i\in[m]$ there is a $j_{i}\in[\ell]$ such that
$\sum_{p=1}^{k}|S_{p}(\varphi)\cap V_{i}^{j_{i}}|$ is even. We will partition
$\mathcal{E}(X,F,W)$ into disjoint sets in terms of $i$ and $j_{i}$ as
follows. First we define $\mathcal{E}(X,F,W,1)$ by fixing $i=1$ and $j_{i}>1$.

$\mathcal{E}(X,F,W,1):=\\{\varphi\in\mathcal{E}(X,F,W)\mid\exists
j_{1}>1:\mbox{$\sum_{p=1}^{k}|S_{p}(\varphi)\cap V_{1}^{j_{1}}|$ is even}\\}.$

For all $i\in\\{2,\ldots,m\\}$, define

$\mathcal{E}(X,F,W,i):=\\{\varphi\in\mathcal{E}(X,F,W)\setminus(\cup_{q=1}^{i-1}\mathcal{E}(X,F,W,q))\mid\exists
j_{i}>1:\mbox{$\sum_{p=1}^{k}|S_{p}(\varphi)\cap V_{i}^{j_{i}}|$ is even}\\}.$

Finally, define
$\mathcal{E}(X,F,W,0):=\mathcal{E}(X,F,W)\setminus(\bigcup_{i=1}^{m}\mathcal{E}(X,F,W,i))$.

Since the sets $\mathcal{E}(X,F,W,0),\ldots,\mathcal{E}(X,F,W,m)$ are a
disjoint partition of $\mathcal{E}(X,F,W)$ for every subset $W$ of $X$, the
lemma follows immediately from the following three claims, which clearly imply
$|\mathcal{E}(X,F,\emptyset)|>|\mathcal{E}(X,F,\\{x_{1}\\}|$, as required.

Claim 1. For all $i\in[m]$,
$|\mathcal{E}(X,F,\emptyset,i)|=|\mathcal{E}(X,F,\\{x_{1}\\},i)|$.

Fix $i\in[m]$. To prove Claim 1, we construct a bijection $b$ from
$\mathcal{E}(X,F,\emptyset,i)$ to $\mathcal{E}(X,F,\\{x_{1}\\},i)$. Since $H$
is connected, there is path from $C_{i}$ to $x_{1}$ in $H$ that starts at some
vertex $y\in C_{i}$, takes an edge from $y$ to $X$ and does not re-visit
$C_{i}$ before reaching $x_{1}$. So there is a path from $(y,1)$ to $x_{1}$ in
$F$ whose vertices are in $X\cup\\{(y^{\prime},1)\mid y^{\prime}\in Y\\}$ and
is of the form $P=(y,1)x_{t_{1}}P_{1}x_{t_{2}}P_{2}x_{t_{3}}P_{3}\dots
x_{t_{s-1}}P_{s-1}x_{t_{s}}$ where $x_{t_{1}},\ldots,x_{t_{s}}$ are distinct
vertices in $X$ with $t_{s}=1$ and each $P_{j}$ is either empty or for some
$i(j)\in[m]\setminus\\{i\\}$, it is a non-empty simple path in $F$ whose
vertices are in $V_{i(j)}^{1}$. Without loss of generality, the path visits
every connected component of $H[Y]$ at most once so for any distinct $j$ and
$j^{\prime}$ such that $P_{j}$ and $P_{j^{\prime}}$ are both non-empty,
$i(j)\neq i(j^{\prime})$.

Our goal is to define the bijection $b$. For each
$\varphi\in\mathcal{E}(X,F,\emptyset,i)$ and each $p\in[k]$, we first define a
subset $S^{\prime}_{p}(\varphi)$ of vertices of $F$. Let $N_{P}(x_{p})$ be the
neighbours of $x_{p}$ in the path $P$ (if $x_{p}$ is not in the path $P$, then
$N_{P}(x_{p})=\emptyset$). Then define
$S^{\prime}_{p}(\varphi)=S_{p}(\varphi)\oplus N_{P}(x_{p})$. Finally, we
define $b(\varphi)$ to be the map which maps every $p\in[k]$ to
$(x_{p},S^{\prime}_{p}(\varphi))$.

We wish to show that $(x_{p},S^{\prime}_{p}(\varphi))$ is a vertex of
$\chi(F,\\{x_{1}\\})$. Since $(x_{p},S_{p}(\varphi))$ is a vertex of
$\chi(F,\emptyset)$, $S_{p}(\varphi)$ is a subset of $N_{F}(x_{p})$. So, by
construction, $S^{\prime}_{p}(\varphi)$ is a subset of $N_{F}(x_{p})$. Each
set $S_{p}(\varphi)$ has even cardinality. Note that $N_{P}(x_{p})$ has even
cardinality unless $p=1$, in which case it has odd cardinality. Thus,
$S^{\prime}_{p}(\varphi)$ has even cardinality unless $p=1$, in which case it
has odd cardinality.

The map $b$ is a bijection since it can be inverted using
$S_{p}(\varphi)=S_{p}^{\prime}(\varphi)\oplus N_{P}(p)$. The map $b(\varphi)$
satisfies (E1) since $\varphi$ satisfies (E1) and $x_{a}\in N_{P}(x_{b})$ iff
$x_{b}\in N_{P}(x_{a})$. The map $b(\varphi)$ It satisfies (E2) since the
definition of $\mathcal{E}(X,F,\emptyset,i)$ guarantees $j_{i}>1$ so
$S_{p}^{\prime}(\varphi)\cap V_{i}^{j_{i}}=S_{p}(\varphi)\cap V_{i}^{j_{i}}$.
It satisfies $c(\varphi(x_{p}))=x_{p}$ for all $x_{p}\in X$ by construction.
Thus, $b(\varphi)\in\mathcal{E}(X,F,\\{x_{1}\\})$. Finally, the same $j_{i}>1$
that shows $\varphi\in\mathcal{E}(X,F,\emptyset,i)$ shows that $b(\varphi)$ is
in $\mathcal{E}(X,F,\\{x_{1}\\},i)$.

Claim 2. $|\mathcal{E}(X,F,\emptyset,0)|>0$.

To prove Claim 2, we exhibit a $\varphi\in\mathcal{E}(X,F,\emptyset,0)$. Let
$Z\subseteq Y$ be a set containing exactly one vertex from each component
$C_{1},\ldots,C_{m}$ such that every vertex in $Z$ is adjacent to $X$ in $H$.
For each $z\in Z$, let $p(z)=\min\\{p\in[k]\mid(x_{p},z)\in E(H)\\}$. For each
$p\in[k]$ let $S_{p}=\\{z\in Z\mid p(z)=p\\}\times\\{2,\ldots,\ell\\}$. Since
$\ell>1$ is odd, $|S_{p}|$ is even. Let $\varphi$ be the map from $X$ to
$V(\chi(F,\emptyset))$ such that, for all $p\in[k]$,
$\varphi(x_{p})=(x_{p},S_{p})$. The map $\varphi$ satisfies (E1) since
$S_{p}\cap X=\emptyset$ for all $p\in[k]$. It satisfies (E2) for any $i\in[m]$
by taking $j=1$ since for all $p\in[k]$, $|S_{p}\cap V_{i}^{1}|=0$. It
satisfies $c(\varphi(x_{p}))=x_{p}$ for all $p\in[k]$ by construction so
$\varphi\in\mathcal{E}(X,F,\emptyset)$. To see that
$\varphi\in\mathcal{E}(X,F,\emptyset,0)$, fix any $i\in[m]$ and any
$j\in\\{2,\ldots,\ell\\}$. Let $z$ be the unique vertex in $Z\cap V(C_{i})$.
Then $(z,j)$ is the unique vertex in $S_{p(z)}\cap V_{i}^{j}$ Furthermore, for
$p^{\prime}\neq p(z)$ with $p^{\prime}\in[k]$, $S_{p^{\prime}}\cap V_{i}^{j}$
is empty. Thus, $\sum_{p=1}^{k}|S_{p}\cap V_{i}^{j}|$ is odd.

Claim 3. $|\mathcal{E}(X,F,\\{x_{1}\\},0)|=0$.

We conclude by proving Claim 3. Assume for contradiction that
$\varphi\in\mathcal{E}(X,F,\\{x_{1}\\},0)$. Let $G=\chi(F,\\{x_{1}\\})$. As in
Definition 49, define $S_{1},\ldots,S_{k}$ such that, for all $p\in[k]$,
$\varphi(x_{p})=(x_{p},S_{p})$. Since $\varphi(x_{p})$ is in $V(G)$, $|S_{1}|$
is odd and for every $p\in\\{2,\ldots,k\\}$, $|S_{p}|$ is even. We will
analyse a matrix $M$. The rows of $M$ are indexed by $x_{1},\dots,x_{k}$ and
the columns of $M$ are indexed by the vertices of $F$. For every vertex $v$ of
$F$, $M(x_{p},v)$ is defined to be $1$ if $v\in S_{p}$ and $0$ otherwise.
Since $|S_{1}|$ is odd and $|S_{2}|,\dots,|S_{k}|$ are even, the total number
of $1$s in $M$ is odd.

We split $M$ into two submatrices: $M_{X}$ consists of the columns indexed by
vertices in $X$ and $M_{Y}$ consists of the columns indexed by the remaining
vertices of $F$. For every $p\in[k]$, $x_{p}\notin S_{p}$ since
$(x_{p},S_{p})$ is a vertex of $G$ and $F$ has no self-loops. Also, $M_{X}$ is
symmetric by (E1). So the number of $1$s in $M_{X}$ is even.

Now consider $M_{Y}$. Since $\varphi\in\mathcal{E}(X,F,\\{x_{1}\\})$, (E2)
implies that for every $i\in[m]$ there is a $j\in[\ell]$ such that
$\sum_{p=1}^{k}|S_{p}\cap V_{i}^{j}|$ is even. Since
$\varphi\in\mathcal{E}(X,F,\\{x_{1}\\},0)$, for each $i\in[m]$, the following
conditions hold.

  * (C1)

$\sum_{p=1}^{k}|S_{p}\cap V_{i}^{1}|$ is even, and

  * (C2)

for all $j>1$, $\sum_{p=1}^{k}|S_{p}\cap V_{i}^{j}|$ is odd.

For each $i\in[m]$ and $j\in[\ell]$, let $M^{j}_{i}$ be the submatrix of
$M_{Y}$ containing only the columns indexed by the vertices in $V_{i}^{j}$.
Then for all $i\in[m]$, condition (C1) implies that $M_{i}^{1}$ contains an
even number of $1$s and condition (C2) implies that for all
$j\in\\{2,\ldots,\ell\\}$, $M_{i}^{j}$ contains an odd number of $1$s. Since
$\ell$ is odd, the total number of $1$s in the matrices
$M_{i}^{1},\ldots,M_{i}^{\ell}$ is even. Consequently, the total number of
$1$s in $M_{Y}$ is even, contradicting the fact that $M$ has an odd number of
$1$s and $M_{X}$ has an even number of $1$s. ∎

##  5 Main Result and Consequences

With upper and lower bounds established, we are now able to proof Theorem 1.

See 1

###### Proof.

We first consider the special case where $(H,X)$ is a _full conjunctive
queries_ , that is, no variable of $(H,X)$ is existentially quantified so
$X=V(H)$. In this case, $(H,X)$ is counting minimal, since counting
equivalence is the same as isomorphism in this case [15]. Moreover,
$\Gamma(H,X)=H$. Thus $\mathsf{sew}(H,X)=\mathsf{tw}(H)$. Since
$\mathrm{Ans}((H,X),G)=\mathrm{Hom}(H,G)$ for $X=V(H)$, counting answers to
$(H,X)$ is the same as counting homomorphisms from $H$, and the WL-dimension
of counting homomorphisms is $\mathsf{tw}(H)$ as shown by Neuen [29].

Now consider the case where $X\neq V(H)$ and let $(H^{\prime},X^{\prime})$ be
a counting minimal conjunctive query with $(H^{\prime},X^{\prime})\sim(H,X)$.
Then, $|\mathrm{Ans}((H,X),G)|=|\mathrm{Ans}((H^{\prime},X^{\prime}),G)|$ for
every graph $G$ and thus $(H,X)$ and $(H^{\prime},X^{\prime})$ have the same
WL-dimension. Furthermore, since $(H,X)$ is connected, so is
$(H^{\prime},X^{\prime})$ — see [16, Section 6]. Theorem 22 now states that
the WL-dimension of $(H^{\prime},X^{\prime})$ is equal to
$\mathsf{ew}(H^{\prime},X^{\prime})$. Finally, by definition of semantic
extension width, we have
$\mathsf{sew}(H,X)=\mathsf{ew}(H^{\prime},X^{\prime})$, concluding the proof.
∎

###  5.1 Homomorphism Indistinguishability and Conjunctive Queries

Given a class of graphs $\mathcal{F}$, two graphs $G$ and $G^{\prime}$ are
called $\mathcal{F}$_-indistinguishable_ , denoted by
$G\cong_{\mathcal{F}}G^{\prime}$ if
$|\mathrm{Hom}(F,G)|=|\mathrm{Hom}(F,G^{\prime})|$ for all $F\in\mathcal{F}$.
If $\mathcal{F}$ is the class of all graphs, then a classical result of Lovász
states that $\cong_{\mathcal{F}}$ coincides with isomorphism (see e.g. Theorem
5.29 in [25]). Recent years have seen numerous exciting results on the
structure of $\mathcal{F}$-indistinguishability, depending on the class
$\mathcal{F}$: For example, Dvorák [19], and Dell, Grohe and Rattan [14] have
shown that $\cong_{\mathcal{F}}$ coincides with $\cong_{k}$, i.e., with
$k$-WL-equivalence, if $\mathcal{F}$ is the class of all graphs of treewidth
at most $k$, and Mancinska and Roberson have shown that $\cong_{\mathcal{F}}$
coincides with what is called quantum-isomorphism if $\mathcal{F}$ is the
class of all planar graphs [26].

To state our first corollary, we extend the notion of homomorphism
indistinguishability to conjunctive queries.

######  Definition 57.

Let $\Psi$ be a class of conjunctive queries. Two graphs $G$ and $G^{\prime}$
are $\Psi$-_indistinguishable_ , denoted by $G\cong_{\Psi}G^{\prime}$, if
$|\mathrm{Ans}((H,X),G)|=|\mathrm{Ans}((H,X),G^{\prime})|$ for all queries
$(H,X)\in\Psi$.

Then, using the notion of conjunctive query indistinguishability, we obtain a
new characterisation of $k$-WL-equivalence.

######  Corollary 58 (Corollary 2, restated).

Let $k$ be a positive integer and let $\Psi_{k}$ be the set of all connected
conjunctive queries with at least one free variable and with semantic
extension width at most $k$. Then for any pair of graphs $G$ and $G^{\prime}$,
$G\cong_{k}G^{\prime}$ if and only if $G\cong_{\Psi_{k}}G^{\prime}$.

###### Proof.

For the first direction, suppose that $G\cong_{k}G^{\prime}$ and consider
$(H,X)\in\Psi_{k}$. Then $\mathsf{sew}(H,X)\leq k$ and thus the WL-dimension
of $(H,X)$ is at most $k$ by Theorem 1. Consequently,
$|\mathrm{Ans}((H,X),G)|=|\mathrm{Ans}((H,X),G^{\prime})|$. This shows that
$G\cong_{\Psi_{k}}G^{\prime}$.

For the other direction, suppose that $G\cong_{\Psi_{k}}G^{\prime}$. Recall
that $\mathsf{sew}(H,V(H))=\mathsf{tw}(H)$ for all $h$. Thus $\Psi_{k}$
contains all conjunctive queries $(H,V(H))$ with $\mathsf{tw}(H)\leq k$. Since
$\mathrm{Ans}((H,V(H)),F)=\mathrm{Hom}(H,F)$ for all $H$ and $F$,
$G\cong_{\Psi_{k}}G^{\prime}$ implies
$G\cong_{\mathcal{F}^{\prime}}G^{\prime}$ where $\mathcal{F}^{\prime}$ is the
class of all conjunctive queries $(H,V(H))$ where $H$ is a _connected_ graph
with treewidth at most $k$. Finally, we can remove the connectivity constraint
as follows: Let $F=F_{1}\cup F_{2}$ be the disjoint union of two graphs
$F_{1}$ and $F_{2}$. If $F$ has treewidth at most $k$, then both $F_{1}$ and
$F_{2}$ also have treewidth at most $k$, since treewidth is monotone under
taking subgraphs. Thus, $G\cong_{\mathcal{F}^{\prime}}G^{\prime}$ implies
$\mathrm{Hom}(F,G)=\mathrm{Hom}(F_{1},G)\cdot\mathrm{Hom}(F_{2},G)=\mathrm{Hom}(F_{1},G^{\prime})\cdot\mathrm{Hom}(F_{2},G^{\prime})=\mathrm{Hom}(F,G^{\prime})$.
Consequently $G\cong_{\mathcal{F}}G^{\prime}$ where $\mathcal{F}$ is the class
of all queries $(H,V(H))$ such that $H$ is a graph with treewidth at most $k$
and thus $G\cong_{k}G^{\prime}$. ∎

In the following corollary, we show that the treewidth of a conjunctive query
alone is insufficient for describing the WL-dimension. This is even the case
for treewidth $1$, i.e., for acyclic queries.

######  Corollary 59.

Acyclic conjunctive queries have unbounded WL-dimension, that is, there is no
$k$ such that $G\cong_{k}G^{\prime}$ if and only if
$G\cong_{\mathcal{T}}G^{\prime}$, where $\mathcal{T}$ is the class of all
acyclic conjunctive queries.

###### Proof.

The corollary follows immediately from Theorem 1 and the fact that acyclic
conjunctive queries can have arbitrary high semantic extension width. Recall
the $k$-star query $(S_{k},X_{k})$, where $X_{k}=\\{x_{1},\dots,x_{k}\\}$,
$V(S_{k})=X_{k}\cup\\{y\\}$ and $E(S_{k})=\\{\\{x_{i},y\\}\mid i\in[k]\\}$.
Clearly, $(S_{k},X_{k})$ is acyclic. Moreover, it is well-known that
$(s_{k},X_{k})$ is counting minimal (see e.g. [15]). Finally,
$\Gamma(S_{k},X_{k})$ is the $k+1$-clique, and thus
$\mathsf{sew}(S_{k},X_{k})=\mathsf{tw}(K_{k+1})=k$. ∎

Corollary 59 is in stark contrast to the quantifier-free case. The WL-
dimension of any acyclic conjunctive query $(H,V(H))$ is equal to $1$ since
this case is equivalent to counting homomorphisms from acyclic graphs [19,
14]. Given Corollary 59 one might ask how powerful indistinguishability by
acyclic conjunctive queries is: Is there any $k>1$ such that
$\mathcal{T}$-indistinguishability is at least as powerful as $k$-WL-
equivalence? We provide a negative answer.

######  Observation 60.

Let $2K_{3}$ denote the graph consisting of two disjoint triangles and let
$C_{6}$ denote the $6$-cycle. Let $(H,X)$ be a connected and acyclic
conjunctive query. Then
$|\mathrm{Ans}((H,X),2K_{3})|=|\mathrm{Ans}((H,X),C_{6}|$.

###### Proof.

For the disjoint union of two conjunctive queries
$(H_{1},X_{1})\cup(H_{2},X_{2})$ and any graph $G$,
$|\mathrm{Ans}((H_{1},X_{1})\cup(H_{2},X_{2}),G)|=|\mathrm{Ans}((H_{1},X_{1}),G)|\cdot|\mathrm{Ans}((H_{2},X_{2}),G)$.
Thus, it suffices to prove the observation for connected queries.

Let $(H,X)$ be any connected acyclic conjunctive query. If $X=\emptyset$ then
the observation is trivial since computing $G\mapsto|\mathrm{Ans}((H,X),G)|$
is equivalent to deciding whether there is a homomorphism from $H$ to $G$. As
$H$ is acyclic, we thus have
$|\mathrm{Ans}((H,X),2K_{3})|=|\mathrm{Ans}((H,X),C_{6}|=1$.

Now assume that $X\neq\emptyset$. We claim that
$|\mathrm{Ans}((H,X),2K_{3})|=|\mathrm{Ans}((H,X),C_{6}|=3\cdot 2^{|X|}$. To
prove the claim, consider $x\in X$ and first note that for any
$\sigma\in\mathrm{Ans}((H,X),2K_{3})$ and any
$\sigma^{\prime}\in\mathrm{Ans}((H,X),2K_{3})$ there are 6 choices for the
image of $x$. Since $H$ is a tree we can count the possible answers $\sigma$
and $\sigma^{\prime}$ recursively with respect to the depth of $H$ rooted at
$x$. For both $\sigma$ and $\sigma^{\prime}$, once the image of a vertex $v\in
V(H)$ is decided there are always exactly two choices for the images of each
child of $v$, both in $2K_{3}$ and $C_{6}$. The claim follows from the fact
that we only count the images of the free variables. ∎

In other words, acyclic conjunctive queries cannot even distinguish $2K_{3}$
and $C_{6}$, which are the most common examples of graphs which are not
$1$-WL-equivalent, but which are $2$-WL-equivalent.

###  5.2 WL-Dimension and the Complexity of Counting

In this section, we give a connection between WL-dimension and the
parameterised complexity of counting answers to conjunctive queries. Recall
that, given a class of conjunctive queries $\Psi$, the counting problem
$\\#\textsc{CQ}(\Psi)$ takes as input a pair consisting of a conjunctive query
$(H,X)\in\Psi$ and a graph $G$ and outputs $|\mathrm{Ans}((H,X),G)|$.

Recall that a class of conjunctive queries has _bounded_ WL-dimension if there
is a constant $B$ that upper bounds the WL-dimension of all queries in the
class. See 3

###### Proof.

Given a conjunctive query $(H,X)$, recall the definition of the graph
$\Gamma(H,X)$ from Definition 10. The _contract_ of $(H,X)$ is the induced
graph subgraph $\Gamma[X]$ (see [15, Definition 8]).

Using the notion of contract, Chen, Durand, and Mengel [18, 9] and Dell, Roth
and Wellnitz [15] have established an exhaustive complexity classification for
$\\#\textsc{CQ}(\Psi)$. For an explicit statement, Theorem 10 in [15] states
that (conditioned on $\mathrm{FPT}\neq W[1]$), $\\#\textsc{CQ}(\Psi)$ is
solvable in polynomial time if and only if both the treewidth of $\Psi$ and
the treewidth of the _contracts_ of $\Psi$ are bounded.

By Theorem 1, the WL-dimension of a connected counting minimal query with
$X\neq\emptyset$ is equal to its extension width. It remains to show that the
condition that both the treewidth of $\Psi$ and the treewidth of the contracts
of $\Psi$ are bounded is the same as the condition that $\Psi$ has bounded
extension width.

First, suppose that $\Psi$ has bounded extension width. Then for some quantity
$B$, every query $(H,X)$ in $\Psi$ has extension width at most $B$. So
$\mathsf{tw}(\Gamma(X,H))\leq B$. Since $H$ and $\Gamma[X]$ are both subgraphs
of $\Gamma(X,H)$, they both have treewidth at most $B$, as required.

For the other direction, suppose that the treewidth of every query in $\Psi$
and every contract of every query in $\Psi$ is at most $B$. Consider a query
$(H,X)\in\Psi$. Let $t_{1}\leq B$ be the treewidth of $H$ and let $t_{2}\leq
B$ be the treewidth of $\Gamma[X]$. Let $\mathcal{T}=(T,\mathcal{B})$ be an
optimal tree-decomposition of $\Gamma[X]$. Let $C_{1},\dots,C_{d}$ be the
connected components of $H[Y]$. For each $i\in[d]$ let $\delta_{i}$ be the
subset of vertices in $X$ that are adjacent to $C_{i}$ in $H$. By the
definition of $\Gamma$, each $\delta_{i}$ induces a clique in $\Gamma$, and
thus in $\Gamma[X]$. Therefore, there is a bag $B_{i}$ that contains
$\delta_{i}$ (see e.g. [4, Lemma 3]). Since the treewidth of $\Gamma[X]$ is
$t_{2}$ it follows that $|\delta_{i}|\leq t_{2}+1$.

Next, for each $i\in[d]$, let $\mathcal{T}_{i}$ be an optimal tree
decomposition of $C_{i}$ and note that the width of all $\mathcal{T}_{i}$ is
at most $t_{1}$ since all components $C_{i}$ are subgraphs of $H$. It is now
straightforward to construct a tree-decomposition of width at most
$t_{1}+t_{2}$ of $\Gamma(H,X)$. For every $i\in[d]$, we add $\delta_{i}$ to
each bag of $\mathcal{T}_{i}$. Finally, we fix an arbitrary node $v_{i}$ of
the tree $T_{i}$ of $\mathcal{T}$ and connect it to the node of $T$ with bag
$B_{i}$. Clearly (T1)-(T3) are satisfied.

∎

###  5.3 Linear Combinations of Conjunctive Queries

The study of linear combinations of homomorphism counts dates back to the work
of Lovász (see the textbook [25]). Recently, staring with the work of Chen and
Mengel [10] and of Curticapean, Dell and Marx [12], the study of these linear
combinations has re-arisen in the context of parameterised counting complexity
theory. Moreover, the works of Seppelt [33], Neuen [29], and Lanzinger and
Barceló [24] have shown that the WL-dimension of a function evaluating a
finite linear combination of homomorphism counts is equal to the maximum WL-
dimension of any term in the combination. Using Theorem 1, we establish a
similar result (Corollary 4) for linear combinations of conjunctive queries.
This gives a precise quantification of the WL-dimension of unions of
conjunctive queries and of conjunctive queries with disequalities and
negations over the free variables.

Following Lovász’s notion of a “quantum graph”[25, Chapter 6.1], we formalise
our linear combinations as follows.

######  Definition 61 (Quantum Query).

A _quantum query_ $Q$ is a formal finite linear combination of conjunctive
queries $Q=\sum_{i=1}^{\ell}c_{i}\cdot(H_{i},X_{i})$ such that, for all
$i\in[\ell]$, $c_{i}\in\mathbb{Q}\setminus\\{0\\}$ and $(H_{i},X_{i})$ is a
connected and counting minimal conjunctive query with $X_{i}\neq 0$. Moreover,
the conjunctive queries $(H_{i},X_{i})$ are pairwise non-isomorphic. We call
the queries $(H_{i},X_{i})$ the _constituents_ of $Q$. The number of answers
of $Q$ in a graph $G$ is defined as
$|\mathrm{Ans}(Q,G)|:=\sum_{i=1}^{\ell}c_{i}\cdot|\mathrm{Ans}((H_{i},X_{i}),G)|$.

Chen and Mengel [10], and Dell, Roth, and Wellnitz [15] have shown that for
every union $\varphi$ of (connected) conjunctive queries with at least one
free variable there is a quantum query $Q[\varphi]$ such that, for all graphs
$G$, the number of answers of $\varphi$ in $G$ is equal to
$|\mathrm{Ans}(Q[\varphi],G)|$. Moreover, $Q[\varphi]$ is unique up to
reordering terms (and up to isomorphim of the constituents). They have also
shown a similar result when $\varphi$ is a conjunctive query with
disequalities and negations.

######  Definition 62 (Hereditary Semantic Extension Width).

The _hereditary semantic extension width_ of a quantum query
$Q=\sum_{i=1}^{\ell}c_{i}\cdot(H_{i},X_{i})$ is
$\mathsf{hsew}(Q)=\max\\{\mathsf{sew}(H_{i},X_{i})\mid i\in[\ell]\\}$.

We define the WL-dimension of a quantum query $Q$ as the WL-dimension of the
graph parameter $G\mapsto|\mathrm{Ans}(Q,G)|$. The following lemma was shown
by Seppelt [33] in the special case of homomorphisms, i.e., the case in which
each constituent $(H_{i},X_{i})$ satisfies $X_{i}=V(H_{i})$. The proof of the
generalised version follows the same idea, combining Seppelt’s approach and
Theorem 1.

See 4

###### Proof.

Let $Q=\sum_{i=1}^{\ell}c_{i}\cdot(H_{i},X_{i})$ and $k=\mathsf{hsew}(Q)$. We
first show that the WL-dimension of $Q$ is upper bounded by $k$; this is the
easy direction. For each $i\in[\ell]$, let $k_{i}=\mathsf{sew}(H_{i},X_{i})$.
By the definition of $\mathsf{hsew}(Q)$, $k=\max_{i\in[\ell]}k_{i}$.

By Theorem 1, the WL-dimension of the function
$G\mapsto|\mathrm{Ans}(H_{i},X_{i})|$ is $k_{i}$. Let $G$ and $G^{\prime}$ be
graphs such that $G\cong_{k}G^{\prime}$ (which means that for every
$i\in[\ell]$, $G\cong_{k_{i}}G^{\prime}$). Then for every $i\in[\ell]$,
$|\mathrm{Ans}((H_{i},X_{i}),G)|=|\mathrm{Ans}((H_{i},X_{i}),G^{\prime})|$ so

$|\mathrm{Ans}(Q,G)|=\sum_{i=1}^{\ell}c_{i}\cdot|\mathrm{Ans}((H_{i},X_{i}),G)|=\sum_{i=1}^{\ell}c_{i}\cdot|\mathrm{Ans}((H_{i},X_{i}),G^{\prime})|=|\mathrm{Ans}(Q,G^{\prime})|.$

This means that the function $G\mapsto|\mathrm{Ans}(Q,G)|$ cannot distinguish
$k$-WL-equivalent graphs so the WL-dimension of $Q$ is at most $k$.

The more difficult direction is the lower bound. To this end, we will
construct graphs $F$ and $F^{\prime}$ such that $F\cong_{k-1}F^{\prime}$ and
$|\mathrm{Ans}(Q,F)|\neq|\mathrm{Ans}(Q,F^{\prime})|$. This implies that the
WL-dimension of the graph parameter $G\mapsto|\mathrm{Ans}(Q,G)|$ is greater
than $k-1$ so the WL-dimension of $Q$ is at least $k$.

Assume without loss of generality that $\mathsf{sew}(H_{1},X_{1})=k$. By
Theorem 1 the WL-dimension of $(H_{1},X_{1})$ is $k$ so $k$ is the minimum
positive integer such that counting answers from $(H_{1},X_{1})$ cannot
distinguish $k$-equivalent graphs. Thus there are graphs $G$ and $G^{\prime}$
with $G\cong_{k-1}G^{\prime}$ and
$|\mathrm{Ans}((H_{1},X_{1}),G)|\neq|\mathrm{Ans}((H_{1},X_{1}),G^{\prime})|$.

The _tensor product_ of two graphs $A$ and $B$, denoted by $A\otimes B$, has
the property that, for every graph $H$, $|\mathrm{Hom}(H,A\otimes
B)|=|\mathrm{Hom}(H,A)|\cdot|\mathrm{Hom}(H,B)|$. See, for example, [25,
Chapters 3.3 and 5.2.3]. For each graph $T$ of treewidth at most $k-1$,
$|\mathrm{Hom}(T,G\otimes
H)|=|\mathrm{Hom}(T,G)|\cdot|\mathrm{Hom}(T,H)|=|\mathrm{Hom}(T,G^{\prime})|\cdot|\mathrm{Hom}(T,H)|=|\mathrm{Hom}(T,G^{\prime}\otimes
H)|$ Thus, for all graphs $H$, $G\otimes H\cong_{k-1}G^{\prime}\otimes H$.

Suppose for contradiction that, for all $H$, $|\mathrm{Ans}(Q,G\otimes
H)|=|\mathrm{Ans}(Q,G^{\prime}\otimes H)|$. This rewrites to

$\sum_{i=1}^{\ell}c_{i}(|\mathrm{Ans}((H_{i},X_{i}),G)|-|\mathrm{Ans}((H_{i},X_{i}),G^{\prime})|)\cdot|\mathrm{Ans}((H_{i},X_{i}),H)|=0.$

Let
$d_{i}:=c_{i}(|\mathrm{Ans}((H_{i},X_{i}),G)|-|\mathrm{Ans}((H_{i},X_{i}),G^{\prime})|)$
and $m=\max\\{|V(H_{i})|\mid i\in[\ell]\\}$. Let $\mathcal{H}$ be the set of
all graphs with at most $m^{m}$ vertices. Then we obtain a system of linear
equations containing the following equation for each $H\in\mathcal{H}$.

$\sum_{i=1}^{\ell}d_{i}\cdot|\mathrm{Ans}((H_{i},X_{i}),H)|=0\,.$

It was shown in [16, Lemma 34(iii)] that the matrix corresponding to this
system has full rank. Therefore, for all $i\in[\ell]$, $d_{i}=0$. This implies
$|\mathrm{Ans}((H_{1},X_{1}),G)|=|\mathrm{Ans}((H_{1},X_{1}),G^{\prime})|$,
contradicting the choice of $G$ and $G^{\prime}$. Thus our assumption was
wrong, and there is a graph $H$ (in fact $H\in\mathcal{H}$) such that
$|\mathrm{Ans}(Q,G\otimes H)|\neq|\mathrm{Ans}(Q,G^{\prime}\otimes H)|$. Since
$G\otimes H\cong_{k_{1}}G^{\prime}\otimes H$, the proof is concluded. ∎

###  5.4 Star Queries and Dominating Sets

In this final section we use Theorem 1 to determine the WL-dimension of
counting dominating sets (proving Corollary 5).

######  Definition 63 (Dominating Set).

Let $G$ be a graph and let $k$ be a positive integer. A _dominating set_ of
$G$ is a subset $D\subseteq V(G)$ such that each vertex of $G$ is either
contained in $D$ or adjacent to a vertex in $D$. The set $\Delta_{k}(G)$
contains all size-$k$ dominating sets of $G$.

For analysing the WL-dimension of counting size-$k$ dominating sets we will
consider, as an intermediate step, the $k$-star-query.

######  Definition 64.

Let $k$ be a positive integer. The $k$-_star_ is the conjunctive query
$(S_{k},X_{k})$ where $X_{k}=\\{x_{1},\dots,x_{k}\\}$,
$V(S_{k})=X\cup\\{y\\}$, and $E(S_{k})=\\{\\{x_{i},y\\}\mid i\in[k]\\}$.

The $k$-star is often written in the more prominent form
$\varphi(x_{1},\dots,x_{k})=\exists y:\bigwedge_{i=1}^{k}E(x_{i},y).$ It is
well-known that $(S_{k},X_{k})$ is counting minimal (see e.g. [15]). Moreover,
$\Gamma(S_{k},X_{k})$ is the $(k+1)$-clique, which has treewidth $k$. Thus
$\mathsf{sew}(S_{k},X_{k})=k$. Corollary 65 follows immediately from Theorem
1.

######  Corollary 65.

The WL-dimension of $(S_{k},X_{k})$ is $k$.

We can now prove Corollary 5.

######  Corollary 66 (Corollary 5, restated).

The WL-dimension of the function $G\mapsto|\Delta_{k}(G)|$ is $k$.

###### Proof.

We start with the lower bound. To this end, given a graph $G$, and a
conjunctive query $(H,X)$, we set

$\mathsf{Inj}((H,X),G)=\\{a\in\mathrm{Ans}((H,X),G)\mid a\text{ is
injective}\\}.$

Let $I=\\{(i,j)\in[k]^{2}\mid i<j\\}$ and consider a subset $J\subseteq I$.
The query $(S_{k},X_{k})/J$ is obtained by identifying $x_{i}$ and $x_{j}$ if
and only if $(i,j)\in J$. Observe that
$(S_{k},X_{k})/J\cong(S_{\ell},X_{\ell})$ for some $\ell\leq k$. By the
principle of inclusion and exclusion, for each graph $G$,

$|\mathsf{Inj}((S_{k},X_{k}),G)|=\sum_{J\subseteq
I}(-1)^{|J|}\cdot|\mathrm{Ans}((S_{k},X_{k})/J,G)|=\sum_{i=1}^{k}c_{i}\cdot|\mathrm{Ans}((S_{i},X_{i}),G)|\,,$

where $c_{i}=\\{J\subseteq I\mid(S_{k},X_{k})/J\cong(S_{i},X_{i})\\}$. Thus,
$|\mathsf{Inj}((S_{k},X_{k}),G)|$ computes the number of answers to the
quantum query with constituents $(S_{i},X_{i})$ and coefficients $c_{i}$.
Moreover, $c_{k}=1$ since $(S_{k},X_{k})/J\cong(S_{k},X_{k})$ if and only if
$J=\emptyset$.333To obtain a quantum query, we need to remove all terms
$(S_{i},X_{i})$ with $c_{i}=0$. In fact, following the analysis in [12], it
can be shown that none of the $c_{i}$ is $0$. However, since we only need
$c_{k}\neq 0$, we omit going into further details. By Corollary 4 and the fact
that $\mathsf{sew}(S_{\ell},X_{\ell})=\ell$ for all $\ell\in[k]$, the WL-
dimension of $G\mapsto|\mathsf{Inj}((S_{k},X_{k}),G)|$ is equal to $k$.

Next observe that $|\mathsf{Inj}((S_{k},X_{k}),G)|/k!$ is the number of
$k$-vertex subsets $A$ of $G$ such that there is a vertex $y\in V(G)$ that is
adjacent to all $a\in A$. Thus
$\binom{|V(G)|}{k}-|\mathsf{Inj}((S_{k},X_{k}),G)|/k!$ is equal to the size of
the set

$D_{k}(G):=\\{A\subseteq V(G)\mid|A|=k\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ \forall y\in V(G):\exists a\in A:\\{a,y\\}\notin
E(G)\\}.$

Let $\overline{G}$ be the self-loop-free complement of $G$, that is, two
_distinct_ vertices $u$ and $v$ in $V(\overline{G})=V(G)$ are adjacent in
$\overline{G}$ if and only if they are not adjacent in $G$. Observe that
$\\{a,y\\}\notin E(G)$ if and only if $a=y$ or $\\{a,y\\}\in E(\overline{G})$.
Therefore $|D_{k}(G)|=|\Delta_{k}(\overline{G})|$.

We are now ready to prove that the WL-dimension of the function
$G\mapsto|\Delta_{k}(G)|$ is at least $k$. Suppose for contradiction that its
WL-dimension is $k^{\prime}$ for some $1\leq k^{\prime}<k$. Then, for all $G$
and $G^{\prime}$ with $G\cong_{k^{\prime}}G^{\prime}$,
$|\Delta_{k}(G)|=|\Delta_{k}(G^{\prime})|$. However, we know that the WL-
dimension of $G\mapsto|\mathsf{Inj}((S_{k},X_{k}),G)|$ is equal to $k$. Thus
there are graphs $F$ and $F^{\prime}$ with $F\cong_{k^{\prime}}F^{\prime}$ and
$|\mathsf{Inj}((S_{k},X_{k}),F)|\neq|\mathsf{Inj}((S_{k},X_{k}),F^{\prime})|$.
. Seppelt has shown that $F\cong_{k^{\prime}}F^{\prime}$ implies
$\overline{F}\cong_{k^{\prime}}\overline{F^{\prime}}$ [33]. Therefore
$|\Delta_{k}(\overline{F})|=|\Delta_{k}(\overline{F^{\prime}})|$. Let $K_{1}$
be the (treewidth $0$) graph containing one isolated vertex. The number of
homomomorphisms from $K_{1}$ to $F$ determines the number of vertices of $F$
so $F\cong_{k^{\prime}}F^{\prime}$ implies $|V(F)|=|V(F^{\prime})|$. Let
$n=|V(F)|=|V(F^{\prime})|$. In summary,

$|\mathsf{Inj}((S_{k},X_{k}),F)|=k!\left(\binom{n}{k}-|\Delta_{k}(\overline{F})|\right)=k!\left(\binom{n}{k}-|\Delta_{k}(\overline{F^{\prime}})|\right)=|\mathsf{Inj}((S_{k},X_{k}),F^{\prime})|,$

which contradicts the choice of $F$ and $F^{\prime}$ and concludes the proof
of the lower bound.

For the upper bound, we have to show that $F\cong_{k}F^{\prime}$ implies
$\Delta_{k}(F)=\Delta_{k}(F^{\prime})$, which is an immediate consequence of
our previous analysis. Since the WL-dimension of
$G\mapsto|\mathsf{Inj}((S_{k},X_{k}),G)|$ is equal to $k$, we have

$|\Delta_{k}(F)|=\binom{n}{k}-|\mathsf{Inj}((S_{k},X_{k}),\overline{F})|/k!=\binom{n}{k}-|\mathsf{Inj}((S_{k},X_{k}),\overline{F^{\prime}})|/k!=|\Delta_{k}(F^{\prime})|.$

This concludes the proof. ∎

## References

  * [1] Vikraman Arvind.  The Weisfeiler-Lehman Procedure.  Bull. EATCS, 120, 2016.  URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/442.
  * [2] Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky.  On the weisfeiler-leman dimension of fractional packing.  Inf. Comput., 288:104803, 2022.  doi:10.1016/j.ic.2021.104803.
  * [3] Pablo Barceló, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov.  Graph neural networks with local graph parameters.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 25280–25293, 2021.
  * [4] Hans L. Bodlaender and Arie M. C. A. Koster.  Safe separators for treewidth.  Discret. Math., 306(3):337–350, 2006.  doi:10.1016/j.disc.2005.12.017.
  * [5] Jan Böker.  Color refinement, homomorphisms, and hypergraphs.  In Ignasi Sau and Dimitrios M. Thilikos, editors, Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, volume 11789 of Lecture Notes in Computer Science, pages 338–350. Springer, 2019.  doi:10.1007/978-3-030-30786-8\\_26.
  * [6] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  IEEE Trans. Pattern Anal. Mach. Intell., 45(1):657–668, 2023\.  doi:10.1109/TPAMI.2022.3154319.
  * [7] 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, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.MFCS.2021.27.
  * [8] Jin-yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Comb., 12(4):389–410, 1992.  doi:10.1007/BF01305232.
  * [9] Hubie Chen and Stefan Mengel.  A trichotomy in the complexity of counting answers to conjunctive queries.  In Marcelo Arenas and Martín Ugarte, editors, 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, volume 31 of LIPIcs, pages 110–126. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.  doi:10.4230/LIPIcs.ICDT.2015.110.
  * [10] Hubie Chen and Stefan Mengel.  Counting answers to existential positive queries: A complexity classification.  In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 315–326. ACM, 2016.  doi:10.1145/2902251.2902279.
  * [11] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.  Can graph neural networks count substructures?  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.  URL: https://proceedings.neurips.cc/paper/2020/hash/75877cb75154206c4e65e76b88a12712-Abstract.html.
  * [12] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.  doi:10.1145/3055399.3055502.
  * [13] Anuj Dawar, Tomás Jakl, and Luca Reggio.  Lovász-Type Theorems and Game Comonads.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.  doi:10.1109/LICS52264.2021.9470609.
  * [14] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász meets weisfeiler and leman.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 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.
  * [15] Holger Dell, Marc Roth, and Philip Wellnitz.  Counting answers to existential questions.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 113:1–113:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.113.
  * [16] Holger Dell, Marc Roth, and Philip Wellnitz.  Counting answers to existential questions.  CoRR, abs/1902.04960, 2019.  URL: http://arxiv.org/abs/1902.04960, arXiv:1902.04960.
  * [17] Yon Dourisboure and Cyril Gavoille.  Tree-decompositions with bags of small diameter.  Discret. Math., 307(16):2008–2029, 2007.  doi:10.1016/j.disc.2005.12.060.
  * [18] Arnaud Durand and Stefan Mengel.  Structural tractability of counting of solutions to conjunctive queries.  Theory Comput. Syst., 57(4):1202–1249, 2015.  doi:10.1007/s00224-014-9543-y.
  * [19] Zdenek Dvorák.  On recognizing graphs by numbers of homomorphisms.  J. Graph Theory, 64(4):330–342, 2010.  doi:10.1002/jgt.20461.
  * [20] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.  doi:10.1007/3-540-29953-X.
  * [21] Martin Grohe.  The logic of graph neural networks.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–17. IEEE, 2021.  doi:10.1109/LICS52264.2021.9470677.
  * [22] Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer.  Color Refinement and Its Applications.  In An Introduction to Lifted Probabilistic Inference. The MIT Press, 08 2021.  arXiv:https://direct.mit.edu/book/chapter-pdf/2101088/c025000\\_9780262365598.pdf, doi:10.7551/mitpress/10548.003.0023.
  * [23] Neil Immerman and Eric Lander.  Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81.  Springer New York, New York, NY, 1990.  doi:10.1007/978-1-4612-4478-3_5.
  * [24] Matthias Lanzinger and Pablo Barceló.  On the power of the weisfeiler-leman test for graph motif parameters.  CoRR, abs/2309.17053, 2023.  arXiv:2309.17053, doi:10.48550/arXiv.2309.17053.
  * [25] László Lovász.  Large Networks and Graph Limits, volume 60 of Colloquium Publications.  American Mathematical Society, 2012.
  * [26] Laura Mancinska and David E. Roberson.  Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 661–672. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00067.
  * [27] Christopher Morris, Gaurav Rattan, and Petra Mutzel.  Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [28] 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.  In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 4602–4609. AAAI Press, 2019\.  doi:10.1609/aaai.v33i01.33014602.
  * [29] Daniel Neuen.  Homomorphism-distinguishing closedness for graphs of bounded tree-width.  arXiv preprint arXiv:2304.07011, 2023.
  * [30] Reinhard Pichler and Sebastian Skritek.  Tractable counting of the answers to conjunctive queries.  J. Comput. Syst. Sci., 79(6):984–1001, 2013.  doi:10.1016/j.jcss.2013.01.012.
  * [31] David E Roberson.  Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree.  arXiv preprint arXiv:2206.10321, 2022.
  * [32] 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, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 79:1–79:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.MFCS.2023.79.
  * [33] 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, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 82:1–82:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.MFCS.2023.82.
  * [34] Gottfried Tinhofer.  Graph isomorphism and theorems of birkhoff type.  Computing, 36(4):285–300, 1986.  doi:10.1007/BF02240204.
  * [35] Gottfried Tinhofer.  A note on compact graphs.  Discret. Appl. Math., 30(2-3):253–264, 1991.  doi:10.1016/0166-218X(91)90049-3.
  * [36] Boris Weisfeiler and Andrei Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Series, 2(9):12–16, 1968.  English translation by G. Ryabov available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.
  * [37] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.  URL: https://openreview.net/forum?id=ryGs6iA5Km.