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


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?

  • $\begingroup$ Is $C$ independent of the values $x_i,x_j$? $\endgroup$ – André Porto Oct 21 '18 at 15:24
  • $\begingroup$ yes, that's right $\endgroup$ – André Oct 21 '18 at 15:28
  • $\begingroup$ 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) $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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$. $\endgroup$ – Fedor Petrov Oct 22 '18 at 7:33
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Oct 22 '18 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.