Slicing all Edges of an n-cube Requires n2/3 Hyperplanes
Ohad Klein
2023年份
1被引次数
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
相关 Paper
- Towards the Erdős-Gallai Cycle Decomposition ConjectureMatija Bucic, Richard MontgomerySTOC 2023
- Hyperbolic intersection graphs and (quasi)-polynomial timeSándor Kisfaludi-BakSODA 2020 · 被引用 5 次
- Hamiltonicity of random subgraphs of the hypercubePadraig Condon, Alberto Espuny Díaz, António Girão, Daniela Kühn 等SODA 2021 · 被引用 11 次
- Untangling Planar Graphs and Curves by Staying PositiveSantiago Aranguri, Hsien-Chih Chang, Dylan FridmanSODA 2022 · 被引用 1 次
- Improved Bounds for Point Selections and Halving Hyperplanes in Higher DimensionsNatan RubinSODA 2024 · 被引用 1 次
