Graph independence number (Caro-Wei) estimate without probabilistic argument?
A short introduction: The independence number $alpha(G)$ of a graph $G$ is the cardinality of the largest independent vertex set. Independent vertex set is made only of vertices with no edges between them.
For example, the set shown above has $alpha(G)=3$ because in set ${A,C,E}$ all vertices are independent and it's impossible to construct a set with four independent elements.
I have stumbled upon a theorem of Caro and Wei who independently provided the following estimate for the lower bound:
$$alpha(G)gesum_{i=1}^{n}frac1{d_i+1}tag{1}$$
My naive attempts to prove the statement fell short so I started to look for a proof elsewhere. Despite the fact that this famous result of Caro and Wei was quoted in many places (Google returned thousands of pages on the first try), it was not easy to find a full proof. This one turned out be my personal favorite (copied from here):
All other proofs that I have found so far are more or less just a copy of it, most often with fewer words. Another copy can be found on MSE (please note that this post is not a copy of the same question).
The proof starts with some combinatorics and then jumps to probabilities and expectations. It's perfectly readable and I have enjoyed it immensely but...
Imagine that you have to explain the theorem to someone (like my son) who is very good at combinatorics but has zero experience with probabilities and expectations.
My question is: Is there a proof of (1) that is not based on a probabilistic argument? Can we replace the probabilistic part of the proof with something that is "more basic", if you understand what I mean. My attemts to find such proof were unsuccessful.
graph-theory alternative-proof
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
add a comment |
A short introduction: The independence number $alpha(G)$ of a graph $G$ is the cardinality of the largest independent vertex set. Independent vertex set is made only of vertices with no edges between them.
For example, the set shown above has $alpha(G)=3$ because in set ${A,C,E}$ all vertices are independent and it's impossible to construct a set with four independent elements.
I have stumbled upon a theorem of Caro and Wei who independently provided the following estimate for the lower bound:
$$alpha(G)gesum_{i=1}^{n}frac1{d_i+1}tag{1}$$
My naive attempts to prove the statement fell short so I started to look for a proof elsewhere. Despite the fact that this famous result of Caro and Wei was quoted in many places (Google returned thousands of pages on the first try), it was not easy to find a full proof. This one turned out be my personal favorite (copied from here):
All other proofs that I have found so far are more or less just a copy of it, most often with fewer words. Another copy can be found on MSE (please note that this post is not a copy of the same question).
The proof starts with some combinatorics and then jumps to probabilities and expectations. It's perfectly readable and I have enjoyed it immensely but...
Imagine that you have to explain the theorem to someone (like my son) who is very good at combinatorics but has zero experience with probabilities and expectations.
My question is: Is there a proof of (1) that is not based on a probabilistic argument? Can we replace the probabilistic part of the proof with something that is "more basic", if you understand what I mean. My attemts to find such proof were unsuccessful.
graph-theory alternative-proof
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
1
I'm trying to understand this paper on algorithmic proof of the result: core.ac.uk/download/pdf/82699691.pdf
– mathnoob
Nov 28 '18 at 17:02
add a comment |
A short introduction: The independence number $alpha(G)$ of a graph $G$ is the cardinality of the largest independent vertex set. Independent vertex set is made only of vertices with no edges between them.
For example, the set shown above has $alpha(G)=3$ because in set ${A,C,E}$ all vertices are independent and it's impossible to construct a set with four independent elements.
I have stumbled upon a theorem of Caro and Wei who independently provided the following estimate for the lower bound:
$$alpha(G)gesum_{i=1}^{n}frac1{d_i+1}tag{1}$$
My naive attempts to prove the statement fell short so I started to look for a proof elsewhere. Despite the fact that this famous result of Caro and Wei was quoted in many places (Google returned thousands of pages on the first try), it was not easy to find a full proof. This one turned out be my personal favorite (copied from here):
All other proofs that I have found so far are more or less just a copy of it, most often with fewer words. Another copy can be found on MSE (please note that this post is not a copy of the same question).
The proof starts with some combinatorics and then jumps to probabilities and expectations. It's perfectly readable and I have enjoyed it immensely but...
Imagine that you have to explain the theorem to someone (like my son) who is very good at combinatorics but has zero experience with probabilities and expectations.
My question is: Is there a proof of (1) that is not based on a probabilistic argument? Can we replace the probabilistic part of the proof with something that is "more basic", if you understand what I mean. My attemts to find such proof were unsuccessful.
graph-theory alternative-proof
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
A short introduction: The independence number $alpha(G)$ of a graph $G$ is the cardinality of the largest independent vertex set. Independent vertex set is made only of vertices with no edges between them.
For example, the set shown above has $alpha(G)=3$ because in set ${A,C,E}$ all vertices are independent and it's impossible to construct a set with four independent elements.
I have stumbled upon a theorem of Caro and Wei who independently provided the following estimate for the lower bound:
$$alpha(G)gesum_{i=1}^{n}frac1{d_i+1}tag{1}$$
My naive attempts to prove the statement fell short so I started to look for a proof elsewhere. Despite the fact that this famous result of Caro and Wei was quoted in many places (Google returned thousands of pages on the first try), it was not easy to find a full proof. This one turned out be my personal favorite (copied from here):
All other proofs that I have found so far are more or less just a copy of it, most often with fewer words. Another copy can be found on MSE (please note that this post is not a copy of the same question).
The proof starts with some combinatorics and then jumps to probabilities and expectations. It's perfectly readable and I have enjoyed it immensely but...
Imagine that you have to explain the theorem to someone (like my son) who is very good at combinatorics but has zero experience with probabilities and expectations.
My question is: Is there a proof of (1) that is not based on a probabilistic argument? Can we replace the probabilistic part of the proof with something that is "more basic", if you understand what I mean. My attemts to find such proof were unsuccessful.
graph-theory alternative-proof
graph-theory alternative-proof
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
asked Nov 27 '18 at 10:16
OldboyOldboy
7,1691832
7,1691832
1
I'm trying to understand this paper on algorithmic proof of the result: core.ac.uk/download/pdf/82699691.pdf
– mathnoob
Nov 28 '18 at 17:02
add a comment |
1
I'm trying to understand this paper on algorithmic proof of the result: core.ac.uk/download/pdf/82699691.pdf
– mathnoob
Nov 28 '18 at 17:02
1
1
I'm trying to understand this paper on algorithmic proof of the result: core.ac.uk/download/pdf/82699691.pdf
– mathnoob
Nov 28 '18 at 17:02
I'm trying to understand this paper on algorithmic proof of the result: core.ac.uk/download/pdf/82699691.pdf
– mathnoob
Nov 28 '18 at 17:02
add a comment |
0
active
oldest
votes
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%2f3015596%2fgraph-independence-number-caro-wei-estimate-without-probabilistic-argument%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3015596%2fgraph-independence-number-caro-wei-estimate-without-probabilistic-argument%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
1
I'm trying to understand this paper on algorithmic proof of the result: core.ac.uk/download/pdf/82699691.pdf
– mathnoob
Nov 28 '18 at 17:02