A373005 Array read by ascending antidiagonals: A(n,k) is the maximum possible cardinality of a set of points of diameter at most k-1 in {0,1}^n.
1, 0, 1, 0, 1, 2, 0, 1, 2, 1, 0, 1, 2, 2, 0, 0, 1, 2, 3, 2, 1, 0, 1, 2, 4, 4, 2, 2, 0, 1, 2, 5, 6, 4, 2, 1, 0, 1, 2, 6, 8, 7, 4, 2, 0, 0, 1, 2, 7, 10, 11, 8, 4, 2, 1, 0, 1, 2, 8, 12, 16, 14, 8, 4, 2, 2, 0, 1, 2, 9, 14, 22, 22, 15, 8, 4, 2, 1, 0, 1, 2, 10, 16, 29, 32, 26, 16, 8, 4, 2, 0
Offset: 0
Examples
The array begins: 1, 1, 2, 1, 0, 1, 2, 1, ... 0, 1, 2, 2, 2, 2, 2, 2, ... 0, 1, 2, 3, 4, 4, 4, 4, ... 0, 1, 2, 4, 6, 7, 8, 8, ... 0, 1, 2, 5, 8, 11, 14, 15, ... 0, 1, 2, 6, 10, 16, 22, 26, ... 0, 1, 2, 7, 12, 22, 32, 42, ... 0, 1, 2, 8, 14, 29, 44, 64, ... ...
Links
- Noga Alon, Zhihan Jin, and Benny Sudakov, The Helly number of Hamming balls and related problems, arXiv:2405.10275 [math.CO], 2024. See p. 3.
- S. L. Bezrukov, Specification of all maximal subsets of the unit cube with respect to given diameter. Problemy Peredachi Informatsii, pages 106-109, 1987. On ResearchGate.
- G. Katona, Intersection theorems for systems of finite sets, Acta Mathematica Academiae Scientiarum Hungaricae 15, 329-337 (1964).
- Daniel J. Kleitman, On a combinatorial conjecture of Erdös, Journal of Combinatorial Theory, Series A 1, 209-214, (1966).
Crossrefs
Programs
-
Mathematica
A[n_,k_]:=If[OddQ[k],Sum[Binomial[n,i],{i,0,(k-1)/2}], Binomial[n-1,k/2-1]+Sum[Binomial[n,i],{i,0,k/2-1}]]; Table[A[n-k,k],{n,0,12},{k,0,n}]//Flatten
Comments