I encountered this small combinatorial problem and do not quite know how to solve it:


Consider a set $\mathbf N:=\left\{1,2,....,N \right\}.$ This set has $\binom{N}{2}$ many subsets of cardinality $2.$ Thus, we can introduce variables $x\_1,...,x\_{\binom{N}{2}}$ taking a value in $\mathbb R$ where each of the variables is associated to precisely one subset of $\mathbf N$ of cardinality $2.$


In other words there is a unique correspondence:


$x\_i \leftrightarrow M\_i$ where $M\_i \subset \mathbf N$ and $\left\lvert M\_i \right\rvert =2.$


I would like to know whether the following estimate is true:


$$ \frac{1}{N} \sum\_{i,j=1}^{\binom{N}{2}} x\_i x\_j \le C \sum\_{i,j=1}^{\binom{N}{2}} \left\lvert M\_i \cap M\_j \right\rvert x\_i x\_j ?$$
for some $C$ independent of $N$ and all $x\_i,x\_j$?


EDIT: 


It holds true if $x\_i=1$, since then the left hand side is $\binom{N}{2}^2/N=\frac{1}{4}(N-1)^2N$ and the right hand side is, using the hypergeometric distribution, $$2\binom{N}{2}+ \binom{N}{2}^2\frac{4}{N}=N(N-1)+N(N-1)^2.$$


So an obvious scaling argument does not disprove the estimate. However, it is not clear to me whether this estimate is true in general?


I emphasize that the left-hand side $\frac{1}{N} \sum\_{i,j=1}^{\binom{N}{2}} x\_i x\_j$ can be interpreted as $$\frac{1}{N} \langle (x\_1,..,x\_{\binom{N}{2}}),\mathbb 1 (x\_1,..,x\_{\binom{N}{2}})\rangle $$ 
where $\mathbb 1$ is the matrix with all entries equal to one. This one has one non-zero eigenvalue with eigenvector $(1,...1)$ and all other eigenvalues are zero. That's why I was particularly curious to study that case separately.


So does this inequality hold true in general?



Is this bound uniform in $N$?
Let $u\_i\in \mathbb{R}^N$ be a vector with two coordinates equal to 1 and other equal to 0, corresponding to the characteristic vector of the set $M\_i$. Then your inequality rewrites as $N^{-1}(\sum x\_i)^2\leqslant C(\sum x\_i u\_i)^2$. Denote $v=(1,1,\dots,1)\in \mathbb{R}^N$. Then $(u\_i,v)=2$ (here $(u,v)$ stands for the inner product of vectors $u,v$) and we have $2\sum x\_i=(\sum x\_i u\_i,v)$. Thus $$\left(\sum x\_i u\_i\right)^2\cdot N=\left(\sum x\_i u\_i\right)^2\cdot v^2\geqslant \left(\sum x\_i u\_i,v\right)^2=4\left(\sum x\_i\right)^2$$
as desired.


