Irredundant Families of Subcubes

Details Irredundant Families of Subcubes Irredundant Families of Subcubes

2010-03-15

arxiv.org/abs/1003.2960v1

Mathematics

Combinatorics

24 pages

Scientific paper

We consider the problem of finding the maximum possible size of a family of k-dimensional subcubes of the n-cube {0,1}^{n}, none of which is contained in the union of the others. (We call such a family `irredundant'). Aharoni and Holzman conjectured that for k > n/2, the answer is {n choose k} (which is attained by the family of all k-subcubes containing a fixed point). We give a new proof of a general upper bound of Meshulam, and we prove that for k >= n/2, any irredundant family in which all the subcubes go through either (0,0,...,0) or (1,1,...,1) has size at most {n choose k}. We then give a general lower bound, showing that Meshulam's upper bound is always tight up to a factor of at most e.

Affiliated with

Also associated with

No associations

Rating

Irredundant Families of Subcubes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Irredundant Families of Subcubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Irredundant Families of Subcubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-214748