A256009 Triangle read by rows: Largest cardinality of a set of Hamming diameter <= k in {0,1}^n, k <= n.

1, 1, 2, 1, 2, 4, 1, 2, 4, 8, 1, 2, 5, 8, 16, 1, 2, 6, 10, 16, 32, 1, 2, 7, 12, 22, 32, 64, 1, 2, 8, 14, 29, 44, 64, 128, 1, 2, 9, 16, 37, 58, 93, 128, 256

Offset

0,3

Comments

Size of largest clique in graph with vertices {0,1}^n, edges joining points with distance <= k.

By considering balls of radius k, a(n,2*k) >= A008949(n,k).

By considering Cartesian products, a(n1 + n2, k1 + k2) >= a(n1,k1)*a(n2,k2).

a(n,0) = 1.

a(n,1) = 2 for n >= 1.

a(n,n) = 2^n.

a(n,2) = n + 1 for n >= 2.

a(n,n-1) = 2^(n-1).

a(n,3) >= 2n for n >= 4, and this appears to be an equality. - Robert Israel, Apr 20 2016

Links

Table of n, a(n) for n=0..44.

MathOverflow question, Isoperimetric inequality on the Hamming cube

Example

Triangle begins
  1
  1   2
  1   2   4
  1   2   4   8
  1   2   5   8    16
  1   2   6  10    16    32
  1   2   7  12    22    32    64
  1   2   8  14    29    44    64   128
  1   2   9  16    37    58    93   128   256
a(4,2) = 5: a suitable set of diameter <= 2 is {0000, 0001, 0010, 0100, 1000}.

Maple

clist:= proc(c, n) local V;
   V:= Vector(n);
   V[convert(c, list)]:= 1;
   convert(V, list);
end proc:
f:= proc(n, k)
uses GraphTheory, combinat;
  local Verts, dist, E, G, V0, G0, vk, Vk, G1;
  if k = 0 then return 1
  elif k >= n then return 2^n
  fi;
Verts:= map(clist, convert(powerset(n), list), n);
  dist:= Matrix(2^n, 2^n, shape=symmetric, (i, j) -> convert(abs~(Verts[i]-Verts[j]), `+`));
  E:= select(e -> dist[e[1], e[2]]<=k, {seq(seq({i, j}, j=i+1..2^n), i=1..2^n)});
G:= Graph(2^n, E);
V0:= Neighborhood(G, 1, 'open');
G0:= InducedSubgraph(G, V0);
vk:= select(j -> dist[1, j] = k, V0);
Vk:= Neighborhood(G0, vk[1], 'open');
G1:= InducedSubgraph(G0, Vk);
CliqueNumber(G1)+2;
end proc:
seq(seq(f(n, k), k=0..n), n=0..6);

Prog

(MATLAB with CPLEX API)
function s = A256009( n, k )
  if k == 0
    s = 1;
    return;
  elseif k >= n
    s = 2^n;
    return;
  end
  cplex = Cplex('problem');
H = dec2bin(0:2^n-1) - '0';
cplex.Model.sense = 'maximize';
cplex.Param.mip.display.Cur = 0;
obj = ones(2^n, 1);
ctype = char('B'*ones(1, 2^n));
cplex.addCols(obj, [], zeros(2^n, 1), [], ctype);
R = sum(H, 2) * ones(1, 2^n);
D = R + R' - 2*H*H';
[ros, cols] = find(triu(D) > k);
ncons = numel(ros);
for i=1:ncons
    cplex.addSOSs('1', [ros(i), cols(i)]', [1, 2]');
end
cplex.solve();
s = cplex.Solution.objval;
end

Crossrefs

Cf. A008949.

Sequence in context: A131074 A059268 A300653 * A123937 A138882 A074634

Adjacent sequences: A256006 A256007 A256008 * A256010 A256011 A256012

Keyword

nonn,tabl,more

Author

Robert Israel, May 06 2015

Status

approved