Skip to main content
1 of 4
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

Does the matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the characteristic vectors of the bases $B\in\mathcal B$). Note that $P$ is contained in the hyperplane $H:=\{y\in\Bbb R^n\mid y_1+\cdots +y_n=r\}$ and that $\mathbf 1/r:=(1/r,...,1/r)\in H$.

Question: Do we have $\mathbf 1/r\in P$, or even better, $\mathbf 1/r\in\mathrm{relint}(P)$?

Here $\mathrm{relint}$ is the relative interior of $P$ (the interior of $P$ considered as a subset of its affine hull).

The title asks for the circumcenter instead of $\mathbf 1/r$. I am happy to know whether any point of constant distance to the vertices of $P$ is in $P$ or $\mathrm{relint}(P)$.

M. Winter
  • 13.6k
  • 3
  • 29
  • 70