MathB.in - Share Mathematics with LaTeX and Markdown

The inequality is trivial for $N = 1$, so we are free to assume $N \geq 2$.

Define a *cherry* as an ordered pair $(u, \{v, w\})$, where $u, v, w$ are vertices of our graph, $v \neq w$, and $u$ is adjacent to both $v$ and $w$. The vertex $u$ will be called the *tip* of the cherry. We will count the number of unique cherries in our graph in two different ways:

Let us denote by $d_i$ the degree of $b_i$.

On the one hand, there are ${d_i\choose 2}$ ways to select two distinct neighbours of $b_i$ for each $i$. This gives a total number of $\sum_{i=1}^{N} {d_i \choose 2}$ cherries in the graph.

On the other hand, for any graph satisfying the conditions, we have the following bound on the number of cherries:

For positive integer $k$, note that each pair $a_i, a_j$ with $|a_i - a_j| = k$ can form a cherry with $b_i$ at the tip for at most ${\frac{N}{k}}$ distinct numbers $i$. This can be seen as follows - of those that form cherries with $a_i$ and $a_j$, all of the $b_i$ must satisfy $|b_i - b_j| \leq \frac{N}{k}$, lest we violate the condition given in the problem. Clearly then we can have at most $\frac{N}{k}$ distinct $b_i$.

Now there are exactly $N-k$ distinct pairs $a_i, a_j$ with $|a_i - a_j| = k$. Summing over $k$, we obtain an upper bound of $\sum_{k=1}^{N} (N-k)\frac{N}{k}$ cherries. Hence we have

$$\sum_{i=1}^{N} {d_i \choose 2} \leq \sum_{k=1}^{N} (N-k)\frac{N}{k}.$$

Expanding the left hand side and rearranging terms, we obtain

$$\sum_{i=1}^{N} d_i^2 \leq 2 \sum_{k=1}^{N} (N-k)\frac{N}{k} + \sum_{j=1}^{N} d_j.$$

Applying the Cauchy Schwartz inequality on the vectors $(d_i)_{i = 1, \dots , N} $ and $\bf 1$ , we obtain

$$ \left(\sum_{i = 1}^{N} d_i\right)^2 \leq N\sum_{i=1}^{N} d_i^2$$

and so

$$\left(\sum_{i = 1}^{N} d_i\right)^2 \leq N \left[ 2 \sum_{k=1}^{N} (N-k)\frac{N}{k} + \sum_{j=1}^{N} d_j\right].$$

From Euler's formula, $\sum_{i = 1}^{N} d_i = 2|E(G)|$, thus

$$ 4|E(G)|^2 \leq 2N \left[ \sum_{k=1}^{N} (N-k)\frac{N}{k} + |E(G)|\right].$$

Or, rearranging,

$$4|E(G)|^2 - 2N|E(G)| - 2N  \sum_{k=1}^{N} (N-k)\frac{N}{k} \leq 0$$

Applying the quadratic formula and taking the positive square root, we obtain

$$|E(G)| \leq \frac{2N + \sqrt{4N^2 + 32N\sum_{k=1}^{N} (N-k)\frac{N}{k}}}{8}$$

Using the shorthand $S_N$ for $\sum_{k=1}^{N} \frac{1}{k}$, and expanding the sum on the right hand side, we have

$$|E(G)| \leq \frac{2N +  \sqrt{4N^2 + 32N^3 S_N - 32N^3}}{8}$$

Now, $S_N - 1 \geq \frac{3}{2} S_N$ as soon as $N \geq 2$. In what follows, we denote by $c$ a constant independent of $N$ that can change from line to line. We compute

$$\frac{2N + \sqrt{4N^2 + 32N^3 S_N - 32N^3}}{8} \leq \frac{2N + \sqrt{cN^3S_N}}{8} = \frac{2N + cN^{3/2}S_N^{1/2}}{8} \leq cN^{3/2}S_N^{1/2}$$

where the first line follows as $N^{3/2}S_N^{1/2} \geq 1$ and $N^3 \geq N^2$ as soon as $N \geq 2$, and the last line from the fact that $N^{3/2}S_N^{1/2} \geq N$.

Applying the given inequality for $S_N$ in the problem statement, we finally have

$$|E(G)| \leq cN^{3/2}(\log_2 N)^{1/2}$$

as required.

Mon, 16 Aug 2021 06:37 GMT