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, ij\leq\frac{n}{4}}(x_ix_j)^2}{n}\geq\alpha$$ This is related to the Laplacian of a special graph with adjacency matrix $A_{ij}=1$ when $ij\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$– Brendan McKayNov 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$– Anthony QuasNov 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) 274291) $\endgroup$– Brendan McKayNov 26, 2020 at 11:30

$\begingroup$ @BrendanMcKay How to calculate the Cheeger constant for this graph? $\endgroup$– nevereverneverNov 26, 2020 at 16:27
1 Answer
$\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 zeromean unitvariance r.v.'s.
It suffices to show that \begin{equation*} E(YZ)^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\colonij\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_{2j1}\cup A_{2j})\cap(B_{2j1}\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(YZ)^2\,1_C\ge L&:=E(YZ)^2\,1_D \\
&=E(YZ)^2\,\Big(\sum_{j=1}^4\big((I_{2j1}+I_{2j})(J_{2j1}+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 $(YZ)^2=Y^2+Z^22YZ$, 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,2j1}+m_{2,2j})(p_{2j1}+p_{2j})(m_{1,2j1}+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 zeromean and unitvariance 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 CauchySchwarz 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 zeromean unitvariance 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. Redefine here $\de_1,\dots,\de_8$ as nonoverlapping subintervals $[0,1]$ of lengths $p_1,\dots,p_8$, and then redefine $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_{2j1}\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:

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