Isoperimetric constant on random graph
$begingroup$
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 Jan 5 at 18:35
David G. Stork
11k31432
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
$endgroup$
add a comment |
$begingroup$
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 Jan 5 at 18:35
David G. Stork
11k31432
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
$endgroup$
add a comment |
$begingroup$
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 Jan 5 at 18:35
David G. Stork
11k31432
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
$endgroup$
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 Jan 5 at 18:35
David G. Stork
11k31432
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
edited Jan 5 at 18:35
David G. Stork
11k31432
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
edited Jan 5 at 18:35
David G. Stork
11k31432
edited Jan 5 at 18:35
David G. Stork
11k31432
edited Jan 5 at 18:35
David G. Stork
11k31432
11k31432
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
asked Jan 5 at 18:25
Thomas LesgourguesThomas Lesgourgues
71517
71517
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
$endgroup$
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
$begingroup$
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 Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
$endgroup$
add a comment |
$begingroup$
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 Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
$endgroup$
add a comment |
$begingroup$
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 Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
$endgroup$
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 Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
answered Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
answered Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
answered Jan 6 at 16:07
Misha LavrovMisha Lavrov
46k656107
46k656107
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.
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
