Return to Question

Federico Ardilla found a matroid whose Tutte polynomial $T_n(x,y)$ obeyed $T_n(1,1) = C_n$ and $T_n(x,y) = T_n(y,x)$. I have checked numerically that $T_n(x,y)$ appears to be $\sum c(p,q,n) x^p y^q$. Federico gives an explicit generating function for his polynomial (Theorem 3.6). From this formula, one can check that the coefficient of $x^p y^q$ depends only on $p+q$. I will add that this is a very unusual property for a Tutte polynomial to have, and I would be interested to know any general property of a matroid which implies it.

Federico Ardila found a matroid whose Tutte polynomial $T_n(x,y)$ obeyed $T_n(1,1) = C_n$ and $T_n(x,y) = T_n(y,x)$. I have checked numerically that $T_n(x,y)$ appears to be $\sum c(p,q,n) x^p y^q$. Federico gives an explicit generating function for his polynomial (Theorem 3.6). From this formula, one can check that the coefficient of $x^p y^q$ depends only on $p+q$. I will add that this is a very unusual property for a Tutte polynomial to have, and I would be interested to know any general property of a matroid which implies it.

Define a vertex $v$ to be "crucial" if $v$ is the youngest member of its generation, all the other members of that generation are childless, but $v$ has children. For example, in the tree $$\begin{matrix} & & a & & \\ & & \downarrow & & \\ & & b & & \\ & \swarrow & \downarrow & \searrow \\ c & & d & & e \\ & & \downarrow & & \downarrow \\ & & f & & g \\ & & \downarrow & \searrow & \\ & & h & & i \\ & & & & \downarrow \\ & & & & j \\ \end{matrix}$$ the crucial elements are $a$, $b$ and $i$. So the root is always crucial.

Define a vertex $v$ to be "crucial" if $v$ is the youngest member of its generation, all the other members of that generation are childless, but $v$ has children. For example, in the tree $$\begin{matrix} & & a & & \\ & & \downarrow & & \\ & & b & & \\ & \swarrow & \downarrow & \searrow \\ c & & d & & e \\ & & \downarrow & & \downarrow \\ & & f & & g \\ & & \downarrow & \searrow & \\ & & h & & i \\ & & & & \downarrow \\ & & & & j \\ \end{matrix}$$ the crucial elements are $a$, $b$, $f$ and $i$. So the root is always crucial.

This is something I found in trying to work on Vince Vatter's excellent question. I have no solution, but a much more precise conjecture.

The lists of integers in Vatter's question are a subset of lists above. Specifically, they are the ones where the root is the only crucial vertex. (Doug Zare's answer was very helpful in making me realize this description.) So our goal is to show that $\sum_q c(1,q,n)$ is Catalan. After a lot of computation, I came to the following conjecture:

This is something I found in trying to work on Vince Vatter's excellent question. I have no solution, but a much more precise conjecture.

The lists of integers in Vatter's question are a subset of lists above. Specifically, they are the ones where the root is the only crucial vertex. (Doug Zare's answer was very helpful in making me realize this description.) So our goal is to show that $\sum_q c(1,q,n)$ is Catalan. After a lot of computation, I came to the following conjecture: