2024/11/14 by David Ellis, Ellis, David, Maria‐Romina Ivan +3
Computer Science · #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2411.09445
How small can a set of vertices in the n-dimensional hypercube Qn be if it meets every copy of Qd? The asymptotic density of such a set (for d fixed and n large) is denoted by γd. It is easy to see that γd ≤ 1/(d+1), and it is known that γd=1/(d+1) for d ≤ 2, but it was recently shown that γd < 1/(d+1) for d ≥ 8. In this paper we show that the latter phenomenon also holds for d=7 and d=6.