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

  • 1
    $\begingroup$ $x$ is an integer vector? Any other constraints? $\endgroup$ – Klaus Draeger Nov 20 '16 at 18:12
  • $\begingroup$ Also note that in dimension $4$ and above, there will be vectors for which your denominator is $0$ due to the four-square theorem. $\endgroup$ – Klaus Draeger Nov 20 '16 at 18:14
  • $\begingroup$ The denominator could be zero in any dimension, as there is no integrality constraint, it seems. $\endgroup$ – Sasho Nikolov Nov 20 '16 at 21:33
  • $\begingroup$ @Sasho Nikolov. for the fraction in the remark, contant part of $f$ gives value $0$ in the numerator and a nonnegetive value in denominator. $\endgroup$ – j.s. Nov 21 '16 at 19:40
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 21 '16 at 20:45

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – j.s. Nov 21 '16 at 19:33
  • $\begingroup$ @b.a Thanks for that - but the example can be adapted to still work with this restriction, see above. $\endgroup$ – Klaus Draeger Nov 21 '16 at 20:52
  • $\begingroup$ you are right. I apologize for my carelessness. I edit my question again. $\endgroup$ – j.s. Nov 21 '16 at 22:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Klaus Draeger Nov 22 '16 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.