What is the dimensionality of Euclidean space where $N$-star can be embedded?

54 Views Asked by At

How many dimensions are required to embed a star graph with $N$ vertices such that the following holds:

  1. The embedding has unit radius i.e. $\| x_0 - x_i \| = 1$ where $x_0$ is the central vertex, $i \neq 0$.
  2. $\| x_i - x_j \| \geq 1, i \neq 0, j \neq 0, i \neq j$.

basically, its a question about the number of points one can fit on a hypersphere such that the distance between any two points is $\geq$ than the radius of the hypersphere.

Seems like it is related to the graph dimension?

To give some simple examples, a 2-star graph (2 leaves) can be embedded in 1 dimension. A 3-star graph requires 2 dimensions.

1

There are 1 best solutions below

0
On BEST ANSWER

It seems reasonable to first answer this question to solve this problem:

What is the maximum number of points that can be placed on a sphere of $\mathbb{R}^n$ of radius $1$ such that the minimum distance between them is at least $1$?

In turn, this problem is equivalent to the problem about the kissing number

In the general case this problem is unsolved. Here is what is known today (November 2022) for the first $10$ dimensions:

$$ \begin{array}{|c|l|} \hline \rm dim & \rm number\ kissing\\ \hline % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... 1 & 2 \\ 2 & 6 \\ 3 & 12 \\ 4 & 24 \\ 5 & 40-44\\ 6 & 72-78\\ 7 & 126-134\\ 8 & 240\\ 9 & 306-363\\ 10 & 500-553\\ \hline \end{array} $$ We see that already for $\mathbb{R}^5$ only the lower $(40)$ and upper $(44)$ bounds are known, but the number itself is unknown.

Thus, one can place with the specified property in $\mathbb{R}^2$ but not in $\mathbb{R}$ those $k$-stars for which $3\leq k\leq6$. And furthermore: $\mathbb{R}^3$, $7\leq k\leq12$; $\mathbb{R}^4$, $13\leq k\leq24$ and so on.

Here is a similar question.