A subspace covering problem in the -cube

详细信息    查看全文

• 作者：Harout Aydinian ^{h.aydinyan@tum.de}
• 关键词：Packing and covering ; Dimension constraint ; Graph decomposition
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P3
• 页码：513-517
• 全文大小：378 K
• 卷排序：216

文摘

In this short note we consider the following problem stated in the paper Ahlswede et al. (2003). Let En={0,1}n⊂RnEn={0,1}n⊂Rn and let Ern⊂En be the vectors of weight rr. How many kk-subspaces of RnRn are needed to cover the elements of Ern? A kk-subspace VV is called optimal if V∩Ern has maximum size, taken over all kk-subspaces V⊂RnV⊂Rn. We are interested in covering of Ern by a set VV of optimal kk-subspaces. In case VV is a covering with V∩U∩Ern=0̸, for all distinct V,U∈VV,U∈V, we have a perfect covering. We here address the simplest case: r=2r=2 with k≤4k≤4. It turns out that complete solution to the case k=3k=3 follows from known results on packings and coverings of a complete graph with cycles of length four. For the case k=4k=4 we show that perfect coverings of E2n always exist, provided the obvious divisibility condition for nn holds. Similarly, we define the covering problem for EnEn, that is the covering of the vectors of EnEn by kk-subspaces. We show that a perfect covering of EnEn by kk-subspaces does not exist, except for the case n=2k=4n=2k=4.