We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.


Let $z\_{i,j}:=\frac{M\_{i,j}}{M\_{i,j}+\sum\_{k\neq i,j}\min(M\_{i,k},M\_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\sum\_{i<j}z\_{i,j}$.




---


**Question:** Can we prove that the maximum value $z^\*$ of $z$ over *all* matrices $M$ defined above is upper bounded by $\alpha n$ for some absolute constant $\alpha$?




---




---


***Note:*** *$M$ can be viewed as the adjacency matrix of a given undirected multi-edge graph. Alternatively, for all $1\le i<j\le n$, $M\_{i,j}$ can be viewed as an integer capacity in a symmetric flow network. For all $1\le i<j\le n$, $z\_{i,j}$ can be viewed as a function of the amount of "flow" between the two nodes $i$ and $j$ passing through paths of length at most $2$ (i.e., containing $2$ edges).*



Combinatorial graph optimization problem on integer adjacency matrices
Consider $$M\_{i,j} = \begin{cases} 1 & \textrm{if } i \equiv j \pmod 2 \\ N & \textrm{if } i \not\equiv j \pmod 2\end{cases}$$ where $N > 1$. Then
$$\min(M\_{i,k}, M\_{k,j}) = \begin{cases} 1 & \textrm{if } i \equiv k \pmod 2 \;\vee\; k \equiv j \pmod 2 \\ N & \textrm{if } i \not\equiv k \pmod 2 \;\wedge\; k \not\equiv j \pmod 2 \end{cases}$$


In particular, if $i \not\equiv j \pmod 2$ then $\forall k: \min(M\_{i,k}, M\_{k,j}) = 1$. We get $$z \ge \sum\_{i < j, i \not\equiv j \pmod 2} \frac{N}{N+n-2} = \left\lfloor \frac{n^2}{4} \right\rfloor \frac{N}{N+n-2}$$ and by choosing sufficiently large $N$ we can exceed $\frac{n^2 - 4}{4}$.


