Mixing
Maximum minimum degree possible in a matchless graph.
$begingroup$
Let $nleq m$ be positive integers.
What is the maximum possible value of $d$ such that there exists a bipartite graph $X,Y$ with $|X|=n$, $|Y|=m$ and minimum degree $d$ that admits no $X$ saturating matching?
graph-theory
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
add a comment |
$begingroup$
Let $nleq m$ be positive integers.
What is the maximum possible value of $d$ such that there exists a bipartite graph $X,Y$ with $|X|=n$, $|Y|=m$ and minimum degree $d$ that admits no $X$ saturating matching?
graph-theory
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
add a comment |
$begingroup$
Let $nleq m$ be positive integers.
What is the maximum possible value of $d$ such that there exists a bipartite graph $X,Y$ with $|X|=n$, $|Y|=m$ and minimum degree $d$ that admits no $X$ saturating matching?
graph-theory
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
$endgroup$
Let $nleq m$ be positive integers.
What is the maximum possible value of $d$ such that there exists a bipartite graph $X,Y$ with $|X|=n$, $|Y|=m$ and minimum degree $d$ that admits no $X$ saturating matching?
graph-theory
graph-theory
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
edited Jan 24 at 5:21
Jorge Fernández Hidalgo
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
asked Jan 23 at 23:48
Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1294195
76.8k1294195
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It is $d = lfloorfrac{n-1}{2}rfloor$.
When $d < frac n2$, we have the following construction. Partition $X$ into $X_1$ and $X_2$ with $|X_i| = d+1$, and partition $Y$ into $Y_1$ and $Y_2$ with $|Y_1| = d$. Then add all edges between $X_i$ and $Y_i$ for $i=1,2$. This has no $X$-saturating matching because the $d+1$ vertices in $X_1$ all want to be matched to the same $d$ vertices in $Y_1$.
When $d ge frac n2$, this does not work. (Vertices in $Y_2$ will not have the right minimum degree.) Here, we can show that there's an $X$-saturating matching by verifying Hall's condition. Let $S subseteq X, S neq varnothing$. Then:
- If $|S| le frac n2$, then $|N(S)| ge d ge |S|$, because just one vertex in $S$ already has $d$ neighbors.
- If $|S| > frac n2$, then $N(S) = Y$, because $|X setminus S| < frac n2 le d$, so each vertex of $Y$ needs a neighbor in $S$ in order to reach the minimum degree of $d$. $|N(S)| = |Y| ge |X| ge |S|$.
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
$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%2f3085241%2fmaximum-minimum-degree-possible-in-a-matchless-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$
It is $d = lfloorfrac{n-1}{2}rfloor$.
When $d < frac n2$, we have the following construction. Partition $X$ into $X_1$ and $X_2$ with $|X_i| = d+1$, and partition $Y$ into $Y_1$ and $Y_2$ with $|Y_1| = d$. Then add all edges between $X_i$ and $Y_i$ for $i=1,2$. This has no $X$-saturating matching because the $d+1$ vertices in $X_1$ all want to be matched to the same $d$ vertices in $Y_1$.
When $d ge frac n2$, this does not work. (Vertices in $Y_2$ will not have the right minimum degree.) Here, we can show that there's an $X$-saturating matching by verifying Hall's condition. Let $S subseteq X, S neq varnothing$. Then:
- If $|S| le frac n2$, then $|N(S)| ge d ge |S|$, because just one vertex in $S$ already has $d$ neighbors.
- If $|S| > frac n2$, then $N(S) = Y$, because $|X setminus S| < frac n2 le d$, so each vertex of $Y$ needs a neighbor in $S$ in order to reach the minimum degree of $d$. $|N(S)| = |Y| ge |X| ge |S|$.
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
add a comment |
$begingroup$
It is $d = lfloorfrac{n-1}{2}rfloor$.
When $d < frac n2$, we have the following construction. Partition $X$ into $X_1$ and $X_2$ with $|X_i| = d+1$, and partition $Y$ into $Y_1$ and $Y_2$ with $|Y_1| = d$. Then add all edges between $X_i$ and $Y_i$ for $i=1,2$. This has no $X$-saturating matching because the $d+1$ vertices in $X_1$ all want to be matched to the same $d$ vertices in $Y_1$.
When $d ge frac n2$, this does not work. (Vertices in $Y_2$ will not have the right minimum degree.) Here, we can show that there's an $X$-saturating matching by verifying Hall's condition. Let $S subseteq X, S neq varnothing$. Then:
- If $|S| le frac n2$, then $|N(S)| ge d ge |S|$, because just one vertex in $S$ already has $d$ neighbors.
- If $|S| > frac n2$, then $N(S) = Y$, because $|X setminus S| < frac n2 le d$, so each vertex of $Y$ needs a neighbor in $S$ in order to reach the minimum degree of $d$. $|N(S)| = |Y| ge |X| ge |S|$.
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
add a comment |
$begingroup$
It is $d = lfloorfrac{n-1}{2}rfloor$.
When $d < frac n2$, we have the following construction. Partition $X$ into $X_1$ and $X_2$ with $|X_i| = d+1$, and partition $Y$ into $Y_1$ and $Y_2$ with $|Y_1| = d$. Then add all edges between $X_i$ and $Y_i$ for $i=1,2$. This has no $X$-saturating matching because the $d+1$ vertices in $X_1$ all want to be matched to the same $d$ vertices in $Y_1$.
When $d ge frac n2$, this does not work. (Vertices in $Y_2$ will not have the right minimum degree.) Here, we can show that there's an $X$-saturating matching by verifying Hall's condition. Let $S subseteq X, S neq varnothing$. Then:
- If $|S| le frac n2$, then $|N(S)| ge d ge |S|$, because just one vertex in $S$ already has $d$ neighbors.
- If $|S| > frac n2$, then $N(S) = Y$, because $|X setminus S| < frac n2 le d$, so each vertex of $Y$ needs a neighbor in $S$ in order to reach the minimum degree of $d$. $|N(S)| = |Y| ge |X| ge |S|$.
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
It is $d = lfloorfrac{n-1}{2}rfloor$.
When $d < frac n2$, we have the following construction. Partition $X$ into $X_1$ and $X_2$ with $|X_i| = d+1$, and partition $Y$ into $Y_1$ and $Y_2$ with $|Y_1| = d$. Then add all edges between $X_i$ and $Y_i$ for $i=1,2$. This has no $X$-saturating matching because the $d+1$ vertices in $X_1$ all want to be matched to the same $d$ vertices in $Y_1$.
When $d ge frac n2$, this does not work. (Vertices in $Y_2$ will not have the right minimum degree.) Here, we can show that there's an $X$-saturating matching by verifying Hall's condition. Let $S subseteq X, S neq varnothing$. Then:
- If $|S| le frac n2$, then $|N(S)| ge d ge |S|$, because just one vertex in $S$ already has $d$ neighbors.
- If $|S| > frac n2$, then $N(S) = Y$, because $|X setminus S| < frac n2 le d$, so each vertex of $Y$ needs a neighbor in $S$ in order to reach the minimum degree of $d$. $|N(S)| = |Y| ge |X| ge |S|$.
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
edited Jan 24 at 5:47
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
answered Jan 24 at 0:24
Misha LavrovMisha Lavrov
47.6k657107
47.6k657107
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%2f3085241%2fmaximum-minimum-degree-possible-in-a-matchless-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
