37 problems

Merino–Welsh conjecture. Every such graph satisfies

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

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…

Stanley's $h$-vector conjecture. For any matroid $M$, there exists such a set $X$ of monomials.

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…

Shteiner–Shteyner's conjecture. If $G$ is bipartite, then

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.…

The universal Tutte–Grothendieck invariant is a morphism of abelian groups … The map of $K$-theory spectra $K(\Gamma):K(\mathbf{Mat}^{\cong})\to K(\mathbf{Mat}^{\mathrm{tc}})$ lift…

Let $\mathcal{G}_{n,m}$ denote the class of graphs with $n$ vertices and $m$ edges, and order this class by the Tutte polynomial poset. A graph is Tutte-maximum if it is a maximum…

Let $\mathcal{G}_{n,n+3}$ be the class of graphs with $n$ vertices and $n+3$ edges, equipped with its Tutte polynomial poset, and consider the graphs described by Wang and by Liu a…

Let $G$ be a graph. Consider its number of spanning trees, its number of acyclic orientations, and its number of totally cyclic orientations. Welsh–Merino conjecture. The number of…

For $\alpha>0$, let ${\mathcal G}_\alpha$ be the class of $\alpha$-dense graphs $G=(V,E)$ satisfying $|E|\geq\alpha|V|$. An FPRAS for a function $f(x)$ is a randomized algorithm th…

Conde–Merino–Welsh conjecture. The following inequalities hold:

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…

Conjectured relationship. There is a relationship between this formula for the Tutte polynomial and the algebro-geometric formula for the Tutte polynomial. The conjecture proposes…

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 $R_1,R_2,\dots$ be the inclusion-wise increasing sequence of regions in the $(q,v)$ plane associated with the Jackson–Sokal hierarchy, and let $R^*$ denote a limiting region. J…

Let $G$ be a graph, and let $R_1$ be the zero-free region in the $(q,v)$ plane. A graph is 2-connected if it is connected and has no cut vertex. Jackson–Sokal's hierarchy conjectur…

Relationship conjecture. There is a relationship between the lattice-point-counting formula for the Tutte polynomial developed here and Speyer's algebro-geometric formula for the T…

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

Biggs's conjecture. The Biggs–Merino polynomial is equal to