Combinatorial graph optimization problem on integer adjacency matrices

Question

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).

Answer 1

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}$.