1
$\begingroup$

Let $S$ be the regular n-dimensional simplex. We create a graph of where the vertices are m-faces and two vertices are connected if there exist a common (m-1)-face which they share. Then the number of vertices is $binomial(n,m)$ and the graph $G$ is regular with $m(n-m)$ vertices.

Prove or disprove:

1) The diameter of $G$ is $diam(G)=min(n-m,m)$

2) $G$ is periodic in the sence of Chris Godsil (google: periodic graph chris godsil)

3) $G$ is distance regular in the sence of Wikipedia.

Also there seems to be a connection to "brains" as follows:

a) Human brain:

1) $n = 205, m = 5$ , $binomial(n,m)\equiv 10^9=$ number of neurons

2) $m(m-n) \equiv 1000 = $ number of synapses per neuron

3) $diam(G)=min(205-5,5)=5 \equiv 6$ = diameter of $G$.

b) Brain of Ciona intestinalis (Wikipedia):

1) $n=22,m=2$

2) $binomial(n,m)=231$

3) $n(n-m)=40$

4) $diam(G)=2\equiv 3$

Thanks for you help in proving or disproving the conjectures above. What I have tried so far is writing a python program to produce the graphs and conjecture about the points above.

$\endgroup$
  • 4
    $\begingroup$ These are just the Johnson graphs. So maybe google that? $\endgroup$ – David Roberson Dec 3 '18 at 22:16
1
$\begingroup$

As for your question 2), according to https://arxiv.org/pdf/0806.2074.pdf, a regular graph is periodic if and only if its eigenvalues are distinct, which is the case for the Johnson graphs.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.