Isoperimetric constant on random graph
Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $mathcal{G}_{n,p}$ verify the following property : for each subset $X in V(G)$ with cardinality $|X|leq n/2$,
$$ e(X, Vbackslash X) geq c |X| $$
Where $ e(X, Vbackslash X)$ denotes the number of edges connecting $X$ and $Vbackslash X$.
I found a "standard" solution, using combinatorial arguments (the constant $c(p)=p$ satisfies the condition), but I have the feeling that a "more elegant" proof should exist.
My intuition is as follow : the problem is equivalent to proving, with $i(G)$ the isoperimetric constant :
$$ forall p, exists c(p)>0, s.t. mathbb{P}[ i(G) > c] rightarrow 1 text{ when }nrightarrow infty $$
And for any graph $G$, we know a lower bound for $i(G)$:
$$ mu_2 /2 leq i(G)$$
With $mu_2$ being the second smallest eigenvalue of the Laplacian matrix of $G$. Now if I can find some bound for $mu_2$ I should be able to do something.
I know that for fixed $p$ the probability that $G$ is connected tends to 1, hence $mu_2 > 0$. But can we find similar argument for $mu_2 > c$ for some constant $c$ ? in term of connectivity surely?
Thanks for the help!
graph-theory eigenvalues-eigenvectors random-graphs
edited 2 days ago
David G. Stork
9,99021332
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
add a comment |
Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $mathcal{G}_{n,p}$ verify the following property : for each subset $X in V(G)$ with cardinality $|X|leq n/2$,
$$ e(X, Vbackslash X) geq c |X| $$
Where $ e(X, Vbackslash X)$ denotes the number of edges connecting $X$ and $Vbackslash X$.
I found a "standard" solution, using combinatorial arguments (the constant $c(p)=p$ satisfies the condition), but I have the feeling that a "more elegant" proof should exist.
My intuition is as follow : the problem is equivalent to proving, with $i(G)$ the isoperimetric constant :
$$ forall p, exists c(p)>0, s.t. mathbb{P}[ i(G) > c] rightarrow 1 text{ when }nrightarrow infty $$
And for any graph $G$, we know a lower bound for $i(G)$:
$$ mu_2 /2 leq i(G)$$
With $mu_2$ being the second smallest eigenvalue of the Laplacian matrix of $G$. Now if I can find some bound for $mu_2$ I should be able to do something.
I know that for fixed $p$ the probability that $G$ is connected tends to 1, hence $mu_2 > 0$. But can we find similar argument for $mu_2 > c$ for some constant $c$ ? in term of connectivity surely?
Thanks for the help!
graph-theory eigenvalues-eigenvectors random-graphs
edited 2 days ago
David G. Stork
9,99021332
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
add a comment |
Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $mathcal{G}_{n,p}$ verify the following property : for each subset $X in V(G)$ with cardinality $|X|leq n/2$,
$$ e(X, Vbackslash X) geq c |X| $$
Where $ e(X, Vbackslash X)$ denotes the number of edges connecting $X$ and $Vbackslash X$.
I found a "standard" solution, using combinatorial arguments (the constant $c(p)=p$ satisfies the condition), but I have the feeling that a "more elegant" proof should exist.
My intuition is as follow : the problem is equivalent to proving, with $i(G)$ the isoperimetric constant :
$$ forall p, exists c(p)>0, s.t. mathbb{P}[ i(G) > c] rightarrow 1 text{ when }nrightarrow infty $$
And for any graph $G$, we know a lower bound for $i(G)$:
$$ mu_2 /2 leq i(G)$$
With $mu_2$ being the second smallest eigenvalue of the Laplacian matrix of $G$. Now if I can find some bound for $mu_2$ I should be able to do something.
I know that for fixed $p$ the probability that $G$ is connected tends to 1, hence $mu_2 > 0$. But can we find similar argument for $mu_2 > c$ for some constant $c$ ? in term of connectivity surely?
Thanks for the help!
graph-theory eigenvalues-eigenvectors random-graphs
edited 2 days ago
David G. Stork
9,99021332
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $mathcal{G}_{n,p}$ verify the following property : for each subset $X in V(G)$ with cardinality $|X|leq n/2$,
$$ e(X, Vbackslash X) geq c |X| $$
Where $ e(X, Vbackslash X)$ denotes the number of edges connecting $X$ and $Vbackslash X$.
I found a "standard" solution, using combinatorial arguments (the constant $c(p)=p$ satisfies the condition), but I have the feeling that a "more elegant" proof should exist.
My intuition is as follow : the problem is equivalent to proving, with $i(G)$ the isoperimetric constant :
$$ forall p, exists c(p)>0, s.t. mathbb{P}[ i(G) > c] rightarrow 1 text{ when }nrightarrow infty $$
And for any graph $G$, we know a lower bound for $i(G)$:
$$ mu_2 /2 leq i(G)$$
With $mu_2$ being the second smallest eigenvalue of the Laplacian matrix of $G$. Now if I can find some bound for $mu_2$ I should be able to do something.
I know that for fixed $p$ the probability that $G$ is connected tends to 1, hence $mu_2 > 0$. But can we find similar argument for $mu_2 > c$ for some constant $c$ ? in term of connectivity surely?
Thanks for the help!
graph-theory eigenvalues-eigenvectors random-graphs
graph-theory eigenvalues-eigenvectors random-graphs
edited 2 days ago
David G. Stork
9,99021332
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
edited 2 days ago
David G. Stork
9,99021332
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
edited 2 days ago
David G. Stork
9,99021332
edited 2 days ago
David G. Stork
9,99021332
edited 2 days ago
David G. Stork
9,99021332
9,99021332
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
asked 2 days ago
Thomas LesgourguesThomas Lesgourgues
726
726
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
From this paper we can estimate the normalized Laplacian spectrum of $mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$bar{L} = I - bar{D}^{-1/2} bar{A}bar{D}^{-1/2}$$
where $bar{D} = (n-1)pI$ is the expected value of $D$, and $bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $bar{D}$ commutes with everything, we can rewrite this as $I - bar{D}^{-1}bar{A}$ which simplifies to$$frac{n}{n-1}I - frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,dots,0,0$ and so the eigenvalues of $bar{L}$ are $0, frac{n}{n-1}, frac{n}{n-1}, dots, frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $epsilon>0$, we have $$|lambda_i(L) - lambda_i(bar{L})| le mathcal Oleft(sqrt{frac{log(n/epsilon)}{(n-1)p}}right)$$ provided $(n-1)p > k(epsilon)log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $lambda_2(L) ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)
answered yesterday
Misha LavrovMisha Lavrov
44k555106
add a comment |
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%2f3063033%2fisoperimetric-constant-on-random-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
From this paper we can estimate the normalized Laplacian spectrum of $mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$bar{L} = I - bar{D}^{-1/2} bar{A}bar{D}^{-1/2}$$
where $bar{D} = (n-1)pI$ is the expected value of $D$, and $bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $bar{D}$ commutes with everything, we can rewrite this as $I - bar{D}^{-1}bar{A}$ which simplifies to$$frac{n}{n-1}I - frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,dots,0,0$ and so the eigenvalues of $bar{L}$ are $0, frac{n}{n-1}, frac{n}{n-1}, dots, frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $epsilon>0$, we have $$|lambda_i(L) - lambda_i(bar{L})| le mathcal Oleft(sqrt{frac{log(n/epsilon)}{(n-1)p}}right)$$ provided $(n-1)p > k(epsilon)log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $lambda_2(L) ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)
answered yesterday
Misha LavrovMisha Lavrov
44k555106
add a comment |
From this paper we can estimate the normalized Laplacian spectrum of $mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$bar{L} = I - bar{D}^{-1/2} bar{A}bar{D}^{-1/2}$$
where $bar{D} = (n-1)pI$ is the expected value of $D$, and $bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $bar{D}$ commutes with everything, we can rewrite this as $I - bar{D}^{-1}bar{A}$ which simplifies to$$frac{n}{n-1}I - frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,dots,0,0$ and so the eigenvalues of $bar{L}$ are $0, frac{n}{n-1}, frac{n}{n-1}, dots, frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $epsilon>0$, we have $$|lambda_i(L) - lambda_i(bar{L})| le mathcal Oleft(sqrt{frac{log(n/epsilon)}{(n-1)p}}right)$$ provided $(n-1)p > k(epsilon)log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $lambda_2(L) ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)
answered yesterday
Misha LavrovMisha Lavrov
44k555106
add a comment |
From this paper we can estimate the normalized Laplacian spectrum of $mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$bar{L} = I - bar{D}^{-1/2} bar{A}bar{D}^{-1/2}$$
where $bar{D} = (n-1)pI$ is the expected value of $D$, and $bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $bar{D}$ commutes with everything, we can rewrite this as $I - bar{D}^{-1}bar{A}$ which simplifies to$$frac{n}{n-1}I - frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,dots,0,0$ and so the eigenvalues of $bar{L}$ are $0, frac{n}{n-1}, frac{n}{n-1}, dots, frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $epsilon>0$, we have $$|lambda_i(L) - lambda_i(bar{L})| le mathcal Oleft(sqrt{frac{log(n/epsilon)}{(n-1)p}}right)$$ provided $(n-1)p > k(epsilon)log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $lambda_2(L) ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)
answered yesterday
Misha LavrovMisha Lavrov
44k555106
From this paper we can estimate the normalized Laplacian spectrum of $mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$bar{L} = I - bar{D}^{-1/2} bar{A}bar{D}^{-1/2}$$
where $bar{D} = (n-1)pI$ is the expected value of $D$, and $bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $bar{D}$ commutes with everything, we can rewrite this as $I - bar{D}^{-1}bar{A}$ which simplifies to$$frac{n}{n-1}I - frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,dots,0,0$ and so the eigenvalues of $bar{L}$ are $0, frac{n}{n-1}, frac{n}{n-1}, dots, frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $epsilon>0$, we have $$|lambda_i(L) - lambda_i(bar{L})| le mathcal Oleft(sqrt{frac{log(n/epsilon)}{(n-1)p}}right)$$ provided $(n-1)p > k(epsilon)log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $lambda_2(L) ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)
answered yesterday
Misha LavrovMisha Lavrov
44k555106
answered yesterday
Misha LavrovMisha Lavrov
44k555106
answered yesterday
Misha LavrovMisha Lavrov
44k555106
answered yesterday
Misha LavrovMisha Lavrov
44k555106
44k555106
add a comment |
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3063033%2fisoperimetric-constant-on-random-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
