# Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?

For a graph $G$ on $n$ vertices, what is the value of following ratio:

$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf} ,$$

where $L_G=D_G-A_G$ is the laplacian matrix of $G$?

Is this parameter related to the spectrum of $G$?

Is this parameter polynomially computable?

Remark: Note that we have $$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{f^Tf} = \lambda_n(G),$$ where $\lambda_n(G)$ is the largest eigenvalue of $L_G$.

• $x$ is an integer vector? Any other constraints? Nov 20 '16 at 18:12
• Also note that in dimension $4$ and above, there will be vectors for which your denominator is $0$ due to the four-square theorem. Nov 20 '16 at 18:14
• The denominator could be zero in any dimension, as there is no integrality constraint, it seems. Nov 20 '16 at 21:33
• @Sasho Nikolov. for the fraction in the remark, contant part of $f$ gives value $0$ in the numerator and a nonnegetive value in denominator.
– j.s.
Nov 21 '16 at 19:40
• you are right. but your formulation still allows a zero denominator. say, $n$ is even, and $f(v) \in \{\pm 1\}$ is positive on half the vertices. Nov 21 '16 at 20:45

## 1 Answer

Without any further constraints, this expression will in general be unbounded, so the maximum won't exist.

Let $V$ be $\{v_1,\ldots,v_n\}$ with $n\ge 2$. Pick $i\neq j$ such that $v_i,v_j$ are not both isolated. The submatrix of the Laplacian for $v_i,v_j$ has the form $\begin{pmatrix}d_i & -a_{ij} \\ -a_{ij} & d_j\end{pmatrix}$ with $a_{ij}\in\{0,1\}$ and $d_i,d_j\ge a_{ij}$, and $d_i+d_j>0$.

For any $\varepsilon>0$, define a function $f_\varepsilon:V\to\mathbb{R}$ by $f_\varepsilon(v_i) = \sqrt{n}-\varepsilon, f_\varepsilon(v_j) = \varepsilon - \sqrt{n}$, and $f_\varepsilon(v) = 0$ for all other $v\in V$. With this, your expression becomes

$(d_i + d_j + 2a_{ij})\frac{n-2\varepsilon\sqrt{n}+\varepsilon^2}{2\varepsilon\sqrt{n}-\varepsilon^2}$.

$(d_i+d_j-2a_{ij}) \ge 1$ by the above, and for $\varepsilon\to 0$, the numerator and denominator of the fraction converge to $n$ and $0$ (from above); therefore, the expression goes to $+\infty$.

• thank you very much. Dear Klaus, there is another constraint that at first I wrongly think it is surplus. I am sorry for this. I edit my question.
– j.s.
Nov 21 '16 at 19:33
• @b.a Thanks for that - but the example can be adapted to still work with this restriction, see above. Nov 21 '16 at 20:52
• you are right. I apologize for my carelessness. I edit my question again.
– j.s.
Nov 21 '16 at 22:04
• This new constraint makes the situation more difficult. I haven't actually tried to prove this, but I think a plausible hypothesis is that cutting $V$ in half (assuming $|V|$ is even) in such a way that the number of edges within the halves is minimized, and mapping $v$ to $1/2$ if $v\in V$ and $-1/2$ otherwise, is a good candidate for a maximizer. Nov 22 '16 at 15:43