1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ $x$ is an integer vector? Any other constraints? $\endgroup$
    – Klaus Draeger
    Commented Nov 20, 2016 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
    Commented Nov 20, 2016 at 18:14
  • $\begingroup$ The denominator could be zero in any dimension, as there is no integrality constraint, it seems. $\endgroup$
    – Sasho Nikolov
    Commented Nov 20, 2016 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.
    Commented Nov 21, 2016 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
    Commented Nov 21, 2016 at 20:45

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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.
    Commented Nov 21, 2016 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
    Commented Nov 21, 2016 at 20:52
  • $\begingroup$ you are right. I apologize for my carelessness. I edit my question again. $\endgroup$
    – j.s.
    Commented Nov 21, 2016 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
    Commented Nov 22, 2016 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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