11 problems

FP-versus-symmetric subtraction conjecture. $[\mathrm{FP}-\text{\normalfont\textsc{\#mon2sat}}]^{\log}$ is strictly contained in…

For a poset $P$, its sign imbalance is the absolute difference between the numbers of even and odd linear extensions. The computational problem Sign Imbalance takes a poset $P$ as…

Let $G=(V,E)$ be a simple planar graph, and let $tr(G)$ be the number of trees in $G$ of all sizes. Planar tree-counting conjecture. The function $tr$ is concise: every positive in…

Let $\mathbf d=(d_1,\ldots,d_n)\in\mathbb N^n$ satisfy $0\le d_i\le n-1$, and let $c(\mathbf d)$ be the number of simple graphs on vertices $v_1,\ldots,v_n$ with $\deg(v_i)=d_i$ fo…

Let $b(M)$ denote the number of bases of a matroid $M$, and restrict $b$ to bicircular matroids. A counting function is concise if every positive integer occurs on an input of size…

Let $\mathbf a\in\mathbb N^r$ and $\mathbf b\in\mathbb N^s$ have common size $n=|\mathbf a|=|\mathbf b|$, and let $\operatorname{CT}(\mathbf a,\mathbf b)$ be the number of continge…

For a partition $\lambda$, let $g(\lambda,\mu,\nu)$ be the Kronecker coefficient and define the symmetric Kronecker coefficient by … A counting function is concise if every positiv…

Let $e(P)$ be the number of linear extensions of a finite poset $P$, and let $e'$ denote its restriction to posets of height two. Write $\mathcal T_{e'}$ for the set of values atta…

Let $\varphi$ be a univariate polynomial closure property of $\#P$, and say that it relativizes when the corresponding closure holds for every oracle version $\#P^A$. Univariate bi…

Let $\varphi$ be a multivariate polynomial closure property of $\#P$, meaning that applying $\varphi$ to polynomially many $\#P$ functions yields a function in the indicated class.…

Faben and Jerrum's conjecture. The problem $\oplus \operatorname{HomsTo}(H)$ is in $\mathrm{FP}$ if the involution-free reduction of $H$ is the empty graph, a singleton vertex with…