Counting Small Induced Subgraphs: Hardness via Fourier Analysis

For a fixed graph property and integer k 1, the problem \#IndSub (, k) asks to count the induced k-vertex subgraphs satisfying in an input graph G. If is trivial on k-vertex graphs (i. e. , if contains either all or no k-vertex graphs), this problem is trivial. Otherwise we prove, among other results: - If is edge-monotone (i. e. , closed under deleting edges), then \#IndSub (, k) cannot be solved in time n^o (k) assuming ETH. This strengthens a result by D\"oring, Marx and Wellnitz STOC 2024 that only ruled out an exponent of o (k/ k). Our results also hold when counting modulo fixed primes. - If there is some fixed > 0 such that at most (2-) ^k{2} graphs on k vertices satisfy, then \#IndSub (, k) cannot be solved in time n^o (k/ k) assuming ETH. Our results hold even when each of the graphs in 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 k factor in the exponent of the lower bound. - If only depends on the number of edges, then \#IndSub (, 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 / k). In all cases, we also obtain \#W1-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. Our results follow from relatively straightforward Fourier analysis, and our paper subsumes most of the known \#W1-hardness results known in the area, often with tighter lower bounds under ETH.