Some questions about an undirected graph
$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)=2equiv 3$
Thanks for you help in proving or disproving the conjectures above.
graph-theory
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
$endgroup$
add a comment |
$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)=2equiv 3$
Thanks for you help in proving or disproving the conjectures above.
graph-theory
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
$endgroup$
$begingroup$
What have you tried so far? You'll get a better response if you provide some context to your work, e.g. where you are stuck. It would also be helpful if you provided a definition or a reference to one ("in the sense of Chris Godsil" is not specific enough to be a working mathematical definition, and questions should not require users to leave the site to find one).
$endgroup$
– platty
Dec 3 '18 at 19:14
$begingroup$
For 2) it is sufficient to show that if $x_1,...,x_s$ are the eigenvalues, then $G$ is periodic if $frac{x_k}{x_l}$ is a rational number and $x_k,x_l$ are not $0$.
$endgroup$
– stackExchangeUser
Dec 3 '18 at 19:17
add a comment |
$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)=2equiv 3$
Thanks for you help in proving or disproving the conjectures above.
graph-theory
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
$endgroup$
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)=2equiv 3$
Thanks for you help in proving or disproving the conjectures above.
graph-theory
graph-theory
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
edited Dec 3 '18 at 19:18
stackExchangeUser
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
asked Dec 3 '18 at 19:04
stackExchangeUserstackExchangeUser
1,163512
1,163512
$begingroup$
What have you tried so far? You'll get a better response if you provide some context to your work, e.g. where you are stuck. It would also be helpful if you provided a definition or a reference to one ("in the sense of Chris Godsil" is not specific enough to be a working mathematical definition, and questions should not require users to leave the site to find one).
$endgroup$
– platty
Dec 3 '18 at 19:14
$begingroup$
For 2) it is sufficient to show that if $x_1,...,x_s$ are the eigenvalues, then $G$ is periodic if $frac{x_k}{x_l}$ is a rational number and $x_k,x_l$ are not $0$.
$endgroup$
– stackExchangeUser
Dec 3 '18 at 19:17
add a comment |
$begingroup$
What have you tried so far? You'll get a better response if you provide some context to your work, e.g. where you are stuck. It would also be helpful if you provided a definition or a reference to one ("in the sense of Chris Godsil" is not specific enough to be a working mathematical definition, and questions should not require users to leave the site to find one).
$endgroup$
– platty
Dec 3 '18 at 19:14
$begingroup$
For 2) it is sufficient to show that if $x_1,...,x_s$ are the eigenvalues, then $G$ is periodic if $frac{x_k}{x_l}$ is a rational number and $x_k,x_l$ are not $0$.
$endgroup$
– stackExchangeUser
Dec 3 '18 at 19:17
$begingroup$
What have you tried so far? You'll get a better response if you provide some context to your work, e.g. where you are stuck. It would also be helpful if you provided a definition or a reference to one ("in the sense of Chris Godsil" is not specific enough to be a working mathematical definition, and questions should not require users to leave the site to find one).
$endgroup$
– platty
Dec 3 '18 at 19:14
$begingroup$
What have you tried so far? You'll get a better response if you provide some context to your work, e.g. where you are stuck. It would also be helpful if you provided a definition or a reference to one ("in the sense of Chris Godsil" is not specific enough to be a working mathematical definition, and questions should not require users to leave the site to find one).
$endgroup$
– platty
Dec 3 '18 at 19:14
$begingroup$
For 2) it is sufficient to show that if $x_1,...,x_s$ are the eigenvalues, then $G$ is periodic if $frac{x_k}{x_l}$ is a rational number and $x_k,x_l$ are not $0$.
$endgroup$
– stackExchangeUser
Dec 3 '18 at 19:17
$begingroup$
For 2) it is sufficient to show that if $x_1,...,x_s$ are the eigenvalues, then $G$ is periodic if $frac{x_k}{x_l}$ is a rational number and $x_k,x_l$ are not $0$.
$endgroup$
– stackExchangeUser
Dec 3 '18 at 19:17
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3024519%2fsome-questions-about-an-undirected-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3024519%2fsome-questions-about-an-undirected-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What have you tried so far? You'll get a better response if you provide some context to your work, e.g. where you are stuck. It would also be helpful if you provided a definition or a reference to one ("in the sense of Chris Godsil" is not specific enough to be a working mathematical definition, and questions should not require users to leave the site to find one).
$endgroup$
– platty
Dec 3 '18 at 19:14
$begingroup$
For 2) it is sufficient to show that if $x_1,...,x_s$ are the eigenvalues, then $G$ is periodic if $frac{x_k}{x_l}$ is a rational number and $x_k,x_l$ are not $0$.
$endgroup$
– stackExchangeUser
Dec 3 '18 at 19:17