# Counting Small Induced Subgraphs:
Hardness via Fourier Analysis ††thanks: Funded by the European Union (ERC,
CountHom, 101077083). Views and opinions expressed are however those of the
author(s) only and do not necessarily reflect those of the European Union or
the European Research Council Executive Agency. Neither the European Union nor
the granting authority can be held responsible for them.

Radu Curticapean
University of Regensburg and IT University of Copenhagen  Daniel Neuen
University of Regensburg

###### Abstract

For a fixed graph property $\Phi$ and integer $k\geq 1$, the problem
$\\#\textnormal{{IndSub}}(\Phi,k)$ asks to count the induced $k$-vertex
subgraphs satisfying $\Phi$ in an input graph $G$. If $\Phi$ is trivial on
$k$-vertex graphs (i.e., if $\Phi$ contains either all or no $k$-vertex
graphs), this problem is trivial. Otherwise we prove, among other results:

  * •

If $\Phi$ is edge-monotone (i.e., closed under deleting edges), then
$\\#\textnormal{{IndSub}}(\Phi,k)$ cannot be solved in time $n^{o(k)}$
assuming ETH. This strengthens a result by Döring, Marx and Wellnitz [STOC
2024] that only ruled out an exponent of $o(\sqrt{\log k}/\log\log k)$. Our
results also hold when counting modulo fixed primes.

  * •

If there is some fixed $\varepsilon>0$ such that at most
$(2-\varepsilon)^{\binom{k}{2}}$ graphs on $k$ vertices satisfy $\Phi$, then
$\\#\textnormal{{IndSub}}(\Phi,k)$ cannot be solved in time $n^{o(k/\sqrt{\log
k})}$ assuming ETH. Our results hold even when each of the graphs in $\Phi$
may come with an arbitrary individual weight. This generalizes previous
results for hereditary properties by Focke and Roth [SIAM J. Comput. 2024] up
to a $\sqrt{\log k}$ factor in the exponent of the lower bound.

  * •

If $\Phi$ only depends on the number of edges, then
$\\#\textnormal{{IndSub}}(\Phi,k)$ cannot be solved in time $n^{o(k)}$
assuming ETH. This improves on a lower bound by Roth, Schmitt and Wellnitz
[FOCS 2020] that only ruled out an exponent of $o(k/\sqrt{\log k})$.

In all cases, we also obtain #W[1]-hardness if $k$ is part of the input and
the problem is parameterized by $k$. We also obtain lower bounds on the
Weisfeiler-Leman dimension.

Most importantly, our results follow from relatively straightforward Fourier
analysis, as opposed to the nontrivial techniques from combinatorics, group
theory, and simplicial topology used in previous papers. Our paper subsumes
most of the known #W[1]-hardness results known in the area, often with tighter
lower bounds under ETH.

5(8.5, 8.75)

##  1 Introduction

Counting small patterns in graphs is of fundamental importance in computer
science. In network analysis and bioinformatics, the counts of small patterns
give insights into properties of the network, e.g., when a pattern count
deviates significantly from the expected value in a random graph [34].
Counting patterns is also interesting from a theoretical perspective: For
example, counting perfect matchings in bipartite graphs is precisely the
problem of evaluating permanents of zero-one matrices; permanents play a
central role in counting complexity and algebraic complexity theory [47, 1].

### Counting Small Induced Subgraphs

While counting perfect matchings amounts to counting subgraph patterns $H$
whose size is comparable to the host graph $G$, many practical applications
ask us to count patterns $H$ that are much smaller than $G$. Such problems can
be formalized and analyzed in the following ways:

  1. 1.

For a _fixed pattern_ $H$, consider the function
$\\#\mathrm{IndSub}(H\to\,\star\,)$: Given an input graph $G$, this function
outputs the number $\\#\mathrm{IndSub}(H\to G)$ of induced $H$-copies in $G$.
Examples are the numbers of triangles or $K_{4}$-copies in a graph $G$. While
each such function can be computed in polynomial time, we wish to use hardness
assumptions such as the _Exponential-Time Hypothesis (ETH)_ [25] or other
complexity assumptions to bound the exponent of this polynomial running time,
in dependence on $H$.

  2. 2.

We may also view both $H$ and $G$ as input when computing
$\\#\mathrm{IndSub}(H\to G)$ and then consider $k\coloneqq|V(H)|$ as a
parameter, a notion from _parameterized complexity_ [13, 19]. In this area,
fixed-parameter tractable algorithms with running time $f(k)n^{O(1)}$ for
computable functions $f$ are sought. Similar to the classical notion of
#P-hardness, the notion of #W[1]-hardness in parameterized complexity allows
us to argue against the existence of such algorithms.

The general problem $\\#\textsc{ParIndSub}$ of computing
$\\#\mathrm{IndSub}(H\to G)$ on input $H,G$ with parameter $|V(H)|$ is
#W[1]-hard, as it subsumes the canonical #W[1]-hard problem
$\\#\textnormal{{Clique}}$ of counting $k$-cliques in a graph $G$ [19]. To
obtain a more detailed picture, the problems
$\\#\textnormal{{ParIndSub}}(\mathcal{H})$ for fixed recursively enumerable
graph classes $\mathcal{H}$ were considered [9]. Here, the input is a graph
$H\in\mathcal{H}$ and a graph $G$, and the output is $\\#\mathrm{IndSub}(H\to
G)$. The parameter is again $|V(H)|$. If $\mathcal{H}$ is finite, then
$\\#\textnormal{{ParIndSub}}(\mathcal{H})$ is clearly polynomial-time
solvable. Otherwise, if $\mathcal{H}$ is infinite (and recursively
enumerable), then it was shown in [9] that
$\\#\textnormal{{ParIndSub}}(\mathcal{H})$ is #W[1]-complete by a
parameterized reduction from $\\#\textnormal{{Clique}}$.

Considering fixed pattern graphs, it was shown that ETH implies a constant
$\alpha>0$ such that, for every $k$-vertex graph $H$, the number
$\\#\mathrm{IndSub}(H\to\,\star\,)$ cannot be computed in time
$O(n^{\alpha\cdot k})$ [8, 16]. This establishes counting induced subgraphs as
a hard problem, regardless of the pattern $H$.

### Counting Small Induced Subgraphs with a Fixed Property

Generalizing the problem of counting induced $k$-vertex subgraphs isomorphic
to a fixed graph $H$, one can fix a set $\Phi$ of $k$-vertex graphs and count
induced subgraphs of $G$ that are isomorphic to some graph $H\in\Phi$; we
denote this value by $\\#\mathrm{IndSub}(\Phi\to G)$. The systematic study of
such counting problems was initiated by Jerrum and Meeks [26, 27, 28]. Given a
fixed graph property $\Phi$, they define the parameterized problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ that asks, on input $(G,k)$, to determine
the number $\\#\mathrm{IndSub}(\Phi^{(k)}\to G)$ of induced $k$-vertex
subgraphs of $G$ that satisfy $\Phi$. Here, the _slice_ $\Phi^{(k)}$ denotes
the restriction of $\Phi$ to graphs on exactly $k$ vertices. Note that $\Phi$
itself may contain graphs of arbitrary sizes in this problem. Since their
initial paper [26], it was shown that $\\#\textnormal{{ParIndSub}}(\Phi)$ is
either fixed-parameter tractable or #W[1]-hard, for every computable property
$\Phi$ [11]. However, the criterion on $\Phi$ for tractability of
$\\#\textnormal{{ParIndSub}}(\Phi)$ remains unknown.

Clearly, if all but finitely many slices of $\Phi$ are trivial (we also say
$k$-trivial) in the sense that they are empty or contain all $k$-vertex
graphs, then $\\#\textnormal{{ParIndSub}}(\Phi)$ is easy to compute. Such
properties $\Phi$ are called _meager_. For all other properties, the following
was conjectured.

######  Conjecture 1.1 ([15, 20, 45]).

For every computable and non-meager property $\Phi$, the parameterized problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

In the last decade, this conjecture has been verified for several special
classes of non-meager properties $\Phi$. Below, we list a set of maximal
results subsuming most of the known results in the area, see also [16, Section
1.1]. When we say that ETH rules out an exponent of $o(f(k))$, we mean that an
algorithm with running time $n^{o(f(k))}$ for
$\\#\textnormal{{ParIndSub}}(\Phi)$ would refute ETH. Even stronger, ETH
implies a constant $\alpha>0$ such that $\\#\mathrm{IndSub}(\Phi^{(k)}\to G)$
cannot be computed in time $O(n^{\alpha\cdot f(k)})$ on $n$-vertex graphs, for
an infinite set of integers $k$.

  1. 1.

If $\Phi$ is closed under deleting edges (edge-monotone) [16] or closed under
deleting vertices (hereditary) [20], then $\\#\textnormal{{ParIndSub}}(\Phi)$
is #W[1]-hard. This strengthens an earlier result that required $\Phi$ to
satisfy both closure properties [45]. It is also shown that ETH rules out an
exponent of $o(\sqrt{\log k}/\log\log k)$ for edge-monotone properties, and an
exponent of $o(k)$ for hereditary properties.

  2. 2.

Given $k\in{\mathbb{N}}$, set $\beta_{\Phi}(k)=0$ if no $k$-vertex graph
satisfies $\Phi$. Otherwise, let $\beta_{\Phi}(k)$ be the number of edge-
counts avoided by $\Phi$ on $k$-vertex graphs, i.e., the number of integers
$\ell$ such that no graph $H$ with $k$ vertices and $\ell$ edges satisfies
$\Phi$. If $\beta_{\Phi}(k)\in\omega(k)$, then
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard [45]. Moreover, ETH rules
out an exponent of $o(\beta_{\Phi}(k)/\sqrt{\log\beta_{\Phi}(k)})$.

  3. 3.

If $\Phi$ depends only on the number of edges of the input graph, then
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard and ETH rules out an
exponent of $o(k/\sqrt{\log k})$ [45].

  4. 4.

If there are infinitely many prime powers $t$ such that $\Phi$ holds for
exactly one of $K_{t,t}$ or $I_{2t}$, then $\\#\textnormal{{ParIndSub}}(\Phi)$
is #W[1]-hard and ETH rules out an exponent of $o(k)$ [15].

In this paper, we strengthen all but the last111In fact, our proofs in Section
5.2 implicitly also subsume and extend this last hardness result. of the above
hardness results in several ways, e.g., by proving hardness for a larger
collection of properties, by proving hardness even for modular counting
variants, by proving tighter lower bounds under ETH, or by showing that the
problems remain hard even when weights are incorporated into $\Phi$. However,
we consider the main contribution of our paper to be the introduction of
_Fourier analysis_ techniques to the study of
$\\#\textnormal{{ParIndSub}}(\Phi)$. Indeed, the well-established toolkit of
Fourier analysis allows us to derive many of the above results as relatively
straightforward consequences of known results or even exercises in textbooks
[39].

### From Induced Subgraphs to Subgraphs

Following other recent works in the area, we approach
$\\#\textnormal{{ParIndSub}}(\Phi)$ by interpreting its $k$-vertex slices
$\Phi^{(k)}$ as linear combinations of other counting functions, namely (not
necessarily induced) _subgraph_ counts: Via the inclusion-exclusion principle
[33, (5.17)], it can be shown that there exist pattern graphs
$H_{1},\ldots,H_{s}$, each on exactly $k$ vertices, and coefficients
$\alpha_{1},\ldots,\alpha_{s}\in{\mathbb{Z}}$ such that

$\\#\mathrm{IndSub}(\Phi^{(k)}\to\,\star\,)=\sum_{i=1}^{s}\alpha_{i}\cdot\\#\mathrm{Sub}(H_{i}\to\,\star\,).$
(1)

The patterns and coefficients are unique up to isomorphism, as the functions
$\\#\mathrm{Sub}(H\to\,\star\,)$ are linearly independent for sets of pairwise
non-isomorphic graphs. Moreover, provided that all patterns have the same
number of vertices, linear combinations as above enjoy a very useful
“complexity monotonicity” property [11]: Their evaluation problem is exactly
as hard as that of their hardest terms. Thus, we can understand the complexity
of $\\#\mathrm{IndSub}(\Phi^{(k)}\to\,\star\,)$ by

  1. 1.

understanding the complexity of $\\#\mathrm{Sub}(H\to\,\star\,)$ depending on
$H$, and

  2. 2.

analyzing which subgraph patterns $H$ have non-zero coefficients in (1),
depending on $\Phi$.

The first item, i.e., the complexity of counting subgraph patterns, is well-
understood [12, 11]. When counting subgraphs rather than induced subgraphs,
easy patterns emerge. For example, the number of subgraph copies of the
edgeless $k$-vertex graph $I_{k}$ in an $n$-vertex graph $G$ is simply
$\binom{n}{k}$, while counting _induced_ copies of $I_{k}$ is equivalent to
counting $k$-cliques. More generally, the subgraph counting variant
$\\#\textnormal{{ParSub}}(\mathcal{H})$ of
$\\#\textnormal{{ParIndSub}}(\mathcal{H})$ is polynomial-time solvable if the
maximum vertex-cover number among graphs in $\mathcal{H}$ is finite [12], and
the problem is #W[1]-hard otherwise, provided that $\mathcal{H}$ is
recursively enumerable [10, 11]. Moreover, ETH implies a constant $\beta>0$
such that, for every graph $H$ with vertex-cover number $t$, the number
$\\#\mathrm{IndSub}(H\to\,\star\,)$ cannot be computed in time
$O(n^{\beta\cdot t/\log t})$ [11]. Since every $k$-vertex graph with a vertex-
cover of size $t$ has at most $tk$ edges, it follows that counting subgraphs
from $k$-vertex pattern graphs $H$ with at least $tk$ edges requires time
$O(n^{\beta\cdot t})$ under ETH, for every $t\in{\mathbb{N}}$. Briefly put, a
sufficient criterion for hardness of counting subgraph patterns is the density
of the pattern.

It turns out to be more difficult to settle the second item, i.e., to
determine whether a graph $H$ appears with non-zero coefficient $\alpha_{H}$
in the linear combination (1) for $\Phi^{(k)}$. On one hand, one can show
straightforwardly that $\alpha_{H}$ is given by the _alternating enumerator_
of $\Phi$ on $H$. We define this quantity, with an extra factor of
$(-1)^{|E(H)|}$ compared to previous works [43, 44, 15], as

$\widehat{\Phi}(H)=(-1)^{|E(H)|}\sum_{S\subseteq
E(H)}(-1)^{|S|}\cdot\Phi(H[S]),$

where $H[S]$ is the subgraph obtained from $H$ by keeping all vertices and
only the edges in $S$.

On the other hand, despite the inconspicuously explicit form of
$\widehat{\Phi}(H)$, it is highly nontrivial to determine for which properties
$\Phi$ and graphs $H$ we have $\widehat{\Phi}(H)\neq 0$. Most approaches
towards this can be traced back to a seminal paper [44] that interprets edge-
monotone properties $\Phi$ defined on $k$-vertex graphs as simplicial
complexes. Up to sign, $\widehat{\Phi}(K_{k})$ then is the (reduced) _Euler
characteristic_ of the complex: Viewing cardinality-$t$ sets as dimension-$t$
facets of the simplex corresponding to $\Phi$, we see that
$\widehat{\Phi}(K_{k})$ counts the odd-dimension minus the even-dimension
facets of the simplex, similar to Euler’s formula for plane graphs. By
understanding group actions on the simplex that preserve the Euler
characteristic modulo primes, it was then shown that
$\widehat{\Phi}(K_{k})\neq 0$ for several properties $\Phi$, e.g., for edge-
monotone properties $\Phi$ that are false on all odd cycles. In subsequent
works [15, 16, 46], group actions on the edges of edge-transitive graphs were
used to derive more general results, culminating in the recent result on edge-
monotone properties [16].

### Our Approach: Connecting the Subgraph Basis and Fourier Analysis

In a nutshell, we observe that Fourier analysis enables a more straightforward
and versatile approach to alternating enumerators than previous approaches. As
mentioned above, a linear combination
$f(\star)=\sum_{H}\alpha_{H}\,\\#\mathrm{IndSub}(H\to\,\star\,)$ with $H$
ranging over $k$-vertex graphs also admits a subgraph count representation
$f(\star)=\sum_{H}\beta_{H}\,\\#\mathrm{Sub}(H\to\,\star\,)$, where $H$ also
ranges over $k$-vertex graphs. Both representations are unique, as the
underlying basis functions are linearly independent. We observe that the basis
change between these representations is “essentially” a Fourier transform.

The precise correspondence can be phrased via polynomials. Let $X_{t}$ be the
undirected complete $t$-vertex graph with an indeterminate $x_{ij}$ on edge
$ij$. We define the weighted subgraph count from $H$ into $X$ as the
polynomial

$\\#\mathrm{Sub}(H\to X_{t})=\sum_{F}\prod_{ij\in E(F)}x_{ij},$ (2)

where $F$ ranges over all subgraphs of $X_{t}$ isomorphic to $H$, ignoring
edge-weights. Also define

$\\#\mathrm{IndSub}(H\to X_{t})=\sum_{F}\prod_{ij\in
E(F)}x_{ij}\prod_{ij\in\overline{E(F)}}(1-x_{ij}),$ (3)

with $\overline{E(F)}=\binom{V(F)}{2}\setminus E(F)$. For every $t$-vertex
graph $G$, we have $\\#\mathrm{Sub}(H\to G)=\\#\mathrm{Sub}(H\to X_{t})$ after
substituting $1$ into $x_{ij}$ for $ij\in E(G)$ and $0$ for $ij\notin E(G)$,
and the same holds for $\\#\mathrm{IndSub}(H\to X_{t})$. In other words, the
evaluations of the polynomials on $0$-$1$-inputs corresponding to $t$-vertex
graphs $G$ are precisely the counts of (induced) $H$-copies in $G$. As
multilinear polynomials are determined by their evaluations on $0$-$1$-inputs,
it follows that $\\#\mathrm{Sub}(H\to X_{t})$ and $\\#\mathrm{IndSub}(H\to
X_{t})$ are the unique multilinear polynomials that agree with
$\\#\mathrm{Sub}(H\to\,\star\,)$ and $\\#\mathrm{IndSub}(H\to\,\star\,)$ on
$t$-vertex graphs, when the latter two functions are viewed as functions
$\\{0,1\\}^{m}\to{\mathbb{R}}$ for $m=\binom{t}{2}$.

The key observation is now that the degrees of these polynomials give very
useful insights into the complexity of $\\#\mathrm{Sub}(H\to\,\star\,)$ and
linear combinations thereof. Recall from the previous subsection that
$\\#\mathrm{Sub}(H\to\,\star\,)$ is hard if $H$ has a large number of edges.
The number of edges in a $k$-vertex graph $H$ however is precisely the degree
of $\\#\mathrm{Sub}(H\to X_{t})$ for $t\geq k$; it suffices to choose $t=k$ in
the following. Also recall the complexity monotonicity property: Linear
combinations $f(\star)=\sum_{H}\beta_{H}\,\\#\mathrm{Sub}(H\to\,\star\,)$,
with $H$ ranging over $k$-vertex graphs, are hard if they contain a function
$\\#\mathrm{Sub}(H\to\,\star\,)$ for large $|E(H)|$. This in turn occurs if
and only if the polynomial representation $f(X_{k})$ has large degree. In
conclusion, we can establish that linear combinations $f(\star)$ of subgraph
counts from $k$-vertex patterns are hard by showing that $f(X_{k})$ has large
degree.

As an example, this reasoning shows that $\\#\mathrm{IndSub}(H\to\,\star\,)$
is hard for _every_ $k$-vertex graph $H$, since its polynomial representation
(3) has degree $\binom{k}{2}$ and its representation over the subgraph count
basis therefore contains a graph on $\binom{k}{2}$ edges, i.e., the complete
graph $K_{k}$. Taking linear combinations of the functions
$\\#\mathrm{IndSub}(H\to\,\star\,)$ for different $H$ may however lead to
cancellations that make $K_{k}$ disappear from this representation.

To understand the degree in the representing polynomial for more general
functions $f$, the rich toolkit of _Fourier analysis_ is available [29, 39].
In a nutshell, the degrees we wish to understand are precisely the _Fourier
degrees_ of Boolean functions, and various well-developed techniques are
available to obtain lower bounds on them. Recall that, in the polynomial
representations above, the function of interest is interpreted as
$f:\\{0,1\\}^{m}\to{\mathbb{R}}$ for $m=\binom{k}{2}$, and the degree of the
unique multilinear polynomial agreeing with $f$ determined the complexity of
$f$. In Fourier analysis, we view $f:\\{-1,1\\}^{m}\to{\mathbb{R}}$ by
interpreting $0$ as $1$ and $1$ as $-1$. The unique multilinear polynomial
agreeing with $f$ is called the _Fourier expansion_ of $f$, and its degree is
the _Fourier degree_ of $f$. While the different representations of inputs
lead to different representing multilinear polynomials, they can be
transformed into each other by a simple affine change of variables, implying
that they have the same degree. We can thus establish that linear combinations
$f(\star)$ of subgraph counts from $k$-vertex patterns are hard by showing
that they have large Fourier degree, interpreted as
$f:\\{-1,1\\}^{m}\to{\mathbb{R}}$.

### Our Results

#### Sparse and Hereditary Properties.

Our first result applies the Fourier machinery to obtain hardness of
moderately sparse properties, i.e., properties that are missing an exponential
fraction of graphs. This implies known results on hereditary properties [20]
as a special case. Moreover, our result holds even for “properties” that do
not output $0$ or $1$. In the following, a graph invariant $\Phi$ is an
isomorphism-invariant function from graphs to ${\mathbb{Q}}$. If there is some
$k\in{\mathbb{N}}$ such that all graphs $G$ with $\Phi(G)\neq 0$ have exactly
$k$ vertices, then we say that $\Phi$ is a _$k$ -vertex graph invariant_ and
define

$\\#\mathrm{IndSub}(\Phi\to G)=\sum_{F}\Phi(F)\cdot\\#\mathrm{IndSub}(F\to
G).$

The _uncertainty principle_ establishes that every function
$f\colon\\{-1,1\\}^{m}\to{\mathbb{R}}$ with small support contains many terms
in its Fourier expansion and thus has large Fourier degree [39]. More
formally, for every $0<\varepsilon<1$ there is some $\delta>0$ such that, if
$1\leq|\operatorname{supp}(f)|\leq(2-\varepsilon)^{m}$, then the Fourier
degree of $f$ is at least $\delta m$. Using this, we show that the subgraph
basis representation of $\\#\mathrm{IndSub}(\Phi\to\star)$ contains a graph
$H$ with $\delta\cdot\binom{k}{2}$ edges, rendering
$\\#\mathrm{IndSub}(\Phi\to\star)$ hard.

######  Theorem 1.2.

For every $0<\varepsilon<1$ there is $\delta>0$ such that, for every
$k$-vertex graph invariant $\Phi$ with
$1\leq|\operatorname{supp}(\Phi)|\leq(2-\varepsilon)^{\binom{k}{2}}$, no
algorithm computes $\\#\mathrm{IndSub}(\Phi\to G)$ in time $O(n^{\delta\cdot
k/\sqrt{\log k}})$ on $n$-vertex graphs $G$ unless ETH fails.

Moreover, for every computable graph invariant $\Phi$ such that
$1\leq|\operatorname{supp}(\Phi^{(k)})|\leq(2-\varepsilon)^{\binom{k}{2}}$
holds for infinitely many slices $\Phi^{(k)}$, the problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard. This holds in particular
when $\Phi$ is a hereditary property that is not meager.

The consequence for hereditary properties follows from the fact that every
non-empty property excluding a fixed induced subgraph $F$ contains at most
$(2-\varepsilon)^{\binom{k}{2}}$ graphs in the $k$-th slice if $k$ is
sufficiently large, depending on $F$ [40].

#### (Edge-)Monotone Properties & Modular Counting.

Let $\Phi$ be a nontrivial $k$-vertex graph property that is monotone, i.e.,
closed under the deletion of edges.222In the literature, this condition is
often called “edge-monotone” (see e.g., [16, 20, 45]). By adapting known
results on the Fourier degrees of monotone functions with symmetry conditions
[14, 41], we show that the subgraph expansion of $\Phi$ contains some
$k$-vertex graph $H$ containing as subgraph the complete bipartite graph
$K_{\ell,\ell}$ for some $\ell>k/4$. This gives us particularly strong bounds
under ETH and holds even when the subgraph expansion is reduced modulo a prime
$p$; then we obtain $\ell>k/p^{2}$.

######  Theorem 1.3.

There is $\delta>0$ such that, for every $k$-vertex graph property that is
monotone and not $k$-trivial, no algorithm computes
$\\#\mathrm{IndSub}(\Phi\to G)$ in time $O(n^{\delta\cdot k})$ on $n$-vertex
graphs $G$ unless ETH fails. Moreover, for every computable graph property
$\Phi$ that, for infinitely many $k$, is monotone on $k$-vertex graphs and not
$k$-trivial, the problem $\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

For every fixed prime $p$, both statements hold even when the value
$\\#\mathrm{IndSub}(\Phi\to G)$ is only to be computed modulo $p$, assuming
the randomized ETH instead of ETH.

#### Fully Symmetric Properties.

For _fully symmetric_ properties, i.e., properties that depend only on the
number of edges, we obtain strong hardness by straightforward applications of
known Fourier analysis results for fully symmetric functions. Special cases of
such properties were studied before [26, 28, 44], and [45] shows that non-
trivial and fully symmetric graph properties $\Phi$ induce hard problems
$\\#\textnormal{{ParIndSub}}(\Phi)$. However, [45] only rules out algorithms
with running time $n^{o(k/\sqrt{\log k})}$ assuming ETH. We obtain tight lower
bounds under ETH with an arguably simpler proof.

######  Theorem 1.4.

There is $\delta>0$ such that, for every $k$-vertex graph property $\Phi$ that
is fully symmetric and not $k$-trivial, no algorithm computes
$\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ in time $O(n^{\delta\cdot k})$ on
$n$-vertex graphs $G$ unless ETH fails.

Moreover, for every computable graph property $\Phi$ that is fully symmetric
on $k$-vertex graphs and not $k$-trivial for infinitely many $k$, the problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

#### Properties Avoiding many Hamming Weights.

We also obtain hardness for properties $\Phi$ that avoid a superlinear number
of Hamming weights, a setting that was also studied before [26, 45]. Given a
$k$-vertex graph invariant $\Phi$, we define its _Hamming weight set_ as ${\sf
hw}(\Phi)\coloneqq\\{|E(H)|\mid H\in\Phi\\}$, i.e., the set of all edge-counts
among the graphs in $\Phi$. We then define a value $\beta_{\Phi}$ that equals
$0$ when $\Phi$ is empty and $\binom{k}{2}-|{\sf hw}(\Phi)|$ otherwise. For a
general graph invariant $\Phi$ and $k\in{\mathbb{N}}$, we define
$\beta_{\Phi}(k)\coloneqq\beta_{\Phi^{(k)}}$. By a symmetrization argument
similar to [38], we obtain:

######  Theorem 1.5.

There is $\delta>0$ such that, for every $0<d\leq k/2$ and $k$-vertex graph
invariant $\Phi$ with $\beta_{\Phi}\geq dk,$ no algorithm computes
$\\#\mathrm{IndSub}(\Phi\to G)$ in time $O(n^{\delta\cdot d/\sqrt{\log d}})$
on $n$-vertex graphs $G$ unless ETH fails. Moreover,
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard for computable graph
invariants $\Phi$ with $\beta_{\Phi}(k)\in\omega(k)$.

#### The All-Even Property.

Finally, consider the curious property $\Phi_{\sf even}$ that contains exactly
those graphs where all vertices have even degree. This property turns out to
be interesting, since only few graphs $H$ are contained in its subgraph
expansion; we can identify them as precisely the bipartite graphs. This
implies that $\\#\textnormal{{ParIndSub}}(\Phi_{\sf even})$ is #W[1]-hard,
with tight lower bounds under ETH, but it also yields non-trivial upper bounds
on its complexity. Moreover, the fact that only bipartite graphs appear in the
subgraph expansion is actually useful to prove hardness of other properties,
as we can take pointwise products with $\Phi_{\sf even}$ to filter out
unwanted graphs from a property $\Phi$ and translate degree lower bounds and
complexity implications for the filtered version back to $\Phi$. In
particular, we can obtain the following variant of Theorem 1.2.

######  Theorem 1.6.

For every $0<\varepsilon<1$ there is $\delta>0$ such that, for every
$k$-vertex graph invariant $\Phi$ with
$1\leq|\operatorname{supp}(\Phi\cdot\Phi_{\sf
even})|\leq(\sqrt{2}-\varepsilon)^{\binom{k}{2}}$, no algorithm computes
$\\#\mathrm{IndSub}(\Phi\to G)$ in time $O(n^{\delta\cdot k/\sqrt{\log k}})$
on $n$-vertex graphs $G$ unless ETH fails.

Moreover, for every computable graph invariant $\Phi$ such that
$1\leq|\operatorname{supp}(\Phi^{(k)}\cdot\Phi_{\sf
even})|\leq(\sqrt{2}-\varepsilon)^{\binom{k}{2}}$ holds for infinitely many
slices $\Phi^{(k)}$, the problem $\\#\textnormal{{ParIndSub}}(\Phi)$ is
#W[1]-hard.

Here, $\Phi\cdot\Phi_{\sf even}$ denotes the point-wise product of $\Phi$ and
$\Phi_{\sf even}$ defined via $(\Phi\cdot\Phi_{\sf
even})(G)=\Phi(G)\cdot\Phi_{\sf even}(G)$. In particular,
$\operatorname{supp}(\Phi\cdot\Phi_{\sf even})$ is the intersection of the
supports of $\Phi$ and $\Phi_{\sf even}$.

### Weisfeiler-Leman Dimension of Induced Subgraph Counts

Our techniques also allow us to bound or even precisely determine the
Weisfeiler-Leman dimension of graph parameters. The $k$-dimensional
Weisfeiler-Leman algorithm ($k$-WL) is a standard heuristic for testing
isomorphism of graphs with connections to various other areas [23, 24, 30,
36]. The _Weisfeiler-Leman dimension_ of a graph invariant $f$ is the minimal
$k\geq 1$ such that $k$-WL distinguishes between all graphs $G,G^{\prime}$ for
which $f(G)\neq f(G^{\prime})$. A high value of this complexity measure
implies inexpressibility in certain logics and lower bounds for symmetric
computational models.

Our results yield bounds on the WL-dimension of
$\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ for various $k$-vertex graph invariants
$\Phi$. For example, for monotone $k$-vertex graph properties $\Phi$, the WL-
dimension of $\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ is $>\frac{k}{4}$. The WL-
dimension of $\\#\mathrm{IndSub}(\Phi_{\sf even}^{(k)}\to\,\star\,)$ is equal
to $\left\lfloor k/2\right\rfloor$.

### Organization of the Paper

In Section 2, we give formal definitions of the graph-theoretic concepts used,
brief introductions to parameterized and exponential-time complexity, and a
synopsis of basic concepts from Fourier analysis. We describe the basis
transformation between induced subgraph counts and subgraph counts and
complexity results for the latter basis in Section 3 before connecting this
transformation to Fourier analysis in Section 4. Based on this foundation, we
then prove our main hardness results in Section 5 and the results on the all-
even property in Section 6. Finally, we adapt the proofs to obtain lower
bounds for the Weisfeiler-Leman dimension of induced subgraph counts in
Section 7. The conclusions list several open problems, and the appendix
contains technical proofs omitted from the main paper to improve reading flow.

##  2 Preliminaries

We write ${\mathbb{Z}}$ for the integers and
${\mathbb{Z}}_{p}=\\{0,1,\dots,p-1\\}$ for the ring with addition and
multiplication taken modulo $p$. For an integer $n\geq 1$, we define
$[n]\coloneqq\\{1,\dots,n\\}$. For a set $X$ and an integer $k\geq 0$, we use
$\binom{X}{k}$ to denote the collection of $k$-element subsets of $X$.

###  2.1 Graphs

We use standard graph notation. All graphs considered in this paper are
undirected and simple, i.e., they contain no multiedges or self-loops. We
write $V(G)$ and $E(G)$ to denote the vertex set and edge set of a graph $G$,
respectively. Also, we use $vw$ as a shorthand for an edge $\\{v,w\\}\in
E(G)$.

A graph $H$ is a _subgraph_ of another graph $G$, denoted $H\subseteq G$, if
$V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. For a graph $G$ and a set
$X\subseteq V(G)$, we write $G[X]=(X,\\{vw\in E(G)\mid v,w\in X\\})$ to denote
the _(vertex-)induced subgraph_ of $G$ by $X$. Similarly, for $S\subseteq
E(G)$, we write $G[S]=(V(G),S)$ to denote the _(edge-)induced subgraph_ of $G$
by $S$. It is usually clear from the context whether we are taking a vertex-
or an edge-induced subgraph.

For $k\geq 1$, we write $K_{k}$ for the complete graph with $k$ vertices,
i.e., $V(K_{k})=[k]$ and $E(K_{k})=\binom{[k]}{2}$. For $k,\ell\geq 1$, we
write $K_{k,\ell}$ to denote the complete bipartite graph with $k+\ell$
vertices, i.e., $V(K_{k,\ell})=[k+\ell]$ and $E(K_{k,\ell})=\\{\\{i,k+j\\}\mid
i\in[k],j\in[\ell]\\}$. We remark that we explicitly define the graph $K_{k}$
to have vertex set $[k]$. In particular, for $S\subseteq\binom{[k]}{2}$, we
commonly use $K_{k}[S]$ to refer to the graph with vertex set $[k]$ and edge
set $S$. If the index $k$ is clear from context, we sometimes omit it and
simply write $K[S]$.

A _graph invariant_ $\Phi$ (over a field ${\mathbb{F}}$) maps each graph $G$
to a value $\Phi(G)\in{\mathbb{F}}$ such that $\Phi(G)=\Phi(G^{\prime})$ for
all isomorphic graphs $G,G^{\prime}$. In this work, we only consider graph
invariants over the rationals ${\mathbb{Q}}$ and over ${\mathbb{Z}}_{p}$ for
prime $p$. Unless stated otherwise, graph invariants are defined over the
rationals. A graph invariant is a _graph property_ if $\Phi(G)\in\\{0,1\\}$
for all graphs $G$. For a graph $G$ and a graph property $\Phi$, we write
$G\in\Phi$ as a shorthand for $\Phi(G)=1$. For $k\geq 1$, a _$k$ -vertex graph
invariant/property_ is a graph invariant/property $\Phi$ such that $\Phi(G)=0$
if $|V(G)|\neq k$. For a graph invariant $\Phi$, we write $\Phi^{(k)}$ to
denote the graph invariant on $k$-vertex graphs derived by $\Phi$, i.e.,

$\Phi^{(k)}(G)=\begin{cases}\Phi(G)&\text{if $|V(G)|=k$}\\\
0&\text{otherwise}\end{cases}.$

For $k\geq 1$, a graph invariant $\Phi$ (over ${\mathbb{F}}$) is _$k$
-trivial_ if there is some $c\in{\mathbb{F}}$ such that $\Phi(G)=c$ for all
$k$-vertex graphs $G$. A graph property $\Phi$ is _meager_ if it is
$k$-trivial for all but finitely many $k$.

For a graph invariant $\Phi$, we define

$\\#\mathrm{IndSub}(\Phi\to G)\coloneqq\sum_{X\subseteq V(G)}\Phi(G[X]).$

Observe that, if $\Phi$ is a graph property, then $\\#\mathrm{IndSub}(\Phi\to
G)$ is the number of vertex-induced subgraphs of $G$ that satisfy $\Phi$. We
write $\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ for the map
$G\mapsto\\#\mathrm{IndSub}(\Phi\to G)$; this is again a graph invariant (over
the same field as $\Phi$).

###  2.2 Parameterized Complexity

We give a brief introduction to parameterized counting complexity and refer
the reader to the textbooks [13, 19] and theses [10, 43] for additional
background.

A _parameterized counting problem_ consists of a function
$P\colon\Sigma^{*}\to{\mathbb{Q}}$ and a _parameterization_
$\kappa\colon\Sigma^{*}\to{\mathbb{Z}}_{\geq 0}$. For an instance
$x\in\Sigma^{*}$, the number $\kappa(x)$ is called the _parameter_ of $x$. The
problem $(P,\kappa)$ is called _fixed-parameter tractable (fpt)_ if there is a
computable function $f$, a constant $c\in{\mathbb{Z}}_{\geq 1}$ and a
(deterministic) algorithm ${\mathcal{A}}$ that, given an instance
$x\in\Sigma^{*}$, computes $P(x)$ in time $f(\kappa(x))\cdot|x|^{c}$.

A _parameterized Turing reduction_ from $(P,\kappa)$ to
$(P^{\prime},\kappa^{\prime})$ is a deterministic fpt-algorithm
${\mathcal{A}}$ with oracle access to $P^{\prime}$ that, given an instance
$x$, computes $P(x)$ and only makes oracle calls to instances $y$ that satisfy
$\kappa^{\prime}(y)\leq g(\kappa(x))$ for some computable function
$g\colon{\mathbb{Z}}_{\geq 0}\to{\mathbb{Z}}_{\geq 0}$. The problem
$\\#\textnormal{{Clique}}$ takes as input a graph $G$ and an integer $k\geq 1$
and asks to determine the number of $k$-cliques in $G$. The number $k$ is the
parameter of the instance $(G,k)$. A parameterized counting problem
$(P,\kappa)$ is _#W[1] -hard_ if there is a parameterized Turing reduction
from $\\#\textnormal{{Clique}}$ to $(P,\kappa)$. A _parsimonious_
parameterized reduction is a parameterized Turing reduction that makes exactly
one oracle call $y$ and then outputs the oracle response on $y$ without
further processing.

For a graph invariant $\Phi$, the parameterized counting problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ takes as input a graph $G$ and an integer
$k\geq 1$ (the parameter) and outputs $\\#\mathrm{IndSub}(\Phi^{(k)}\to G)$.
When studying the complexity of $\\#\textnormal{{ParIndSub}}(\Phi)$, it will
mostly suffice to restrict our attention to the _$k$ -th slice_ of the
problem, for fixed integers $k\geq 1$, where the input consists only of a
graph $G$. This motivates us to define the following problem: Given $k\geq 1$
and a $k$-vertex graph invariant $\Phi$, the problem
$\\#\textnormal{{IndSub}}(\Phi)$ takes as input a graph $G$ and outputs
$\\#\mathrm{IndSub}(\Phi\to G)$. For a graph invariant $\Phi$, we also write
$\\#\textnormal{{IndSub}}(\Phi,k)$ instead of
$\\#\textnormal{{IndSub}}(\Phi^{(k)})$. Compared to
$\\#\textnormal{{ParIndSub}}(\Phi)$, this problem is polynomial-time solvable
for any fixed $\Phi$ and $k$.

#### Modular Counting.

Given a prime $p$, we write $\\#_{p}$ to denote the modular counting version
of a problem: For example, $\\#_{p}\textnormal{{Clique}}$ denotes the problem
of counting $k$-cliques modulo $p$. We say a problem $(P,\kappa)$ is
$\textnormal{{Mod}}_{p}\textnormal{{W[1]}}$-hard if there is a parameterized
Turing reduction from $\\#_{p}\textnormal{{Clique}}$ to $(P,\kappa)$. Note
that a parsimonious parameterized reduction from $\\#\textnormal{{Clique}}$ to
the non-modular counting version $(P^{\prime},\kappa)$ of $P$ implies such a
reduction.

For counting induced subgraphs, we only consider modular counting versions for
graph properties $\Phi$. In particular, if $\Phi$ is a graph property, then
$\\#\mathrm{IndSub}(\Phi\to G)$ is an integer and we can safely define
$\\#_{p}\mathrm{IndSub}(\Phi\to G)\in\\{0,\dots,p-1\\}$. In turn, this allows
us to define the problems $\\#_{p}\textnormal{{ParIndSub}}(\Phi)$ and
$\\#_{p}\textnormal{{IndSub}}(\Phi)$ for graph properties $\Phi$.

#### Fine-Grained Lower Bounds.

To obtain more fine-grained lower bounds on the complexity of
$\\#\textnormal{{ParIndSub}}(\Phi)$ as well as
$\\#\textnormal{{IndSub}}(\Phi)$, we also rely on the _Exponential Time
Hypothesis (ETH)_ dating back to [25] (see, e.g., [13, Conjecture 14.1]).

######  Conjecture 2.1 (Exponential Time Hypothesis (ETH)).

There is a real number $\varepsilon>0$ such that the problem $3$-Sat cannot be
solved in time $O(2^{\varepsilon n})$, where $n$ denotes the number of
variables of the input formula.

In the setting of modular counting, we rely on the following slightly stronger
conjecture that even rules out randomized algorithms.

######  Conjecture 2.2 (Randomized Exponential Time Hypothesis (rETH)).

There is a real number $\varepsilon>0$ such that the problem $3$-Sat cannot be
solved in time $O(2^{\varepsilon n})$ by a randomized algorithm with error
probability at most $1/3$, where $n$ denotes the number of variables of the
input formula.

###  2.3 Boolean Functions

Let $f\colon\\{-1,1\\}^{m}\to{\mathbb{R}}$ be a Boolean function of arity $m$.
The reader is encouraged to associate $-1$ with True and $1$ with False. The
_Fourier expansion of $f$_ is its unique representation as a multilinear
polynomial in ${\mathbb{R}}[x_{1},\ldots,x_{m}]$. For $S\subseteq[m]$, define
the monomial corresponding to $S$ as

$x^{S}\coloneqq\prod_{i\in S}x_{i}.$

Then there are unique so-called _Fourier coefficients_
$\widehat{f}(S)\in{\mathbb{R}}$ for $S\subseteq[m]$ such that

$f(\boldsymbol{x})=\sum_{S\subseteq[m]}\widehat{f}(S)x^{S}.$ (4)

See [39, Theorem 1.1] for a proof of the existence and uniqueness of (4), and
the entire textbook [39] for extensive background on the Fourier expansion of
Boolean functions. We write

$\displaystyle\operatorname{supp}(f)$
$\displaystyle\coloneqq\\{\boldsymbol{x}\in\\{-1,1\\}^{m}\mid
f(\boldsymbol{x})\neq 0\\},$ $\displaystyle\operatorname{supp}(\widehat{f})$
$\displaystyle\coloneqq\\{S\subseteq[m]\mid\widehat{f}(S)\neq 0\\}.$

By the _uncertainty principle_ , one of these two sets is always large; see
[39, Exercise 3.15].

######  Lemma 2.3 (Uncertainty Principle).

If $f\colon\\{-1,1\\}^{m}\to{\mathbb{R}}$ is not the zero function, then

$|\operatorname{supp}(f)|\cdot|\operatorname{supp}(\widehat{f})|\geq 2^{m}.$

The _degree_ $\deg(f)$ of $f$ is the degree of the Fourier expansion, i.e.,

$\deg(f)\coloneqq\max\\{|S|\mid S\in\operatorname{supp}(\widehat{f})\\}.$

By standard upper bounds on binomial coefficients (see, e.g., [19, Lemma
16.19]), small degree of $f$ implies small support:

######  Lemma 2.4.

Let $\mathbf{H}(c)=-c\log_{2}(c)-(1-c)\log_{2}(1-c)$ be the binary entropy
function. For every function $f\colon\\{-1,1\\}^{m}\to{\mathbb{R}}$ with
$\deg(f)\leq cm$ for $0<c\leq 1/2$, we have

$|\operatorname{supp}(\widehat{f})|\ \leq\ \sum_{k=0}^{\lfloor
cm\rfloor}\binom{m}{k}\ \leq\ 2^{\mathbf{H}(c)m}.$

Conversely, if $|\operatorname{supp}(\widehat{f})|>2^{\mathbf{H}(c)m}$, then
$\deg(f)>cm$.

We regularly need to restrict Boolean functions to subcubes. Let
$f\colon\\{-1,1\\}^{m}\to{\mathbb{R}}$ be a Boolean function of arity $m$ and
let $J\subseteq[m]$. We write $\overline{J}\coloneqq[m]\setminus J$ for the
complement of $J$ in $[m]$. Also let
$\boldsymbol{z}=(z_{j})_{j\in\overline{J}}\in\\{-1,1\\}^{\overline{J}}$. Then
we define the _restriction of $f$ to $J$ using $\boldsymbol{z}$_, denoted by
$f_{J|\boldsymbol{z}}\colon\\{-1,1\\}^{J}\to{\mathbb{R}}$, to be subfunction
of $f$ given by fixing the coordinates in $\overline{J}$ to the values in
$\boldsymbol{z}$. Slightly abusing notation, for
$\boldsymbol{y}\in\\{-1,1\\}^{J}$, we write $(\boldsymbol{y},\boldsymbol{z})$
for the composite tuple in $\\{-1,1\\}^{m}$, even tough $\boldsymbol{y}$ and
$\boldsymbol{z}$ are not actually concatenated. In this notation, we have
$f_{J|\boldsymbol{z}}(\boldsymbol{y})=f(\boldsymbol{y},\boldsymbol{z})$.
Consistent with previous notation, we use
$\widehat{f}_{J|\boldsymbol{z}}(S)\in{\mathbb{R}}$ for $S\subseteq J$ to
denote the Fourier coefficients of $f_{J|\boldsymbol{z}}$. Then

$\widehat{f}_{J|\boldsymbol{z}}(S)=\sum_{T\subseteq\overline{J}}\widehat{f}(S\cup
T)\prod_{j\in T}z_{j}$ (5)

for all $S\subseteq J$; see [39, Proposition 3.21]. In particular,
$\deg(f)\geq\deg(f_{J|\boldsymbol{z}})$.

##  3 Complexity in the Subgraph Basis

It is known that pattern counting problems can be expressed and studied in
different bases. For example, the problems studied in this paper admit direct
expressions as linear combinations of induced subgraph counts for graphs
$F_{1},\ldots,F_{s}$ and coefficients
$\alpha_{1},\ldots,\alpha_{s}\in{\mathbb{Q}}$, i.e.,

$f(\,\star\,)=\sum_{i=1}^{s}\alpha_{i}\cdot\\#\mathrm{IndSub}(F_{i}\to\,\star\,).$
(6)

Such problems can also be expressed as linear combinations of not necessarily
induced subgraph counts for graphs $H_{1},\ldots,H_{s}$ and coefficients
$\beta_{1},\ldots,\beta_{s}\in{\mathbb{Q}}$, i.e.,

$f(\,\star\,)=\sum_{j=1}^{t}\beta_{j}\cdot\\#\mathrm{Sub}(H_{j}\to\,\star\,).$
(7)

See [33, (5.17)] for a proof. The subgraph basis representation (7) turns out
to be more useful for understanding the complexity of $f$. In the
transformation from (6) to (7), and in this paper in general, the following
notion is central:

######  Definition 3.1.

The _alternating enumerator_ of a graph invariant $\Phi$ on a graph $H$ is

$\widehat{\Phi}(H)=(-1)^{|E(H)|}\sum_{S\subseteq E(H)}(-1)^{|S|}\,\Phi(H[S]).$

######  Remark 3.2.

In earlier works [15, 16, 44], the alternating enumerator is defined without
the factor $(-1)^{|E(H)|}$. These works aim at showing that
$\widehat{\Phi}(H)\neq 0$ for certain graphs $H$; such statements are not
affected by the absence of the factor $(-1)^{|E(H)|}$. To obtain more
straightforward statements in Lemmas 3.3, 4.1 and 5.19, we prefer the variant
defined above.

The coefficients in the subgraph representation of a graph invariant can be
shown to be alternating enumerators. While similar correspondences are known,
see [15, Lemma 8] or [44, Theorem 1], we could not find the precise lemma
below in the literature. The appendix includes an explicit proof based on the
inclusion–exclusion principle.

######  Lemma 3.3.

Given a $k$-vertex graph invariant $\Phi$, for $k\geq 1$, we have

$\\#\mathrm{IndSub}(\Phi\to\star)=\sum_{H}\widehat{\Phi}(H)\cdot\\#\mathrm{Sub}(H\to\star),$
(8)

where $H$ ranges over all unlabelled $k$-vertex graphs.

To show hardness of the problem $\\#\textnormal{{IndSub}}(\Phi)$ (and its
variants) we follow previous work [16, 15, 44] and identify graphs of
unbounded tree-width with non-zero alternating enumerator: For a graph $H$, we
write $\operatorname{tw}(H)$ for the tree-width of $H$ (see, e.g., [13,
Chapter 7]) and say that an (infinite) sequence of graphs $(H_{k})_{k\geq 1}$
has _unbounded tree-width_ if, for every $t\geq 1$, there is some $k\geq 1$
such that $\operatorname{tw}(H_{k})\geq t$.

######  Theorem 3.4.

Let $\Phi$ be a computable graph invariant and let $(H_{k})_{k\geq 1}$ be a
sequence of graphs of unbounded tree-width.

  1. (a)

If $\widehat{\Phi}(H_{k})\neq 0$ for all $k\geq 0$, then
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

  2. (b)

If $\widehat{\Phi}(H_{k})\neq 0\bmod p$ for all $k\geq 0$, then
$\\#_{p}\textnormal{{ParIndSub}}(\Phi)$ is
$\textnormal{{Mod}}_{p}\textnormal{{W[1]}}$-hard.

Also, we use the next theorem to obtain more fine-grained lower bounds based
on ETH and rETH.

######  Theorem 3.5.

There is a universal constant $\alpha_{\textsc{ind}}>0$ and an integer
$N_{0}\geq 1$ such that for all numbers $k,\ell\geq 1$, the following holds:

  1. (a)

If $\Phi$ is a $k$-vertex graph invariant and there exists a graph $H$ with
$\widehat{\Phi}(H)\neq 0$ and $E(H)\geq k\cdot\ell\geq N_{0}$, then
$\\#\textnormal{{IndSub}}(\Phi)$ cannot be solved in time
$O(n^{\alpha_{\textsc{ind}}\cdot\ell/\sqrt{\log\ell}})$ unless ETH fails.

  2. (b)

Under the same conditions as above, if $H$ is additionally a supergraph of
$K_{\ell,\ell}$, then $\\#\textnormal{{IndSub}}(\Phi)$ cannot be solved in
time $O(n^{\alpha_{\textsc{ind}}\cdot\ell})$ unless ETH fails.

  3. (c)

If $p$ is a prime and the condition $\widehat{\Phi}(H)\neq 0$ is replaced by
$\widehat{\Phi}(H)\neq 0\bmod p$, then Items (a) and (b) hold for
$\\#_{p}\textnormal{{ParIndSub}}(\Phi)$ instead of
$\\#\textnormal{{ParIndSub}}(\Phi)$, assuming rETH instead of ETH.

Both theorems can be proved by (variants of) known arguments [10, 15, 16, 44]
and several special cases have already been stated in the literature (see,
e.g., [16]). Still, we provide full proofs in Appendix A.

Finally, let us also note the following algorithmic result. Let $G$ be a
graph. A _vertex cover_ of $G$ is a set $C\subseteq V(G)$ such that $e\cap
C\neq\emptyset$ for every edge $e\in E(G)$. The _vertex cover number_ of $G$,
denoted by $\operatorname{vc}(G)$, is the minimal size of a vertex cover of
$G$.

######  Theorem 3.6.

Let $\Phi$ be a computable graph invariant and let $t(k)$ denote the maximal
vertex cover number of a $k$-vertex graph $H$ such that $\widehat{\Phi}(H)\neq
0$. Then $\\#\textnormal{{ParIndSub}}(\Phi)$ can be solved in time $f(k)\cdot
n^{t(k)+1}$ for some computable function $f$.

The theorem is shown as a consequence of [11, Theorem 1.1] in Appendix A.

##  4 Subgraph Basis versus Fourier Basis

While previous works (see, e.g., [15, 16, 44]) analyse the alternating
enumerator directly to obtain hardness results, we observe that there is a
close connection to the Fourier coefficients of the natural Boolean function
representing $\Phi$. This allows rely on a plethora of existing results (see,
e.g., [39]) on the Fourier expansion of Boolean functions to obtain hardness
results for $\\#\textnormal{{IndSub}}(\Phi)$ for various different types of
graph invariants $\Phi$.

We start by representing a graph invariant as a Boolean function. Let us fix
some $k\geq 1$. Let $\Phi$ be a $k$-vertex graph invariant. We associate the
Boolean function $f_{\Phi}$ of arity $\binom{k}{2}$ defined as follows. For
ease of notation, we write $K\coloneqq K_{k}$ for the complete graph on $k$ in
the remainder of this section. We define the function

$f_{\Phi}\colon\\{-1,1\\}^{E(K)}\to{\mathbb{R}}$

via

$f_{\Phi}(\boldsymbol{x})\coloneqq\Phi(K[\boldsymbol{x}])$

where $K[\boldsymbol{x}]\coloneqq K[S_{\boldsymbol{x}}]$ and
$S_{\boldsymbol{x}}=\\{e\in E(K)\mid\boldsymbol{x}_{e}=-1\\}$.

Consistent with previous notation, for every $S\subseteq E(K)$, we write
$\widehat{f}_{\Phi}(S)$ to denote the Fourier coefficient of $f_{\Phi}$ on
$S$, i.e.,

$f_{\Phi}(\boldsymbol{x})=\sum_{S\subseteq E(K)}\widehat{f}_{\Phi}(S)x^{S}.$

To connect the alternating enumerator to the Fourier coefficients, we focus on
inclusion-wise maximal edge sets evaluating to a non-zero value. Indeed, to
obtain hardness results via the results from Section 3, we aim to find
$k$-vertex graphs $H$ such that $\widehat{\Phi}(H)\neq 0$ and $H$ has large
tree-width. Since the tree-width cannot decrease when adding edges, it is
reasonable to focus on graphs with an inclusion-wise maximal edge set
satisfying $\widehat{\Phi}(H)\neq 0$.

Let $S\subseteq E(K)$. We say that $S$ is _$\widehat{f}$ -maximal_ if
$\widehat{f}(S)\neq 0$ and $\widehat{f}(S^{\prime})=0$ for every $S\subsetneq
S^{\prime}\subseteq E(K)$. Similarly, we say $S$ is _$\widehat{\Phi}$
-maximal_ if $\widehat{\Phi}(K[S])\neq 0$ and
$\widehat{\Phi}(K[S^{\prime}])=0$ for every $S\subsetneq S^{\prime}\subseteq
E(K)$.

######  Lemma 4.1.

Let $k\geq 1$ and let $\Phi$ be a graph invariant on $k$-vertex graphs. Also
let $S\subseteq E(K)$. Then $S$ is $\widehat{\Phi}$-maximal if and only if $S$
is $\widehat{f}_{\Phi}$-maximal.

######  Remark 4.2.

We stress that Lemma 4.1 does not hold if $S$ is not $\widehat{\Phi}$-maximal
(or equivalently, not $\widehat{f}_{\Phi}$-maximal). For example, consider the
property $\Psi$ which only contains the complete graph $K$, i.e., $\Psi(G)=1$
if and only if $G$ is isomorphic to $K$. Then $\widehat{\Psi}(H)\neq 0$ if and
only if $H$ is isomorphic to $K$. On the other hand,
$\operatorname{supp}(\widehat{f}_{\Psi})$ contains all subsets of $E(K)$ by
the uncertainty principle (Lemma 2.3). Observe that $E(K)$ is the unique
$\widehat{\Psi}$-maximal set and it is the unique $\widehat{f}_{\Psi}$-maximal
set. A second example is also discussed in Remark 6.3.

For the proof of Lemma 4.1, we introduce another multilinear polynomial in
${\mathbb{R}}[(x_{e})_{e\in E(K)}]$ related to the property $\Phi$. Let us
write $\boldsymbol{x}=(x_{e})_{e\in E(K)}$. We define the polynomial

$q_{\Phi}(\boldsymbol{x})\coloneqq\sum_{E\subseteq
E(K)}\Phi(K[E])\cdot\prod_{e\in E}x_{e}\prod_{e\in E(K)\setminus E}(1-x_{e}).$
(9)

Let $e_{1},\ldots,e_{m}$ be an enumeration of $E(K)$. Note that
$q_{\Phi}(a_{1},\ldots,a_{m})=\Phi(K[E])$ if $a_{1},\ldots,a_{m}$ are the
zero-one values defined by $a_{i}=[e_{i}\in E]$ for all $i\in[m]$.

######  Lemma 4.3.

Let $\Phi$ be a graph invariant on $k$-vertex graphs. Then

$q_{\Phi}(\boldsymbol{x})=\sum_{S\subseteq E(K)}\widehat{\Phi}(K[S])\cdot
x^{S}.$ (10)

###### Proof.

For $E\subseteq E(K)$ let $q_{E}(\boldsymbol{x})\coloneqq\prod_{e\in
E}x_{e}\prod_{e\in E(K)\setminus E}(1-x_{e})$. Then

$q_{E}(\boldsymbol{x})=\sum_{S\subseteq E(K)\setminus E}(-1)^{|S|}x^{E\cup
S}=\sum_{S\supseteq E}(-1)^{|S\setminus E|}x^{S}.$

It follows that the coefficient of $x^{S}$ is equal to

$\sum_{E\subseteq S}(-1)^{|S\setminus
E|}\cdot\Phi(K[E])=(-1)^{|S|}\cdot\sum_{E\subseteq
S}(-1)^{E}\cdot\Phi(K[E])=\widehat{\Phi}(K[S]).$

∎

###### Proof of Lemma 4.1.

Let us number the variables $\boldsymbol{x}=(x_{e})_{e\in E(K)}$ as
$\boldsymbol{x}=(x_{1},\dots,x_{m})$ where $m\coloneqq|E(K)|=\binom{k}{2}$. We
claim that

$q_{\Phi}(x_{1},\dots,x_{m})=f_{\Phi}(1-2x_{1},\dots,1-2x_{m}).$ (11)

First observe that, together with Equations (4) and (10), this implies the
claim since the “inclusionwise maximal monomials” in both polynomials
$q_{\Phi}(\boldsymbol{x})$ and (the Fourier expansion of)
$f_{\Phi}(\boldsymbol{x})$ are identical.

To prove Equation (11), consider some $a_{1},\dots,a_{m}\in\\{0,1\\}$. Let
$E\coloneqq\\{i\in[m]\mid a_{i}=1\\}$. Slightly abusing notation, we also view
$E$ as a subset of $E(K)$ via the numbering of variables fixed at the
beginning of the proof. Then

$q_{\Phi}(a_{1},\dots,a_{m})=\Phi(K[E])=f_{\Phi}(1-2a_{1},\dots,1-2a_{m})$

since the function $t(y)=1-2y$ satisfies $t(0)=1$ and $t(1)=-1$. Since
$f_{\Phi}$ is the unique multilinear polynomial satisfying all these
equations, we conclude Equation (11). ∎

##  5 Hardness Results via the Fourier Basis

With Lemma 4.1 at hand, we can now exploit tools from the analysis of Boolean
functions to find graphs with non-zero alternating enumerator. Together with
the known results discussed in Section 3, this allows us to obtain hardness
results for the problems $\\#\textnormal{{IndSub}}(\Phi)$ and
$\\#\textnormal{{ParIndSub}}(\Phi)$.

###  5.1 Moderately Small Properties

As a first application, we consider the uncertainty principle (see Lemma 2.3).
For ease of notation, for a graph invariant $\Phi$ on $k$-vertex graphs, we
write

$\operatorname{supp}(\Phi)\coloneqq\\{K[S]\mid
S\in\operatorname{supp}(f_{\Phi})\\}.$

Observe that $\operatorname{supp}(\Phi)$ contains exactly the graphs $G$ with
vertex set $[k]$ for which $\Phi(G)\neq 0$. For an arbitrary graph invariant
$\Phi$ (which is not only defined on $k$-vertex graphs) we also write
$\operatorname{supp}_{k}(\Phi)\coloneqq\operatorname{supp}(\Phi^{(k)})$.

######  Theorem 5.1.

For every $0<\varepsilon<1$ there is some $\delta>0$ such that the following
holds. Let $k\geq 1$ and let $\Phi$ be a $k$-vertex graph invariant such that

$1\leq|\operatorname{supp}(\Phi)|\leq(2-\varepsilon)^{\binom{k}{2}}.$

Then there is a $k$-vertex graph $H$ such that $\widehat{\Phi}(H)\neq 0$ and
$|E(H)|\geq\delta\cdot\binom{k}{2}$.

###### Proof.

Let $0<\varepsilon<1$. We define
$\alpha\coloneqq\log_{2}(1+\frac{\varepsilon}{2})$. Note that $0<\alpha<1$. So
there is a unique $0<\delta<\frac{1}{2}$ such that $\alpha=\mathbf{H}(\delta)$
where $\mathbf{H}$ is the entropy function (see Lemma 2.4).

Now let $k\geq 1$ and let $\Phi$ be a $k$-vertex graph invariant such that

$1\leq|\operatorname{supp}(\Phi)|\leq(2-\varepsilon)^{\binom{k}{2}}.$

Since $|\operatorname{supp}(\Phi)|\geq 1$ we get that $f_{\Phi}$ is not the
zero function. By Lemma 2.3 it holds that

$\displaystyle|\operatorname{supp}(\widehat{f}_{\Phi})|$ $\displaystyle\geq
2^{\binom{k}{2}}\cdot|\operatorname{supp}(f_{\Phi})|^{-1}=2^{\binom{k}{2}}\cdot|\operatorname{supp}(\Phi)|^{-1}$
$\displaystyle\geq
2^{\binom{k}{2}}\cdot(2-\varepsilon)^{-\binom{k}{2}}>\left(1+\frac{\varepsilon}{2}\right)^{\binom{k}{2}}=2^{\alpha\cdot\binom{k}{2}}.$

So there is some $S\in\operatorname{supp}(\widehat{f}_{\Phi})$ such that
$|S|\geq\delta\cdot\binom{k}{2}$ by Lemma 2.4. We may suppose without loss of
generality that $S$ is an inclusion-wise maximal set from
$\operatorname{supp}(\widehat{f}_{\Phi})$ since adding further elements only
increases the cardinality. We set $H\coloneqq K_{k}[S]$. Then
$\widehat{\Phi}(H)\neq 0$ by Lemma 4.1. ∎

By combining Theorem 5.1 with Theorems 3.4(a) and 3.5(a), we obtain the
following.

######  Corollary 5.2 (Theorem 1.2 restated).

For every $0<\varepsilon<1$ there are $N_{0},\delta>0$ such that the following
holds. Let $k\geq N_{0}$ and let $\Phi$ be a $k$-vertex graph invariant such
that

$1\leq|\operatorname{supp}(\Phi)|\leq(2-\varepsilon)^{\binom{k}{2}}.$

Then there is no algorithm that solves $\\#\textnormal{{IndSub}}(\Phi)$ in
time $O(n^{\delta\cdot k/\sqrt{\log k}})$ unless ETH fails.

Moreover, for every computable graph invariant $\Phi$ such that

$1\leq|\operatorname{supp}_{k}(\Phi)|\leq(2-\varepsilon)^{\binom{k}{2}}$

holds for infinitely many $k$, the problem $\\#\textnormal{{ParIndSub}}(\Phi)$
is #W[1]-hard.

A notable example of graph properties that have moderately small support are
hereditary graph properties. A graph property $\Phi$ is _hereditary_ if
$G[X]\in\Phi$ for every graph $G$ such that $G\in\Phi$ and every $X\subseteq
V(G)$, i.e., $\Phi$ is closed under taking (vertex-)induced subgraphs.

######  Theorem 5.3.

Let $\Phi$ be a non-trivial hereditary graph property. Then there is an
integer $k_{0}\geq 1$ and some $\varepsilon>0$ such that

$|\operatorname{supp}_{k}(\Phi)|\leq(2-\varepsilon)^{\binom{k}{2}}$

for every $k\geq k_{0}$.

###### Proof.

Since $\Phi$ is non-trivial there is some graph $F$ such that $\Phi(F)=0$. So
every graph $G\in\Phi$ does not contain $F$ as an induced subgraph. Now the
statement follows directly from [40] that bounds the number of graphs that do
not contain $F$ as an induced subgraph. ∎

So in particular, Corollary 5.2 generalizes the results from [20] giving
#W[1]-hardness for non-trivial hereditary properties. However, we point out
that [20] shows that $\\#\textnormal{{ParIndSub}}(\Phi)$ for hereditary
properties $\Phi$ cannot be solved in time $n^{o(k)}$ assuming ETH whereas
Corollary 5.2 only rules out algorithms with running time $n^{o(k/\sqrt{\log
k})}$ (if $\Phi$ is not meager). On the other hand, we stress that Corollary
5.2 also covers many non-hereditary properties and even holds for graph
invariants that are not necessarily $0$-$1$-valued. In particular, negative
weights are allowed, which could _a priori_ lead to intricate cancellations.

###  5.2 Monotone Properties

Next, we concern ourselves with monotone properties. Let $k\geq 1$ and let
$\Phi$ be a $k$-vertex graph property. We say that $\Phi$ is _monotone_ if
$G[S]\in\Phi$ for every $G\in\Phi$ and every $S\subseteq E(G)$. For an
arbitrary property $\Phi$, we say that $\Phi$ is _monotone on $k$-vertex
graphs_ if $\Phi^{(k)}$ is monotone.

######  Remark 5.4.

In the literature (on the complexity of counting induced subgraphs; see, e.g.,
[16, 20, 45]) this type of property is usually called _edge-monotone_ whereas
_monotone_ properties are usually those that are hereditary and edge-monotone
(on $k$-vertex graphs for all $k\geq 1$).

We prefer _monotone_ properties since we are generally aiming to follow the
notation used for analysing Boolean functions (see, e.g., [39]).

The following theorem is a simple modification of a result from [14].

######  Theorem 5.5.

Let $k\geq 1$ and $p$ a prime number. Let $\Phi$ is a $k$-vertex graph
property that is monotone and not $k$-trivial.

Then there is some $k$-vertex graph $H$ such that $\widehat{\Phi}(H)\neq
0\bmod p$ and the complete bipartite graph $K_{\ell,\ell}$ is a subgraph of
$H$ for some $\ell>\frac{k}{p^{2}}$.

More concretely, building on earlier work of Rivest and Vuillemin [41], Dodis
and Khanna [14] show that the polynomial $q_{\Phi}$ has degree $\Omega(k^{2})$
if $\Phi$ is a graph property on $k$-vertex graphs that is monotone and not
$k$-trivial. More precisely, [14] shows that $q_{\Phi}$ has degree
$\Omega(k^{2})$ when interpreted as a polynomial over the two-element field
${\mathbb{Z}}_{2}$. Analysing their arguments in more detail, it is in fact
shown that $q_{\Phi}$ contains a monomial (with non-zero coefficient) that
corresponds to a graph $H$ such that $K_{\ell,\ell}$ is a subgraph of $H$ for
some $\ell>\frac{k}{4}$. A simple extension of the arguments gives the
statement above for every prime $p\geq 3$.

Since [14] does not provide proof details and their arguments need to be
slightly extended, we give a full proof here. Let us stress again that the
following proof of Theorem 5.5 precisely follows the arguments from [14].

Toward the proof of Theorem 5.5, we require some additional tools. For a
finite set $\Omega$ we write $\operatorname{Sym}(\Omega)$ to denote the
symmetric group over ground set $\Omega$. For $m\geq 1$ we also write $S_{m}$
as a shortcut for of $\operatorname{Sym}([m])$.

Let $p$ be a prime number and $m\geq 1$. Let
$f\colon\\{0,1\\}^{m}\to{\mathbb{Z}}_{p}$ be a function over
${\mathbb{Z}}_{p}$ of arity $m$. A permutation $\sigma\in S_{m}$ is an
_automorphism of $f$_ if $f(\boldsymbol{a})=f(\boldsymbol{a}^{\sigma})$ for
every $\boldsymbol{a}=(a_{1},\dots,a_{m})\in\\{0,1\\}^{m}$ where
$\boldsymbol{a}^{\sigma}=(a_{\sigma(1)},\dots,a_{\sigma(m)})$ is the tuple
obtained from $\boldsymbol{a}$ by permuting its entries according to $\sigma$.
We define the _automorphism group of $f$_, denoted by $\operatorname{Aut}(f)$,
to be the group of all automorphisms of $f$. We say that $f$ is _transitive_
if $\operatorname{Aut}(f)$ is transitive, i.e., for every $i,j\in[m]$ there is
some $\sigma\in\operatorname{Aut}(f)$ such that $\sigma(i)=j$.

Similar to before, the function $f$ can be written as a multilinear polynomial
over ${\mathbb{Z}}_{p}$ as

$q(\boldsymbol{x})=q(x_{1},\dots,x_{m})\coloneqq\sum_{\boldsymbol{a}\in\\{0,1\\}^{m}}f(\boldsymbol{a})\cdot\prod_{i\colon
a_{i}=1}x_{i}\prod_{i\colon a_{i}=0}(1-x_{i}).$

We write $\deg_{p}(f)$ to denote the degree of $q$ (over the field
${\mathbb{Z}}_{p}$).

Also, we write $\vec{0}=(0,\dots,0)$ and $\vec{1}=(1,\dots,1)$ to denote the
all-zero and all-one vector of length $m$, respectively.

######  Lemma 5.6.

Let $f\colon\\{0,1\\}^{m}\to{\mathbb{Z}}_{p}$ be a function over
${\mathbb{Z}}_{p}$ where $p$ is prime and $m=p^{k}$ for some integer $k\geq
1$. Also suppose $f$ is transitive and $f(\vec{0})\neq f(\vec{1})$. Then
$\deg_{p}(f)=m$.

###### Proof.

Let $q(\boldsymbol{x})=q(x_{1},\dots,x_{m})$ denote the unique multilinear
polynomial over ${\mathbb{Z}}_{p}$ representing $f$. We write the polynomial
as

$q(\boldsymbol{x})=\sum_{S\subseteq[m]}\widehat{q}(S)\cdot x^{S}$

for appropriate numbers $\widehat{q}(S)\in{\mathbb{Z}}_{p}$ for every
$S\subseteq[m]$. Observe that $f(\vec{0})=q(\vec{0})=\widehat{q}(\emptyset)$
and

$f(\vec{1})=q(\vec{1})=\sum_{S\subseteq[m]}\widehat{q}(S).$

We need to argue that $\widehat{q}([m])\neq 0$. The following two claims form
the key ingredients.

######  Claim 5.7.

For every $S\subseteq[m]$ and $\sigma\in\operatorname{Aut}(f)$, we have
$\widehat{q}(S)=\widehat{q}(S^{\sigma})$, where $S^{\sigma}=\\{\sigma(i)\mid
i\in S\\}$.

###### Proof.

Let $\sigma\in\operatorname{Aut}(f)$. Consider the polynomial

$q_{\sigma}(\boldsymbol{x})=\sum_{S\subseteq[m]}\widehat{q}(S^{\sigma})\cdot
x^{S}.$

We have that

$q(\boldsymbol{a})=f(\boldsymbol{a})=f(\boldsymbol{a}^{\sigma})=q_{\sigma}(\boldsymbol{a})$

for all $\boldsymbol{a}\in\\{0,1\\}^{m}$. Since the multilinear representation
of $f$ is unique, we conclude that $q=q_{\sigma}$ which implies that
$\widehat{q}(S)=\widehat{q}(S^{\sigma})$ for every $S\subseteq[m]$. ∎

######  Claim 5.8.

For every $\emptyset\subsetneq S\subsetneq[m]$, the cardinality of
$S^{\operatorname{Aut}(f)}\coloneqq\\{S^{\sigma}\mid\sigma\in\operatorname{Aut}(f)\\}$
is divisible by $p$.

###### Proof.

Let $\emptyset\subsetneq S\subsetneq[m]$. We show that

$|S|\cdot|S^{\operatorname{Aut}(f)}|=m\cdot|\\{S^{\prime}\in
S^{\operatorname{Aut}(f)}\mid 1\in S^{\prime}\\}|.$ (12)

First observe that this implies the claim, since $|S|<m$ and hence, at least
one prime factor of $m=p^{k}$ needs to divide $|S^{\operatorname{Aut}(f)}|$.

To show Equation (12), consider the $|S^{\operatorname{Aut}(f)}|$ by $m$
matrix $M$ with entries

$M_{S^{\prime},i}=\begin{cases}1&\text{if }i\in S^{\prime}\\\
0&\text{otherwise}\end{cases}$

for all $S^{\prime}\in S^{\operatorname{Aut}(f)}$ and $i\in[m]$. Now, we count
the number of ones in the matrix $M$ by rows and by columns.

First, counting the number of ones by rows gives
$|S|\cdot|S^{\operatorname{Aut}(f)}|$ since each row contains exactly $|S|$
many ones since all sets in $S^{\operatorname{Aut}(f)}$ have the same size. On
the other hand, the first column of $M$ contains $|\\{S^{\prime}\in
S^{\operatorname{Aut}(f)}\mid 1\in S^{\prime}\\}|$ many ones. Since $f$ is
transitive, all columns contain the same number of ones, so in total we get
$m\cdot|\\{S^{\prime}\in S^{\operatorname{Aut}(f)}\mid 1\in S^{\prime}\\}|$
many one-entries. Together, this implies Equation (12). ∎

We partition the power set $2^{[m]}$ of the set $[m]$ into the orbits
$O_{0},O_{1},\dots,O_{\ell}$ under the automorphism group
$\operatorname{Aut}(f)$. Observe that $\\{\emptyset\\}$ and $\\{[m]\\}$ are
two of the orbits and we may assume without loss of generality that
$O_{0}=\\{\emptyset\\}$ and $O_{\ell}=\\{[m]\\}$. By Claim 5.8 we get that $p$
divides $|O_{j}|$ for every $j\in\\{1,\dots,\ell-1\\}$. Let
$j\in\\{1,\dots,\ell-1\\}$. By Claim 5.7 we get that
$\widehat{q}(S)=\widehat{q}(S^{\prime})$ for all $S,S^{\prime}\in O_{j}$. So

$\sum_{S\in O_{j}}\widehat{q}(S)=0$

since $p$ divides $|O_{j}|$ and all operations are carried out over
${\mathbb{Z}}_{p}$. Overall, this means that

$f(\vec{1})=q(\vec{1})=\sum_{S\subseteq[m]}\widehat{q}(S)=\widehat{q}(\emptyset)+\widehat{q}([m]).$

Because $f(\vec{0})=q(\vec{0})=\widehat{q}(\emptyset)$ and $f(\vec{0})\neq
f(\vec{1})$, we conclude that $\widehat{q}([m])\neq 0$. ∎

Let $p$ be a prime number and $m\geq 1$. Let
$f\colon\\{0,1\\}^{m}\to{\mathbb{Z}}_{p}$ be a function over
${\mathbb{Z}}_{p}$ of arity $m$. Consistent with previous notation, for
$J\subseteq[m]$ and
$\boldsymbol{a}=(a_{j})_{j\in\overline{J}}\in\\{0,1\\}^{\overline{J}}$, we
write $f_{J|\boldsymbol{a}}$ to denote the restriction of $f$ to $J$ using
$\boldsymbol{a}$.

Let $q(\boldsymbol{x})=q(x_{1},\dots,x_{m})$ denote the unique multilinear
polynomial over ${\mathbb{Z}}_{p}$ representing $f$. We write the polynomial
as

$q(\boldsymbol{x})=\sum_{S\subseteq[m]}\widehat{q}(S)\cdot x^{S}$

for appropriate numbers $\widehat{q}(S)\in{\mathbb{Z}}_{p}$ for every
$S\subseteq[m]$. We also use $q_{J|\boldsymbol{a}}$ to denote the polynomial
with variables $(x_{j})_{j\in J}$ obtained from restricting $q$ to $J$ using
$\boldsymbol{a}$. Observe that $q_{J|\boldsymbol{a}}$ is the unique
multilinear representation of $f_{J|\boldsymbol{a}}$.

Let $\boldsymbol{x}_{J}\coloneqq(x_{j})_{j\in J}$ and suppose we write

$q_{J|\boldsymbol{a}}(\boldsymbol{x}_{J})=\sum_{S\subseteq
J}\widehat{q}_{J|\boldsymbol{a}}(S)\cdot x^{S}.$

Then

$\widehat{q}_{J|\boldsymbol{a}}(S)=\sum_{T\subseteq\overline{J}}\widehat{q}(S\cup
T)\prod_{j\in T}a_{j}.$ (13)

for all $S\subseteq J$ (cf. Equation (5)).

######  Lemma 5.9.

Let $p$ be a prime number and suppose $k=p^{\ell}$ for some integer $\ell\geq
1$. Also suppose $\Phi$ is a graph property on $k$-vertex graphs that is
monotone and not $k$-trivial.

Then there is some $k$-vertex graph $H$ such that $\widehat{\Phi}(H)\neq
0\bmod p$ and the complete bipartite graph $K_{p^{\ell-1},p^{\ell-1}}$ is a
subgraph of $H$.

###### Proof.

For $i\in\\{0,\dots,\ell\\}$ we define an equivalence relation $\sim_{i}$ on
$[k]$ via

$a\sim_{i}b\quad\iff\quad\left\lceil\frac{a}{p^{i}}\right\rceil=\left\lceil\frac{b}{p^{i}}\right\rceil.$

Also, we set $F_{i}$ to be the graph with vertex set $V(F_{i})\coloneqq[k]$
and edge set $E(F_{i})\coloneqq\\{ab\mid a\neq b\wedge a\sim_{i}b\\}$. Note
that $F_{i}$ is a disjoint union of $p^{\ell-i}$ many complete graphs of size
$p^{i}$. Moreover,

$\emptyset=E(F_{0})\subseteq E(F_{1})\subseteq\dots\subseteq
E(F_{\ell})=\binom{[k]}{2}.$

Since $\Phi$ is monotone and not $k$-trivial, there is some
$i^{*}\in\\{0,\dots,\ell-1\\}$ such that $\Phi(F_{i})=1$ for all $i\leq
i^{*}$, and $\Phi(F_{i})=0$ for all $i>i^{*}$.

$e_{1}$$e_{2}$$e_{3}$$A_{2}$$A_{1}$$A_{3}$ Figure 1: Visualization of the
construction of the graph $H^{*}$ in the proof of Lemma 5.9 for $p=3$. Each
thick gray edge represents a complete biclique between the corresponding sets.

We define $H_{0}\coloneqq F_{i^{*}}$ and define a second sequence of graphs
(see also Figure 1). We partition the set $[k]$ into $p$ intervals
$A_{1},\dots,A_{p}$ of size $p^{\ell-1}$ each, i.e.,

$A_{i}\coloneqq\left\\{(i-1)\cdot p^{\ell-1}+1,\dots,i\cdot
p^{\ell-1}\right\\}.$

Also, fix an arbitrary order $\\{e_{1},\dots,e_{m}\\}=\\{vw\mid v\neq
w\in[p]\\}=\binom{[p]}{2}$ on the two-elements subsets of $[p]$, and define
$M_{j}\coloneqq\\{e_{1},\dots,e_{j}\\}$ for all $j\in[p]$. We define the graph
$H_{j}$ with vertex set $V(H_{j})=[k]$ and edge set

$E(H_{j})\coloneqq E(H_{0})\cup\\{ab\mid a\in A_{v},b\in A_{w},vw\in
M_{j}\\}.$

Observe that

$E(H_{0})\subseteq E(H_{1})\subseteq\dots\subseteq E(H_{p}).$

Also $\Phi(H_{0})=1$ and $\Phi(H_{p})=0$ since $H_{p}$ contains a subgraph
isomorphic to $F_{i^{*}+1}$. So there is some $j^{*}\in\\{0,\dots,p-1\\}$ such
that $\Phi(H_{j})=1$ for all $j\leq j^{*}$, and $\Phi(H_{j})=0$ for all
$j>j^{*}$. Let us set $H^{*}\coloneqq H_{j^{*}}$ and $V\coloneqq A_{v}$ and
$W\coloneqq A_{w}$ where $vw=e_{j^{*}}$.

######  Claim 5.10.

For every $i\in[p]$ and every $s,s^{\prime}\in A_{i}$ there is an automorphism
$\sigma\in\operatorname{Aut}(H^{*})$ such that $\sigma(s)=s^{\prime}$ and
$\sigma(t)=t$ for all $t\in[k]\setminus A_{i}$.

###### Proof.

This follows immediately from observing that $H^{*}[A_{i}]$ is a disjoint
union of complete graphs of the same size, and every $s,s^{\prime}\in A_{i}$
have the same neighbors outside of $A_{i}$ in $H^{*}$. ∎

Now, consider the polynomial $q_{\Phi}(\boldsymbol{x})$ defined over
${\mathbb{Z}}_{p}$ where $\boldsymbol{x}=(x_{e})_{e\in E(K_{k})}$, and also
let $f\colon\\{0,1\\}^{E(K)}\to{\mathbb{Z}}_{p}$ be the function represented
by $q_{\Phi}$. Let

$J\coloneqq\\{vw\in E(K_{k})\mid v\in V,w\in W\\}$

and $\overline{J}\coloneqq E(K_{k})\setminus J$. Let
$\boldsymbol{a}=(a_{e})_{e\in\overline{J}}\in\\{0,1\\}^{\overline{J}}$ be the
tuple defined via

$a_{e}\coloneqq\begin{cases}1&\text{if }e\in E(H^{*})\\\
0&\text{otherwise}\end{cases}.$

Now, consider the polynomial $q^{*}=(q_{\Phi})_{J|\boldsymbol{a}}$ and the
function $f^{*}\colon\\{0,1\\}^{J}\to{\mathbb{Z}}_{p}$ represented by $q^{*}$.

We claim that $f^{*}$ satisfies the requirements of Lemma 5.6. First,
$|J|=|V\times W|=p^{\ell-1}\cdot p^{\ell-1}=p^{2\ell-2}$ is a prime power of
$p$. Also, $f^{*}(\vec{0})=\Phi(H^{*})=1$ and
$f^{*}(\vec{1})=\Phi(H_{j^{*}+1})=0$, so $f^{*}(\vec{0})\neq f^{*}(\vec{1})$.
It remains to verify that $f^{*}$ is transitive.

######  Claim 5.11.

$f^{*}$ is transitive.

###### Proof.

Let $e_{1},e_{2}\in J$ and suppose $e_{1}=s_{1}t_{1}$ and $e_{2}=s_{2}t_{2}$
where $s_{1},s_{2}\in V$ and $t_{1},t_{2}\in W$. By Claim 5.10 there is
automorphism $\sigma\in\operatorname{Aut}(H^{*})$ such that
$\sigma(s_{1})=s_{2}$ and $\sigma(t_{1})=t_{2}$, and additionally
$V=V^{\sigma}\coloneqq\\{\sigma(s)\mid s\in V\\}$ and
$W=W^{\sigma}\coloneqq\\{\sigma(t)\mid t\in W\\}$.

Now let $\bar{\sigma}\in\operatorname{Sym}(E(K_{k}))$ be defined via
$\bar{\sigma}(st)\coloneqq\sigma(s)\sigma(t)$. Observe that
$\bar{\sigma}(e_{1})=e_{2}$ and $J^{\bar{\sigma}}=J$. We claim that
$\bar{\sigma}|_{J}\in\operatorname{Aut}(f^{*})$. Indeed,
$\bar{\sigma}\in\operatorname{Aut}(f)$ since $f$ represents a graph property.
Also,
$\boldsymbol{a}^{\bar{\sigma}}=(a_{\sigma(e)})_{e\in\overline{J}}=\boldsymbol{a}$
since $\sigma\in\operatorname{Aut}(H^{*})$. Together, this implies that
$\bar{\sigma}|_{J}\in\operatorname{Aut}(f^{*})$. ∎

By Lemma 5.6 we get that $\deg_{p}(f^{*})=|J|$. By Equation (13) and Lemma 4.3
this implies that there is some $J\subseteq S\subseteq E(K_{k})$ such that
$\widehat{\Phi}(K_{k}[S])\neq 0\bmod p$. Hence, we can set $H\coloneqq
K_{k}[S]$. Observe that $|V|=|W|=k/p=p^{\ell-1}$ and the complete bipartite
graph between $V$ and $W$ is a subgraph of $H$ since $J\subseteq E(H)$. ∎

###### Proof of Theorem 5.5.

Let $\ell$ be maximal such that $p^{\ell}\leq k$. We prove by induction on
$d=k-p^{\ell}$ that there is some $k$-vertex graph $H$ such that
$\widehat{\Phi}(H)\neq 0\bmod p$ and $K_{p^{\ell-1},p^{\ell-1}}$ is a subgraph
of $H$.

For the base case $d=0$ the statement immediately follows from Lemma 5.9. So
suppose $d>0$. We distinguish three cases.

  * •

First suppose that $\Phi(K_{1,k-1})=1$. We define the property $\Psi$ on
$(k-1)$-vertex graphs via $\Psi(G)=1$ if and only if $\Phi(G^{+})=1$ where
$G^{+}$ is the graph obtained from $G$ by adding a universal vertex. Then
$\Psi$ is a graph property that is monotone and non-trivial on $(k-1)$-vertex
graphs. Indeed, observe that $\Psi(I_{k-1})=\Phi(K_{1,k-1})=1$, where
$I_{k-1}$ is the edge-less graph on $k-1$ vertices, and
$\Psi(K_{k-1})=\Phi(K_{k})=0$.

By the induction hypothesis, we conclude that there is some $(k-1)$-vertex
graph $H^{\prime}$ such that $\widehat{\Psi}(H^{\prime})\neq 0\bmod p$ and
$K_{p^{\ell-1},p^{\ell-1}}$ is a subgraph of $H^{\prime}$.

Now, let $J\coloneqq\\{e\in E(K_{k})\mid k\notin e\\}$. Then

$q_{\Psi}=(q_{\Phi})|_{J|\vec{1}}.$

Using Equation (13) and Lemma 4.3, we conclude that there is some $k$-vertex
graph $H$ such that $\widehat{\Phi}(H)\neq 0\bmod p$ and $H^{\prime}\subseteq
H$.

  * •

Next suppose that $\Phi(K_{k-1}+K_{1})=0$ where $K_{k-1}+K_{1}$ is the
disjoint union of the complete graphs $K_{k-1}$ and $K_{1}$. We define the
property $\Psi$ via $\Psi(G)=1$ if and only if $\Phi(G+K_{1})=1$ where
$G+K_{1}$ is the graph obtained from $G$ by adding an isolated vertex. Then
$\Psi$ is a graph property that is monotone and non-trivial on $(k-1)$-vertex
graphs. Indeed, observe that $\Psi(I_{k-1})=\Phi(I_{k})=1$ and
$\Psi(K_{k-1})=\Phi(K_{k-1}+K_{1})=0$.

By the induction hypothesis, we conclude that there is some $(k-1)$-vertex
graph $H^{\prime}$ such that $\widehat{\Psi}(H^{\prime})\neq 0\bmod p$ and
$K_{p^{\ell-1},p^{\ell-1}}$ is a subgraph of $H^{\prime}$.

Now, let $J\coloneqq\\{e\in E(K_{k})\mid k\notin e\\}$. Then

$q_{\Psi}=(q_{\Phi})|_{J|\vec{0}}.$

Using Equation (13) and Lemma 4.3, we conclude that there is some $k$-vertex
graph $H$ such that $\widehat{\Phi}(H)\neq 0\bmod p$ and $H^{\prime}\subseteq
H$.

  * •

Finally, suppose neither of the previous two cases holds. Let $r\coloneqq
k-2p^{\ell-1}$. Observe that $r>0$ since $2p^{\ell-1}<p^{\ell}$. Let
$s\coloneqq p^{\ell-1}$. Consider the graph $H^{*}=K_{r+s}+I_{s}$ on vertex
set $[k]$, i.e., $H^{*}$ is a complete graph on $r+s$ vertices together with
$s$ isolated vertices. Let $U,V,W$ be a partition of $[k]$ so that $|U|=r$,
$|V|=|W|=s$ and $H^{*}[U\cup V]$ is a complete graph.

Now, we proceed similarly to the proof of Lemma 5.9. Consider the polynomial
$q_{\Phi}(\boldsymbol{x})$ defined over ${\mathbb{Z}}_{p}$ where
$\boldsymbol{x}=(x_{e})_{e\in E(K_{k})}$. Let

$J\coloneqq\\{vw\in E(K_{k})\mid v\in V,w\in W\\}$

and $\overline{J}\coloneqq E(K_{k})\setminus J$. Let
$\boldsymbol{a}=(a_{e})_{e\in\overline{J}}\in\\{0,1\\}^{\overline{J}}$ be the
tuple defined via

$a_{e}\coloneqq\begin{cases}1&\text{if }e\in E(H^{*})\\\
0&\text{otherwise}\end{cases}.$

Now, consider the polynomial $q^{*}=(q_{\Phi})_{J|\boldsymbol{a}}$ and the
function $f^{*}\colon\\{0,1\\}^{J}\to{\mathbb{Z}}_{p}$ represented by $q^{*}$.

We claim that $f^{*}$ satisfies the requirements of Lemma 5.6. First,
$|J|=p^{\ell-1}\cdot p^{\ell-1}=p^{2\ell-2}$ is a prime power of $p$. Also,
$f^{*}(\vec{0})=1$ since otherwise $\Phi(K_{1,k-1})=1$ by monotonicity which
leads to the first case. Moreover, $f^{*}(\vec{1})=0$ since otherwise
$\Phi(K_{k-1}+K_{1})=0$ by monotonicity which leads to the second case. In
particular, $f^{*}(\vec{0})\neq f^{*}(\vec{1})$. Also, $f^{*}$ is transitive
by the same arguments as in Claim 5.11

By Lemma 5.6 we get that $\deg_{p}(f^{*})=|J|$. By Equation (13) and Lemma 4.3
this implies that there is some $J\subseteq S\subseteq E(K_{k})$ such that
$\widehat{\Phi}(K_{k}[S])\neq 0\bmod p$. Hence, we can set $H\coloneqq
K_{k}[S]$. Observe that $|V|=|W|=s=p^{\ell-1}$ and the complete bipartite
graph between $V$ and $W$ is a subgraph of $H$ since $J\subseteq E(H)$.

This completes the induction. To finish the proof we note that
$p^{\ell-1}>\frac{k}{p^{2}}$. ∎

By combining Theorem 5.5 for $p=2$ with Theorems 3.4(a) and 3.5(b), we obtain
the following corollary which improves on the results obtained in [16].

######  Corollary 5.12.

There are $N_{0},\delta>0$ such that the following holds. Let $k\geq N_{0}$
and let $\Phi$ be a $k$-vertex graph property that is monotone and not
$k$-trivial. Then there is no algorithm that solves
$\\#\textnormal{{IndSub}}(\Phi)$ in time $O(n^{\delta\cdot k})$ unless ETH
fails.

Moreover, for every computable graph property $\Phi$ that is monotone on
$k$-vertex graphs and not $k$-trivial for infinitely many $k$, the problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

Also, by combining Theorem 5.5 with Theorems 3.4(b) and 3.5(c), we obtain
hardness for modular counting.

######  Corollary 5.13 (Theorem 1.3 restated).

Let $p$ be a fixed prime. Then there are $N_{0},\delta>0$ such that the
following holds. Let $k\geq N_{0}$ and let $\Phi$ be a $k$-vertex graph
property that is monotone and not $k$-trivial. Then there is no algorithm that
solves $\\#_{p}\textnormal{{IndSub}}(\Phi)$ in time $O(n^{\delta\cdot k})$
unless rETH fails.

Moreover, for every computable graph property $\Phi$ that is monotone on
$k$-vertex graphs and not $k$-trivial for infinitely many $k$, the problem
$\\#_{p}\textnormal{{ParIndSub}}(\Phi)$ is
$\textnormal{{Mod}}_{p}\textnormal{{W[1]}}$-hard.

###  5.3 Fully Symmetric Properties

We say that a $k$-vertex graph property $\Phi$ is _fully symmetric_ if
$\Phi(G)=\Phi(G^{\prime})$ for all $k$-vertex graphs $G,G^{\prime}$ with
$|E(G)|=|E(G^{\prime})|$. In other words, $\Phi$ is fully symmetric if it only
depends on the number of edges. As usual, we say a graph property $\Phi$ is
_fully symmetric on $k$-vertex graphs_ if $\Phi^{(k)}$ is fully symmetric.
After a series of partial results on the hardness of fully symmetric
properties [26, 28, 44], it was shown in [45] that
$\\#\textnormal{{IndSub}}(\Phi)$ is hard for every non-trivial, fully
symmetric $k$-vertex graph property. However, [45] could only rule out
algorithms with running time $n^{o(k/\sqrt{\log k})}$ for
$\\#\textnormal{{IndSub}}(\Phi)$ assuming ETH. In the following, we give a
simpler proof of hardness and obtain lower bounds that are tight under ETH.

Our proof relies on the following theorem from [48]. A Boolean function
$f\colon\\{-1,1\\}^{m}\to{\mathbb{R}}$ is _fully symmetric_ if
$f(\boldsymbol{a})=f(\boldsymbol{a}^{\sigma})$ for every
$\boldsymbol{a}\in\\{-1,1\\}^{m}$ and every $\sigma\in S_{m}$, i.e.,
$f(\boldsymbol{a})$ only depends on the number of $1$-entries in
$\boldsymbol{a}$. Observe that a property $\Phi$ on $k$-vertex graphs is fully
symmetric if and only if $f_{\Phi}$ is fully symmetric.

######  Theorem 5.14 ([48, Theorem 2.8]).

Let $f\colon\\{-1,1\\}^{m}\to\\{0,1\\}$ be a Boolean function that is fully
symmetric and non-constant. Then $\deg(f)\geq p-1$ where $p$ is the largest
prime number such that $p\leq m+1$.

We note that [48, Theorem 2.8] is stated in a slightly different form, but the
version stated here immediately follows from the proof. We also remark that
for every $m\geq 2$ there is a prime $p\leq m$ such that $p\geq
m-O(m^{0.525})$ using known estimates on the maximal gap between consecutive
prime numbers [5].

######  Theorem 5.15.

Let $k\geq 2$. Suppose $\Phi$ is a $k$-vertex graph property that is fully
symmetric and not $k$-trivial. Then there is a $k$-vertex graph $H$ such that
$\widehat{\Phi}(H)\neq 0$ and $K_{\ell}$ is a subgraph of $H$ where $\ell\geq
2$ is maximal such that

$\binom{\ell}{2}+1\leq p\leq\binom{k}{2}+1$

for some prime $p$.

###### Proof.

Let $m\coloneqq p-1$ and note that $m\geq 1$. Then

$\binom{\ell}{2}\leq m\leq\binom{k}{2}.$

So there is a set $J\subseteq E(K_{k})$ such that $|J|=m$ and
$E(K_{\ell})\subseteq J$. Let us write $\overline{J}\coloneqq
E(K_{k})\setminus J$.

######  Claim 5.16.

There is a tuple $\boldsymbol{z}\in\\{-1,1\\}^{\overline{J}}$ such that the
restriction

$f^{*}=(f_{\Phi})_{J|\boldsymbol{z}}\colon\\{-1,1\\}^{J}\to\\{0,1\\}$

of $f_{\Phi}$ to $J$ using $\boldsymbol{z}$ is fully symmetric and non-
constant.

###### Proof.

We first show that $f^{*}=(f_{\Phi})_{J|\boldsymbol{z}}$ is fully symmetric
for every tuple $\boldsymbol{z}\in\\{-1,1\\}^{\overline{J}}$. Indeed, let
$\sigma\in\operatorname{Sym}(J)$ be a permutation of $J$, and let
$\sigma^{*}\in\operatorname{Sym}(E(K_{k}))$ be the unique extension of
$\sigma$ that fixes all points outside of $J$. Then
$f^{*}(\boldsymbol{a})=f_{\Phi}(\boldsymbol{a},\boldsymbol{z})=f_{\Phi}((\boldsymbol{a},\boldsymbol{z})^{\sigma^{*}})=f_{\Phi}((\boldsymbol{a}^{\sigma},\boldsymbol{z}))=f^{*}(\boldsymbol{a}^{\sigma})$
where the second equality holds since $f_{\Phi}$ is fully symmetric.

So it remains to argue that there is some
$\boldsymbol{z}\in\\{-1,1\\}^{\overline{J}}$ such that
$(f_{\Phi})_{J|\boldsymbol{z}}$ is non-constant. Suppose towards a
contradiction that $(f_{\Phi})_{J|\boldsymbol{z}}$ is constant for every
$\boldsymbol{z}\in\\{-1,1\\}^{\overline{J}}$. This means that for every
$\boldsymbol{z}\in\\{-1,1\\}^{\overline{J}}$ there is some
$\alpha(\boldsymbol{z})\in\\{0,1\\}$ such that $(f_{\Phi})_{J|\boldsymbol{z}}$
always evaluates to $\alpha(\boldsymbol{z})$. Since $f_{\Phi}$ is non-
constant, there are
$\boldsymbol{z}_{1},\boldsymbol{z}_{2}\in\\{-1,1\\}^{\overline{J}}$ such that
$\alpha(\boldsymbol{z}_{1})\neq\alpha(\boldsymbol{z}_{2})$. Additionally, we
may assume that $\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$ only differ in
one entry. But now there are
$\boldsymbol{y}_{1},\boldsymbol{y}_{2}\in\\{-1,1\\}^{J}$ such that
$(\boldsymbol{y}_{1},\boldsymbol{z}_{1})$ and
$(\boldsymbol{y}_{2},\boldsymbol{z}_{2})$ have the same number of $1$-entries
since $m\geq 1$. So
$f_{\Phi}(\boldsymbol{y}_{1},\boldsymbol{z}_{1})=\alpha(\boldsymbol{z}_{1})\neq\alpha(\boldsymbol{z}_{2})=f_{\Phi}(\boldsymbol{y}_{2},\boldsymbol{z}_{2})$.
But this is a contradiction since $f_{\Phi}$ is fully symmetric. ∎

So $\deg(f^{*})=m$ by Theorem 5.14 which implies that $\widehat{f^{*}}(J)\neq
0$. By Equation (5) there is some set $T\subseteq\overline{J}$ such that
$\widehat{f}_{\Phi}(J\cup S)\neq 0$. We may suppose that $S$ is chosen to be
inclusion-wise maximal. Then $\widehat{\Phi}(K_{k}[J\cup S])\neq 0$ by Lemma
4.1. To finish the proof observe that $K_{\ell}$ is a subgraph of $H\coloneqq
K_{k}[J\cup S]$ since $E(K_{\ell})\subseteq J$. ∎

Note that, by Bertrand’s Postulate, it is always possible to choose
$\ell\geq\frac{k}{2}$. In fact, using the estimate on the maximal gap between
consecutive prime numbers [5] discussed above, it is possible to choose
$\ell\geq k-O(k^{0.025})$. So by combining Theorem 5.15 with Theorems 3.4(a)
and 3.5(b), we obtain the following.

######  Corollary 5.17 (Theorem 1.4 restated).

There are $N_{0},\delta>0$ such that the following holds. Let $k\geq N_{0}$
and let $\Phi$ be a $k$-vertex graph property that is fully symmetric and not
$k$-trivial. Then there is no algorithm that solves
$\\#\textnormal{{IndSub}}(\Phi)$ in time $O(n^{\delta\cdot k})$ unless ETH
fails.

Moreover, for every computable graph property $\Phi$ that is fully symmetric
on $k$-vertex graphs and not $k$-trivial for infinitely many $k$, the problem
$\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

We note that the second part of the corollary has already been obtained in
[45] using different arguments, but the first part has not been known prior to
this work.

###  5.4 Invariants with Few Distinct Hamming Weights

In this section, we show that the polynomial interpretation of properties
underlying the Fourier transform also entails lower bounds for properties (and
even graph invariants) $\Phi$ that avoid a superlinear number of Hamming
weights. In particular, our theorem allows us to recover [26, Theorem 3.4],
which yields hardness when $\Phi$ holds only for $o(k^{2})$ distinct Hamming
weights, and [45, Main Theorem 5], which applies whenever $\omega(k)$ Hamming
weights are avoided. Our result even holds for graph invariants rather than
properties, and it also rules out $n^{o(\beta(k)/\sqrt{\log\beta(k)})}$ time
algorithms for $\\#\textnormal{{ParIndSub}}(\Phi)$ under ETH; see the
defintion of $\beta$ below.

Given a $k$-vertex graph invariant $\Phi$, define its _Hamming weight set_ as
${\sf hw}(\Phi)\coloneqq\\{|E(H)|\mid H\in\Phi\\}.$ In the following, and
throughout this section, let $m\coloneqq\binom{k}{2}$. Then ${\sf
hw}(\Phi)\subseteq\\{0,\ldots,m\\}$ is the set of all edge-counts (i.e,
Hamming weights, when viewed as bitstrings) among the graphs in $\Phi$. We
then define a value that counts the avoided Hamming weights, except when
$\Phi$ is empty, as

$\beta_{\Phi}=\begin{cases}0&\text{if }|{\sf hw}(\Phi)|=0\\\
\binom{k}{2}-|{\sf hw}(\Phi)|&\text{otherwise}.\end{cases}$

For a general graph invariant $\Phi$ and $k\in{\mathbb{N}}$, we define
$\beta_{\Phi}(k)\coloneqq\beta_{\Phi^{(k)}}$.

######  Lemma 5.18.

For every $k$-vertex graph invariant $\Phi$ with $\Phi(G)\geq 0$ for all
graphs $G$, there is a $k$-vertex graph $H$ with $\widehat{\Phi}(H)\neq 0$ and
$|E(H)|\geq\beta_{\Phi}$.

###### Proof.

We assume that $|{\sf hw}(\Phi)|\notin\\{0,m\\}$, as the lemma holds vacuously
otherwise. Let $q_{\Phi}(\boldsymbol{x})$ be the multivariate polynomial from
Equation (9) representing $\Phi$ over $\\{0,1\\}^{m}$. If
$q_{\Phi}(\boldsymbol{x})$ contains a monomial of degree $d$, then Lemma 4.3
yields $\widehat{\Phi}(H)\neq 0$ for some graph $H$ with $d$ edges. So it
suffices to prove that $\deg(q_{\Phi})\geq m-|{\sf hw}(\Phi)|$.

We consider the symmetric polynomial

$q_{\Phi}^{\mathrm{symm}}(x_{1},\ldots,x_{m})=\sum_{\pi\in
S_{m}}q_{\Phi}(x_{\pi(1)},\ldots,x_{\pi(m)}).$

For $a_{1},\ldots,a_{m}\in\\{0,1\\}$, we have
$q_{\Phi}^{\mathrm{symm}}(a_{1},\ldots,a_{m})\neq 0$ if and only if
$a_{1}+\ldots+a_{m}\in{\sf hw}(\Phi)$. Indeed, every $H$ with $\Phi(H)\neq 0$
and $|E(H)|=a_{1}+\ldots+a_{m}$ contributes a positive term to the sum on the
right-hand side, and only such $H$ can contribute. Being positive, the values
from different terms cannot cancel in the overall summation.

This symmetric polynomial can be “compressed” to a univariate one. More
precisely, by [38, Lemma 3.2] (see also [35]), there exists a univariate
polynomial $\tilde{q}$ such that, for all $a_{1},\ldots,a_{m}\in\\{0,1\\}$, we
have

$\tilde{q}(a_{1}+\ldots+a_{m})=q_{\Phi}^{\mathrm{symm}}(a_{1},\ldots,a_{m}).$

For integers $z\in\\{0,\ldots,m\\}$, we thus have $\tilde{q}(z)\neq 0$ if and
only if $z\in{\sf hw}(\Phi)$. Since $|{\sf hw}(\Phi)|\notin\\{0,m\\}$, we have
that $\tilde{q}$ is not the zero polynomial. But since $\tilde{q}$ has
$m-|{\sf hw}(\Phi)|$ roots, its degree is at least $m-|{\sf hw}(\Phi)|$. It
follows that

$\deg(q_{\Phi})\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\deg(q_{\Phi}^{\mathrm{symm}})\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\deg(\tilde{q})\leavevmode\nobreak\ \geq\leavevmode\nobreak\ m-|{\sf
hw}(\Phi)|\leavevmode\nobreak\ \geq\leavevmode\nobreak\ \beta_{\Phi}.$

This proves the lemma via Lemma 4.3. ∎

In the following, we that the assumption of nonnegativity on the graph
invariant $\Phi$ can be dropped by passing from $\Phi$ to its pointwise square
and observing that this at most doubles the degree of the representing
polynomial. More formally, for two graph invariants $\Phi_{1},\Phi_{2}$, the
_point-wise product_ is the graph invariant $\Psi=\Phi_{1}\cdot\Phi_{2}$
defined via $\Psi(G)=\Phi_{1}(G)\cdot\Phi_{2}(G)$.

######  Lemma 5.19.

Let $\Phi_{1},\Phi_{2}$ be graph invariants and let
$\Psi\coloneqq\Phi_{1}\cdot\Phi_{2}$. Then, for every graph $H$,

$\widehat{\Psi}(H)=\sum_{\begin{subarray}{c}S_{1},S_{2}\subseteq E(H)\colon\\\
S_{1}\cup
S_{2}=E(H)\end{subarray}}\widehat{\Phi}_{1}(H[S_{1}])\cdot\widehat{\Phi}_{2}(H[S_{2}]).$

###### Proof.

Suppose $k\coloneqq|V(H)|$. Let $m\coloneqq\binom{k}{2}$ and let
$q(\boldsymbol{x})\coloneqq q_{\Psi}(\boldsymbol{x})$ be the multilinear
polynomial from (9) representing $\Psi$ over $\\{0,1\\}^{m}$. Likewise, let
$q_{1}(\boldsymbol{x})\coloneqq q_{\Phi_{1}}(\boldsymbol{x})$ and
$q_{2}(\boldsymbol{x})\coloneqq q_{\Phi_{2}}(\boldsymbol{x})$ be the
multilinear polynomials representing $\Phi_{1}$ and $\Phi_{2}$.

Given a polynomial $r(\boldsymbol{x})$ with maximum degree $2$ per variable,
let $r_{\textsf{red}}$ denote the polynomial obtained by replacing $x_{i}^{2}$
with $x_{i}$ in every monomial. We clearly have
$r(\boldsymbol{a})=r_{\textsf{red}}(\boldsymbol{a})$ for all
$\boldsymbol{a}\in\\{0,1\\}^{m}$. Since every multilinear polynomial in $m$
indeterminates is determined by its evaluations on all values
$\boldsymbol{a}\in\\{0,1\\}^{m}$, we obtain
$q(\boldsymbol{x})=(q_{1}(\boldsymbol{x})\cdot
q_{2}(\boldsymbol{x}))_{\textsf{red}}$, since
$q(\boldsymbol{a})=q_{1}(\boldsymbol{a})\cdot q_{2}(\boldsymbol{a})$ for all
$\boldsymbol{a}\in\\{0,1\\}^{m}$. We now consider the coefficients of
$q(\boldsymbol{x})$.

In the product $q_{1}(\boldsymbol{x})\cdot q_{2}(\boldsymbol{x})$, monomials
$x^{S}$ represent multisets $S$ of edges from $E(H)$ with multiplicity at most
$2$ per edge. Let $\widehat{q}_{i}(S)$ denote the coefficient of $x^{S}$ in
$q_{i}(\boldsymbol{x})$ for $i\in\\{1,2\\}$; we have
$\widehat{q}_{i}(S)=\widehat{\Phi}_{i}(K_{k}[S])$ by Lemma 4.3. By collecting
monomials after polynomial multiplication, the coefficient of $x^{S}$ in
$q_{1}(\boldsymbol{x})\cdot q_{2}(\boldsymbol{x})$ equals

$\sum_{\begin{subarray}{c}S_{1},S_{2}\subseteq S\colon\\\ S_{1}\cup
S_{2}=S\end{subarray}}\widehat{\Phi}_{1}(K_{k}[S_{1}])\cdot\widehat{\Phi}_{2}(K_{k}[S_{2}]),$
(14)

where the union $S_{1}\cup S_{2}$ is interpreted as a multiset union, i.e.,
counting copies. Collecting monomials after substitution, it follows that the
coefficient $\widehat{q}(S)=\widehat{\Psi}(H[S])$ of $x^{S}$ in
$q(\boldsymbol{x})=(q_{1}(\boldsymbol{x})\cdot
q_{2}(\boldsymbol{x}))_{\textsf{red}}$ for a _set_ (rather than multiset)
$S\subseteq E(H)$ also equals (14), but with $S_{1}\cup S_{2}$ interpreted as
a set union, i.e., not counting copies. This proves the lemma, as
$\widehat{q}_{i}(S)=\widehat{\Phi}_{i}(K_{k}[S])$ and
$\widehat{q}(S)=\widehat{\Psi}(K_{k}[S])$. ∎

Applying Lemma 5.19 to $\Psi\coloneqq\Phi\cdot\Phi$, we obtain the following
variant of Lemma 5.18.

######  Theorem 5.20.

For every $k$-vertex graph invariant $\Phi$, there is a $k$-vertex graph $H$
with $\widehat{\Phi}(H)\neq 0$ and $|E(H)|\geq\beta_{\Phi}/2$.

###### Proof.

Let $m=\binom{k}{2}$. For $\Psi:=\Phi\cdot\Phi$, we have $\Psi(G)\geq 0$ for
all graphs $G$. Moreover, the graph invariants $\Psi$ and $\Phi$ satisfy ${\sf
hw}(\Psi)={\sf hw}(\Phi)$ and thus $\beta_{\phi}=\beta_{\Psi}$. By Lemma 5.18,
there is a $k$-vertex graph $H^{\prime}$ with $\widehat{\Psi}(H^{\prime})\neq
0$ and $|E(H^{\prime})|\geq\beta_{\Psi}=\beta_{\Phi}$. By Lemma 5.19, the set
$E(H^{\prime})$ can be written as $E(H^{\prime})=S_{1}\cup S_{2}$ with
$\widehat{\Phi}(H^{\prime}[S_{1}])\neq 0$ and
$\widehat{\Phi}(H^{\prime}[S_{2}])\neq 0$. It follows that one of $S_{1}$ or
$S_{2}$ contains at least $\beta_{\Phi}/2$ edges; choose $H$ to be the
corresponding graph $H^{\prime}[S_{1}]$ or $H^{\prime}[S_{2}]$. ∎

By combining Theorem 5.20 with Theorems 3.4(a) and 3.5(a), we obtain the
following. For functions $f,g:{\mathbb{N}}\to{\mathbb{Q}}$, we say that
$f\in\omega_{\mathrm{inf}}(g)$ if there is an infinite sequence
$n_{0},n_{1},n_{2},\ldots$ such that $f(n_{i})\in\omega(g(n_{i}))$. Note that
$f(n_{i})$ and $g(n_{i})$ take $i$ as input. Recall that
$\beta_{\Phi}(k)=\beta_{\Phi^{(k)}}$, where $\Phi^{(k)}$ is the $k$-th slice
of $\Phi$.

######  Corollary 5.21 (Theorem 1.5 restated).

There are $N_{0},\delta>0$ such that the following holds. Let $k\geq N_{0}$
and $0<d\leq k/2$, let $\Phi$ be a $k$-vertex graph invariant, and let

$\beta_{\Phi}\geq dk.$

Then there is no algorithm that solves $\\#\textnormal{{IndSub}}(\Phi)$ in
time $O(n^{\delta\cdot d/\sqrt{\log d}})$ unless ETH fails.

Moreover, for every computable graph invariant $\Phi$ such that

$\beta_{\Phi}(k)\in\omega_{\mathrm{inf}}(k),$

the problem $\\#\textnormal{{ParIndSub}}(\Phi)$ is #W[1]-hard.

##  6 All Degrees are Even

In this section we consider the property $\Phi_{\sf even}$ defined via

$\Phi_{\sf even}(G)=\begin{cases}1&\text{if }\deg_{G}(v)\equiv 0\bmod 2\text{
for all }v\in V(G)\\\ 0&\text{otherwise,}\end{cases}$

i.e., $\Phi_{\sf even}$ contains exactly those graphs where all vertices have
even degree. This property turns out to be interesting since
$\widehat{\Phi}_{\sf even}(H)=0$ for most graphs $H$. While
$\\#\textnormal{{ParIndSub}}(\Phi_{\sf even})$ is still #W[1]-hard, this
property allows us to also derive non-trivial upper bounds on the complexity.
Moreover, the fact that $\widehat{\Phi}_{\sf even}(H)=0$ for most graphs $H$
surprisingly allows us to obtain hardness of
$\\#\textnormal{{ParIndSub}}(\Phi)$ for other properties $\Phi$.

The starting point for our analysis is the observation that each slice
$\Phi_{\sf even}^{(k)}$ forms a vector space over the $2$-element field
${\mathbb{Z}}_{2}$. Indeed, $\Phi_{\sf even}^{(k)}$ contains exactly those
graphs that are in the _cycle space_ of $K_{k}$. This allows us to use basic
tools from linear algebra to determine exactly which graphs $H$ satisfy
$\widehat{\Phi}_{\sf even}(H)\neq 0$.

######  Theorem 6.1.

The graphs $H$ satisfying $\widehat{\Phi}_{\sf even}(H)\neq 0$ are precisely
the bipartite graphs.

###### Proof.

Let $H$ be a bipartite graph. For every $S\subseteq E(H)$ with $\Phi_{\sf
even}(H[S])=1$ we have $|S|$ even, so every term in

$\widehat{\Phi}_{\sf even}(H)=\sum_{S\subseteq E(H)}(-1)^{|S|}\cdot\Phi_{\sf
even}(H[S])$

is non-negative. Since the term $\Phi_{\sf even}(H[\emptyset])=1$ is strictly
positive, we get $\widehat{\Phi}_{\sf even}(H)\neq 0$.

Next, let $H$ be a non-bipartite graph and let $C^{*}\subseteq E(H)$ be the
edges of an odd cycle in $H$. Consider the cycle space of $H$, i.e., the set
of all subgraphs in which all vertices have even degree:

${\mathcal{C}}\coloneqq\\{S\subseteq E(H)\mid H[S]\in\Phi_{\sf even}\\}.$

As noted above, ${\mathcal{C}}$ can be viewed as a subspace of
${\mathbb{Z}}_{2}^{E(H)}$ where each $C\in{\mathcal{C}}$ is identified with
its corresponding indicator vector $v_{C}\in{\mathbb{Z}}_{2}^{E(H)}$. Slightly
abusing notation, we identify $C$ with $v_{C}$.

######  Claim 6.2.

There is a basis $\\{C_{1},\dots,C_{d}\\}\subseteq{\mathcal{C}}$ such that
$|C_{i}|$ is odd for every $i\in[d]$.

###### Proof.

Clearly, there is a basis ${\mathcal{B}}$ of ${\mathcal{C}}$ such that
$C^{*}\in{\mathcal{B}}$. But then

${\mathcal{B}}^{*}\coloneqq\\{C\mid C\in{\mathcal{B}},|C|\text{ is
odd}\\}\cup\\{C\oplus C^{*}\mid C\in{\mathcal{B}},|C|\text{ is even}\\}$

is also a basis of ${\mathcal{C}}$, where $C\oplus C^{*}$ denotes the
symmetric difference of $C$ and $C^{*}$ (i.e., the corresponding vectors over
${\mathbb{Z}}_{2}$ are added). Every element of ${\mathcal{B}}^{*}$ has odd
cardinality, as desired. ∎

Now let $\\{C_{1},\dots,C_{d}\\}$ be the basis constructed in the claim. Since
$|C_{i}|$ is odd for every $i\in[d]$, we get that

$|\bigoplus_{i\in M}C_{i}|\equiv|M|\mod 2$

for every $M\subseteq[d]$. It follows that

$\displaystyle\widehat{\Phi}_{\sf even}(H)$ $\displaystyle=\sum_{S\subseteq
E(H)}(-1)^{|S|}\cdot\Phi_{\sf even}(H[S])$
$\displaystyle=\sum_{C\in{\mathcal{C}}}(-1)^{|C|}$
$\displaystyle=\sum_{M\subseteq[d]}(-1)^{|\bigoplus_{i\in M}C_{i}|}$
$\displaystyle=\sum_{M\subseteq[d]}(-1)^{|M|}$ $\displaystyle=0$

where the last equality follows from the Binomial Theorem. ∎

######  Remark 6.3.

A weaker version of Theorem 6.1 can also be obtained via the Fourier
expansion. Let $k\geq 1$ and let $\Psi\coloneqq\Phi_{\sf even}^{(k)}$. The set
$\operatorname{supp}(f_{\Psi})$ forms a subspace of ${\mathbb{Z}}_{2}^{m}$ for
$m\coloneqq\binom{k}{2}$. Then $\operatorname{supp}(\widehat{f}_{\Psi})$ is
the complement space of this space, see [39, Proposition 3.11]. Since
$\operatorname{supp}(f_{\Psi})$ corresponds to the _cycle space_ of $K_{k}$,
we obtain that $\operatorname{supp}(\widehat{f}_{\Psi})$ corresponds to the
_cut space_ of $K_{k}$. It follows that the $\widehat{f}_{\Psi}$-maximal sets
are precisely the edge sets of complete bipartite graphs on $k$ vertices. By
Lemma 4.1, we can therefore conclude that

  1. 1.

$\widehat{\Phi}_{\sf even}(H)\neq 0$ for all complete bipartite graphs $H$,
and

  2. 2.

if $\widehat{\Phi}_{\sf even}(H)\neq 0$ then $H$ is bipartite.

We remark that this weaker statement is sufficient to obtain all results
presented in the remainder of this section. Our Theorem 6.1 shows that _all_
bipartite graphs $H$ are in the support of $\widehat{\Phi}_{\sf even}(H)$, not
just the complete bipartite graphs.

By combining Theorem 5.15 with Theorems 3.4(a) and 3.5(b), we obtain the
following.

######  Corollary 6.4.

There are $N_{0},\delta>0$ such that for every $k\geq N_{0}$ there is no
algorithm that solves $\\#\textnormal{{IndSub}}(\Phi_{\sf even}^{(k)})$ in
time $O(n^{\delta\cdot k})$ unless ETH fails. Moreover,
$\\#\textnormal{{ParIndSub}}(\Phi_{\sf even})$ is #W[1]-hard.

In contrast to the results in Section 5, Theorem 6.1 also allows us to obtain
a non-trivial upper bound on the complexity of
$\\#\textnormal{{ParIndSub}}(\Phi_{\sf even})$. This follows from Theorem 3.6,
by observing that each bipartite graph with $k$ vertices has vertex cover
number at most $\lfloor k/2\rfloor$.

######  Corollary 6.5.

The problem $\\#\textnormal{{ParIndSub}}(\Phi_{\sf even})$ can be solved in
time $f(k)\cdot n^{\lfloor k/2\rfloor+1}$ for some computable function $f$.

Observe that the algorithm from the last corollary achieves roughly a
quadratic speed-up over the brute-force algorithm, which runs in time
$f(k)\cdot n^{k}$ for some computable function $f$. We note that we are not
aware of any other non-meager property $\Phi$ that is “fundamentally
different” from $\Phi_{\sf even}$ for which a similar (or better) running time
can be achieved.333If we complement the property $\Phi_{\sf even}$, or we
complement every graph in $\Phi_{\sf even}$, then Theorem 6.1 still holds and
the same runtime can be achieved. We do not view such variants of the property
$\Phi_{\sf even}$ as “fundamentally different”.

Next, we use Theorem 6.1 to obtain hardness results for
$\\#\textnormal{{IndSub}}(\Phi)$ for other graph invariants. Indeed, Theorem
6.1 shows that the property $\\#\textnormal{{IndSub}}(\Phi,k,$) is “relatively
easy” in the sense that only few graphs have non-zero alternating enumerator.
Surprisingly, this fact allows us to prove hardness results for other graph
invariants by exploiting Lemma 5.19.

More precisely, to obtain hardness results for
$\\#\textnormal{{IndSub}}(\Phi)$ for a $k$-vertex graph invariant $\Phi$, the
key idea is to take a point-wise product $\Psi\coloneqq\Phi_{\sf
even}\cdot\Phi$. If $\Psi(H^{*})\neq 0$ for some $k$-vertex graph $H^{*}$ that
is “far away” from being bipartite, we can conclude that there is some
$k$-vertex graph $H$ with many edges such that $\widehat{\Phi}(H)\neq 0$ using
Lemma 5.19. This approach is demonstrated in the following corollary.

######  Corollary 6.6.

For every $k$-vertex graph property $\Phi$ whose intersection with $\Phi_{\sf
even}$ is non-empty and contains only bipartite graphs, there is a $k$-vertex
graph $H$ such that $\widehat{\Phi}(H)\neq 0$ and $K_{\ell}$ is a subgraph of
$H$ for some $\ell\geq\frac{k}{2}$.

###### Proof.

Let $\Psi\coloneqq\Phi\cdot\Phi_{\sf even}$. Note that $\Psi$ is also a graph
property that corresponds to the intersection of $\Phi$ and $\Phi_{\sf even}$.
Then every $k$-vertex graph $H\in\Psi$ has an even number of edges. So

$\widehat{\Psi}(K_{k})=\sum_{S\subseteq
E(K_{k})}(-1)^{|S|}\cdot\Psi(K_{k}[S])=\sum_{S\subseteq
E(K_{k})}\Psi(K_{k}[S])$

denotes the number of $k$-vertex graphs in $\Psi$. Since there is at least one
such graph, we conclude that $\widehat{\Psi}(K_{k})\neq 0$.

By Lemma 5.19 there are sets $S,S_{\sf even}\subseteq E(K_{k})$ such that
$S\cup S_{\sf even}=E(K_{k})$ and $\widehat{\Phi}(K_{k}[S])=1$ and
$\widehat{\Phi}_{\sf even}(K_{k}[S_{\sf even}])=1$. We set $H\coloneqq
K_{k}[S]$. Since $\widehat{\Phi}_{\sf even}(K_{k}[S_{\sf even}])=1$, we
conclude that $K_{k}[S_{\sf even}]$ is bipartite by Theorem 6.1. Let $V,W$
denote a bipartition of $K_{k}[S_{\sf even}]$. Then $\binom{V}{2}\subseteq S$
and $\binom{W}{2}\subseteq S$ since $S\cup S_{\sf even}=E(K_{k})$. In
particular, $H$ contains a clique of size at least $\frac{k}{2}$. ∎

We can also combine a similar approach with the Uncertainty Principle (see
Lemma 2.3) to obtain a variant of Theorem 5.1.

######  Theorem 6.7.

For every $0<\varepsilon<1$ there are $\delta,k_{0}>0$ such that the following
holds. Let $k\geq k_{0}$ and let $\Phi$ be a $k$-vertex graph invariant such
that

$1\leq|\operatorname{supp}(\Phi\cdot\Phi_{\sf
even})|\leq\left(\sqrt{2}-\varepsilon\right)^{\binom{k}{2}}.$

Then there is a $k$-vertex graph $H$ such that $\widehat{\Phi}(H)\neq 0$ and
$|E(H)|\geq\delta\cdot\binom{k}{2}$.

Observe that, in comparison with Theorem 5.1, we only require
$\Phi\cdot\Phi_{\sf even}$ to have small support, but we need a stronger upper
bound on its size.

Toward the proof of Theorem 6.7, we require the followings tool. Let $G$ be a
graph. A set $S\subseteq E(G)$ is an _edge bipartization_ if $G-S\coloneqq
G[E(G)\setminus S]$ is bipartite. The _edge bipartization number_ of $G$ is
the minimum integer $k\geq 0$ such that there is an edge bipartization
$S\subseteq E(G)$ of size $|S|=k$.

######  Lemma 6.8.

For every $0<\varepsilon<1$ there are $\delta,k_{0}>0$ such that the following
holds. Let $k\geq k_{0}$ and let ${\mathcal{C}}$ be a set of graphs with
vertex set $[k]$ such that

$|{\mathcal{C}}|\geq\left(\sqrt{2}+\varepsilon\right)^{\binom{k}{2}}.$

Then there is some $G\in{\mathcal{C}}$ with edge bipartization number at least
$\delta\cdot\binom{k}{2}$.

###### Proof.

Let $0<\varepsilon<1$ and suppose $k_{0}$ is a sufficiently large integer
(depending on $\varepsilon$). Also let

$\alpha\coloneqq\log_{2}\left(1+\frac{\varepsilon}{\sqrt{2}\cdot 3}\right).$

Then $0<\alpha<1$ and there is some $0<\delta<\frac{1}{2}$ such that
$\alpha=\mathbf{H}(\delta)$ where $\mathbf{H}$ is the entropy function.

Now let $k\geq k_{0}$. Also let ${\mathcal{B}}$ denote the set of bipartite
graphs with vertex set $[k]$. By [18, Lemma 7] it holds that

$|{\mathcal{B}}|\leq\left(\sqrt{2}+\frac{\varepsilon}{3}\right)^{\binom{k}{2}}$

since $k\geq k_{0}$ is sufficiently large. Next, let ${\mathcal{H}}$ denote
the set of graphs $H$ with vertex set $[k]$ and
$|E(H)|\leq\delta\cdot\binom{k}{2}$. Then, by Lemma 2.4, we get

$|{\mathcal{H}}|\leq
2^{\mathbf{H}(\delta)\cdot\binom{k}{2}}=\left(1+\frac{\varepsilon}{\sqrt{2}\cdot
3}\right)^{\binom{k}{2}}.$

We define ${\mathcal{B}}\otimes{\mathcal{H}}$ to be the set of graphs $G$ with
vertex set $[k]$ such that $E(G)=E(B)\cup E(H)$ for some $B\in{\mathcal{B}}$
and $H\in{\mathcal{H}}$. Then every graph $G$ with vertex set $[k]$ and edge
bipartization number at most $\delta\cdot\binom{k}{2}$ is contained in
${\mathcal{B}}\otimes{\mathcal{H}}$. Also,

$\displaystyle|{\mathcal{B}}\otimes{\mathcal{H}}|\leq|{\mathcal{B}}|\cdot|{\mathcal{H}}|$
$\displaystyle\leq\left(\sqrt{2}+\frac{\varepsilon}{3}\right)^{\binom{k}{2}}\cdot\left(1+\frac{\varepsilon}{\sqrt{2}\cdot
3}\right)^{\binom{k}{2}}$
$\displaystyle=\left(\sqrt{2}+\frac{\varepsilon}{3}+\frac{\varepsilon}{3}+\frac{\varepsilon^{2}}{\sqrt{2}\cdot
9}\right)^{\binom{k}{2}}<\left(\sqrt{2}+\varepsilon\right)^{\binom{k}{2}}.$

This implies that ${\mathcal{C}}$ contains some graph with edge bipartization
number at least $\delta\cdot\binom{k}{2}$. ∎

###### Proof of Theorem 6.7.

Fix some $0<\varepsilon<1$ and choose $\delta,k_{0}>0$ according to Lemma 6.8.

Let $\Psi\coloneqq\Phi\cdot\Phi_{\sf even}$ and suppose

$1\leq|\operatorname{supp}(\Psi)|\leq\left(\sqrt{2}-\varepsilon\right)^{\binom{k}{2}}.$

Since $|\operatorname{supp}(\Psi)|\geq 1$ we get that $f_{\Psi}$ is not the
zero function. By Lemma 2.3 it holds that

$|\operatorname{supp}(\widehat{f}_{\Psi})|\geq
2^{\binom{k}{2}}\cdot|\operatorname{supp}(f_{\Psi})|^{-1}=2^{\binom{k}{2}}\cdot|\operatorname{supp}(\Psi)|^{-1}\geq
2^{\binom{k}{2}}\cdot\left(\sqrt{2}-\varepsilon\right)^{-\binom{k}{2}}\geq\left(\sqrt{2}+\varepsilon\right)^{\binom{k}{2}}.$

By Lemma 6.8, there is some $S\in\operatorname{supp}(\widehat{f}_{\Psi})$ such
that $K_{k}[S]$ has edge bipartization number at least
$\delta\cdot\binom{k}{2}$. We may suppose without loss of generality that $S$
is an inclusion-wise maximal set from
$\operatorname{supp}(\widehat{f}_{\Psi})$ since adding further elements only
increases the edge bipartization number. We set $F\coloneqq K_{k}[S]$. Then
$\widehat{\Psi}(F)\neq 0$ by Lemma 4.1. Also, $F$ has edge edge bipartization
number at least $\delta\cdot\binom{k}{2}$.

Now, by Lemma 5.19 there are sets $B,S_{\sf even}\subseteq E(F)$ such that
$B\cup S_{\sf even}=E(F)$ and $\widehat{\Phi}(F[B])\neq 0$ and
$\widehat{\Phi}_{\sf even}(F[S_{\sf even}])\neq 0$. We set $H\coloneqq F[B]$.
Since $\widehat{\Phi}_{\sf even}(F[S_{\sf even}])=1$, we conclude that
$F[S_{\sf even}]$ is bipartite by Theorem 6.1. So $B$ is an edge bipartization
of $F$ and hence, $|B|\geq\delta\cdot\binom{k}{2}$. ∎

By combining Theorem 6.7 with Theorems 3.4(a) and 3.5(a), we obtain the
following.

######  Corollary 6.9 (Theorem 1.6 restated).

For every $0<\varepsilon<1$ there are $N_{0},\delta>0$ such that the following
holds. Let $k\geq N_{0}$ and let $\Phi$ be a $k$-vertex graph invariant such
that

$1\leq|\operatorname{supp}(\Phi\cdot\Phi_{\sf
even})|\leq(\sqrt{2}-\varepsilon)^{\binom{k}{2}}.$

Then there is no algorithm that solves $\\#\textnormal{{IndSub}}(\Phi)$ in
time $O(n^{\delta\cdot k/\sqrt{\log k}})$ unless ETH fails.

Moreover, for every computable graph invariant $\Phi$ such that

$1\leq|\operatorname{supp}_{k}(\Phi\cdot\Phi_{\sf
even})|\leq(\sqrt{2}-\varepsilon)^{\binom{k}{2}}$

holds for infinitely many $k$, the problem $\\#\textnormal{{ParIndSub}}(\Phi)$
is #W[1]-hard.

##  7 Weisfeiler-Leman Dimension

Besides hardness results for induced subgraph counts, our techniques also
allow us to bound or even precisely determine the Weisfeiler-Leman dimension
of such graph parameters. The $k$-dimensional Weisfeiler-Leman algorithm
($k$-WL) is a standard heuristic for testing isomorphism of graphs, but it
also has surprising connections to various other areas of computer science,
including finite model theory and machine learning [23, 24, 30, 36]. We omit a
detailed description of the WL algorithm here and refer the interested reader
to [23, 24, 30]. Indeed, the following characterization shown by Dvorák [17]
is sufficient for our purposes.

A homomorphism from a graph $F$ to a graph $G$ is a mapping $\varphi\colon
V(F)\to V(G)$ such that $\varphi(v)\varphi(w)\in E(G)$ for every edge $vw\in
E(F)$. We write $\\#\mathrm{Hom}(F\to G)$ to denote the number of
homomorphisms from $F$ to $G$. Then two graphs $G,G^{\prime}$ are
_distinguished_ by $k$-WL if $\\#\mathrm{Hom}(F\to G)\neq\\#\mathrm{Hom}(F\to
G^{\prime})$ for some graph $F$ with $\operatorname{tw}(F)\leq k$.

The _Weisfeiler-Leman dimension_ of a graph invariant $f$ is the minimal
$k\geq 1$ such that $k$-WL distinguishes between all graphs $G$ and
$G^{\prime}$ for which $f(G)\neq f(G^{\prime})$. For the graph parameters
considered in this paper, such a number $k$ indeed exists. Due to the
connections of WL to various other areas of computer science, the WL-dimension
has become a widely studied measure (see, e.g., [3, 4, 21, 22, 32, 37]). Our
results yield bounds on the WL-dimension of
$f(\star)=\\#\mathrm{IndSub}(\Phi^{(k)}\to\,\star\,)$ for various graph
invariants $\Phi$.

More precisely, combining results from [11] and [32, 37], we establish a
connection between the WL dimension and the alternating enumerator of certain
graphs with respect to $\Phi$. We start by covering the necessary tools from
[11] and [32, 37].

######  Definition 7.1.

A graph invariant $\Psi$ is a _graph motif parameter_ if there is a finite
collection of graphs ${\mathcal{L}}$ and coefficients
$\alpha_{F}\in{\mathbb{R}}$ for all $F\in{\mathcal{L}}$ such that

$\Psi(G)=\sum_{F\in{\mathcal{L}}}\alpha_{F}\cdot\\#\mathrm{Hom}(F\to G)$

for all graphs $G$.

The WL dimension of graph motif parameters has been determined in [32, 37].

######  Theorem 7.2 ([32, 37]).

Let $\Psi$ be a _graph motif parameter_ and suppose there are a finite
collection of pairwise non-isomorphic graphs ${\mathcal{L}}$ and coefficients
$\alpha_{F}\in{\mathbb{R}}\setminus\\{0\\}$ for all $F\in{\mathcal{L}}$ such
that

$\Psi(G)=\sum_{F\in{\mathcal{L}}}\alpha_{F}\cdot\\#\mathrm{Hom}(F\to G)$

for all graphs $G$. Then the WL dimension of $\Psi$ is equal to
$\max_{F\in{\mathcal{L}}}\operatorname{tw}(F)$.

Also, it has been shown in [11] that, for every graph invariant $\Phi$ on
$k$-vertex graphs, the function $\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ is a
graph motif parameter. In fact, [11] even provides explicit formulas to
determine the set ${\mathcal{L}}$ and the coefficients $\alpha_{F}$ for all
graphs $F\in{\mathcal{L}}$. For the purpose of this paper, the following
weaker version is sufficient.

For a graph $H$ consider a partition $\rho$ of $V(H)$ such that each block
$B\in\rho$ is an independent set. Then we define $H/\rho$ as the graph
obtained from $H$ by contracting each block to a single vertex. Formally, we
set $V(H/\rho)=\rho$ and $E(H/\rho)=\\{B_{1}B_{2}\mid\exists v_{1}\in
B_{1},v_{2}\in B_{2}\colon v_{1}v_{2}\in E(H)\\}$. We say a graph $F$ is a
quotient of $H$, denoted by $F\preceq H$, if $F$ is isomorphic to $H/\rho$ for
some partition $\rho$ of $V(H)$ such that each block $B\in\rho$ is an
independent set.

######  Lemma 7.3 ([11]).

Let $\Phi$ be a $k$-vertex graph invariant. Then there is a finite collection
of pairwise non-isomorphic graphs ${\mathcal{L}}$ and coefficients
$\alpha_{F}\in{\mathbb{R}}\setminus\\{0\\}$ such that

  1. (I)

$\\#\mathrm{IndSub}(\Phi\to
G)=\sum_{F\in{\mathcal{L}}}\alpha_{F}\cdot\hom(F,G)$ for all graphs $G$,

  2. (II)

$F\in{\mathcal{L}}$ for all graphs such that $\widehat{\Phi}(F)\neq 0$, and

  3. (III)

if $F\in{\mathcal{L}}$, then there is some $k$-vertex graph $H$ such that
$F\preceq H$ and $\widehat{\Phi}(H)\neq 0$.

The next lemma is an immediate consequence of Theorem 7.2 and Lemma 7.3.

######  Lemma 7.4.

Let $\Phi$ be a $k$-vertex graph invariant. Suppose there is a $k$-vertex
graph $H$ with $\widehat{\Phi}(H)\neq 0$ and $\operatorname{tw}(H)\geq\ell$.
Then the WL dimension of $\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ is at least
$\ell$.

We can combine Lemma 7.4 with Theorems 5.1, 5.5, 5.15, 5.20, 6.1 and 6.7 as
well as Lemma 5.18 and Corollary 6.6 to obtain bounds on the WL dimension of
certain graph invariants. Let us only explicitly mention the following
consequence, which follows from Theorem 5.5 by setting $p=2$ and gives a lower
bound that differs from the trivial upper bound of $k-1$ only by the constant
factor $4$.

######  Corollary 7.5.

Let $k\geq 1$ and suppose $\Phi$ is a monotone $k$-vertex graph property. Then
the WL dimension of $\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ is strictly greater
than $\frac{k}{4}$.

For $\Phi_{\sf even}$, we can even determine the WL dimension of
$\\#\mathrm{IndSub}(\Phi_{\sf even}^{(k)}\to\,\star\,)$ exactly.

######  Theorem 7.6.

For every $k\geq 2$ the WL dimension of $\\#\mathrm{IndSub}(\Phi_{\sf
even}^{(k)}\to\,\star\,)$ is equal to $\left\lfloor\frac{k}{2}\right\rfloor$.

The proof relies on the following simple lemma.

######  Lemma 7.7.

Let $H$ be a graph and $F$ a quotient of $H$. Then
$\operatorname{tw}(F)\leq\operatorname{vc}(F)\leq\operatorname{vc}(H)$.

###### Proof.

The first inequality is folklore. For the second inequality, let $\rho$ be a
partition of $H$ into independent sets, and let $C$ be a vertex cover of $H$.
Then $C/\rho\coloneqq\\{B\in\rho\mid B\cap C\neq\emptyset\\}$ is a vertex
cover of $H/\rho$. So $\operatorname{vc}(H/\rho)\leq\operatorname{vc}(H)$.
Since $F$ is a quotient of $H$, the second inequality holds. ∎

###### Proof of Theorem 7.6.

Let $B=K_{\left\lfloor k/2\right\rfloor,\left\lfloor k/2\right\rfloor}$. We
have $\operatorname{tw}(B)=\left\lfloor\frac{k}{2}\right\rfloor$ and by
Theorem 6.1, we have $\widehat{\Phi}_{\sf even}(B)\neq 0$. So the WL dimension
of $\\#\mathrm{IndSub}(\Phi_{\sf even}^{(k)}\to\,\star\,)$ is at least
$\left\lfloor\frac{k}{2}\right\rfloor$ by Lemma 7.4.

For the other direction, let $H$ be a graph such that $\widehat{\Phi}_{\sf
even}(H)\neq 0$ and let $F$ be a quotient of $H$. Then $H$ is bipartite by
Theorem 6.1 which implies that
$\operatorname{tw}(F)\leq\operatorname{vc}(H)\leq\left\lfloor\frac{k}{2}\right\rfloor$
by Lemma 7.7. This implies that the WL dimension of
$\\#\mathrm{IndSub}(\Phi_{\sf even}^{(k)}\to\,\star\,)$ is at most
$\left\lfloor\frac{k}{2}\right\rfloor$ by Theorem 7.2 and Lemma 7.3(III). ∎

##  8 Conclusion

We show that relatively straightforward applications of Fourier analysis can
yield strong complexity results for the problem of counting induced subgraphs
satisfying a fixed property $\Phi$. Our mostly self-contained paper supersedes
significant results for this problem obtained over the last decade via
different techniques. Nevertheless, several open problems remain.

  1. 1.

Most importantly, given a general non-meager property $\Phi$, is the
parameterized problem $\\#\textnormal{{ParIndSub}}(\Phi)$ indeed #W[1]-hard?
Note that this is not the case for all non-meager graph _invariants_ $\Psi$.
Indeed, consider the $k$-vertex graph invariant $\Psi$ that counts the copies
of $K_{1,k-1}$ in a $k$-vertex graph. Then the problem
$\\#\textnormal{{IndSub}}(\Psi)$ counts copies of $K_{1,k-1}$ in a graph $G$,
which can be solved in linear time.

  2. 2.

One approach towards settling the above question may be to invoke Corollary
6.9 for products $\Phi\cdot\Psi$ with other properties $\Psi$ that have at
most moderately large degree, besides $\Phi_{\sf even}$. Given a $k$-vertex
graph property $\Phi$, let $q_{k}$ for $k\in{\mathbb{N}}$ denote the maximum
value of $\operatorname{tw}(H)$ among all $k$-vertex graphs $H$ with
$\widehat{\Phi}(H)\neq 0$. Which values $q_{k}$ can be attained by a
$k$-vertex graph property $\Phi$?

  3. 3.

Finally, it is interesting to obtain tighter lower bounds for the Weisfeiler-
Leman dimension of $\\#\mathrm{IndSub}(\Phi\to\,\star\,)$ for $k$-vertex graph
invariants $\Phi$. Such bounds translate into tighter inexpressibility results
in logics and computational lower bounds for symmetric circuits.

## References

  * [1] Manindra Agrawal.  Determinant versus permanent.  In International Congress of Mathematicians. Vol. III, pages 985–997. Eur. Math. Soc., Zürich, 2006.  doi:10.4171/022-3/48.
  * [2] Omid Amini, Fedor V. Fomin, and Saket Saurabh.  Counting subgraphs via homomorphisms.  SIAM J. Discret. Math., 26(2):695–717, 2012.  doi:10.1137/100789403.
  * [3] Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky.  On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.  J. Comput. Syst. Sci., 113:42–59, 2020.  doi:10.1016/j.jcss.2020.04.003.
  * [4] 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.
  * [5] Roger C. Baker, Glyn Harman, and János Pintz.  The difference between consecutive primes. II.  Proc. London Math. Soc. (3), 83(3):532–562, 2001.  doi:10.1112/plms/83.3.532.
  * [6] Andreas Björklund, Holger Dell, and Thore Husfeldt.  The parity of set systems under random restrictions with applications to exponential time problems.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 231–242. Springer, 2015.  doi:10.1007/978-3-662-47672-7\\_19.
  * [7] Chandra Chekuri and Julia Chuzhoy.  Polynomial bounds for the grid-minor theorem.  J. ACM, 63(5):40:1–40:65, 2016.  doi:10.1145/2820609.
  * [8] Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia.  Tight lower bounds for certain parameterized np-hard problems.  Inf. Comput., 201(2):216–231, 2005.  URL: https://doi.org/10.1016/j.ic.2005.05.001, doi:10.1016/J.IC.2005.05.001.
  * [9] Yijia Chen, Marc Thurley, and Mark Weyer.  Understanding the complexity of induced subgraph isomorphisms.  In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 587–596. Springer, 2008.  doi:10.1007/978-3-540-70575-8\\_48.
  * [10] Radu Curticapean.  The simple, little and slow things count: on parameterized counting complexity.  PhD thesis, Saarland University, 2015.  doi:10.22028/D291-26612.
  * [11] 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.
  * [12] Radu Curticapean and Dániel Marx.  Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130–139. IEEE Computer Society, 2014.  doi:10.1109/FOCS.2014.22.
  * [13] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [14] Yevgeniy Dodis and Sanjeev Khanna.  Space time tradeoffs for graph properties.  In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages and Programming, 26th International Colloquium, ICALP’99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 291–300. Springer, 1999.  doi:10.1007/3-540-48523-6\\_26.
  * [15] Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz.  Counting induced subgraphs: An algebraic approach to #W[1]-hardness.  Algorithmica, 84(2):379–404, 2022.  doi:10.1007/s00453-021-00894-9.
  * [16] Simon Döring, Dániel Marx, and Philip Wellnitz.  Counting small induced subgraphs with edge-monotone properties.  In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1517–1525. ACM, 2024\.  doi:10.1145/3618260.3649644.
  * [17] Zdenek Dvorák.  On recognizing graphs by numbers of homomorphisms.  J. Graph Theory, 64(4):330–342, 2010.  doi:10.1002/jgt.20461.
  * [18] Paul Erdős, Daniel J. Kleitman, and Bruce L. Rothschild.  Asymptotic enumeration of $K_{n}$-free graphs.  In Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II, pages 19–27. Accad. Naz. Lincei, Rome, 1976.
  * [19] 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.
  * [20] Jacob Focke and Marc Roth.  Counting small induced subgraphs with hereditary properties.  SIAM J. Comput., 53(2):189–220, 2024.  doi:10.1137/22m1512211.
  * [21] Martin Fürer.  On the combinatorial power of the Weisfeiler-Lehman algorithm.  In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 260–271, 2017.  doi:10.1007/978-3-319-57586-5\\_22.
  * [22] Andreas Göbel, Leslie A. Goldberg, and Marc Roth.  The Weisfeiler-Leman dimension of conjunctive queries.  Proc. ACM Manag. Data, 2(2):86:1–86:17, 2024.  doi:10.1145/3651587.
  * [23] Martin Grohe.  Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic.  Cambridge University Press, 2017.  doi:10.1017/9781139028868.
  * [24] Martin Grohe and Daniel Neuen.  Recent advances on the graph isomorphism problem.  In Konrad K. Dabrowski, Maximilien Gadouleau, Nicholas Georgiou, Matthew Johnson, George B. Mertzios, and Daniël Paulusma, editors, Surveys in Combinatorics, 2021: Invited lectures from the 28th British Combinatorial Conference, Durham, UK, July 5-9, 2021, pages 187–234. Cambridge University Press, 2021.  doi:10.1017/9781009036214.006.
  * [25] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.  doi:10.1006/jcss.2001.1774.
  * [26] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting connected subgraphs and graph motifs.  J. Comput. Syst. Sci., 81(4):702–716, 2015.  doi:10.1016/j.jcss.2014.11.015.
  * [27] Mark Jerrum and Kitty Meeks.  Some hard families of parameterized counting problems.  ACM Trans. Comput. Theory, 7(3):11:1–11:18, 2015.  doi:10.1145/2786017.
  * [28] Mark Jerrum and Kitty Meeks.  The parameterised complexity of counting even and odd induced subgraphs.  Comb., 37(5):965–990, 2017.  doi:10.1007/s00493-016-3338-5.
  * [29] Stasys Jukna.  Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics.  Springer, 2012.  doi:10.1007/978-3-642-24508-4.
  * [30] Sandra Kiefer.  The Weisfeiler-Leman algorithm: an exploration of its power.  ACM SIGLOG News, 7(3):5–27, 2020.  doi:10.1145/3436980.3436982.
  * [31] Alexandr V. Kostochka.  Lower bound of the Hadwiger number of graphs by their average degree.  Comb., 4(4):307–316, 1984.  doi:10.1007/BF02579141.
  * [32] 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.
  * [33] László Lovász.  Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 2012.  doi:10.1090/coll/060.
  * [34] Ron Milo, Shai S. Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri B. Chklovskii, and Uri Alon.  Network motifs: Simple building blocks of complex networks.  Science, 298(5594):824–827, 2002.  doi:10.1126/science.298.5594.824.
  * [35] Marvin Minsky and Seymour Papert.  Perceptrons - an introduction to computational geometry.  MIT Press, 1987.  doi:10.7551/mitpress/11301.001.0001.
  * [36] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt.  Weisfeiler and Leman go machine learning: the story so far.  J. Mach. Learn. Res., 24(333):1–59, 2023.  URL: http://jmlr.org/papers/v24/22-0240.html.
  * [37] Daniel Neuen.  Homomorphism-distinguishing closedness for graphs of bounded tree-width.  In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors, 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, volume 289 of LIPIcs, pages 53:1–53:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.  doi:10.4230/LIPIcs.STACS.2024.53.
  * [38] Noam Nisan and Mario Szegedy.  On the degree of boolean functions as real polynomials.  Comput. Complex., 4:301–313, 1994.  doi:10.1007/BF01263419.
  * [39] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, New York, 2014.  doi:10.1017/CBO9781139814782.
  * [40] Hans J. Prömel and Angelika Steger.  Excluding induced subgraphs. III. A general asymptotic.  Random Structures Algorithms, 3(1):19–31, 1992.  doi:10.1002/rsa.3240030104.
  * [41] Ronald L. Rivest and Jean Vuillemin.  On recognizing graph properties from adjacency matrices.  Theor. Comput. Sci., 3(3):371–384, 1976.  doi:10.1016/0304-3975(76)90053-0.
  * [42] Neil Robertson and Paul D. Seymour.  Graph minors. v. excluding a planar graph.  J. Comb. Theory B, 41(1):92–114, 1986.  doi:10.1016/0095-8956(86)90030-4.
  * [43] Marc Roth.  Counting problems on quantum graphs.  PhD thesis, Saarland University, Germany, 2019.  doi:10.22028/D291-28348.
  * [44] Marc Roth and Johannes Schmitt.  Counting induced subgraphs: A topological approach to #W[1]-hardness.  Algorithmica, 82(8):2267–2291, 2020.  doi:10.1007/s00453-020-00676-9.
  * [45] Marc Roth, Johannes Schmitt, and Philip Wellnitz.  Counting small induced subgraphs satisfying monotone properties.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1356–1367. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00128.
  * [46] Marc Roth, Johannes Schmitt, and Philip Wellnitz.  Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 108:1–108:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.108, doi:10.4230/LIPICS.ICALP.2021.108.
  * [47] Leslie G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.  doi:10.1016/0304-3975(79)90044-6.
  * [48] Joachim von zur Gathen and James R. Roche.  Polynomials with two values.  Comb., 17(3):345–362, 1997.  doi:10.1007/BF01215917.
  * [49] Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu.  Finding four-node subgraphs in triangle time.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1671–1680. SIAM, 2015.  doi:10.1137/1.9781611973730.111.

##  Appendix A Omitted Proofs

In several previous works, graph invariants $f(\star)$ were studied by viewing
them as linear combinations of homomorphism counts
$f(\star)=\sum_{i=1}^{s}\alpha_{i}\,\\#\mathrm{Hom}(H_{i}\to\,\star\,)$ and
exploiting a so-called _complexity monotonicity_ property: In many important
computational models, linear combinations of homomorphism counts as above are
as hard to evaluate as their “hardest” homomorphism counts
$\\#\mathrm{Hom}(H_{i}\to\,\star\,)$ for $i\in[s]$.

In general, this does not hold for linear combinations of _subgraph_ counts
$\sum_{i=1}^{s}\alpha_{i}\,\\#\mathrm{Sub}(H_{i}\to\,\star\,)$. As an example,
the easily computed quantity $\binom{E(G)}{k}$ counts all $k$-edge subgraphs
of $G$. This count can be viewed as the sum of $\\#\mathrm{Sub}(H\to G)$ for
all graphs $H$ with $|E(H)|=k$, which includes expanders $H$ on $\Omega(k)$
vertices and complete graphs on $\Omega(\sqrt{k})$ vertices. A variant of the
general complexity monotonicity property does however hold under the guarantee
that all pattern graphs $H_{i}$ have the same number of vertices. We include a
proof below; for technical reasons, we require a variant that involves vertex-
colors.

###  A.1 Vertex-Colored Graphs

To address the vertex-colored version, we need to introduce some terminology
for colored graphs (that is not required outside of the appendix). In the
following, a _vertex-colored graph_ with colors $C$ is an undirected graph
$G=(V,E,c)$ that is given together with a _coloring_ $c\colon V(G)\to C$. We
write $G^{\circ}=(V,E)$ for the uncolored graph underlying $G$. We call $G$
_colorful_ if $c$ is a bijection, and we call it _canonically colored_ if
$C=V(G)$ and $c$ is the identity function. For $i\in C$, we write $V_{i}(G)$
for the vertices of color $i$, and for $i,j\in C$, we write $E_{ij}(G)$ for
the edges in $G$ with one endpoint of color $i$ and another of color $j$. For
$X\subseteq C$ and $Y\subseteq\binom{C}{2}$, let $G_{\setminus X,Y}$ be the
graph obtained from $G$ by deleting all vertices with colors from $X$ and all
edges whose endpoints have a color pair from $Y$, i.e,

$G_{\setminus X,Y}=\left(V\setminus\bigcup_{i\in X}V_{i},\
E\setminus\bigcup_{ij\in Y}E_{ij}\right).$

Given vertex-colored graphs $H$ and $G$, we write $\\#\mathrm{Sub}(H\to G)$
for the number of subgraphs $F$ of $G$ that are isomorphic to $H$ by an
isomorphism that respects colors. For colored graphs $F$ and $H$ with
colorings $c_{F}$ and $c_{H}$, this is an isomorphism $\pi\colon V(F)\to V(H)$
with $c_{F}(v)=c_{H}(\pi(v))$ for all $v\in V(H)$. The following fact is
immediate.

######  Fact A.1.

For graphs $H$ and $G$ with canonically colored $H$, we have

$\\#\mathrm{Sub}(H\to G)=\\#\mathrm{Sub}(H\to
G_{\setminus\emptyset,\overline{E(H)}}).$

Note that no vertices are removed, while all edges in $E_{ij}(G)$ with
$ij\notin E(H)$ are removed. Thus, when considering $\\#\mathrm{Sub}(H\to G)$
for graphs $H$ and $G$ with canonically colored $H$, we may assume
$E_{ij}(G)=\emptyset$ for all $ij\notin E(H)$.

###  A.2 Isolating Colored Subgraphs from Linear Combinations

We follow the standard approach [10, 2] of applying the inclusion-exclusion
principle on the set of subgraphs of a graph $G$. This principle allows us to