How can dividing the graph into k-1 subsets guarantee that a clique on k vertices is avoided ?
up vote
0
down vote
favorite
Could someone provide a formal proof or an intuitive sense of it ? The proof for Turan's Theorem is provided for reference
discrete-mathematics extremal-combinatorics extremal-graph-theory
asked Nov 20 at 15:42
Arka Prava Paul
53
add a comment |
up vote
0
down vote
favorite
Could someone provide a formal proof or an intuitive sense of it ? The proof for Turan's Theorem is provided for reference
discrete-mathematics extremal-combinatorics extremal-graph-theory
asked Nov 20 at 15:42
Arka Prava Paul
53
The graph with that construction, also called the Turan graph $T(n,k-1)$ if it has $n$ vertices, has no $k$-cliques because if you were to try to construct a $k$-clique, every vertex in the clique would need to belong to a different part, since by construction, no two vertices in the same part are adjacent. But there are only $k-1$ parts, so you can only pick one vertex per part, and hence can have at most a $(k-1)$-clique. More interesting is the fact that this graph has the maximum number of edges.
– Kevin Long
Nov 20 at 16:15
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Could someone provide a formal proof or an intuitive sense of it ? The proof for Turan's Theorem is provided for reference
discrete-mathematics extremal-combinatorics extremal-graph-theory
asked Nov 20 at 15:42
Arka Prava Paul
53
Could someone provide a formal proof or an intuitive sense of it ? The proof for Turan's Theorem is provided for reference
discrete-mathematics extremal-combinatorics extremal-graph-theory
discrete-mathematics extremal-combinatorics extremal-graph-theory
asked Nov 20 at 15:42
Arka Prava Paul
53
asked Nov 20 at 15:42
Arka Prava Paul
53
asked Nov 20 at 15:42
Arka Prava Paul
53
asked Nov 20 at 15:42
Arka Prava Paul
53
asked Nov 20 at 15:42
Arka Prava Paul
53
53
The graph with that construction, also called the Turan graph $T(n,k-1)$ if it has $n$ vertices, has no $k$-cliques because if you were to try to construct a $k$-clique, every vertex in the clique would need to belong to a different part, since by construction, no two vertices in the same part are adjacent. But there are only $k-1$ parts, so you can only pick one vertex per part, and hence can have at most a $(k-1)$-clique. More interesting is the fact that this graph has the maximum number of edges.
– Kevin Long
Nov 20 at 16:15
add a comment |
The graph with that construction, also called the Turan graph $T(n,k-1)$ if it has $n$ vertices, has no $k$-cliques because if you were to try to construct a $k$-clique, every vertex in the clique would need to belong to a different part, since by construction, no two vertices in the same part are adjacent. But there are only $k-1$ parts, so you can only pick one vertex per part, and hence can have at most a $(k-1)$-clique. More interesting is the fact that this graph has the maximum number of edges.
– Kevin Long
Nov 20 at 16:15
The graph with that construction, also called the Turan graph $T(n,k-1)$ if it has $n$ vertices, has no $k$-cliques because if you were to try to construct a $k$-clique, every vertex in the clique would need to belong to a different part, since by construction, no two vertices in the same part are adjacent. But there are only $k-1$ parts, so you can only pick one vertex per part, and hence can have at most a $(k-1)$-clique. More interesting is the fact that this graph has the maximum number of edges.
– Kevin Long
Nov 20 at 16:15
The graph with that construction, also called the Turan graph $T(n,k-1)$ if it has $n$ vertices, has no $k$-cliques because if you were to try to construct a $k$-clique, every vertex in the clique would need to belong to a different part, since by construction, no two vertices in the same part are adjacent. But there are only $k-1$ parts, so you can only pick one vertex per part, and hence can have at most a $(k-1)$-clique. More interesting is the fact that this graph has the maximum number of edges.
– Kevin Long
Nov 20 at 16:15
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
draft saved
draft discarded
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%2f3006478%2fhow-can-dividing-the-graph-into-k-1-subsets-guarantee-that-a-clique-on-k-vertice%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
The graph with that construction, also called the Turan graph $T(n,k-1)$ if it has $n$ vertices, has no $k$-cliques because if you were to try to construct a $k$-clique, every vertex in the clique would need to belong to a different part, since by construction, no two vertices in the same part are adjacent. But there are only $k-1$ parts, so you can only pick one vertex per part, and hence can have at most a $(k-1)$-clique. More interesting is the fact that this graph has the maximum number of edges.
– Kevin Long
Nov 20 at 16:15