CMI2022-B: 5

Question

For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the following conditions:

• $\left ( i, j \right ) \in R \Rightarrow i < j$;
• $i <j \Rightarrow \left [ ((i, j) \in R)  \text{ or } (\exists k:(i, k) \in R \wedge (k, j)\in R)\right ]$.

For example, $\left \{ (1, 2),(2, 3) \right \}$ is a $2$- spanner for $\left \{ 1, 2, 3 \right \}$, and

$$\text{R}_{1} = \left \{ (1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5), (4, 6), (4, 7), (5, 6), (6, 7) \right \}$$

is a $2$- spanner for $\text{S} = \left \{ 1, \ldots,7 \right \}$. There are other $2$-spanners for $\text{S}$, of course. $\text{R}_{2} =\left \{ \left ( i, j \right ) \mid i, j\in \left \{ 1,\ldots,7 \right \}, i < j \right \}$ is an example. But $\text{R}_{1}$ is of size $10$, while $\text{R}_{2}$ is of size $21$. We would like to find $2$-spanners that are as small as possible.

1. Suppose you are given $2$-spanners $\text{R}_{1}$ and $\text{R}_{2}$ for $\left \{ 1,\ldots,7 \right \}$ and $\left \{ 9,\ldots,15 \right \}$ respectively, each of size $10$. Use them to construct a $2$-spanner $\text{R}$ for $\left \{ 1,\ldots,15 \right \}$. Try to get $\text{R}$ of size $34$.
2. Generalize the above construction to show that any set $\text{S}$ of size $2^{k} – 1$ (for $k > 2)$ has a $2$-spanner of size $(k – 2) 2^{k} + 2$.

Answer 1

Let S = {a,b,c,d,e,f,g} where a,b,...g are natural numbers - then one of the smallest possible 2-pennet (R) = { (a,b), (b,c), (c,d), (d,e), (e,f), (f,g), (d,f), (d,g), (b,d), (a,d)} $\Rightarrow |R|=10.$

Part a:

{1,2...,7} - smallest possible 2-pennet size is 10 

{9,10,...,15} - smallest possible 2-pennet size is 10 

{1,2,....,15} = {1,2,...,7} , 8 , {9,10,...,15} = 10 + connecting 8 + 10 = 10 + 14 + 10 = 34

 

How connecting 8 in the above 2 different sets require 14 elements of R ?
connect every vertex of {1,2,...,7 } with 8 $\Rightarrow \text{7 elements}$

connect every vertex of {9,10,...,15 } with 8 $\Rightarrow \text{7 elements}$

Total 14 required.

---

Part b: Proof by induction

Given that total $(k-2).2^k+2$ elements required in R for the set S with $2^k - 1$ elements.

Step 1:

For n=1: S={1}, SxS = {(1,1)}, R=$\phi$, $\Rightarrow |R|=0.$ and the formula gives (1-2)2 + 2 = 0. 

For n=2: S={1,2,3}, SxS = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}, R=$\{(1,2),(2,3)\}, \Rightarrow |R|=2$ and the formula gives $(2-2)2^2 + 2 = 2$ 

 

Step 2: Assume the given formula is true for 'n' elements $\Rightarrow$ S with $'2^n-1'$ elements

Step 3: We need to show the formula is true for 'n+1' elements $\Rightarrow$ S with $'2^{(n+1)}-1'$ elements

Formula gives $((n+1)-2).2^{(n+1)}+2 = (n-1).2^{(n+1)}+2$

Set with $'2^{(n+1)}-1'$ elements = $\underbrace{'2^{n}-1'}_ {\text{(first $2^n-1$ elements)}} + \text{Middle element}+ \underbrace{'2^{n}-1'}_ {\text{(last $2^n-1$ elements)}}$

Which have $((n-2).2^n+2) + \text{Connection with Middle element}+((n-2).2^n+2) $ elements in R

= $((n-2).2^n+2) +2.{2^{n}-2}+((n-2).2^n+2) $

= $2^n.((n-2)+2+(n-2)) + 2 -2 +2$

= $2^n.(2n-2) +2$

= $2^n.(2.(n-1)) + 2$

= $2^{(n+1)}(n-2) + 2$

Therefore, Given formula is true for 'n+1' elements also.

---

Connection with Middle element = no.of elements in left side set + no.of elements in right side set. = 2.${(2^{n}-1)}={(2.2^{n}-2)}$