Frustration of a weighted bipartite graph Given a bipartite graph with $|V_1|=n$ and $|V_2|=m$, we can assign each vertex with value $-1$ or $1$, and we can assign each edge with any real value. Define an energy function as such:
$$ V = \sum_{ij} E_{ij}v_{1i}v_{2j} $$
where $v_{1i}$ denotes the value of $i$'th vertex in the first subset, $v_{2j}$ denotes the value of the $j$'th vertex in the second subset, and $E_{ij}$ denotes the value of the edge connect the two vertices.
Assuming that we have an assignment of edge values $\mathbf{E}$ such that the maximum energy is realized when all the vertices are assigned $1$, then what is the lower bound of the following value:
$$\frac{\sum_{ij} E_{ij}}{\sum_{ij} |E_{ij}|}$$
I ran a number of simulations and it seems that this value is bounded below by $0.5$, but I want to prove this analytically, but don't know where to start. Any tips would be appreciated.
 A: There is no constant positive lower bound for
$$\frac{\max\sum E_{ij}v_{1i}v_{2j}}{\sum|E_{ij}|}.$$
For any $\epsilon>0,$ there are large $\epsilon$-quasirandom graphs $G$ in the sense that
$$|e(S)-\tfrac14 |S|^2|\leq \epsilon |V(G)|^2$$
for all subsets $S\subseteq V(G).$ Here $e(S)$ denotes the number of edges whose endpoints both lie in $S.$ See Chung, Graham, Wilson's "Quasirandom graphs" - you can take $G$ to be a large Paley graph.
Let $\epsilon>0.$ Set $n=m=|V(G)|$ and take the underlying spin glass graph to be $K_{n,n}.$ Number the vertices of $G$ by $1,\dots,n.$ For $1\leq i,j\leq n$ define $E_{ij}$ to be $1$ if $ij$ is an edge of $G,$ and $-1$ otherwise.
So $\sum|E_{ij}|=n^2.$
By $\epsilon$-quasirandomness, for any $S\subseteq \{1,\dots,n\}$ we have
$$|\sum_{i,j\in S}E_{ij}|=|4e(S)-|S|^2|\leq 4 \epsilon n^2.$$
For any $S,T\subseteq\{1,\dots,n\}$ we have
\begin{align*}
&\sum_{(i,j)\in S\times T}E_{ij}\\
&=\tfrac12\sum_{(i,j)\in S\times T}E_{ij}+\tfrac12\sum_{(i,j)\in T\times S}E_{ij}\\\\
&=
\tfrac12\sum_{i,j\in S\cup T}E_{ij}
+\tfrac12\sum_{i,j\in S\cap T}E_{ij}
-\tfrac12\sum_{i,j\in S\setminus T}E_{ij}
-\tfrac12\sum_{i,j\in T\setminus S}E_{ij}
\end{align*}
which has absolute value at most $2 \epsilon n^2.$
So
$$\sum E_{ij}v_{1i}v_{2j}=\sum_{x,y\in\{-1,1\}}\sum_{\substack{i,j\\v_{1i}=x\\ v_{2j}=y}} E_{ij}v_{1i}v_{2j}\leq\sum_{x,y\in\{-1,1\}}2\epsilon n^2\leq 8\epsilon n^2.$$
(The third summation sign is over $i,j$ such that $v_{1i}=x$ and $v_{2j}=y.$)
We have shown that for any $\epsilon>0$ we can pick $n,m,E_{ij}$ such that
$$\frac{\max\sum E_{ij}v_{1i}v_{2j}}{\sum|E_{ij}|}\leq 8\epsilon.$$
Finally, take $w_{1i},w_{2j}\in\{-1,1\}$ maximizing $\sum E_{ij}w_{1i}w_{2j},$ and define $E'_{ij}=E_{ij}w_{1i}w_{2j}.$
This ensures that $\sum E'_{ij}v_{1j}v_{2j}$ is maximized at $v_{1i}=v_{2j}=1$ as required, and the value of $\max\sum E'_{ij}v_{1i}v_{2j}$ is the same as for $E_{ij}.$
