Recall that a doubly-stochastic matrix is a square matrix with non-negative elements such the sum of the elements in every row, as well as in every column, is $1$. The set of doubly-stochastic matrices is described by the Birkhoff – von Neumann theorem. For the matrices of prime order $p\ge 3$, this theorem can be interpreted to describe the set of all functions $w\colon\mathbb F_p^2\to\mathbb R^+$ such that for some pair of fixed directions in $\mathbb F_p^2$, every line $l$ in any of these directions gets its exact share of the total mass of $w$: $$ \sum_{x\in l} w(x) = \frac1p\,\sum_{x\in\mathbb F_p^2 } w(x). \tag{$*$} $$

Let's say that a line $l\in\mathbb F_p^2$ is even if it satisfies ($*$), and that a direction in $\mathbb F_p^2$ is even if all $p$ lines in this directions are even. Suppose that, instead of just two even directions (as in the Birkhoff – von Neumann theorem), there are $k\ge 3$ even directions. Intuitively, one can expect much more structure in this case.

For a prime $p$ and integer $3\le k\le p$, what is the set of all functions $w\colon\mathbb F_p^2\to\mathbb R^+$ possessing at least $k$ even directions?

In particular, isn't this set of functions the matching polytope of some graph?

  • $\begingroup$ The naive conjecture is that it's given by the convex hull of special permutation matrices (those that have a 1 in every line paralel to any of the given directions). Is this known to be false? $\endgroup$ – Gjergji Zaimi Jan 23 at 22:04
  • $\begingroup$ @GjergjiZaimi: this is hardly the case; at least, not for large values of $k$. For $k>p/2$, for instance, there do not exist any permutation matrices with $k$ even directions. $\endgroup$ – Seva Jan 24 at 11:16
  • $\begingroup$ Isn't the indicator function of an arbitrary line that's not parallel to any of our directions always such a permutation? $\endgroup$ – Gjergji Zaimi Jan 25 at 16:57
  • $\begingroup$ @GjergjiZaimi: Right, but this is the only exception. $\endgroup$ – Seva Jan 25 at 17:26
  • $\begingroup$ Another equivalent way of phrasing my conjecture is that the vertices of this polytope (assuming we normalize the sum to 1 on each direction) are all lattice points. $\endgroup$ – Gjergji Zaimi Jan 25 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.