4
$\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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Isn't the independence number of the union of the squared graph and itself? $\endgroup$
    – LeechLattice
    Commented Feb 15, 2019 at 11:33
  • $\begingroup$ @Bullet51 it is, but how does it help? $\endgroup$
    – Fedor Petrov
    Commented Feb 15, 2019 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
    Commented Feb 15, 2019 at 11:35
  • $\begingroup$ One could use independence number bounds, like Lovasz $\theta$ bound, Hoffman $\lambda_1$ bound, etc. $\endgroup$
    – LeechLattice
    Commented Feb 15, 2019 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$
    – user135868
    Commented Feb 15, 2019 at 11:39

2 Answers 2

Reset to default
6
$\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.

Improve this answer
$\endgroup$
1
  • 2
    $\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 $j\ne 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
    Commented Feb 18, 2019 at 9:00
4
$\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,v\in 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\}$.

Improve this answer
$\endgroup$
5
  • $\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$
    – user135868
    Commented Feb 15, 2019 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$
    – LeechLattice
    Commented Feb 15, 2019 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$
    – user135868
    Commented Feb 15, 2019 at 12:33
  • $\begingroup$ @Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number $\endgroup$
    – LeechLattice
    Commented Feb 15, 2019 at 12:34
  • $\begingroup$ @Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out $\endgroup$
    – user135868
    Commented Feb 15, 2019 at 12:38

You must log in to answer this question.