Dark Mode

488 views

6 votes

Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$.

$$ V(H) = \{S \subseteq \mathbb{R}^n : \: S \text{ is a basis for } \mathbb{R}^n\};$$

$$E(H) = \{ \{S, T\} \: : \: \mid S \setminus T \mid = 1 \text{ and } \mid T \setminus S \mid =1 \}, $$

where $S \setminus T = \{ x \in S \: : \: x \notin T \}$. Which of the following statements is FALSE?

- $H$ has an inifinite number of vertices
- The diameter of $H$ is infinite
- $H$ is conneceted
- $H$ contains an infinite clique
- $H$ contains an infinite independent set

0

0

1 vote

**Option (B)**

I would like to strongly recommend to watch this video of legendary 3b1b for understanding what are basis vectors.

Basis vectors are linearly independent vectors that can span full space.

Lets first understand what this graph is about.

**Vertices of this graph are set of basis vectors. **(Note: In nth dimensional vector space there are n linearly independent basis vectors).

So each vertex will be of the form S={v1,v2,v3,..vn} where S is set of basis vectors.

and here Vi = [x1,x2,x3,x4 , xn] can be any n dimensional vector.

**Edge between any two vectors is present if only if there is exactly one basis vector different among two vertices. **

Now we can see for the given vertex there can be infinite adjacent vertices cause we have infinite options for replacing one of the basis vectors. Hence (a) is true.

Graph will be connected cause suppose even if we have two vertices Vi not equals Vj such that each basis vector among two of them is different , even then we can reach to other vertex by replacing **one of the basic vector at time** (See the condition of Adjacency) and eventually we will reach our desired vertex in at max **n** steps (changing each basis vertex at time).

Hence the diameter of the graph will be finite and **n. **

Graph has infinite vertices and there will infinite cliques of size 3 , for example Vi , Vj , Vk and each of them has exactly one basis vector different.

Similarly, we can show it has infinite independent set by considering all the vertices with two or more different basis vectors cause such vertices are not connected to each other.

We can relate this graph with the graph of hamming distances even there, an edge is present between two vertices when only one bit is swapped (here in this case : **one basis vector is changed**).