4
$\begingroup$

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?

$\endgroup$
8
  • $\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$ Commented Jan 23, 2019 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
    Commented Jan 24, 2019 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$ Commented Jan 25, 2019 at 16:57
  • $\begingroup$ @GjergjiZaimi: Right, but this is the only exception. $\endgroup$
    – Seva
    Commented Jan 25, 2019 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$ Commented Jan 25, 2019 at 19:46

0

You must log in to answer this question.