Sur l'évaluation $t(M; 2,\,0)$ du polynôme de Tutte d'un matroïde et une conjecture de B. Grünbaum relative aux arrangements de droites du plan.

November 1980

Let $t(\scr M;x,y)$ denote the Tutte polynomial of the matroid $\scr M$. If $\scr M$ is the underlying matroid of an oriented matroid $\scr O$ then, as M. Las Vergnas has shown, $t(\scr M;2,0)$ is the number of complete acyclic sets of $\scr O$. (If $\scr O$ is the oriented matroid which arises from an arrangement of hyperplanes through the origin in Euclidean space then this is the number of regions of maximal dimension in the cell complex determined by the arrangement.) In this paper, it is proven that $2^{r-1}(n-r+2)\leq t(\scr M;2,0)\leq 2\sum_{i=0}^{r-1}( \smallmatrix n-1 \\ i \endsmallmatrix )$ for any matroid of rank $r$ having $n$ points (not necessarily orientable), thereby generalizing the identical result for oriented matroids. Also given are conditions on $\scr M$ under which these inequalities can be strengthened. Of particular interest is the result that if $\scr M$ is a matroid of rank 3 with $n\geq 9$ points and if $t(\scr M;2,0)>6n-10$ then $t(\scr M;2,0)\geq 8(n-3)$. This establishes and generalizes a conjecture of B. Grünbaum [Arrangements and spreads, Amer. Math. Soc., Providence, R.I., 1972; MR0307027 (46 #6148)]. This conjecture was partially established by G. B. Purdy [Discrete Math. 25 (1979), no. 2, 157--163; MR0523090 (80h:05017); Geom. Dedicata 9 (1980), no. 1, 107--109; MR0566442 (81e:51002)]. Reviewed by Jim Lawrence

Authors in the community:

• 

  R

  Raúl Manuel Cordovil Cordeiro Vinagre

  ist23593

European Journal of Combinatorics

317

322

1

4

mathematics - Mathematics

eng - English