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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.