Packing vertices on a hypercube graph?
$begingroup$
Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The problem is to maximise the number of red vertices for a given n.
I have absolutely no idea where to start. Any help is appreciated.
graph-theory
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
$endgroup$
add a comment |
$begingroup$
Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The problem is to maximise the number of red vertices for a given n.
I have absolutely no idea where to start. Any help is appreciated.
graph-theory
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
$endgroup$
$begingroup$
Isn't the independence number of the union of the squared graph and itself?
$endgroup$
– Bullet51
Feb 15 at 11:33
$begingroup$
@Bullet51 it is, but how does it help?
$endgroup$
– Fedor Petrov
Feb 15 at 11:34
$begingroup$
If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters.
$endgroup$
– quarague
Feb 15 at 11:35
$begingroup$
One could use independence number bounds, like Lovasz $theta$ bound, Hoffman $lambda_1$ bound, etc.
$endgroup$
– Bullet51
Feb 15 at 11:36
$begingroup$
Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8
$endgroup$
– Grothendeeeeck
Feb 15 at 11:39
add a comment |
$begingroup$
Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The problem is to maximise the number of red vertices for a given n.
I have absolutely no idea where to start. Any help is appreciated.
graph-theory
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
$endgroup$
Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The problem is to maximise the number of red vertices for a given n.
I have absolutely no idea where to start. Any help is appreciated.
graph-theory
graph-theory
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
asked Feb 15 at 11:29
GrothendeeeeckGrothendeeeeck
183
183
$begingroup$
Isn't the independence number of the union of the squared graph and itself?
$endgroup$
– Bullet51
Feb 15 at 11:33
$begingroup$
@Bullet51 it is, but how does it help?
$endgroup$
– Fedor Petrov
Feb 15 at 11:34
$begingroup$
If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters.
$endgroup$
– quarague
Feb 15 at 11:35
$begingroup$
One could use independence number bounds, like Lovasz $theta$ bound, Hoffman $lambda_1$ bound, etc.
$endgroup$
– Bullet51
Feb 15 at 11:36
$begingroup$
Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8
$endgroup$
– Grothendeeeeck
Feb 15 at 11:39
add a comment |
$begingroup$
Isn't the independence number of the union of the squared graph and itself?
$endgroup$
– Bullet51
Feb 15 at 11:33
$begingroup$
@Bullet51 it is, but how does it help?
$endgroup$
– Fedor Petrov
Feb 15 at 11:34
$begingroup$
If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters.
$endgroup$
– quarague
Feb 15 at 11:35
$begingroup$
One could use independence number bounds, like Lovasz $theta$ bound, Hoffman $lambda_1$ bound, etc.
$endgroup$
– Bullet51
Feb 15 at 11:36
$begingroup$
Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8
$endgroup$
– Grothendeeeeck
Feb 15 at 11:39
$begingroup$
Isn't the independence number of the union of the squared graph and itself?
$endgroup$
– Bullet51
Feb 15 at 11:33
$begingroup$
Isn't the independence number of the union of the squared graph and itself?
$endgroup$
– Bullet51
Feb 15 at 11:33
$begingroup$
@Bullet51 it is, but how does it help?
$endgroup$
– Fedor Petrov
Feb 15 at 11:34
$begingroup$
@Bullet51 it is, but how does it help?
$endgroup$
– Fedor Petrov
Feb 15 at 11:34
$begingroup$
If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters.
$endgroup$
– quarague
Feb 15 at 11:35
$begingroup$
If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters.
$endgroup$
– quarague
Feb 15 at 11:35
$begingroup$
One could use independence number bounds, like Lovasz $theta$ bound, Hoffman $lambda_1$ bound, etc.
$endgroup$
– Bullet51
Feb 15 at 11:36
$begingroup$
One could use independence number bounds, like Lovasz $theta$ bound, Hoffman $lambda_1$ bound, etc.
$endgroup$
– Bullet51
Feb 15 at 11:36
$begingroup$
Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8
$endgroup$
– Grothendeeeeck
Feb 15 at 11:39
$begingroup$
Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8
$endgroup$
– Grothendeeeeck
Feb 15 at 11:39
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $alpha leq |V|* frac{-lambda}{d-lambda}$, where $lambda$ is the smallest eigenvalue of the graph, and $d$ is the degree of the graph.
In order to compute the smallest eigenvalue, we can apply the character formula for Cayley graphs of abelian groups: in this case, the eigevalues are simply $sum_{s}prod_a{s_a}$, where $s$ ranges over all codewords with 1 or 2 $-1$s (the remaining bits are $1$), and $a$ some subset of indicies.
As $s$ is invariant with bit permutation, only the size of $a$ matter. Let $w$ denote the size of $a$. The corresponding eigenvalue is $2w^2 - 2wn - 2w + frac{n^2+n}2$, and attains its minimum at $w=frac{n}2$ and $w=frac{n}2+1$, where the value is $-frac{n}2$.
The upper bound is therefore $frac{2^n}{n+2}$. In odd dimensions the reasoning applies too, but the bound is the same of Fedor Petrov's.
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
$endgroup$
1
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
add a comment |
$begingroup$
The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube ${0,1}^n$ except the origin $(0,0,dots,0)$, and call the functions from $A$ to $mathbb{F}_2$ red if it sums up to 0 on every facet ${x_i=1}$ for all $i=1,2,dots,k$. We get exactly $2^{n-k}=2^n/(n+1)$ red functions and any two of them differ at least in three vertices. Indeed, if red functions $f,g$ differ in at most two vertices $u,vin A$, then there exists $i$ such that $u_i=1$ and $v_i=0$, and one of the functions $f,g$ has odd sum on the facet ${x_i=1}$.
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
$endgroup$
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
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: "504"
};
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%2fmathoverflow.net%2fquestions%2f323297%2fpacking-vertices-on-a-hypercube-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $alpha leq |V|* frac{-lambda}{d-lambda}$, where $lambda$ is the smallest eigenvalue of the graph, and $d$ is the degree of the graph.
In order to compute the smallest eigenvalue, we can apply the character formula for Cayley graphs of abelian groups: in this case, the eigevalues are simply $sum_{s}prod_a{s_a}$, where $s$ ranges over all codewords with 1 or 2 $-1$s (the remaining bits are $1$), and $a$ some subset of indicies.
As $s$ is invariant with bit permutation, only the size of $a$ matter. Let $w$ denote the size of $a$. The corresponding eigenvalue is $2w^2 - 2wn - 2w + frac{n^2+n}2$, and attains its minimum at $w=frac{n}2$ and $w=frac{n}2+1$, where the value is $-frac{n}2$.
The upper bound is therefore $frac{2^n}{n+2}$. In odd dimensions the reasoning applies too, but the bound is the same of Fedor Petrov's.
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
$endgroup$
1
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
add a comment |
$begingroup$
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $alpha leq |V|* frac{-lambda}{d-lambda}$, where $lambda$ is the smallest eigenvalue of the graph, and $d$ is the degree of the graph.
In order to compute the smallest eigenvalue, we can apply the character formula for Cayley graphs of abelian groups: in this case, the eigevalues are simply $sum_{s}prod_a{s_a}$, where $s$ ranges over all codewords with 1 or 2 $-1$s (the remaining bits are $1$), and $a$ some subset of indicies.
As $s$ is invariant with bit permutation, only the size of $a$ matter. Let $w$ denote the size of $a$. The corresponding eigenvalue is $2w^2 - 2wn - 2w + frac{n^2+n}2$, and attains its minimum at $w=frac{n}2$ and $w=frac{n}2+1$, where the value is $-frac{n}2$.
The upper bound is therefore $frac{2^n}{n+2}$. In odd dimensions the reasoning applies too, but the bound is the same of Fedor Petrov's.
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
$endgroup$
1
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
add a comment |
$begingroup$
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $alpha leq |V|* frac{-lambda}{d-lambda}$, where $lambda$ is the smallest eigenvalue of the graph, and $d$ is the degree of the graph.
In order to compute the smallest eigenvalue, we can apply the character formula for Cayley graphs of abelian groups: in this case, the eigevalues are simply $sum_{s}prod_a{s_a}$, where $s$ ranges over all codewords with 1 or 2 $-1$s (the remaining bits are $1$), and $a$ some subset of indicies.
As $s$ is invariant with bit permutation, only the size of $a$ matter. Let $w$ denote the size of $a$. The corresponding eigenvalue is $2w^2 - 2wn - 2w + frac{n^2+n}2$, and attains its minimum at $w=frac{n}2$ and $w=frac{n}2+1$, where the value is $-frac{n}2$.
The upper bound is therefore $frac{2^n}{n+2}$. In odd dimensions the reasoning applies too, but the bound is the same of Fedor Petrov's.
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
$endgroup$
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $alpha leq |V|* frac{-lambda}{d-lambda}$, where $lambda$ is the smallest eigenvalue of the graph, and $d$ is the degree of the graph.
In order to compute the smallest eigenvalue, we can apply the character formula for Cayley graphs of abelian groups: in this case, the eigevalues are simply $sum_{s}prod_a{s_a}$, where $s$ ranges over all codewords with 1 or 2 $-1$s (the remaining bits are $1$), and $a$ some subset of indicies.
As $s$ is invariant with bit permutation, only the size of $a$ matter. Let $w$ denote the size of $a$. The corresponding eigenvalue is $2w^2 - 2wn - 2w + frac{n^2+n}2$, and attains its minimum at $w=frac{n}2$ and $w=frac{n}2+1$, where the value is $-frac{n}2$.
The upper bound is therefore $frac{2^n}{n+2}$. In odd dimensions the reasoning applies too, but the bound is the same of Fedor Petrov's.
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
edited Feb 15 at 14:55
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
answered Feb 15 at 12:02
Bullet51Bullet51
1,355314
1,355314
1
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
add a comment |
1
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
1
1
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
$begingroup$
I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $jne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)geqslant k$.
$endgroup$
– Fedor Petrov
Feb 18 at 9:00
add a comment |
$begingroup$
The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube ${0,1}^n$ except the origin $(0,0,dots,0)$, and call the functions from $A$ to $mathbb{F}_2$ red if it sums up to 0 on every facet ${x_i=1}$ for all $i=1,2,dots,k$. We get exactly $2^{n-k}=2^n/(n+1)$ red functions and any two of them differ at least in three vertices. Indeed, if red functions $f,g$ differ in at most two vertices $u,vin A$, then there exists $i$ such that $u_i=1$ and $v_i=0$, and one of the functions $f,g$ has odd sum on the facet ${x_i=1}$.
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
$endgroup$
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
add a comment |
$begingroup$
The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube ${0,1}^n$ except the origin $(0,0,dots,0)$, and call the functions from $A$ to $mathbb{F}_2$ red if it sums up to 0 on every facet ${x_i=1}$ for all $i=1,2,dots,k$. We get exactly $2^{n-k}=2^n/(n+1)$ red functions and any two of them differ at least in three vertices. Indeed, if red functions $f,g$ differ in at most two vertices $u,vin A$, then there exists $i$ such that $u_i=1$ and $v_i=0$, and one of the functions $f,g$ has odd sum on the facet ${x_i=1}$.
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
$endgroup$
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
add a comment |
$begingroup$
The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube ${0,1}^n$ except the origin $(0,0,dots,0)$, and call the functions from $A$ to $mathbb{F}_2$ red if it sums up to 0 on every facet ${x_i=1}$ for all $i=1,2,dots,k$. We get exactly $2^{n-k}=2^n/(n+1)$ red functions and any two of them differ at least in three vertices. Indeed, if red functions $f,g$ differ in at most two vertices $u,vin A$, then there exists $i$ such that $u_i=1$ and $v_i=0$, and one of the functions $f,g$ has odd sum on the facet ${x_i=1}$.
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
$endgroup$
The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube ${0,1}^n$ except the origin $(0,0,dots,0)$, and call the functions from $A$ to $mathbb{F}_2$ red if it sums up to 0 on every facet ${x_i=1}$ for all $i=1,2,dots,k$. We get exactly $2^{n-k}=2^n/(n+1)$ red functions and any two of them differ at least in three vertices. Indeed, if red functions $f,g$ differ in at most two vertices $u,vin A$, then there exists $i$ such that $u_i=1$ and $v_i=0$, and one of the functions $f,g$ has odd sum on the facet ${x_i=1}$.
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
edited Feb 15 at 11:45
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
answered Feb 15 at 11:38
Fedor PetrovFedor Petrov
49.4k5114230
49.4k5114230
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
add a comment |
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph.
$endgroup$
– Grothendeeeeck
Feb 15 at 12:14
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Grothendeeeeck The Lovasz $theta$ bound gives $n leq 8/3$ in this case, which proves the optimality of the number of vertices.
$endgroup$
– Bullet51
Feb 15 at 12:22
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself?
$endgroup$
– Grothendeeeeck
Feb 15 at 12:33
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number
$endgroup$
– Bullet51
Feb 15 at 12:34
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
$begingroup$
@Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out
$endgroup$
– Grothendeeeeck
Feb 15 at 12:38
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f323297%2fpacking-vertices-on-a-hypercube-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
$begingroup$
Isn't the independence number of the union of the squared graph and itself?
$endgroup$
– Bullet51
Feb 15 at 11:33
$begingroup$
@Bullet51 it is, but how does it help?
$endgroup$
– Fedor Petrov
Feb 15 at 11:34
$begingroup$
If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters.
$endgroup$
– quarague
Feb 15 at 11:35
$begingroup$
One could use independence number bounds, like Lovasz $theta$ bound, Hoffman $lambda_1$ bound, etc.
$endgroup$
– Bullet51
Feb 15 at 11:36
$begingroup$
Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8
$endgroup$
– Grothendeeeeck
Feb 15 at 11:39