Complexity in Enumerative Combinatorics — Conjecture 1 (Wilf)

Definitions and mathematical statement

Under the usual convention that graphs are finite, simple, and undirected, let $[n]=\{1,\ldots,n\}$ for each positive integer $n$. A graph on $[n]$ has an edge set $E\subseteq\binom{[n]}{2}$. Two such graphs are isomorphic if a permutation of $[n]$ carries one edge set to the other. Define \[ a_n=\left|\left\{E:E\subseteq\binom{[n]}{2}\right\}/\mathfrak S_n\right|, \] where $\mathfrak S_n$ acts by permuting vertices. Thus $a_n$ counts unlabeled graphs on $n$ vertices under this convention.

The supplied conjecture, attributed to Wilf and listed as Conjecture 1 in Pak's 2018 source, asserts:

The sequence $\{a_n\}$ has no Wilfian formula of type $\mathrm{(W1)}$.

The supplied record does not define a Wilfian formula of type $\mathrm{(W1)}$, including its computational model or complexity requirement. Consequently, this assertion retains an undefined source term and is not yet a complete formal computational statement. The graph convention above is a conventional interpretation requiring confirmation against the source; the record also does not specify whether the sequence includes $n=0$.

Short English statement

The conjecture attributed to Wilf says that the sequence counting unlabeled graphs has no Wilfian formula of type $\mathrm{(W1)}$. The supplied excerpt omits the definition of that formula type, so a precise complexity statement requires further source information.

Sources

• Local UnsolvedMath registry, permanent ID $800317$, source problem code catalogue entry, in the AMR Open Problem Lists collection. The supplied record labels the problem open; this status is not independently verified.
• Pak, Complexity Problems in Enumerative Combinatorics (2018), Conjecture 1. Supplied source URL: https://arxiv.org/abs/1803.06636. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not a claim of independent source access.
• Attribution/context: Wilf. The excerpt refers to an original paper labeled [Wilf], but supplies no title, publication details, or separate URL for that reference. The registry lists Pak as proposer and 2018 as the proposed year; these indexing fields do not resolve the original Wilf attribution or date.