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