0
$\begingroup$

The following inequality comes from the literature: N. Alon, Y. Caro, On the number of subgraphs of prescribed type of planar graphs with a given number of vertices //North-Holland Mathematics Studies. North-Holland, 1984, 87: 25-36. This inequality plays a pivotal role in proving an upper bound on the number of copies of $K_{1,k}$ in planar graphs.

If $\bar{y}=\left(y_1, y_2, \ldots, y_n\right)$ and $\bar{z}=\left(z_1, \ldots, z_n\right)$ are nondecreasing sequences of positive integers, and if there exist $i$ and $j, 1 \leqslant i<j \leqslant n$, such that $z_i=y_i-1$, $z_i=y_i+1$ and $z_l=y_l$, for all $l \neq i, j$, then we say that $\bar{z}$ is obtained from $\bar{y}$ by a simple improvement. It is easily checked that in this case $$ \sum_{i=1}^n\left(\begin{array}{l} y_i \\ k \end{array}\right) \leqslant \sum_{i=1}^n\left(\begin{array}{l} z_i \\ k \end{array}\right), \text { for all } k \geqslant 2, $$ and the inequality is strict iff $y_j \geqslant k-1$.

The author states that it is easily verifiable, but I haven't yet conceived a rigorous proof for this inequality.

$\endgroup$

1 Answer 1

2
$\begingroup$

We wish to prove that $\sum{z_i\choose k}-\sum{y_i\choose k}\ge0$; by the conditions given this amounts to showing that $${y_j+1\choose k}-{y_j\choose k}+{y_i-1\choose k}-{y_i\choose k}\ge0.$$ Now \begin{align*} {y_j+1\choose k}-{y_j\choose k} &={(y_j+1)\dots(y_j-k+2)\over k!}-{y_j\dots(y_j-k+1)\over k!}\\ &={y_j\dots(y_j-k+2)\over k!}(y_j+1-(y_j-k+1))\\ &={y_j\dots(y_j-k+2)\over(k-1)!}; \end{align*} similarly we have $${y_i-1\choose k}-{y_i\choose k} =-{(y_i-1)\dots(y_i-k+1)\over(k-1)!}.$$ Thus we are left to prove that $$y_j\dots(y_j-k+2)\ge(y_i-1)\dots(y_i-k+1),$$ which follows from the fact that $y_j\ge y_i$.

$\endgroup$
2
  • $\begingroup$ Sorry. I still don't understand why proving ${y_j+1\choose k}-{y_j\choose k}+{y_i-1\choose k}-{y_i\choose k}\ge0$ is sufficient. $\endgroup$
    – licheng
    Commented Nov 12, 2023 at 13:56
  • $\begingroup$ I see. It is my mistake. I mistakenly interpreted all $l \neq i,j$ with $y_l=z_l$ as the existence of $l$ where $l \neq i,j$ with $y_l=z_l$. $\endgroup$
    – licheng
    Commented Nov 12, 2023 at 13:59

You must log in to answer this question.

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