The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A256009 Triangle read by rows: Largest cardinality of a set of Hamming diameter <= k in {0,1}^n, k <= n. 1
 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 (list; table; graph; refs; listen; history; text; internal format)
 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 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, e]<=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, '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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 4 14:51 EDT 2020. Contains 335448 sequences. (Running on oeis4.)