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

<p>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 &amp; -a_{ij} \\ -a_{ij} &amp; d_j\end{pmatrix}$ with $a_{ij}\in\{0,1\}$ and $d_i,d_j\ge a_{ij}$, and $d_i+d_j&gt;0$.</p>

<p>For any $\varepsilon&gt;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</p>

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

<p>$(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$.</p>

CC BY-SA 3.0
2016-11-21T19:33:03.103Z
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.
CC BY-SA 3.0
2016-11-21T20:52:20.393Z
@b.a Thanks for that - but the example can be adapted to still work with this restriction, see above.
Klaus Draeger
CC BY-SA 3.0
2016-11-21T22:04:02.543Z
you are right. I apologize for my carelessness. I edit my question again.
j.s.
CC BY-SA 3.0
2016-11-22T15:43:50.777Z
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.
Klaus Draeger
CC BY-SA 3.0
2016-11-21T18:33:29.153Z
2016-11-21T20:49:56.463Z
2016-11-21T20:49:56.463Z
Klaus Draeger
<p>For a graph $G$ on $n$ vertices, what is the value of following ratio: </p>

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

<p>where $L_G=D_G-A_G$ is the laplacian matrix of $G$? </p>

<p>Is this parameter related to the spectrum of $G$? </p>

<p>Is this parameter polynomially computable? </p>

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

CC BY-SA 3.0
2016-11-20T18:12:14.867Z
$x$ is an integer vector? Any other constraints?
Klaus Draeger
CC BY-SA 3.0
2016-11-20T18:14:29.997Z
Also note that in dimension $4$ and above, there will be vectors for which your denominator is $0$ due to the four-square theorem.
Klaus Draeger
CC BY-SA 3.0
2016-11-20T21:33:26.887Z
The denominator could be zero in any dimension, as there is no integrality constraint, it seems.
Sasho Nikolov
CC BY-SA 3.0
2016-11-21T19:40:07.497Z
@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.
CC BY-SA 3.0
2016-11-21T20:45:27.397Z
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.
Sasho Nikolov
CC BY-SA 3.0
2016-11-21T22:03:15.020Z
@Sasho Nikolov. you are right. I apologize for my carelessness. I edit my question.
j.s.
CC BY-SA 3.0
2016-11-22T16:37:43.443Z
Does it have any meaning ? geometric or combinatorial?
Igor Shinkar
<cc.complexity-theory><polynomial-time><spectral-graph-theory>
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?
j.s.
# 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?

(Asked by: username_0 on 2016-11-20)

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

**Tags:** cc.complexity-theory, polynomial-time, spectral-graph-theory

> **Comments:**
> **username_1**: $x$ is an integer vector? Any other constraints?  
> **username_1**: Also note that in dimension $4$ and above, there will be vectors for which your denominator is $0$ due to the four-square theorem.  
> **username_2**: The denominator could be zero in any dimension, as there is no integrality constraint, it seems.  
> **username_0**: @username_2. for the fraction in the remark, contant part of $f$ gives value $0$ in the numerator and a nonnegetive value in denominator.  
> **username_2**: 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.  
> **username_0**: @username_2. you are right. I apologize for my carelessness. I edit my question.  
> **username_3**: Does it have any meaning ? geometric or combinatorial?  

---

## 1 answers

### Answer by username_1 on 2016-11-21. Score: 1

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

> **Comments:**
> **username_0**: 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.  
> **username_1**: @b.a Thanks for that - but the example can be adapted to still work with this restriction, see above.  
> **username_0**: you are right. I apologize for my carelessness. I edit my question again.  
> **username_1**: 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.  

---

