Perfect matching in the n-unit-cube, Is hyperplane statement wrong?
up vote
0
down vote
favorite
I was thinking about perfect matchings in the graph of the unit-cube of dimension $n$: $Q_n = [0,1]^n$. ($0$-$1$-strings of length n are vertices. Two of such are connected by an edge iff. they differ by only 1 bit (i.e. Hamming distance is equal to 1)).
Suppose you're given an arbitrary perfect matching $M$ in $Q_n$. Is it possible to find a facet $F$ of $Q_n$ such that all matching edges $e = (v,w) in M$ that cover a vertex in $F$ lie in $F$? Stated differently, if $v in F$ and $(v,w) in M$ for some vertex $w$, does that imply that $w in F$? This statement should be equivalent to finding a separating hyperplane, that separates $Q_n$ into two $(n-1)$-cubes, such that no matching edge crosses the hyperplane.
What do you think, is this true or false? Obviously its false for $n=1$ but I think it should hold for all $n geq 2$, but can't prove it!
Any advice on how to prove it or a counterexample is greatly appreciated!
Thanks!
combinatorics graph-theory matching-theory bit-strings
asked Nov 14 at 19:38
Doc
367113
add a comment |
up vote
0
down vote
favorite
I was thinking about perfect matchings in the graph of the unit-cube of dimension $n$: $Q_n = [0,1]^n$. ($0$-$1$-strings of length n are vertices. Two of such are connected by an edge iff. they differ by only 1 bit (i.e. Hamming distance is equal to 1)).
Suppose you're given an arbitrary perfect matching $M$ in $Q_n$. Is it possible to find a facet $F$ of $Q_n$ such that all matching edges $e = (v,w) in M$ that cover a vertex in $F$ lie in $F$? Stated differently, if $v in F$ and $(v,w) in M$ for some vertex $w$, does that imply that $w in F$? This statement should be equivalent to finding a separating hyperplane, that separates $Q_n$ into two $(n-1)$-cubes, such that no matching edge crosses the hyperplane.
What do you think, is this true or false? Obviously its false for $n=1$ but I think it should hold for all $n geq 2$, but can't prove it!
Any advice on how to prove it or a counterexample is greatly appreciated!
Thanks!
combinatorics graph-theory matching-theory bit-strings
asked Nov 14 at 19:38
Doc
367113
1
By “facet” do you mean an induced $Q_{n-1}$-subgraph?
– Santana Afton
Nov 14 at 19:39
Yes. With facet I mean an $n-1$ dimensional face of $Q_n$ viewed as a polytope. Each facet has one coordinate fixed to $0$ (or $1$) and all others are still in the interval $[0,1]$.
– Doc
Nov 14 at 19:53
Is this a counter example? I’m not sure I can find a sub-cube that only fully contains matching edges. I apologize in advance for the quality — I’m not at my desk at the moment.
– Santana Afton
Nov 14 at 20:10
Thanks for your effort, but to be quite honest, I am not sure whether I understand your drawing correctly.
– Doc
Nov 14 at 20:20
1
Let me know if this is any better.
– Santana Afton
Nov 14 at 21:13
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I was thinking about perfect matchings in the graph of the unit-cube of dimension $n$: $Q_n = [0,1]^n$. ($0$-$1$-strings of length n are vertices. Two of such are connected by an edge iff. they differ by only 1 bit (i.e. Hamming distance is equal to 1)).
Suppose you're given an arbitrary perfect matching $M$ in $Q_n$. Is it possible to find a facet $F$ of $Q_n$ such that all matching edges $e = (v,w) in M$ that cover a vertex in $F$ lie in $F$? Stated differently, if $v in F$ and $(v,w) in M$ for some vertex $w$, does that imply that $w in F$? This statement should be equivalent to finding a separating hyperplane, that separates $Q_n$ into two $(n-1)$-cubes, such that no matching edge crosses the hyperplane.
What do you think, is this true or false? Obviously its false for $n=1$ but I think it should hold for all $n geq 2$, but can't prove it!
Any advice on how to prove it or a counterexample is greatly appreciated!
Thanks!
combinatorics graph-theory matching-theory bit-strings
asked Nov 14 at 19:38
Doc
367113
I was thinking about perfect matchings in the graph of the unit-cube of dimension $n$: $Q_n = [0,1]^n$. ($0$-$1$-strings of length n are vertices. Two of such are connected by an edge iff. they differ by only 1 bit (i.e. Hamming distance is equal to 1)).
Suppose you're given an arbitrary perfect matching $M$ in $Q_n$. Is it possible to find a facet $F$ of $Q_n$ such that all matching edges $e = (v,w) in M$ that cover a vertex in $F$ lie in $F$? Stated differently, if $v in F$ and $(v,w) in M$ for some vertex $w$, does that imply that $w in F$? This statement should be equivalent to finding a separating hyperplane, that separates $Q_n$ into two $(n-1)$-cubes, such that no matching edge crosses the hyperplane.
What do you think, is this true or false? Obviously its false for $n=1$ but I think it should hold for all $n geq 2$, but can't prove it!
Any advice on how to prove it or a counterexample is greatly appreciated!
Thanks!
combinatorics graph-theory matching-theory bit-strings
combinatorics graph-theory matching-theory bit-strings
asked Nov 14 at 19:38
Doc
367113
asked Nov 14 at 19:38
Doc
367113
asked Nov 14 at 19:38
Doc
367113
asked Nov 14 at 19:38
Doc
367113
asked Nov 14 at 19:38
Doc
367113
367113
1
By “facet” do you mean an induced $Q_{n-1}$-subgraph?
– Santana Afton
Nov 14 at 19:39
Yes. With facet I mean an $n-1$ dimensional face of $Q_n$ viewed as a polytope. Each facet has one coordinate fixed to $0$ (or $1$) and all others are still in the interval $[0,1]$.
– Doc
Nov 14 at 19:53
Is this a counter example? I’m not sure I can find a sub-cube that only fully contains matching edges. I apologize in advance for the quality — I’m not at my desk at the moment.
– Santana Afton
Nov 14 at 20:10
Thanks for your effort, but to be quite honest, I am not sure whether I understand your drawing correctly.
– Doc
Nov 14 at 20:20
1
Let me know if this is any better.
– Santana Afton
Nov 14 at 21:13
add a comment |
1
By “facet” do you mean an induced $Q_{n-1}$-subgraph?
– Santana Afton
Nov 14 at 19:39
Yes. With facet I mean an $n-1$ dimensional face of $Q_n$ viewed as a polytope. Each facet has one coordinate fixed to $0$ (or $1$) and all others are still in the interval $[0,1]$.
– Doc
Nov 14 at 19:53
Is this a counter example? I’m not sure I can find a sub-cube that only fully contains matching edges. I apologize in advance for the quality — I’m not at my desk at the moment.
– Santana Afton
Nov 14 at 20:10
Thanks for your effort, but to be quite honest, I am not sure whether I understand your drawing correctly.
– Doc
Nov 14 at 20:20
1
Let me know if this is any better.
– Santana Afton
Nov 14 at 21:13
1
1
By “facet” do you mean an induced $Q_{n-1}$-subgraph?
– Santana Afton
Nov 14 at 19:39
By “facet” do you mean an induced $Q_{n-1}$-subgraph?
– Santana Afton
Nov 14 at 19:39
Yes. With facet I mean an $n-1$ dimensional face of $Q_n$ viewed as a polytope. Each facet has one coordinate fixed to $0$ (or $1$) and all others are still in the interval $[0,1]$.
– Doc
Nov 14 at 19:53
Yes. With facet I mean an $n-1$ dimensional face of $Q_n$ viewed as a polytope. Each facet has one coordinate fixed to $0$ (or $1$) and all others are still in the interval $[0,1]$.
– Doc
Nov 14 at 19:53
Is this a counter example? I’m not sure I can find a sub-cube that only fully contains matching edges. I apologize in advance for the quality — I’m not at my desk at the moment.
– Santana Afton
Nov 14 at 20:10
Is this a counter example? I’m not sure I can find a sub-cube that only fully contains matching edges. I apologize in advance for the quality — I’m not at my desk at the moment.
– Santana Afton
Nov 14 at 20:10
Thanks for your effort, but to be quite honest, I am not sure whether I understand your drawing correctly.
– Doc
Nov 14 at 20:20
Thanks for your effort, but to be quite honest, I am not sure whether I understand your drawing correctly.
– Doc
Nov 14 at 20:20
1
1
Let me know if this is any better.
– Santana Afton
Nov 14 at 21:13
Let me know if this is any better.
– Santana Afton
Nov 14 at 21:13
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Here is a perfect matching in $Q_4$ that does not have this property.
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
1
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
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
accepted
Here is a perfect matching in $Q_4$ that does not have this property.
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
1
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
add a comment |
up vote
3
down vote
accepted
Here is a perfect matching in $Q_4$ that does not have this property.
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
1
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Here is a perfect matching in $Q_4$ that does not have this property.
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
Here is a perfect matching in $Q_4$ that does not have this property.
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
answered Nov 14 at 21:07
Misha Lavrov
41.7k555101
41.7k555101
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
1
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
add a comment |
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
1
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
I think we came up with very nearly the same matching!
– Santana Afton
Nov 14 at 21:14
1
1
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
It's quite possible that there is only one construction up to symmetry here. We have 4 directions, and in each one of them we want at least one (and therefore at least two) edges.
– Misha Lavrov
Nov 14 at 21:34
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
Thanks, I was pretty sure that this holds!
– Doc
Nov 15 at 7:31
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998733%2fperfect-matching-in-the-n-unit-cube-is-hyperplane-statement-wrong%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
By “facet” do you mean an induced $Q_{n-1}$-subgraph?
– Santana Afton
Nov 14 at 19:39
Yes. With facet I mean an $n-1$ dimensional face of $Q_n$ viewed as a polytope. Each facet has one coordinate fixed to $0$ (or $1$) and all others are still in the interval $[0,1]$.
– Doc
Nov 14 at 19:53
Is this a counter example? I’m not sure I can find a sub-cube that only fully contains matching edges. I apologize in advance for the quality — I’m not at my desk at the moment.
– Santana Afton
Nov 14 at 20:10
Thanks for your effort, but to be quite honest, I am not sure whether I understand your drawing correctly.
– Doc
Nov 14 at 20:20
1
Let me know if this is any better.
– Santana Afton
Nov 14 at 21:13