Covering almost all the layers of the hypercube with multiplicities

DOI10.1016/J.DISC.2023.113397MaRDI QIDQ6041856zbMATH OpenFDO

Authors Arijit Ghosh, Chandrima Kayal, Soumi Nandi

Publication date 15 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.13752

zbMATH Keywords

coveringhypercubenullstellensatzpolynomial method

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Abstract: Given a hypercube $mathcal{Q}^n:={0,1}^n$ in $mathbb{R}^n$ and $kin0,dots,n$, the $k$-th layer $mathcal{Q}_k^n$ of $mathcal{Q}^n$ denotes the set of all points in $mathcal{Q}^n$ whose coordinates contain exactly $k$ many ones. For a fixed $tinmathbbN$ and $kin0,dots,n$, let $PinmathbbRleft[x_1,dots,x_{n}ight]$ be a polynomial that has zeroes of multiplicity at least $t$ at all points of $mathcal{Q}^{n}setminusmathcal{Q}_k^n$, and $P$ has zeros of multiplicity exactly $t-1$ at all points of $mathcal{Q}_k^n$. In this short note, we show that ${\displaystyle }$deg(P) geq maxleft{ k, n-k ight}+2t-2.${\displaystyle }$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=maxleftk,n-kight+2t-2$, such that every point of $mathcal{Q}_k^n$ 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"uredi (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.

Recommendations

• On almost \(k\)-covers of hypercubes
• Exact hyperplane covers for subsets of the hypercube
• Covering the cube by affine hyperplanes
• Covering all but the low weight vertices of the unit cube
• Essential positive covers of the cube

Cites work

• A generalized combinatorial nullstellensatz for multisets
• Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
• Alon's nullstellensatz for multisets
• Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
• Chevalley's theorem with restricted variables
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Covering the cube by affine hyperplanes
• Démonstration d'une hypothèse de M. Artin
• Exact hyperplane covers for subsets of the hypercube
• Explicit exponential lower bounds for exact hyperplane covers
• Extensions to the method of multiplicities, with applications to Kakeya sets and mergers
• On almost \(k\)-covers of hypercubes
• On zeros of a polynomial in a finite grid
• Partitions of vector spaces
• Polynomials that vanish to high order on most of the hypercube
• Punctured combinatorial Nullstellensätze
• Some extensions of Alon's Nullstellensatz
• The polynomial method and restricted sums of congruence classes
• Warning's second theorem with restricted variables

Cited in

(7)

• Covering the cube by affine hyperplanes
• Covering all but the low weight vertices of the unit cube
• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Explicit exponential lower bounds for exact hyperplane covers
• On almost \(k\)-covers of hypercubes
• scientific article; zbMATH DE number 4112541 (Why is no real title available?)
• About almost covering subsets of the hypercube

This page was built for publication: Covering almost all the layers of the hypercube with multiplicities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041856)