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

• The question in the title is different from the question in the body. Which one is correct? Mar 7, 2019 at 8:24
• Sorry, the body is correct. Edited. Mar 7, 2019 at 8:29
• Interesting question. Where does it come from? Mar 7, 2019 at 8:30
• It comes from my research in a certain class of spin-glass model. Mar 7, 2019 at 8:33
• Let $P$ be the sum of the non-negative edge weights and $N$ be the sum of the negative edge weights. We want to show $${P+N\over P-N}\geq\frac12\iff P\geq-3N$$ Mar 7, 2019 at 8:51

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

• Thank you. At least I don't feel so stupid for not being able to prove it. This is going to take me some effort to absorb. I am reasonably certain that this has earned the bounty, but I need to take a bit of time to understand the solution before making the award. Mar 17, 2019 at 19:50
• Where it says, "Number the edges of 𝐺 by $1,…,𝑛,$" did you mean to say "number the vertices?" Mar 17, 2019 at 20:01
• I took the liberty of correcting what seems an obvious typo. May I ask if this result about spin glass graphs was previously known, or if you just solved the problem now? I'm going to have to read up on Paley graphs. (I think quasi-random graphs are probably beyond me) but I will award this answer the bonus as soon as I am permitted to. Mar 17, 2019 at 21:16
• @saulspatz: I did mean to say vertices. The links between quasirandomness (more generally, dense graph limits) and statistical physics of mean field models are very well explored, but it is always hard to point to a specific result
– Dap
Mar 18, 2019 at 6:39
• @PeaBrane: I get $0.313609$ for the result of plugging in the Paley graph $QR(13)$ to the construction in my answer, but I haven't checked the calculation very carefully. $E$ is chosen to be a symmetric matrix so that identity is just of the form $A=\tfrac12 A+\tfrac12 A$
– Dap
Mar 22, 2019 at 13:44

For concreteness I carried out the construction suggested by Dap for some small Paley graphs. With $$QR(5)$$ the fraction is $${13\over 25}>\frac12,$$ but with $$QR(9)$$ I got $${44\over81}=0.407407...$$

Here is the graph: $$\left[\begin{matrix}1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1\\1 & 1 & 1 & -1 & 1 & 1 & 1 & 1 & -1\\-1 & 1 & 1 & 1 & 1 & 1 & -1 & 1 & -1\\-1 & -1 & 1 & 1 & -1 & 1 & 1 & 1 & 1\\1 & 1 & 1 & -1 & 1 & 1 & -1 & -1 & 1\\-1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & 1\\1 & 1 & -1 & 1 & -1 & 1 & 1 & 1 & 1\\1 & 1 & 1 & 1 & -1 & -1 & 1 & 1 & -1\\1 & -1 & -1 & 1 & 1 & 1 & 1 & -1 & 1\end{matrix}\right]$$
The entry in row $$i,$$ column $$j$$ is the weight of the edge joining $$v_{1i}$$ and $$v_{2j}.$$ One can verify that the assignment of all ones maximizes the energy.

With $$QR(13)$$ I computed a fraction a fraction of $${53\over169}\approx0.3136094674556213,$$ confirming Dap's result. The matrix is $$\left[\begin{array}{ccccccccccccc}1 & -1 & 1 & 1 & 1 & -1 & 1 & 1 & 1 & 1 & 1 & -1 & 1\\-1 & 1 & -1 & -1 & 1 & 1 & 1 & 1 & 1 & -1 & 1 & 1 & -1\\1 & -1 & 1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & 1\\1 & -1 & 1 & 1 & -1 & 1 & 1 & 1 & -1 & 1 & 1 & 1 & -1\\1 & 1 & -1 & -1 & 1 & -1 & -1 & 1 & 1 & 1 & 1 & 1 & 1\\-1 & 1 & 1 & 1 & -1 & 1 & 1 & -1 & 1 & -1 & 1 & 1 & 1\\1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & 1 & 1 & 1 & -1 & -1\\1 & 1 & 1 & 1 & 1 & -1 & -1 & 1 & -1 & -1 & 1 & 1 & -1\\1 & 1 & 1 & -1 & 1 & 1 & 1 & -1 & 1 & 1 & -1 & 1 & 1\\1 & -1 & -1 & 1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & 1 & -1\\1 & 1 & -1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 & 1 & -1 & 1\\-1 & 1 & 1 & 1 & 1 & 1 & -1 & 1 & 1 & 1 & -1 & 1 & -1\\1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & -1 & 1\end{array}\right]$$