Isoperimetric Tools

Shadows in the n-Cube

Let Qⁿ denote the n-cube and let Qⁿ_k be its k-th level, i.e. the set of all binary strings with exactly k ones. For a subset A of Qⁿ_k denote by Shadow(A) the set of all elements of Qⁿ_k-1 that are covered by A (in the partial order of Qⁿ).

For given n, k, and m, consider the problem of finding an m-subset of Qⁿ_k with the minimum value of |Shadow(A)| among all m-subsets of Qⁿ_k. The fundamental theorem of Kruskal [3] and Katona [2] tells that the set formed by the first m elements of Qⁿ_k in the squashed order, is one of solutions to this problem. More information on the shadow minimization problems can be found in the survey [1].

The squashed order <_sq is defined as follows: for two binary strings a=a₁...a_n and b=b₁...b_n we write a <_sq b if a_n=b_n, a_n-1=b_n-1, . . . , a_i+1=b_i+1, but a_i<b_i for some i.
To see an example of the squashed order on Q⁵ click here.

A subset A of Qⁿ_k is called segment if A consists of consecutive elements of Qⁿ_k in the squashed order. Let C be the set of all elements of Qⁿ_k that preceed any element of A in the squashed order. The new shadow of A is defined as Shadow_new(A) = Shadow(A U C) \ Shadow(C). Clearly, the (new) shadow of a segment A is the sum of the new shadows of its elements.

This tool is intended for computing the new shadows of the elements and subsets of Qⁿ_k for n in the range [3..31] and k in the range [2..n-1]. The segment A is defined by the numbers m and r of its first and last elements in the squashed ordering of Qⁿ_k. The numbers m and r can be entered directly in the "m=" and "r=" fields (see below), or defined as the binomial coefficient "p C q" (p choose q). Only one of these representations should be provided. That is, if a value of m is entered in the "m=" field, then the corresponding fields for the binomial coefficient must be empty, and vice versa. The same rule is also applied to r. The numbers m and r must satisfy the following natural conditions 1 <= m <= r <= |Qⁿ_k|. The tool output, for an example n=20, k=10, m=126585, and r=126587, has the following format:

#       element                n.s.  sum
126585  11110100100000110101    4     4
126586  11101100100000110101    3     7
126587  11011100100000110101    2     9

where # is the element number in the squashed ordering of Qⁿ_k starting from 1, element is the binary representation of that element, n.s. is the size of the new shadow of this element, and sum is the current sum of new shadows.

References

[1] S.L. Bezrukov and U. Leck: The theory of Macaulay posets, in: Numbers, Information and Complexity, I. Althöfer, N. Cai, G. Dueck, L. Khachatrian, M. Pinsker, A. Sarközy, I. Wegener and Z. Zhang (eds.), Kluwer Academic Publishers, 2000, 75-94.
[2] G.O.H. Katona: A theorem of finite sets, in: Theory of graphs, Academia Kiado, Budapest, 1968, 187-207.
[3] J.B. Kruskal: The optimal number of simplices in a complex, Math. Optimization Tech., Univ. of Calif. Press, Berkeley, California, 1963, 251-268.

Last modified: Mon, Jan 23, 2023.