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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Fedor Petrov
    Commented 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$
    – Fedor Petrov
    Commented Oct 22, 2018 at 10:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .