20 problems

Let $H$ be a bipartite graph, and let $\widetilde{T}_H(x,y)$ denote its normalized Tutte polynomial. Assume that every vertex of $H$ has degree at least $2$. Merino–Welsh conjectur…

Characterization of strongly Tutte-descriptive activities. For any graph $G$, an activity $\psi$ is strongly Tutte-descriptive if and only if there exists a decision tree $\Delta$…

For a connected undirected graph $G$, let $T(G;x,y)$ denote its Tutte polynomial and let $\EuScript{K}(G)$ denote its critical group. Non-determination conjecture. There exist conn…

Cubic Tutte relation conjecture. The second derivative of Speyer's polynomial satisfies

Let $M$ be a matroid. A matroid is simple if it has no loops or parallel elements, and co-simple if its dual has no loops or parallel elements. Simple co-simple matroid conjecture.…

Boesch's conjecture. Each uniformly most reliable graph in $\mathcal{C}_{n,m}$ is a $0$-element in $\mathcal{C}_{n,m}$.

Merino–Welsh conjectures. The following three inequalities should hold:

Merino–Welsh conjecture. The inequality

Let $\bar\gamma(\underline{a};x,y)$ be the composition-indexed quantity used in the source. Let $(a_0,a_,\ldots,a_r)$ be a composition with $a_0=0$ and $a_r\geq 2$. Merino–Welsh co…

Let $M$ be a matroid with no loops or isthmuses, and let $T(M;x,y)$ denote its Tutte polynomial. Multiplicative Merino–Welsh conjecture. … This is presented as a seemingly stronger…

Let $M$ be a binary matroid, let $T_M(x,y)$ denote its Tutte polynomial, and let $z$ be an integer. Las Vergnas's second conjecture. The value … is an odd integer for every binary…

Jackson–Sokal's density conjecture. The zeros of the Tutte polynomials of graphs are dense in the following regions: (a) $q<0$ and $v<-2$; (b) $q<0$ and $0<v<-q/2$; (c)…

Let $M$ be a matroid without loops or coloops, and let $T(M;x,y)$ be its Tutte polynomial. Matroidal Merino–Welsh conjectures. The following inequalities hold: … … and … These conj…

Let $G$ be a graph with no bridges and no loops. Let $\tau(G)$ be its number of spanning trees, let $(G)$ be its number of acyclic orientations, and let $^*(G)$ be its number of to…

Subparking-function and acyclic-cut orientation conjecture. For any graph $G$ and choice of sink $q\in V(G)$, there exists an ordered, $q$-rooted spanning tree $T$ of $G$ such that

Inactivity conjecture. There exists an edge $e$ of $G$ such that, for every spanning tree $T$, $e$ does not belong to $\psi(T)$; equivalently, $e$ is active in no spanning tree.

Let $G$ be a connected undirected graph, let $s$ be a vertex of $G$, and let $N$ be the set of neighbors of $s$, excluding $s$. For each nonempty subset $W\subseteq N$, let…

Sink-independence conjecture. The sequence \left(\textbf{\texttt{\sum}}\,_{G,s}(B)\right)_{B\in\mathcal{C}/\sim} is independent of the choice of $s$, up to a permutation of its en…

Let $M$ be a matroid, and let $T_M(x,y)$ denote its Tutte polynomial. Say that $M$ contains two disjoint bases if it has bases $B_1$ and $B_2$ with $B_1\cap B_2=\varnothing$; alter…

Let $G$ be a finite planar self-dual lattice, or let $G$ be the square lattice with free or periodic boundary conditions in the thermodynamic limit. For $q\geq 1$, introduce $v$ by…