login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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