6
$\begingroup$

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?

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

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Oct 22, 2018 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$ Oct 22, 2018 at 10:09

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.