# Some questions about a family of regular undirected graphs

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.

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