Lune

FOCS2023Top-tier venue

Slicing all Edges of an n-cube Requires n2/3 Hyperplanes

Ohad Klein

2023Year
1Citations

Abstract

Consider the n-cube graph with vertices {−1,1}n\{-1,1\}^{n} and edges connecting vertices with Hamming distance 1. How many hyperplanes in Rn\mathbb{R}^{n} are needed in order to dissect all edges? We show that at least Ω~(n2/3)\widetilde{\Omega}(n^{2/3}) are needed, which improves the previous bound of Ω(n0.51)\Omega(n^{0.51}) by Yehuda and Yehudayoff.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines