# Is this bound uniform in $N$?

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 $C$ independent of the values $x_i,x_j$? – André Porto Oct 21 '18 at 15:24
• yes, that's right – André Oct 21 '18 at 15:28
• I think your computation for all 1's is bit inaccurate and we should get the constant exactly $1/4$ (my answer suggests this). In the left hand side we must have $2\binom{N}2$ (corr. to $i=j$) plus $\binom{N}2(2N-4)$ (corr. to $2N-4$ edges which share a common vertex with fixed edge of a complete graph) – Fedor Petrov Oct 21 '18 at 20:59

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.
• I am afraid that no: it may appear that $\sum x_i u_i=0$ (choose generic $x's$ corresponding to edges and define after that $x$'s corresponding to vertices so that $\sum x_i u_i$ becomes equal to 0), but $\sum x_i\ne 0$. – Fedor Petrov Oct 22 '18 at 7:33
• Consider all arrays $(x_i)$ for which $\sum x_i u_i=0$. They form a subspace $\Phi$ in the space of all arrays. The space $\Phi^\perp$ consisting of arrays $(y_i)$ satisfying $\sum x_iy_i=0$ for all $y_i\in \Phi$ and it consists of the arrays $(v\cdot u_i),v\in \mathbb{R}^N$. Thus $\sum x_i=0$ if and only if there exists a vector $v$ satisfying $v\cdot u_i=1$ for all $i$. It is easy to see that such a vector $v$ must have equal coordinates if $\{u_i\}$ contain all $k$-sets, $k<N$ being fixed, and two vector for different $k$ do not match. – Fedor Petrov Oct 22 '18 at 10:09