2024/10/27 by Noga Alon, Maria Axenovich, Alon, Noga +3
Engineering · Decision Sciences · #Optimization and Packing Problems #Process Optimization and Integration #Risk and Safety Analysis
paper · pdf · doi:10.48550/arxiv.2410.20498
Let d ≥ 1 and s ≤ 2d be nonnegative integers. For a subset A of vertices of the hypercube Qn and n≥ d, let λ(n,d,s,A) denote the fraction of subcubes Qd of Qn that contain exactly s vertices of A. Let λ(n,d,s) denote the maximum possible value of λ(n,d,s,A) as A ranges over all subsets of vertices of Qn, and let λ(d,s) denote the limit of this quantity as n tends to infinity. We prove several lower and upper bounds on λ(d,s), showing that for all admissible values of d and s it is larger than 0.28. We also show that the values of s=s(d) such that λ(d,s)=1 are exactly \0,2d-1,2d\. In addition we prove that if 0