Slicing all Edges of an n-cube Requires n2/3 Hyperplanes
Ohad Klein
2023Year
1Citations
Abstract
Consider the n-cube graph with vertices and edges connecting vertices with Hamming distance 1. How many hyperplanes in are needed in order to dissect all edges? We show that at least are needed, which improves the previous bound of 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.
Related papers
- Towards the Erdős-Gallai Cycle Decomposition ConjectureMatija Bucic, Richard MontgomerySTOC 2023
- Hyperbolic intersection graphs and (quasi)-polynomial timeSándor Kisfaludi-BakSODA 2020 · 5 citations
- Hamiltonicity of random subgraphs of the hypercubePadraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn et al.SODA 2021 · 11 citations
- Untangling Planar Graphs and Curves by Staying PositiveSantiago Aranguri, Hsien-Chih Chang, Dylan FridmanSODA 2022 · 1 citation
- Improved Bounds for Point Selections and Halving Hyperplanes in Higher DimensionsNatan RubinSODA 2024 · 1 citation
