论文标题
几乎覆盖了多种多数的所有超立方体的层
Almost covering all the layers of hypercube with multiplicities
论文作者
论文摘要
给定一个超立方体$ \ MATHCAL {q}^{n}：= \ {0,1 \}^{n} $ in $ \ MATHBB {r}^{r}^{n} $和$ k \ in \ in \ {0，\ {0，\ dots，\ dots，n \} $ $ \ MATHCAL {q}^{n} $表示$ \ Mathcal {q}^{n} $中的所有点的集合，其坐标完全包含$ k $许多。对于固定的$ t \ in \ mathbb {n} $和$ k \ in \ {0，\ dots，n \} $，让$ p \ in \ mathbb {r} \ left [x_ {1}，\ dots，\ dots，\ dots，x_ {n} \ right] $ \ MATHCAL {Q}^{n} \ setMinus \ Mathcal {q}^{n} _ {k} $，并且$ p $在$ \ \ \ nathcal的所有点上都具有$ t-1 $的零零零，{q}^}^{n} _ {n} _}简而言之，我们表明$$ deg（p）\ geq \ max \ left \ {k，n-k \ right \}+2t-2。 \ max \ left \ {k，n-k \ right \}+2t-2 $，使得$ \ mathcal {q}^{n} _ {k} $的每个点都将被完全覆盖$ t-t-1 $ times，并且每个其他点$ \ mathcal {q}^{q}^{n} $至少都会覆盖$ t $ t $ t $ t $ t $ t $ t $ t $ t $。请注意，将$ k = 0 $和$ t = 1 $，我们恢复了Alon和Füredi的广受赞誉的涵盖结果（欧洲联合杂志杂志，1993年）。使用上述超级平面家族，我们将Venkitesh的猜想（Electronic of Combinatorics，2022）反驳了用超平方$ \ MATHCAL {q}^{n} $的对称子集，并用超植物的对称子集进行反驳。为了证明上述结果，我们引入了一种称为索引复杂性的超立方体子集的复杂性的新量度，我们认为这将是独立的。 我们还研究了由上述结果证明背后的想法动机的限制性集群问题的新有趣变体。
Given a hypercube $\mathcal{Q}^{n} := \{0,1\}^{n}$ in $\mathbb{R}^{n}$ and $k \in \{0, \dots, n\}$, the $k$-th layer $\mathcal{Q}^{n}_{k}$ of $\mathcal{Q}^{n}$ denotes the set of all points in $\mathcal{Q}^{n}$ whose coordinates contain exactly $k$ many ones. For a fixed $t \in \mathbb{N}$ and $k \in \{0, \dots, n\}$, let $P \in \mathbb{R}\left[x_{1}, \dots, x_{n}\right]$ be a polynomial that has zeroes of multiplicity at least $t$ at all points of $\mathcal{Q}^{n} \setminus \mathcal{Q}^{n}_{k}$, and $P$ has zeros of multiplicity exactly $t-1$ at all points of $\mathcal{Q}^{n}_{k}$. In this short note, we show that $$deg(P) \geq \max\left\{ k, n-k\right\}+2t-2.$$Matching the above lower bound we give an explicit construction of a family of hyperplanes $H_{1}, \dots, H_{m}$ in $\mathbb{R}^{n}$, where $m = \max\left\{ k, n-k\right\}+2t-2$, such that every point of $\mathcal{Q}^{n}_{k}$ will be covered exactly $t-1$ times, and every other point of $\mathcal{Q}^{n}$ will be covered at least $t$ times. Note that putting $k = 0$ and $t=1$, we recover the much celebrated covering result of Alon and Füredi (European Journal of Combinatorics, 1993). Using the above family of hyperplanes we disprove a conjecture of Venkitesh (The Electronic Journal of Combinatorics, 2022) on exactly covering symmetric subsets of hypercube $\mathcal{Q}^{n}$ with hyperplanes. To prove the above results we have introduced a new measure of complexity of a subset of the hypercube called index complexity which we believe will be of independent interest. We also study a new interesting variant of the restricted sumset problem motivated by the ideas behind the proof of the above result.
