Mixing
number of 4 cycles
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Let $C_4$ be a cycle with $4$ vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>nsqrt n$, how many $C_4$s exist? Is there a lower bound for this?
graph-theory graph-minor
asked 2 hours ago
shahrzad haddadan
262
add a comment |Â
up vote
3
down vote
favorite
Let $C_4$ be a cycle with $4$ vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>nsqrt n$, how many $C_4$s exist? Is there a lower bound for this?
graph-theory graph-minor
asked 2 hours ago
shahrzad haddadan
262
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $C_4$ be a cycle with $4$ vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>nsqrt n$, how many $C_4$s exist? Is there a lower bound for this?
graph-theory graph-minor
asked 2 hours ago
shahrzad haddadan
262
Let $C_4$ be a cycle with $4$ vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>nsqrt n$, how many $C_4$s exist? Is there a lower bound for this?
graph-theory graph-minor
graph-theory graph-minor
asked 2 hours ago
shahrzad haddadan
262
asked 2 hours ago
shahrzad haddadan
262
asked 2 hours ago
shahrzad haddadan
262
asked 2 hours ago
shahrzad haddadan
262
asked 2 hours ago
shahrzad haddadan
262
262
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
Yes, this is known. For $d = Omega(n^1/2)$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $Omega(d^4)$ total $C_4$s.
This is best possible because it's realized by a random graph.
The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.
answered 1 hour ago
GMB
1,111617
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Yes, this is known. For $d = Omega(n^1/2)$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $Omega(d^4)$ total $C_4$s.
This is best possible because it's realized by a random graph.
The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.
answered 1 hour ago
GMB
1,111617
add a comment |Â
up vote
3
down vote
Yes, this is known. For $d = Omega(n^1/2)$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $Omega(d^4)$ total $C_4$s.
This is best possible because it's realized by a random graph.
The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.
answered 1 hour ago
GMB
1,111617
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Yes, this is known. For $d = Omega(n^1/2)$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $Omega(d^4)$ total $C_4$s.
This is best possible because it's realized by a random graph.
The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.
answered 1 hour ago
GMB
1,111617
Yes, this is known. For $d = Omega(n^1/2)$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $Omega(d^4)$ total $C_4$s.
This is best possible because it's realized by a random graph.
The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.
answered 1 hour ago
GMB
1,111617
edited 1 hour ago
answered 1 hour ago
GMB
1,111617
answered 1 hour ago
GMB
1,111617
answered 1 hour ago
GMB
1,111617
1,111617
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41730%2fnumber-of-4-cycles%23new-answer', 'question_page');
);
Post as a guest
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
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
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
