Counting Small Induced Subgraphs:
Hardness of Symmetry-Based Properties
June 30, 2026
Abstract
Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) for fixed graph properties \(\Phi\): Given an input graph \(G\) and \(k\in{\mathbb{N}}\), count the \(k\)-vertex subsets \(S \subseteq V(G)\) such that the induced subgraph \(G[S]\) satisfies \(\Phi\). For recursively enumerable \(\Phi\), it is known that \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) is either #W[1]-hard or fixed-parameter tractable. A direct classification depending on \(\Phi\) however still remains open.
In particular, the status was open for the property of graphs without nontrivial automorphisms, also mentioned in a very recent survey on parameterized counting by Roth (Comput. Sci. Rev. 2026). This is a natural property that evades all currently known techniques for proving #W[1]-hardness, including a general toolkit based on Fourier analysis that was very recently introduced by Curticapean and Neuen (SODA 2025). In this paper, we show that counting induced \(k\)-vertex graphs without nontrivial automorphisms is #W[1]-hard by constructing “clique scaffolds”, i.e., problem-specific restrictions of the property that enable a reduction from the \(k\)-clique problem.
More generally, we show that for every finite group \(Q\), counting \(k\)-vertex induced subgraphs with automorphism group \(Q\) is #W[1]-hard.
1 Introduction↩︎
Pattern counting is an important routine in network analysis [1]: Given a small fixed pattern \(H\) and a large host graph \(G\), this problem asks us to determine the number of \(H\)-occurrences in \(G\). More formally, we wish to count (induced) subgraphs of \(G\) that are isomorphic to \(H\). The complexity of such problems has been fully classified for individual fixed patterns \(H\):
Given a \(k\)-vertex graph \(H\), we can count induced \(H\)-copies in an \(n\)-vertex graph in time \(n^{\omega k/3 + O(1)}\) [2], where \(\omega \leq 2.372\) is the exponent of matrix multiplication [3]. Under the exponential-time hypothesis ETH, there is a constant \(\alpha >0\) such that no \(O(n^{\alpha k})\) time algorithm exists for the problem [4]. In other words, the concrete structure of the pattern \(H\) is irrelevant for this problem, only the number of vertices matters.
Given a graph \(H\) of vertex-cover number \(t\), we can count the (not necessarily induced) \(H\)-subgraphs in \(G\) in time \(n^{t+O(1)}\), and ETH implies a constant \(\alpha >0\) such that no \(O(n^{\alpha t / \log t})\) time algorithm exists for the problem [5], [6]. Note that \(t\) may be much smaller than the number of vertices in some graphs \(H\).
1.1 Counting Small Patterns With a Fixed Property↩︎
In some applications, we may not be interested in concrete fixed patterns \(H\), but rather in counting occurrences of all patterns that satisfy a given graph property \(\Phi\). For example, we may wish to determine how many \(k\)-vertex subsets \(S\) induce a graph with at least \(75\%\) of the \(k \choose 2\) possible edges. This naturally leads to the problem of counting \(k\)-vertex subsets \(S\) of \(V(G)\) such that \(G[S]\) satisfies a fixed property \(\Phi\). Other examples include the problems of counting the induced \(k\)-vertex subgraphs that are connected, planar, or satisfy other application-specific properties.
Such problems can certainly be solved by counting induced \(H\)-copies for all individual \(H \in \Phi\) and summing these counts up. For some properties \(\Phi\), however, this is clearly not the best strategy: If \(\Phi\) contains all graphs, then there are exactly \(n \choose k\) induced \(k\)-vertex subgraphs satisfying \(\Phi\). In particular, there is no need to determine the (hard) individual counts arising from specific graphs \(H\in \Phi\). A very recent paper also presented nontrivial properties \(\Phi\) for which the total count is easier to determine than the individual pattern counts [7].
This renews an intriguing question that has been open for over a decade: For which properties \(\Phi\) can we count \(k\)-vertex induced subgraphs satisfying \(\Phi\) in significantly less than \(n^{O(k)}\) time, or even in \(O(n^d)\) time for an exponent \(d=d_\Phi\) that does not depend on \(k\)?
1.2 Known Results↩︎
This question can be formalized well in the language of parameterized complexity, where a fixed-parameter tractable running time \(f(k)n^{O(1)}\) for problems with instance size \(n\) and parameter value \(k\) is considered efficient. Some parameterized problems are believed to be hard, e.g., the canonical #W[1]-hard problem \(\#\textrm{\mathrm{\small Clique}}\) that asks to count \(k\)-cliques in \(n\)-vertex graphs \(G\) [8]. The exponential-time hypothesis rules out \(n^{o(k)}\) time algorithms for this problem [4].
Within parameterized complexity, our induced subgraph counting problem leads to the following problem \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) for fixed graph properties \(\Phi\), originally defined by Jerrum and Meeks [9], [10]: On input a graph \(G\) and the parameter \(k\in \mathbb{N}\), count the \(k\)-vertex subsets \(S\) such that \(G[S]\) satisfies \(\Phi\). In principle, a dichotomy for \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) is known: For every recursively enumerable property \(\Phi\), this problem is either fixed-parameter tractable or #W[1]-hard, with no intermediate cases [6]. However, the dichotomy criterion on \(\Phi\) presented in [6] relies on specific equations that a priori have no combinatorial meaning. Consequently, checking the criterion even for very natural properties \(\Phi\) required nontrivial effort: Several highly technical papers and more recent streamlined results established hardness of \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) for important classes of properties, e.g., when
\(\Phi\) holds only for \((2-\epsilon)^m\) graphs for \(m = {k \choose 2}\), e.g., when \(\Phi\) is nontrivial and closed under vertex-deletions [11], [13],
\(\Phi(H)\) depends only on the number of edges in \(H\) [11], [14], or
the \(k\)-vertex graphs in \(\Phi\) avoid \(\omega(k)\) of the \({k \choose 2}+1\) possible edge-densities [11], [14].
A full classification of the problems \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) with an easily checkable criterion on \(\Phi\) however remains open [7], [11].
1.3 Counting Asymmetric Graphs↩︎
Even the status of several natural graph properties \(\Phi\) remained unresolved, e.g., the property of asymmetric graphs, which have only the trivial automorphism: \[\Phi_{\sf asym}\mathrel{\vcenter{:}}= \{H\mid \mathop{\mathrm{Aut}}(H)\text{ is trivial}\}.\]
The complexity status of \(\#\textrm{\mathrm{\small IndSub}}(\Phi_{\sf asym})\) is mentioned explicitly as an open problem in a recent survey on parameterized counting problems by Roth [15]. Curiously, this property eschews all the general hardness results above, e.g., it is not monotone under edge- or vertex-deletions, almost all graphs are asymmetric [16], and we show in Lemma 15 in the appendix that \(\Phi_{\sf asym}\) avoids only \(O(k)\) instead of the required \(\omega(k)\) edge-densities. Additionally, \(\Phi_{\sf asym}\) is problematic for the group-theoretic techniques developed in previous works [12], [17], [18]: These techniques ultimately rely on graphs \(H\) with \(\Phi(H) \neq \Phi(\overline{H})\), but \(H\) and \(\overline{H}\) have the same automorphism group and are thus not distinguished by \(\Phi_{\sf asym}\).
This establishes the asymmetry property as a very natural bottleneck for the known hardness techniques for \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) and makes counting asymmetric induced subgraphs a useful benchmark problem: any hardness proof requires a strategy that does not rely on monotonicity, density restrictions, or group-theoretic techniques that require comparisons with the complement.
1.4 Our Results↩︎
We show that counting induced \(k\)-vertex subgraphs without symmetries is \(\textrm{\textsf{\#W[1]}}\)-hard and provide a tight lower bound based on hardness of counting \(k\)-cliques.
Theorem 1. The problem \(\#\textrm{\mathrm{\small IndSub}}(\Phi_{\sf asym})\) is \(\textrm{\textsf{\#W[1]}}\)-hard. Moreover, for every \(c>0\) and \(k\), an \(O(n^{ck})\) time algorithm for \(\#\textrm{\mathrm{\small IndSub}}(\Phi_{\sf asym})\) implies an \(O(n^{4ck})\) algorithm for \(\#\textrm{\mathrm{\small Clique}}\).
We also prove a more general result: Say that a graph \(H\) realizes a group \(Q\) if the automorphism group \(\mathop{\mathrm{Aut}}(H)\) is isomorphic to \(Q\). By Frucht’s theorem, every finite group \(Q\) is realized by some graph \(H\).1 For a fixed finite collection of finite groups \(\mathcal{Q}\), we then define \[\Psi_{\mathcal{Q}} \mathrel{\vcenter{:}}= \{H\mid H\text{ realizes some }Q\in \mathcal{Q}\}.\]
An important special case is of course \(\mathcal{Q} = \{Q\}\) for a single group \(Q\). In particular, we have \(\Psi_{\{S_1\}} = \Phi_{\sf asym}\), where \(S_1\) is the trivial group.
Theorem 2. For every fixed collection of finite groups \(\mathcal{Q}\) with \(0 < |\mathcal{Q}| < \infty\), the problem \(\#\textrm{\mathrm{\small IndSub}}(\Psi_{\mathcal{Q}})\) is \(\textrm{\textsf{\#W[1]}}\)-hard. Moreover, there is a constant \(\alpha = \alpha_\mathcal{Q}\) such that, for every \(c>0\) and \(k\), an \(O(n^{ck})\) time algorithm implies an \(O(n^{\alpha ck})\) algorithm for \(\#\textrm{\mathrm{\small Clique}}\).
1.5 Proof Techniques↩︎
Recent approaches to the complexity of \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) were based on sophisticated ways to understand Möbius transforms on the subset lattice. In this paper, we instead work with simple ad-hoc restrictions of the graph property \(\Phi_{\sf asym}\) and obtain a fairly direct “local” reduction from \(\#\textrm{\mathrm{\small Clique}}\) to \(\#\textrm{\mathrm{\small IndSub}}(\Phi_{\sf asym})\).
Simulating a Boolean OR on the Edges of a Clique
We give a simple parameterized reduction from counting \(\ell\)-cliques to counting induced \(k\)-vertex graphs satisfying \(\Phi\), provided there is a restriction of \(\Phi\) that amounts to a Boolean OR on the edges of an \(\ell\)-clique.
Our notion of restriction is formalized in the following way: For \(\ell,k \in {\mathbb{N}}\), we define an \((\ell,k)\)-clique scaffold to be a labeled graph \(R\) on vertex set \([k]\) such that \([\ell]\) is an independent set in \(R\). Intuitively speaking, all edges \(uv\in R\) are required, all edges in \([\ell] \choose 2\) are free, and all other edges are forbidden. See 1 for an example. This interpretation gives rise to a new property \(\Phi|_R\) on labeled graphs with vertex set \([\ell]\), by setting \(\Phi|_R(S)=\Phi(R\cup S)\) for all graphs \(S\) with \(V(S)=[\ell]\). 2
If we can find an \((\ell,k)\)-clique scaffold \(R\) such that \(\Phi|_R\) is a Boolean OR on the edges of \(K_\ell\), then hardness follows. In other words, we require that \(\Phi(R)=0\) but \(\Phi(R\cup S)=1\) for all \(S\) on vertex set \([\ell]\) with \(|E(S)|>0\). The reduction also applies if the logical negation \(\neg \Phi\) contains such an OR; here \(\neg \Phi\) is the property of graphs not satisfying \(\Phi\). 3
Constructing Restrictions From Symmetries
Our restrictions for \(\Phi_{\sf asym}\) are derived from ladder graphs; see 1 for an example. The ladder with two pendant vertices has exactly two automorphisms: the identity and vertical reflection. A careful choice of free edges ensures that any non-empty set of free edges breaks the symmetry. In particular, the free edges can be chosen as the edges of an \(\ell\)-clique for \(\ell = \Omega(k)\), which enables a simple reduction from the \(\ell\)-clique problem.
Regarding our 2 for more general properties \(\Psi_{\mathcal{Q}}\), note that \(\mathcal{Q}=\{S_1\}\) recovers the case of \(\Phi_{\sf asym}\). In all other cases, we use Frucht’s theorem, which asserts that every finite group \(Q\) is realized by some graph. Our restriction relies on gluing “key gadgets” onto this graph that (i) preserve the automorphism group, and (ii) support a large clique on free edges such that adding any non-empty subset of free edges gives a graph whose automorphisms form a proper subgroup of \(Q\).
2 Preliminaries↩︎
For integers \(n\geq 1\), let \([n]:=\{1,2,\dots,n\}\).
Graphs.
For a graph \(G=(V,E)\), let \(N(v)\) be the neighborhood of \(v\in V\). A clique in \(G\) is a set \(S\subseteq V\) such that \(u,v\in S\) implies \(uv\in E\). An independent set (also known as a stable set) requires \(uv \notin E\) instead.
We also consider (not necessarily properly) \(k\)-colored graphs, for \(k \in {\mathbb{N}}\): Such graphs \(G=(V,E)\) are given together with a partition \(V=V_1 \cup \ldots \cup V_k\). A vertex-set \(S\subseteq V\) is colorful if \(S=\{v_1,\ldots,v_k\}\) with \(v_i \in V_i\) for all \(i \in [k]\).
For a graph \(G\) and a set of edges \(X\), we denote by \(G \cup X\) the graph \((V(G), E(G) \cup X)\).
In this paper, a (labeled graph) property is a function from labeled graphs to \(\{0,1\}\). It is a graph property if all isomorphic graphs \(H,H'\) satisfy \(\Phi(H)=\Phi(H')\). For \(k\in{\mathbb{N}}\), a \(k\)-vertex graph property has its domain restricted to the \(k\)-vertex graphs.
Groups.
An automorphism of \(G\) is a bijection \(f:V\to V\) preserving (non)-adjacency; the set of all such mappings forms the group \(\mathrm{Aut}(G)\). We say \(G\) is asymmetric if \(\mathrm{Aut}(G) = \{\mathrm{id}\}\).
For each integer \(k\), denote the symmetric group of degree \(k\) by \(S_k\). Denote the trivial group by \(S_1=\{\mathrm{id}\}\). For groups \(Q_1\) and \(Q_2\), we write \(Q_1\le Q_2\) to denote that \(Q_1\) is a subgroup of \(Q_2\).
Parameterized Complexity.
The problem \(\#\textrm{\mathrm{\small Clique}}\) is the canonical \(\textrm{\textsf{\#W[1]}}\)-hard parameterized counting problem: On input a graph \(G\) and \(k\in {\mathbb{N}}\), compute the number of \(k\)-cliques in \(G\). A parameterized problem with inputs \((x,k')\) is \(\textrm{\textsf{\#W[1]}}\)-hard if there is a parameterized reduction from \(\#\textrm{\mathrm{\small Clique}}\) to the target problem, i.e., an algorithm solving \(\#\textrm{\mathrm{\small Clique}}\) in time \(f(k)n^{O(1)}\) with oracle access to the target problem, such that all oracle queries satisfy \(k'\leq g(k)\). Here, \(f\) and \(g\) are computable functions.
We use a multicolored version \(\#\textrm{\mathrm{\small ColorfulClique}}\), where \(G\) is \(k\)-colored and we count colorful cliques, as defined above. To reduce \(\#\textrm{\mathrm{\small Clique}}\) to \(\#\textrm{\mathrm{\small ColorfulClique}}\), replace each vertex \(v\in V(G)\) by a \(k\)-independent set \(C_v\), replace edges \(uv\) by complete bipartite graphs between \(C_u\) and \(C_v\), and for each \(i\in [k]\), define the color class \(V_i\) to consist of the \(i\)-th vertex from all independent sets \(C_v\) for \(v\in V(G)\). Each \(k\)-clique of \(G\) corresponds to exactly \(k!\) colorful \(k\)-cliques in the constructed graph, so we divide the resulting count by \(k!\).
3 Main Reduction↩︎
For reference, we repeat the definitions from the introduction.
Definition 3. For \(\ell, k\in {\mathbb{N}}\) with \(\ell \leq k\), an \((\ell,k)\)-clique scaffold is a labeled graph \(R\) on vertex set \([k]\) such that \([\ell]\) is an independent set in \(R\). Let \(\Phi\) be a \(k\)-vertex property of graphs with vertex set \([k]\) and write \(K= \binom{[\ell]}{2}\). We say that \(\Phi\) contains an \(\ell\)-clique OR if there is a clique scaffold \(R\) such that \(\Phi(R)=0\) and \(\Phi(R\cup S)=1\) for all \(\emptyset \subsetneq S\subseteq K\).
We show that large \(\ell\)-clique ORs in \(\Phi\) or in \(\neg \Phi\) render \(\Phi\) hard. Towards this, we consider the problem \(\#\textrm{\mathrm{\small ColorfulIndSub}}(\Phi)\), also studied in other works [9], [10], [12], [20], [21]: On input \(k \in \mathbb{N}\) and a \(k\)-colored graph \(G=(V,E)\), count the colorful sets \(S \subseteq V\) such that \(\Phi\) is satisfied by the uncolored graph underlying \(G[S]\). This problem can be reduced to the uncolored version by a standard application of the inclusion-exclusion principle; see also [5], [11], [22] for related examples and below for a self-contained proof.
Lemma 4. For every property \(\Phi\), there is a parameterized reduction from the problem \(\#\textrm{\mathrm{\small ColorfulIndSub}}(\Phi)\) to \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) that does not increase the parameter value.
Proof. Let \((G,k)\) be an instance for \(\#\textrm{\mathrm{\small ColorfulIndSub}}(\Phi)\) with \(V=V_1 \cup \ldots \cup V_k\). For \(A\subseteq [k]\), let \(X_A\) be the set of \(k\)-vertex subsets satisfying \(\Phi\) that avoid all colors from \(A\) but otherwise ignore the colors. Each value \(\#X_A\) for \(A\subseteq [k]\) can be determined with an oracle call \((G_A,k)\) for \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\), where \(G_A\) is obtained from \(G\) by deleting all vertices with colors from \(A\). The parameter \(k\) does not increase. The number of colorful sets in \(G\) satisfying \(\Phi\) can be computed with \(2^k\) oracle calls and \(2^k n^2\) additional time via \(\sum_{A\subseteq [k]}(-1)^{|A|} \#X_A\). ◻
Lemma 5. Let \(\Phi\) be a \(k\)-vertex property that contains an \(\ell\)-clique OR. Given an \(\ell\)-colored graph \(G\) on \(n\) vertices, we can compute in \(f(k)n^2\) time a \(k\)-colored graph \(G'\) on \(n+k-\ell\) vertices such that the number of colorful \(\ell\)-cliques in \(G\) equals the number of colorful \(k\)-vertex sets in \(G'\) that do not* satisfy \(\Phi\).*
Proof. Consider an instance for \(\#\textrm{\mathrm{\small ColorfulClique}}\) with graph \(G=(V, E)\), parameter value \(\ell\), and partition \(V=V_1 \cup\ldots\cup V_\ell\). Let \(R\) be a \((\ell,k)\)-clique scaffold witnessing that \(\Phi\) contains an \(\ell\)-clique OR; we find it using brute-force in \(f(k)\) time.
We define an instance for \(\#\textrm{\mathrm{\small ColorfulIndSub}}(\Phi)\) with graph \(G'=(V',E')\), parameter value \(k\), and partition \(V'=V'_1 \cup\ldots\cup V'_k\) as follows:
For \(i\in [\ell]\), let \(V'_i\) be a copy of \(V_i\) and let the edges be those of the complement graph \(\overline{G}\), i.e., for each \(uv\not\in E(G)\), add the corresponding edge between the copies of \(u\) and \(v\) in \(G'\).
For \(i\in [k]\setminus [\ell]\), let \(V'_i=\{w_i\}\) for a fresh vertex \(w_i\).
For \(i,j\in [k]\setminus [\ell]\), add the edge \(w_iw_j\) iff \(ij\in E(R)\). For \(i \in [\ell]\) and \(j \in [k]\setminus [\ell]\), add all edges between \(V'_i\) and \(w_j\) iff \(ij\in E(R)\). No edges are added for \(ij\) with \(ij\notin E(R)\).
Every colorful set \(S \subseteq V(G')\) picks all \(w_i\) for \(i\in [k]\setminus [\ell]\) and some \(v_i \in V'_i\) for each \(i\in [\ell]\). Let \(T\) be the set of edges induced by \(v_1,\dots,v_\ell\) in \(G'\). Then \(G'[S]\cong R\cup T\), and \(T=\emptyset\) if and only if \(\{v_1,\dots,v_\ell\}\) is a clique in \(G\). If \(T=\emptyset\), then \(\Phi(G'[S])=0\); if \(T\neq\emptyset\), then \(\Phi(G'[S])=1\) by the definition of an \(\ell\)-clique OR. Thus colorful \(\ell\)-cliques in \(G\) are exactly the colorful \(k\)-vertex sets in \(G'\) that do not satisfy \(\Phi\). ◻
In the following, write \(\Phi^{(k)}\) for the property defined on \(k\)-vertex graphs that agrees with \(\Phi\) on its domain, and write \(\neg \Phi^{(k)}\) for its pointwise negation.
Theorem 6. Let \(\Phi\) be a computable graph property and assume that every \(\ell \in {\mathbb{N}}\) admits some \(k=k(\ell)\) such that either \(\Phi^{(k)}\) or \(\neg \Phi^{(k)}\) contains an \(\ell\)-clique OR.
Then \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) is \(\textrm{\textsf{\#W[1]}}\)-hard.
If additionally \(k(\ell) \leq d\ell\) for a constant \(d\geq1\) and all \(\ell\), then the following holds: If \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\) on parameter \(k\) admits an \(f(k)n^{ck}\) time algorithm for \(0<c\leq 1\), then \(\#\textrm{\mathrm{\small ColorfulClique}}\) with parameter value \(\ell\) can be solved in time \(f'(\ell)n^{cd\ell}\) for some computable function \(f'\).
Proof. We prove the second part first. Choose \(k \leq d\ell\). Let \(G\) be an \(\ell\)-colored instance of \(\#\textrm{\mathrm{\small ColorfulClique}}\) with color classes \(V_1,\dots,V_\ell\). Let \(N:=\prod_{i=1}^{\ell}|V_i|\) be the total number of colorful choices. Suppose first that \(\Phi^{(k)}\) contains an \(\ell\)-clique OR. By 5, we obtain a \(k\)-colored graph \(G'\) on \(n+k-\ell\) vertices such that the number of colorful \(\ell\)-cliques in \(G\) is \(N\) minus the number of colorful \(k\)-vertex sets in \(G'\) satisfying \(\Phi^{(k)}\). This latter quantity can be computed in time \(f(k)n^{ck}\) using 4 and the assumed algorithm for \(\#\textrm{\mathrm{\small IndSub}}(\Phi^{(k)})\).
If instead \(\neg \Phi^{(k)}\) contains an \(\ell\)-clique OR, the same construction applied to \(\neg \Phi^{(k)}\) gives that the colorful \(\ell\)-cliques in \(G\) are counted by the colorful \(k\)-vertex sets in \(G'\) satisfying \(\Phi^{(k)}\). Again this value is computed in time \(f(k)n^{ck}\) using 4 and the assumed algorithm. Thus \(\#\textrm{\mathrm{\small ColorfulClique}}\) with parameter \(\ell\) can also be solved in time \(f(k)n^{ck} \leq f(d\ell)n^{cd\ell}\).
For the \(\textrm{\textsf{\#W[1]}}\)-hardness, recall that \(\#\textrm{\mathrm{\small ColorfulClique}}\) is \(\textrm{\textsf{\#W[1]}}\)-hard. Since \(\Phi\) is computable, we can use brute-force to find, for every \(\ell\), some computable \(k(\ell)\) for which either \(\Phi^{(k)}\) or \(\neg \Phi^{(k)}\) contains an \(\ell\)-clique OR. The argument above therefore gives a parameterized reduction to \(\#\textrm{\mathrm{\small IndSub}}(\Phi)\). ◻
4 Asymmetry has Clique-ORs↩︎
We now prove 1 by showing that every \(\ell \in {\mathbb{N}}\) admits some \(k \in {\mathbb{N}}\) such that \(\Phi_{\sf asym}\) contains an \(\ell\)-clique OR. To this end, we construct a clique scaffold \(R\) based on a modified \(2\times 2\ell\) grid, a structure whose automorphisms are easy to characterize and can be made asymmetric by planting certain edges in the first row.
Definition 7. For any \(\ell \in {\mathbb{N}}\), let \(F_\ell\) be a \(2\times 2\ell\) grid with the edge \(\{(1,1),(2,1)\}\) removed. Let \(K= \binom {C}{2}\) where \(C=\{(1,2i) \mid i\in[\ell]\}\). For \(k:=4\ell\), the graph \(F_{\ell}\) is an \((\ell,k)\)-clique scaffold after relabeling vertices in \(C\) with \(1,\dots,\ell\).
See also Figure 1 for \(F_{5}\). We show \(F_{\ell}\) is a witness that \(\Phi_{\sf asym}\) contains an \(\ell\)-clique OR. Clearly \(F_{\ell}\) is symmetric and \(|F_{\ell}| = 4\ell\). We show that adding any non-empty subset of \(K\) to \(F_{\ell}\) results in an asymmetric graph.
Lemma 8. Let \(F_\ell\) and \(K\) be defined as above. For every \(\ell \in {\mathbb{N}}\), there is an \((\ell,k)\)-clique scaffold \(R\) where \(k:=|V(F_\ell)|=4\ell\) such that for any \(X \subseteq K\), the automorphism group of \(F':=F_{\ell}\cup X\) is non-trivial if and only if \(X= \emptyset\), that is, \(\Phi_{\sf asym}^{(k)}\) contains an \(\ell\)-clique OR witnessed by \(F_{\ell}\).
Proof. By definition, \(F_{\ell}\) forms an \((\ell,k)\)-clique scaffold. Given \(|\mathop{\mathrm{Aut}}(F')|>1\) for \(X=\emptyset\), it suffices to show \(\mathop{\mathrm{Aut}}(F')\) is trivial under the assumption \(X \neq \emptyset\). Suppose \(f \in \mathop{\mathrm{Aut}}(F')\); we show \(f\) must be the identity map. Since only the pendant vertices \((1,1)\) and \((2,1)\) have degree \(1\), the automorphism \(f\) either fixes or swaps them.
In Case 1, the pendant vertices are fixed by \(f\). We proceed by induction on the columns to show \(f\) is the identity map. For the base case of the first column, as \((1,2)\) is the unique neighbor of \((1,1)\) and \(f\) is an automorphism, \(f\) maps \((1,2)\) to \((1,2)\). Similarly, it maps \((2,2)\) to \((2,2)\).
Suppose \(f\) is identical in the first \(j-1\) columns for \(3\le j\le 2\ell\). For the \(j\)-th column, we first consider \((2,j)\). Since \(f\) fixes \((2,j-1)\) and all its neighbors except for \((2,j)\), to preserve the neighborhood of \((2,j-1)\), \(f\) must map \((2,j)\) to \((2,j)\).
For \((1,j)\), we observe that \[\{ (1,j),(2,j-1) \} = N((1,j-1)) \cap N((2,j)),\] regardless of the choices of \(X\). As \(f\) fixes \((1,j-1),(2,j),(2,j-1)\), their remaining common neighbor is also fixed. Hence, the \(j\)-th column is fixed by \(f\), and thus \(f\) is the trivial automorphism.
In Case 2, the pendant vertices are swapped by \(f\). By a similar argument, we show that every column is “flipped” by \(f\), that is, \(f\) maps \((x,y)\) to \((3-x,y)\) for all \(x\in[2],y\in [2\ell]\). However, since \(f\) preserves the degree and maps \((1,2j)\) to \((2,2j)\) for all \(j\in[\ell]\), the degree of \((1,2j)\) is \(3\) when \(j\neq \ell\) and \(2\) when \(j=\ell\), which means no edge in \(X\) is incident to \((1,2j)\). This implies \(X\) is the empty set, contradicting the assumption that \(X\neq\emptyset\). ◻
We are ready to apply the reduction from Section 3 to obtain Theorem 1.
Proof of Theorem 1. By Lemma 8, for every \(\ell\in {\mathbb{N}}\), the property \(\Phi_{\sf asym}\) on \(4\ell\) vertices contains an \(\ell\)-clique OR witnessed by the \((\ell,4\ell)\)-clique scaffold \(F_{\ell}\). The theorem follows by applying Theorem 6. ◻
5 General Automorphism Groups↩︎
In Lemma 8, we constructed a clique scaffold graph with a particular non-trivial automorphism group \(Q\) such that adding free edges breaks all symmetries. We now construct similar graphs for every non-trivial finite group \(Q\): adding any non-empty subset of free edges breaks some symmetries of \(Q\), resulting in a strictly smaller automorphism group.
To begin with, Frucht’s Theorem tells us that every finite group \(Q\) admits an undirected simple graph \(F_Q\) with automorphism group isomorphic to \(Q\).
Theorem 9 (Frucht’s Theorem [23], [24] Section 4.3). For any finite group \(Q\), there exists a graph \(F_Q\) such that \(|V(F_Q)|=O(|Q|)\) and \(\mathrm{Aut}(F_Q)\cong Q\).
The theorem yields graphs as “black boxes” without explicit structural properties. To obtain a suitable placement for the free edges, we introduce the following gadget.
Definition 10. For any \(\ell\in {\mathbb{N}}\), the gadget \(\mathrm{\small Key}_\ell\) has \(V(\mathrm{\small Key}_\ell):=\{x,y_1,\dots,y_6,z\} \cup\{a_{i},b_i,c_i\mid i\in[2\ell]\}\). For clarity, the edge set is defined by the adjacency relations shown in 2. For the free edges, we set \(K:=\binom{C}{2}\) where \(C=\{c_{2i-1} \mid i\in[\ell] \}\).
Figure 2: The key gadget of order \(\ell\). The figure depicts only the first and last segments of the edge families \(\{a_{i}a_{i+1},c_ic_{i+1} \mid i\in[2\ell-1]\} \cup \{a_ib_i,b_ic_i \mid i\in [2\ell] \}\). All remaining non-clique edges are drawn explicitly. The red dashed edges represent the edges of the clique induced by the vertices \(c_{2i-1}\); these edges form \(K\) in Lemma 12..
Then, we define the graph \(F_{Q,\ell}\) that forms a clique scaffold for any \(\ell\in \mathbb{N}\). We replace each vertex \(u\) in \(F_Q\) with a copy of the gadget \(\mathrm{\small Key}_\ell\) by identifying \(u\) with \(x\) in \(\mathrm{\small Key}_\ell\) and keep the edges \(uv\) in \(F_Q\) unchanged. Denote the obtained graph by \(F_{Q,\ell}\) and denote the vertices in the copy of \(\mathrm{\small Key}_\ell\) for \(u\) by \(x_u,y_{u,i},a_{u,i},b_{u,i},c_{u,i}\) and \(z_u\) respectively; see Figure 3. For any \(u_0\in V(F_Q)\), the graph \(F_{Q,\ell}\) forms a \((\ell,O(\ell))\)-clique scaffold if we relabel vertices \(c_{u_0,2i-1}\) for \(i\in[\ell]\) with \(1,\dots,\ell\).
The following lemma shows that attaching keys does not change the automorphism group.
Lemma 11. For any finite group \(Q\) and \(\ell \in {\mathbb{N}}\), the automorphism group of the graph \(F_{Q,\ell}\) is isomorphic to \(Q\).
Proof. Any automorphism \(f\) of \(F_{Q}\) induces an automorphism \(f'\) of \(F_{Q,\ell}\), defined by \[f'(y_{u,i}) := y_{f(u),i}\] for all \(u\in V(F_Q), i\in[6]\) and similarly for \(x_u,a_{u,j},b_{u,j},c_{u,j}\) and \(z_u\) for all applicable \(u\) and \(j\). It is clear that \(f'\) is an automorphism of \(F_{Q,\ell}\). It follows that \(Q\) is isomorphic to a subgroup of \(\mathrm{Aut}(F_{Q,\ell})\). It suffices to prove that the mapping \(f\mapsto f'\) is surjective.
Let \(g\in \mathrm{Aut}(F_{Q,\ell})\) be an automorphism. Since the set of vertices of degree 1 in \(F_{Q,\ell}\) is \(V_1:=\{z_u \mid u \in V(F_Q)\}\), the automorphism \(g\) preserves \(V_1\), i.e., \(g(V_1)=V_1\), which induces a bijection \(f\) of \(V(F_Q)\) by \(u \mapsto v\) if \(g(z_u)=z_v\). We proceed by showing that \(f\) is an automorphism so that we can define \(f'\) as before and, furthermore, \(g=f'\).
Let \(g_1\) be the partial automorphism with domain \(V_1\) obtained by restricting \(g\) to \(V_1\). We extend \(g_1\) and prove \(g\) is the unique automorphism that extends \(g_1\) by the following claim.
Claim. Let \(h:V(F_{Q,\ell})\to V(F_{Q,\ell})\) be a partial automorphism with domain \(D\) and let \(d\in D\) be such that the degrees of the neighbors of \(d\) not in \(D\) are unique, i.e., \[\mathrm{deg}(e_1)\neq \mathrm{deg}(e_2) \quad \text{for all } e_1,e_2\in N(d)\setminus D, e_1\neq e_2\] where \(N(d)\) is the neighborhood of \(d\). If there is an automorphism \(p\) of \(F_{Q,\ell}\) extending \(h\), then there exists a unique partial automorphism \(h'\) with domain \(D\cup N(d)\) extending \(h\) that can be further extended to an automorphism (not necessarily \(p\)).
Proof of the claim. By the existence of \(p\) in the assumption, we only need to prove the uniqueness. If \(h'\) extends \(h\) and can be further extended to an automorphism, it must preserve degrees and adjacency. Looking at the undetermined neighbors \(N(d)\setminus D\) of \(d\), the degrees of their images are unique among the unmapped neighbors of \(h(d)\). In particular, their images are uniquely determined, given by \(h'(e) := p(e)\) for any \(e\in N(d) \setminus D\). \(\dashv\)
By consecutively applying the claim to \[z_u,a_{u,2\ell},b_{u,2\ell},a_{u,2\ell-1},b_{u,2\ell-1},\dots,a_{u,1},b_{u,1},y_{u,6},y_{u,1},y_{u,2}\] as the vertex \(d\) and starting with \(g_1\) as the partial automorphism, one can verify that the only automorphism extending \(g_1\), which is exactly \(g\), maps \[\label{eq:defg} \begin{array}{ccc} z_u & \quad & x_u \\ \downarrow & & \downarrow \\ z_v & \quad & x_v \end{array} \qquad \begin{array}{ccc} a_{u,i} & \quad & b_{u,i} \\ \downarrow & & \downarrow \\ a_{v,i} & \quad & b_{v,i} \end{array} \qquad \begin{array}{c} c_{u,i} \\ \downarrow \\ c_{v,i} \end{array} \qquad \begin{array}{c} y_{u,j} \\ \downarrow \\ y_{v,j} \end{array}\tag{1}\] for all \(u\in V(F_{Q})\) and all \(i\in[2\ell],j\in[6]\) where \(v\in V(F_{Q})\) is the vertex satisfying \(g_1(z_u)=z_v\).
For \(u_1,u_2\in V(F_Q)\), \[\begin{align} f(u_1)f(u_2)\in E(F_Q) &\iff x_{f(u_1)}x_{f(u_2)}\in E(F_{Q,\ell}) & \text{(definition of F_{Q,\ell})}\\ &\iff g(x_{u_1})g(x_{u_2})\in E(F_{Q,\ell}) &\text{(g(x_u)=x_{f(u)})}\\ &\iff x_{u_1}x_{u_2} \in E(F_{Q,\ell})&\text{(g is automorphism)}\\ &\iff u_1u_2\in E(F_Q),&\text{(definition of F_{Q,\ell})} \end{align}\] where \(g(x_u)=x_{f(u)}\) follows from the definition of \(f\) and Equation (1 ).
Then \(f\) is an automorphism of \(F_Q\) and we can define \(f'\). However, by Equation (1 ), it is obvious that \(f'=g\) and thus the mapping \(f\mapsto f'\) is surjective. ◻
We find a large useful independent set in \(F_{Q,\ell}\) for any finite group \(Q\).
Lemma 12. Let \(Q\) be a non-trivial finite group and \(\ell\in {\mathbb{N}}\). There is a graph \(F=(V,E)\) on \(O(|Q|\cdot \ell)\) vertices and an independent set \(C\) of size \(\ell\) such that for any \(X\subseteq \binom{C}{2}\), the automorphism group of \(F':=F\cup X\) is isomorphic to \(Q\) if and only if \(X=\emptyset\).
Proof. By Theorem 9, there is a graph \(F_Q\) on \(O(|Q|)\) vertices with automorphism group isomorphic to \(Q\). Let \(u_0\in V(F_Q)\) be an arbitrary vertex with an orbit of size at least 2, that is, there is an automorphism \(g\in \mathrm{Aut}(F_Q)\) such that \(g(u_0)\neq u_0\). Such a vertex exists since \(Q\) is non-trivial. We take \(F\) to be the graph \(F_{Q,\ell}\) defined above and the independent set \(C\) to be \(\{c_{u_0,2i-1} \mid i\in[\ell]\}\).
By Lemma 11, \(\mathrm{Aut}(F')\cong Q\) if \(X=\emptyset\). When \(X\) is not empty, it can be proved that \(\mathrm{Aut}(F')\) is isomorphic to a subgroup of \(Q\) by a similar argument as in the proof of Lemma 11 and an automorphism \(f\) of \(F_{Q,\ell}\) is an automorphism of \(F'\) if and only if \(f(z_{u_0})=z_{u_0}\). Since the size of the orbit of \(u_0\) is at least 2, \(\mathrm{Aut}(F')\) is isomorphic to a proper subgroup of \(Q\), which completes the proof. ◻
It is also natural to consider the complexity of counting subgraphs whose automorphism group belongs to a given collection of groups \(\mathcal{Q}\). As anticipated, Lemma 12 can be generalized to any collection of groups in the following two corollaries, which in turn shows the corresponding hardness of the counting problem.
Corollary 13. Let \(\mathcal{Q}\) be any fixed collection of finite groups such that \(0<|\mathcal{Q}|<\infty\) and \(S_1\notin \mathcal{Q}\). For every \(\ell\in {\mathbb{N}}\), there is an \((\ell,k)\)-clique scaffold \(R\) where \(k:=O(\ell)\) with an independent set \(C\) such that for any \(X\subseteq \binom{C}{2}\), the automorphism group of \(R':=R\cup X\) is in \(\mathcal{Q}\) if and only if \(X=\emptyset\), that is, the property \(\neg \Psi_{\mathcal{Q}}^{(k)}\) contains an \(\ell\)-clique OR witnessed by \(R\).
Proof. We apply Lemma 12 with a suitable \(Q\in \mathcal{Q}\): Take any \(Q\in \mathcal{Q}\) and examine whether any proper subgroup of \(Q\) is in \(\mathcal{Q}\). If so, replace \(Q\) with one of its proper subgroups that is in \(\mathcal{Q}\) and repeat. Since \(\mathcal{Q}\) is finite, this eventually halts. Then, we apply Lemma 12 with this \(Q\) and \(\ell\). Now we have an \((\ell,O(\ell))\)-clique scaffold \(R:=F_{Q,\ell}\) and an independent set \(C\) such that \(\text{Aut}(F_{Q,\ell})\in \mathcal{Q}\) and \(\text{Aut}(R\cup X) \notin \mathcal{Q}\) for any non-empty \(X\subseteq \binom{C}{2}\), which completes the proof. ◻
By finding a minimal group not in \(\mathcal{Q}\), we obtain an analog of Lemma 8.
Corollary 14. Let \(\mathcal{Q}\) be any fixed collection of finite groups such that \(0<|\mathcal{Q}|<\infty\) and \(S_1\in \mathcal{Q}\). For every \(\ell \in {\mathbb{N}}\), there is an \((\ell,k)\)-clique scaffold \(R\), where \(k:=O(\ell)\), with an independent set \(C\) such that for any \(X\subseteq \binom{C}{2}\), the automorphism group of \(R':=R\cup X\) is not in \(\mathcal{Q}\) if and only if \(X=\emptyset\), that is, the property \(\Psi_{\mathcal{Q}}^{(k)}\) contains an \(\ell\)-clique OR witnessed by \(R\).
Then the main reduction from Section 3 can be applied straightforwardly.
Proof of Theorem 2. By Corollary 13 and Corollary 14, for every \(\ell\in {\mathbb{N}}\), there exists \(k=O(\ell)\) such that either \(\Psi_{\mathcal{Q}}^{(k)}\) or \(\neg \Psi_{\mathcal{Q}}^{(k)}\) contains an \(\ell\)-clique OR, depending on whether \(S_1 \in \mathcal{Q}\). The theorem follows by applying Theorem 6. ◻
6 Edge-densities of Asymmetric Graphs↩︎
We show that there are only \(O(k)\) distinct edge-counts \(m\) such that every \(k\)-vertex \(m\)-edge graph is symmetric.
Lemma 15. For sufficiently large \(k\in {\mathbb{N}}\) and any \(2k\le m \le \binom{k}{2} - 2k\), there exists an asymmetric graph on \(k\) vertices and \(m\) edges.
Proof. We assume without loss of generality that \(m \leq \binom{k}{2}/2\): For larger \(m\), we construct a graph whose complement is asymmetric; taking complements preserves asymmetry.
In the following, we present two constructions, each addressing a certain range of edge densities. The lemma then follows by case distinction: Choose Construction 1 for \(m \leq k^2/51\) and Construction 2 otherwise.
Construction 1: For \(2k\le m \le k^2 / 51\), we use a modified ladder. Recall that the ladder \(F_{\ell}\) consists of \(4\ell\) vertices and \(6\ell-3\) edges; by Lemma 8, it is asymmetric if any non-empty subset of free edges is added to the ladder. Let \(k=4\ell+r\) for some \(\ell\) and \(0\le r \le 3\). To accommodate the vertex count, we replace the edge \(\{(1,2\ell),(2,2\ell)\}\) with a path of length \(r+1\) in \(F_{\ell}\) when \(r\neq 0\), which preserves the asymmetry, and then add arbitrary \(m-(6\ell-3+r)>0\) free edges to obtain an asymmetric graph with the required number of edges. By the definition of \(F_{\ell}\), there are at least \(\binom{\ell}{2}\ge \binom{k/5}{2}\ge \frac{1}{51}k^2\) available free edges, which is sufficient for this range of \(m\).
Construction 2: For \(2k\log k\le m \le \binom{k}{2}/2\), we use an “indexed clique”. We define a base graph \(F\) together with a set of free edges \(X\). Let \(F\) contain a clique \(I\) of size \(\lceil \log k\rceil\), where each vertex is attached by a path of a unique length from \(\{1,2,\dots,\lceil \log k\rceil\}\). The remaining \(t := k - \lceil \log k \rceil - \lceil \log k \rceil(\lceil \log k \rceil+1)/2\) vertices, denoted by \(v_1, \dots, v_t\), are joined to \(I\) such that each \(v_i\) possesses a unique neighborhood in \(I\) of cardinality at least two. Formally:
\(N(v_i) \cap I \neq N(v_j) \cap I\) for all \(i \neq j\), and
\(|N(v_i) \cap I| \ge 2.\)
Let \(X\) denote the set of all potential edges with both endpoints in \(\{v_i\}_{i \in [t]}\).
Let \(F':=F\cup Y\) for any \(Y\subseteq X\). Any automorphism \(f\) of \(F'\) must fix the attached paths pointwise, as the vertices of degree one are distinguished by their unique distances to the nearest vertex of degree at least three. Consequently, \(f\) also fixes \(I\) pointwise. It then follows that \(f\) must map \(v_i\) to \(v_i\) due to their distinct neighborhoods in \(I\). Hence, \(f\) is the identity map, rendering \(F'\) asymmetric.
In this construction, the number of edges in \(F\) is at most \[\binom{\lceil \log k\rceil}{2}+\frac{(\lceil \log k\rceil+1)(\lceil \log k\rceil+2)}{2}+k\lceil \log k\rceil \le 2k\log k.\] The number of available free edges is \(|X| = \binom{t}{2} > \binom{k}{2}/2\) for sufficiently large \(k\). ◻
References↩︎
In fact, \(Q\) is realized by infinitely many non-isomorphic graphs \(H\). For example, the group \(Q=S_3\) is realized by \(K_3\) or \(K_{1,3}\), or by any uniform subdivision of \(K_{1,3}\).↩︎
In terms of Boolean functions, this amounts to a restriction of \(\Phi\) to a subcube \(\Phi|_R : \{0,1\}^{E(K_\ell)}\to \{0,1\}\) specified by the offset \(R\), see [7], [19].↩︎
In principle, the reduction from \(\ell\)-cliques works whenever \(\Phi|_R\) has Fourier degree \(\ell \choose 2\). However, both the construction of the clique scaffold and the reduction from counting \(\ell\)-cliques are particularly straightforward when \(\Phi|_R\) is a Boolean OR.↩︎