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

Author

Robert Israel, May 06 2015

Keywords

• nonn
• tabl
• more

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

Examples

			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}.
		

Links

• MathOverflow question, Isoperimetric inequality on the Hamming cube

Crossrefs

Cf. A008949.

Programs

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);