Mixing
How many independent even cycles in $G(n,m)$
$begingroup$
In the random graph model $G(n,m)$, how many independent even cycles are there ?
More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$
for $c=0,1,ldots$ ?
For my purposes, it would be enough to calculate
$$ mathbb{E}(2^C) := sum_{c=0}^infty 2^c cdot P(C=c) = sum_{c=0}^{m/4} 2^c cdot P(C=c) $$
graph-theory random-graphs
asked Jan 7 at 8:34
TeddyTeddy
1,252816
$endgroup$
add a comment |
$begingroup$
In the random graph model $G(n,m)$, how many independent even cycles are there ?
More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$
for $c=0,1,ldots$ ?
For my purposes, it would be enough to calculate
$$ mathbb{E}(2^C) := sum_{c=0}^infty 2^c cdot P(C=c) = sum_{c=0}^{m/4} 2^c cdot P(C=c) $$
graph-theory random-graphs
asked Jan 7 at 8:34
TeddyTeddy
1,252816
$endgroup$
add a comment |
$begingroup$
In the random graph model $G(n,m)$, how many independent even cycles are there ?
More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$
for $c=0,1,ldots$ ?
For my purposes, it would be enough to calculate
$$ mathbb{E}(2^C) := sum_{c=0}^infty 2^c cdot P(C=c) = sum_{c=0}^{m/4} 2^c cdot P(C=c) $$
graph-theory random-graphs
asked Jan 7 at 8:34
TeddyTeddy
1,252816
$endgroup$
In the random graph model $G(n,m)$, how many independent even cycles are there ?
More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$
for $c=0,1,ldots$ ?
For my purposes, it would be enough to calculate
$$ mathbb{E}(2^C) := sum_{c=0}^infty 2^c cdot P(C=c) = sum_{c=0}^{m/4} 2^c cdot P(C=c) $$
graph-theory random-graphs
graph-theory random-graphs
asked Jan 7 at 8:34
TeddyTeddy
1,252816
asked Jan 7 at 8:34
TeddyTeddy
1,252816
asked Jan 7 at 8:34
TeddyTeddy
1,252816
asked Jan 7 at 8:34
TeddyTeddy
1,252816
asked Jan 7 at 8:34
TeddyTeddy
1,252816
1,252816
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This probably varies a lot depending on which kind of $m$ you're looking at.
Here's a partial answer. For any $n$-vertex, $m$-edge, $2$-connected graph $G$ with odd cycles, $C=m-n$. We also have:
Theorem 4.3, Frieze and Karonski's Random Graphs.
Let $m = frac12 n(log n + log log n + c_n)$. Then $$lim_{n to infty} Pr[G(n,m) text{ is $2$-connected}] = begin{cases}0 & text{if } c_n to -infty \ e^{-e^{-c}} & text{if }c_n to c \ 1 & text{if }c_n to infty.end{cases}$$
This tells us when $G(n,m)$ is $2$-connected with high probability; odd cycles appear much earlier, and therefore $2^C = 2^{m-n}$ with high probability; since $C le m-n-1$ always, this means $mathbb E[2^C] sim 2^{m-n}$ for such $m$.
For smaller $m$, we need to think about the number of blocks (maximal $2$-connected subgraphs) in $G(n,m)$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:
- In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
- Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
- Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).
The result about $2$-connected graphs also applies when the $2$-core of $G$ is $2$-connected, since we can delete vertices of degree $1$ without changing $m-n$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.
The claim that $C ge m-n$ when $G$ is $2$-connected might be well-known, but it's new to me, so I will prove it.
In this case, the cycle space is generated by $m-(n-1)$ cycles. To show that the even cycle space is generated by $m-n$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.
Take any two odd cycles. Let $u_1, v_1$ be three vertices on one cycle, and $u_2, v_2$ be three vertices on another. The graph where we add a vertex $x_i$ adjacent to $u_i, v_i$ for $i=1,2$ is also $2$-connected, so there are $2$ disjoint paths from $x_1$ to $x_2$. Deleting $x_1$ and $x_2$ produces, without loss of generality, a path $P$ from $u_1$ to $u_2$ and a path $Q$ from $v_1$ to $v_2$.
If we follow $P$ from $u_1$ to $u_2$, then go from $u_2$ to $v_2$ in the second cycle (in some direction), then follow $Q$ back from $v_2$ to $v_1$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $u_2$ to $v_2$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $2$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
$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%2f3064767%2fhow-many-independent-even-cycles-in-gn-m%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$
This probably varies a lot depending on which kind of $m$ you're looking at.
Here's a partial answer. For any $n$-vertex, $m$-edge, $2$-connected graph $G$ with odd cycles, $C=m-n$. We also have:
Theorem 4.3, Frieze and Karonski's Random Graphs.
Let $m = frac12 n(log n + log log n + c_n)$. Then $$lim_{n to infty} Pr[G(n,m) text{ is $2$-connected}] = begin{cases}0 & text{if } c_n to -infty \ e^{-e^{-c}} & text{if }c_n to c \ 1 & text{if }c_n to infty.end{cases}$$
This tells us when $G(n,m)$ is $2$-connected with high probability; odd cycles appear much earlier, and therefore $2^C = 2^{m-n}$ with high probability; since $C le m-n-1$ always, this means $mathbb E[2^C] sim 2^{m-n}$ for such $m$.
For smaller $m$, we need to think about the number of blocks (maximal $2$-connected subgraphs) in $G(n,m)$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:
- In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
- Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
- Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).
The result about $2$-connected graphs also applies when the $2$-core of $G$ is $2$-connected, since we can delete vertices of degree $1$ without changing $m-n$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.
The claim that $C ge m-n$ when $G$ is $2$-connected might be well-known, but it's new to me, so I will prove it.
In this case, the cycle space is generated by $m-(n-1)$ cycles. To show that the even cycle space is generated by $m-n$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.
Take any two odd cycles. Let $u_1, v_1$ be three vertices on one cycle, and $u_2, v_2$ be three vertices on another. The graph where we add a vertex $x_i$ adjacent to $u_i, v_i$ for $i=1,2$ is also $2$-connected, so there are $2$ disjoint paths from $x_1$ to $x_2$. Deleting $x_1$ and $x_2$ produces, without loss of generality, a path $P$ from $u_1$ to $u_2$ and a path $Q$ from $v_1$ to $v_2$.
If we follow $P$ from $u_1$ to $u_2$, then go from $u_2$ to $v_2$ in the second cycle (in some direction), then follow $Q$ back from $v_2$ to $v_1$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $u_2$ to $v_2$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $2$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
$endgroup$
add a comment |
$begingroup$
This probably varies a lot depending on which kind of $m$ you're looking at.
Here's a partial answer. For any $n$-vertex, $m$-edge, $2$-connected graph $G$ with odd cycles, $C=m-n$. We also have:
Theorem 4.3, Frieze and Karonski's Random Graphs.
Let $m = frac12 n(log n + log log n + c_n)$. Then $$lim_{n to infty} Pr[G(n,m) text{ is $2$-connected}] = begin{cases}0 & text{if } c_n to -infty \ e^{-e^{-c}} & text{if }c_n to c \ 1 & text{if }c_n to infty.end{cases}$$
This tells us when $G(n,m)$ is $2$-connected with high probability; odd cycles appear much earlier, and therefore $2^C = 2^{m-n}$ with high probability; since $C le m-n-1$ always, this means $mathbb E[2^C] sim 2^{m-n}$ for such $m$.
For smaller $m$, we need to think about the number of blocks (maximal $2$-connected subgraphs) in $G(n,m)$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:
- In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
- Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
- Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).
The result about $2$-connected graphs also applies when the $2$-core of $G$ is $2$-connected, since we can delete vertices of degree $1$ without changing $m-n$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.
The claim that $C ge m-n$ when $G$ is $2$-connected might be well-known, but it's new to me, so I will prove it.
In this case, the cycle space is generated by $m-(n-1)$ cycles. To show that the even cycle space is generated by $m-n$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.
Take any two odd cycles. Let $u_1, v_1$ be three vertices on one cycle, and $u_2, v_2$ be three vertices on another. The graph where we add a vertex $x_i$ adjacent to $u_i, v_i$ for $i=1,2$ is also $2$-connected, so there are $2$ disjoint paths from $x_1$ to $x_2$. Deleting $x_1$ and $x_2$ produces, without loss of generality, a path $P$ from $u_1$ to $u_2$ and a path $Q$ from $v_1$ to $v_2$.
If we follow $P$ from $u_1$ to $u_2$, then go from $u_2$ to $v_2$ in the second cycle (in some direction), then follow $Q$ back from $v_2$ to $v_1$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $u_2$ to $v_2$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $2$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
$endgroup$
add a comment |
$begingroup$
This probably varies a lot depending on which kind of $m$ you're looking at.
Here's a partial answer. For any $n$-vertex, $m$-edge, $2$-connected graph $G$ with odd cycles, $C=m-n$. We also have:
Theorem 4.3, Frieze and Karonski's Random Graphs.
Let $m = frac12 n(log n + log log n + c_n)$. Then $$lim_{n to infty} Pr[G(n,m) text{ is $2$-connected}] = begin{cases}0 & text{if } c_n to -infty \ e^{-e^{-c}} & text{if }c_n to c \ 1 & text{if }c_n to infty.end{cases}$$
This tells us when $G(n,m)$ is $2$-connected with high probability; odd cycles appear much earlier, and therefore $2^C = 2^{m-n}$ with high probability; since $C le m-n-1$ always, this means $mathbb E[2^C] sim 2^{m-n}$ for such $m$.
For smaller $m$, we need to think about the number of blocks (maximal $2$-connected subgraphs) in $G(n,m)$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:
- In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
- Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
- Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).
The result about $2$-connected graphs also applies when the $2$-core of $G$ is $2$-connected, since we can delete vertices of degree $1$ without changing $m-n$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.
The claim that $C ge m-n$ when $G$ is $2$-connected might be well-known, but it's new to me, so I will prove it.
In this case, the cycle space is generated by $m-(n-1)$ cycles. To show that the even cycle space is generated by $m-n$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.
Take any two odd cycles. Let $u_1, v_1$ be three vertices on one cycle, and $u_2, v_2$ be three vertices on another. The graph where we add a vertex $x_i$ adjacent to $u_i, v_i$ for $i=1,2$ is also $2$-connected, so there are $2$ disjoint paths from $x_1$ to $x_2$. Deleting $x_1$ and $x_2$ produces, without loss of generality, a path $P$ from $u_1$ to $u_2$ and a path $Q$ from $v_1$ to $v_2$.
If we follow $P$ from $u_1$ to $u_2$, then go from $u_2$ to $v_2$ in the second cycle (in some direction), then follow $Q$ back from $v_2$ to $v_1$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $u_2$ to $v_2$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $2$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
$endgroup$
This probably varies a lot depending on which kind of $m$ you're looking at.
Here's a partial answer. For any $n$-vertex, $m$-edge, $2$-connected graph $G$ with odd cycles, $C=m-n$. We also have:
Theorem 4.3, Frieze and Karonski's Random Graphs.
Let $m = frac12 n(log n + log log n + c_n)$. Then $$lim_{n to infty} Pr[G(n,m) text{ is $2$-connected}] = begin{cases}0 & text{if } c_n to -infty \ e^{-e^{-c}} & text{if }c_n to c \ 1 & text{if }c_n to infty.end{cases}$$
This tells us when $G(n,m)$ is $2$-connected with high probability; odd cycles appear much earlier, and therefore $2^C = 2^{m-n}$ with high probability; since $C le m-n-1$ always, this means $mathbb E[2^C] sim 2^{m-n}$ for such $m$.
For smaller $m$, we need to think about the number of blocks (maximal $2$-connected subgraphs) in $G(n,m)$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:
- In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
- Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
- Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).
The result about $2$-connected graphs also applies when the $2$-core of $G$ is $2$-connected, since we can delete vertices of degree $1$ without changing $m-n$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.
The claim that $C ge m-n$ when $G$ is $2$-connected might be well-known, but it's new to me, so I will prove it.
In this case, the cycle space is generated by $m-(n-1)$ cycles. To show that the even cycle space is generated by $m-n$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.
Take any two odd cycles. Let $u_1, v_1$ be three vertices on one cycle, and $u_2, v_2$ be three vertices on another. The graph where we add a vertex $x_i$ adjacent to $u_i, v_i$ for $i=1,2$ is also $2$-connected, so there are $2$ disjoint paths from $x_1$ to $x_2$. Deleting $x_1$ and $x_2$ produces, without loss of generality, a path $P$ from $u_1$ to $u_2$ and a path $Q$ from $v_1$ to $v_2$.
If we follow $P$ from $u_1$ to $u_2$, then go from $u_2$ to $v_2$ in the second cycle (in some direction), then follow $Q$ back from $v_2$ to $v_1$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $u_2$ to $v_2$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $2$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
edited Jan 8 at 22:20
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
answered Jan 8 at 17:11
Misha LavrovMisha Lavrov
45.5k656107
45.5k656107
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%2f3064767%2fhow-many-independent-even-cycles-in-gn-m%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
