Does there exist a constant $\alpha>0$ such that the following holds? $$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(x_i-x_j)^2}{n}\geq\alpha$$ This is related to the Laplacian of a special graph with adjacency matrix $A_{ij}=1$ when $|i-j|\leq n/4$ and 0 otherwise. This conjecture essentially says that the second smallest eigenvalue of the unnormalized Laplacian will grow linearly in $n$. This is definitely true if the graph is fully connected.

  • $\begingroup$ Did you try approaching it via the Cheeger inequality? It shouldn't be too hard to find a good lower bound on the Cheeger constant for these graphs. $\endgroup$ Nov 25, 2020 at 23:38
  • $\begingroup$ @BrendanMcKay: doesn’t a lower bound on the Cheeger constant give you an upper bound on the second eigenvalue, rather than a lower bound? $\endgroup$ Nov 26, 2020 at 7:53
  • $\begingroup$ @AnthonyQuas Actually both. If $h$ is the Cheeger constant, $\lambda_2$ is the second smallest eigenvalue, and $\varDelta$ is the maximum degree, then $\frac12\lambda_2\le h\le \sqrt{\lambda_2(2\varDelta-\lambda_2)}$. (B. Mohar, JCT(B), 47 (1989) 274-291) $\endgroup$ Nov 26, 2020 at 11:30
  • $\begingroup$ @BrendanMcKay How to calculate the Cheeger constant for this graph? $\endgroup$ Nov 26, 2020 at 16:27

1 Answer 1


$\newcommand\Om\Omega\newcommand\de\delta\newcommand\tL{\tilde L}$ It will be useful to restate the problem in probabilistic terms.

Consider the probability space $\Om_n:=[n]^2$ with $P(\{(i,j)\})=1/n^2$ for all $(i,j)\in[n]^2$, where $[n]:=\{1,\dots,n\}$. Let $Y$ and $Z$ be random variables (r.v.'s) defined on $\Om_n$ as follows: \begin{equation*} Y((i,j)):=x_i\sqrt n,\quad Z((i,j)):=x_j\sqrt n \end{equation*} for all $(i,j)\in[n]^2$, so that $Y$ and $Z$ are iid zero-mean unit-variance r.v.'s.

It suffices to show that \begin{equation*} E(Y-Z)^2\,1_C\ge c \tag{-2} \end{equation*} for some universal constant $c>0$ and all large enough $n$, where \begin{equation*} C:=\{(i,j)\in[n]^2\colon|i-j|\le n/4\}. \end{equation*}

Suppose that $n\ge8$. Partition the interval $[n]$ into intervals $\de_1,\dots,\de_8$ in $\mathbb N$ of lengths as equal as possible, so that for any $k$ and $l$ in $[8]$ such that $k<l$ the interval $\de_k$ is to the left of $\de_l$, and \begin{equation*} p_k:=P(A_k)=P(B_k)\ge p:=1/15 \tag{-1} \end{equation*} for all $k\in[8]$, where \begin{equation*} A_k:=\de_k\times[n],\quad B_k:=[n]\times\de_k. \tag{-0.5} \end{equation*} Note that events $A_k$ and $B_l$ are independent for any $k,l$ in $[n]$.

The first crucial observation is that
\begin{equation*} \begin{aligned} C\supseteq D&:=\bigcup_{j=1}^4\big((A_{2j-1}\cup A_{2j})\cap(B_{2j-1}\cup B_{2j})\big) \\ &\cup\bigcup_{j=1}^3(A_{2j}\cap B_{2j+1}) \cup\bigcup_{j=1}^3(A_{2j+1}\cap B_{2j}), \end{aligned} \tag{0} \end{equation*} and all these intersections are pairwise disjoint. Therefore, letting \begin{equation*} I_k:=1_{A_k},\quad J_k:=1_{B_k} \tag{0.5} \end{equation*} for each $k\in[8]$, we get \begin{equation*} \begin{aligned} E(Y-Z)^2\,1_C\ge L&:=E(Y-Z)^2\,1_D \\ &=E(Y-Z)^2\,\Big(\sum_{j=1}^4\big((I_{2j-1}+I_{2j})(J_{2j-1}+J_{2j})\big) \\ & +\sum_{j=1}^3 I_{2j} J_{2j+1}+\sum_{j=1}^3 I_{2j+1} J_{2j}\Big). \end{aligned} \tag{1} \end{equation*} Writing now $(Y-Z)^2=Y^2+Z^2-2YZ$, recalling that $Y$ and $Z$ are iid r.v.'s, and introducing \begin{equation*} m_{2,k}:=EY^2I_k=EZ^2J_k, \quad m_{1,k}:=EYI_k=EZJ_k, \tag{1.5} \end{equation*} we see that \begin{equation*} \begin{aligned} L&=\tL:=2\sum_{j=1}^4 \big((m_{2,2j-1}+m_{2,2j})(p_{2j-1}+p_{2j})-(m_{1,2j-1}+m_{1,2j})^2\big) \\ & +2\sum_{j=1}^3 \big(m_{2,2j} p_{2j+1}+m_{2,2j+1} p_{2j}-2m_{1,2j+1} m_{1,2j}\big). \end{aligned} \tag{2} \end{equation*}

The conditions that $Y$ is zero-mean and unit-variance imply that \begin{equation*} \sum_{k=1}^8 m_{1,k}=0,\quad \sum_{k=1}^8 m_{2,k}=1. \tag{3} \end{equation*} Moreover, by the Cauchy--Schwarz inequality, \begin{equation*} m_{2,k}\ge m_{1,k}^2/p_k\quad \forall k\in[8]. \tag{4} \end{equation*} Finally, by (-1), \begin{equation*} p_k\in[1/15,1], \quad \sum_{k=1}^8 p_k=1. \tag{5} \end{equation*}

By compactness, the minimum -- say $\tL_{\min}$ -- of $\tL$ given (3)--(5) is attained. So, it remains to show that $\tL_{\min}>0$. Suppose otherwise: that $\tL=\tL_{\min}\le0$.

The second crucial point is that for any $m_{2,1},\dots,m_{2,8},m_{1,1},\dots,m_{1,8},p_1,\dots,p_8$ satisfying conditions (3)--(5), there exist r.v.'s $Y$ and $Z$ (defined, say, on the standard probability space over $\Om:=[0,1]^2$) and events $A_1,\dots,A_8,B_1,\dots,B_8$ such that, with the $I_k$'s and $J_k$'s still defined by (0.5), the nonuples $(Y,I_1,\dots,I_8)$ and $(Z,J_1,\dots,J_8)$ are iid, $(A_1,\dots,A_k)$ is a partition of $\Om$, $(B_1,\dots,B_k)$ is also a partition of $\Om$, $P(A_k)=P(B_k)=p_k$ for all $k\in[8]$ (cf. (-1)), and $Y$ and $Z$ are iid zero-mean unit-variance r.v.'s such that
$EY^2I_k=EZ^2J_k=m_{2,k}$ and $EYI_k=EZJ_k=m_{1,k}$ (cf. (1.5)).

$\Big($Indeed, all these conditions can be satisfied e.g. as follows. Re-define here $\de_1,\dots,\de_8$ as non-overlapping subintervals $[0,1]$ of lengths $p_1,\dots,p_8$, and then re-define $A_1,\dots,A_8,B_1,\dots,B_8$ by the formula \begin{equation*} A_k:=\de_k\times[0,1],\quad B_k:=[0,1]\times\de_k; \end{equation*} cf. (-0.5). Finally, for each $k\in[8]$ partition the interval $\de_k$ (of length $p_k$) into two subintervals, say $\eta_k$ and $\zeta_k$, each of length $p_k/2$, and let \begin{equation*} Y:=\sum_{k=1}^8(u_k\,1_{\eta_k\times[0,1]}+v_k\,1_{\zeta_k\times[0,1]}), \quad Z:=\sum_{k=1}^8(u_k\,1_{[0,1]\times\eta_k}+v_k\,1_{[0,1]\times\zeta_k}), \end{equation*} where \begin{equation*} u_k:=\frac{m_{1,k}-\sqrt{p_k m_{2,k}-m_{1,k}^2}}{p_k}, \quad v_k:=\frac{m_{1,k}+\sqrt{p_k m_{2,k}-m_{1,k}^2}}{p_k}. \end{equation*} Then all the conditions on events $A_1,\dots,A_8,B_1,\dots,B_8$ and r.v.'s $Y,Z$ listed in the paragraph just above will be satisfied.$\Big)$

So, the minimum value of $L$ coincides with $\tL_{\min}$, which was assumed to be $\le0$. Since $L\ge0$, we may now assume without loss of generality that $L=0$. Looking now back at (1), we see that then $Y=Z$ almost surely (a.s.) on the event $D$, still defined as in (0).

Therefore and because $Y$ and $Z$ are iid, it follows (i) that $Y$ is a.s. constant on $A_{2j-1}\cup A_{2j}$ for each $j\in[4]$ and (ii) $Y$ is a.s. constant on $A_{2j}\cup A_{2j+1}$ for each $k\in[3]$. So, $Y$ is a.s. constant on $\Om$. Since $EY=0$, we have $Y=0$ a.s., which contradicts the condition that $Y$ is of unit variance. $\Box$

If one is curious, numerical minimization of $L$ given (3) and (4) with $p_1=\dots=p_8=1/8$ gives about the same result by three different methods: $L\ge0.038060$. So, it appears that, at least for large enough $n$, the best constant $c$ in (-2) is $>3/100$. Here is an image of the corresponding Mathematica notebook:

enter image description here

  • $\begingroup$ Doesn't $A_3\cap B_4$ show up twice in the union, equation (0)? $\endgroup$ Nov 25, 2020 at 18:55
  • $\begingroup$ The proof is very interesting! Any intuition how you came up with this? $\endgroup$ Nov 25, 2020 at 22:02
  • $\begingroup$ @AnthonyQuas : Thank you for your comment. This is now fixed. $\endgroup$ Nov 26, 2020 at 1:28
  • $\begingroup$ @neverevernever : I am glad you liked the proof. I guess the main idea was this: I had to be able to make the "chain" statement (i)--(ii) in the last paragraph of the proof. To that end, the needed "links" of the desired "chain" were added in the second line of the definition of $D$ in (0). $\endgroup$ Nov 26, 2020 at 1:35

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.