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

%I #28 Dec 17 2017 07:15:17

%S 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,

%T 8,14,29,44,64,128,1,2,9,16,37,58,93,128,256

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

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

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

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

%C a(n,0) = 1.

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

%C a(n,n) = 2^n.

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

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

%C a(n,3) >= 2n for n >= 4, and this appears to be an equality. - _Robert Israel_, Apr 20 2016

%H MathOverflow question, <a href="http://mathoverflow.net/questions/205877/isoperimetric-inequality-on-the-hamming-cube/205904">Isoperimetric inequality on the Hamming cube</a>

%e Triangle begins

%e 1

%e 1 2

%e 1 2 4

%e 1 2 4 8

%e 1 2 5 8 16

%e 1 2 6 10 16 32

%e 1 2 7 12 22 32 64

%e 1 2 8 14 29 44 64 128

%e 1 2 9 16 37 58 93 128 256

%e a(4,2) = 5: a suitable set of diameter <= 2 is {0000, 0001, 0010, 0100, 1000}.

%p clist:= proc(c,n) local V;

%p V:= Vector(n);

%p V[convert(c,list)]:= 1;

%p convert(V,list);

%p end proc:

%p f:= proc(n,k)

%p uses GraphTheory, combinat;

%p local Verts, dist, E, G, V0, G0, vk, Vk, G1;

%p if k = 0 then return 1

%p elif k >= n then return 2^n

%p fi;

%p Verts:= map(clist, convert(powerset(n),list), n);

%p dist:= Matrix(2^n,2^n,shape=symmetric,(i,j) -> convert(abs~(Verts[i]-Verts[j]),`+`));

%p E:= select(e -> dist[e[1],e[2]]<=k, {seq(seq({i,j},j=i+1..2^n),i=1..2^n)});

%p G:= Graph(2^n,E);

%p V0:= Neighborhood(G,1,'open');

%p G0:= InducedSubgraph(G,V0);

%p vk:= select(j -> dist[1,j] = k, V0);

%p Vk:= Neighborhood(G0,vk[1],'open');

%p G1:= InducedSubgraph(G0, Vk);

%p CliqueNumber(G1)+2;

%p end proc:

%p seq(seq(f(n,k), k=0..n),n=0..6);

%o (MATLAB with CPLEX API)

%o function s = A256009( n,k )

%o if k == 0

%o s = 1;

%o return;

%o elseif k >= n

%o s = 2^n;

%o return;

%o end

%o cplex = Cplex('problem');

%o H = dec2bin(0:2^n-1) - '0';

%o cplex.Model.sense = 'maximize';

%o cplex.Param.mip.display.Cur = 0;

%o obj = ones(2^n,1);

%o ctype = char('B'*ones(1,2^n));

%o cplex.addCols(obj,[],zeros(2^n,1),[],ctype);

%o R = sum(H,2) * ones(1,2^n);

%o D = R + R' - 2*H*H';

%o [ros,cols] = find(triu(D) > k);

%o ncons = numel(ros);

%o for i=1:ncons

%o cplex.addSOSs('1',[ros(i),cols(i)]',[1,2]');

%o end

%o cplex.solve();

%o s = cplex.Solution.objval;

%o end

%Y Cf. A008949.

%K nonn,tabl,more

%O 0,3

%A _Robert Israel_, May 06 2015