Complexity in Enumerative Combinatorics — Conjecture 2

Definitions and mathematical statement

A planar graph is a graph admitting an embedding in the plane without edge crossings. A plane graph is a graph equipped with such an embedding. A plane triangulation ordinarily means a plane graph in which every face, including the unbounded face, has boundary length three. A graph is $3$-connected if it has at least four vertices and remains connected after deletion of any set of at most two vertices.

For each admissible vertex number $n$, the supplied source defines \[ a_n=\#\{\text{unlabeled plane triangulations with }n\text{ vertices}\}, \qquad b_n=\#\{\text{$3$-connected planar graphs with }n\text{ vertices}\}. \] Here $\#$ denotes the number of objects under the intended counting convention. The source does not fully specify that convention: in particular, the graph class, equivalence of plane embeddings, and labeling convention for $b_n$ require clarification.

Conjecture 2 (Pak, 2018; supplied formulation). The sequences $\{a_n\}$ and $\{b_n\}$ can be computed in time polynomial in $n$. Under the interpretation that this asks for individual exact coefficients, the claim is that there exist algorithms $A,B$ and polynomials $p,q$ such that, for every admissible $n$, \[ A(n)=a_n,\qquad B(n)=b_n,\qquad T_A(n)\le p(n),\qquad T_B(n)\le q(n). \] This algorithmic formulation is conditional on fixing the counting conventions and computational model. The supplied excerpt does not specify input and output encodings, whether individual coefficients or initial segments are requested, or the values and conventions for small $n$. No such choices are asserted here.

Short English statement

Pak's supplied conjecture asks whether the exact numbers of unlabeled plane triangulations and of $3$-connected planar graphs with $n$ vertices can be computed in time polynomial in $n$. Counting conventions and computational details remain unresolved. The registry labels the problem open; that label is supplied curation, not an independently verified status assessment.

Sources

• Local UnsolvedMath registry, permanent ID $800318$, source problem code catalogue entry, title "Complexity in Enumerative Combinatorics --- Conjecture 2." The record attributes the conjecture to Pak (2018) and labels it open. Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Pak, Complexity Problems in Enumerative Combinatorics (2018), Conjecture 2. Supplied source URL: https://arxiv.org/abs/1803.06636. The source record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not claims of independent source access or verification.