Point-hyperplane Incidence Geometry and the Log-rank Conjecture
Point-hyperplane Incidence Geometry and the Log-rank Conjecture
复制标题
DOI：
10.1145/3543684
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Noah G. Singer;M. Sudan
中科院分区：
文献类型：
--
作者：
Noah G. Singer;M. Sudan
我们从点hyperplane事件的几何学的角度研究对数秩的概念。大型（即2 – Polylog（D））的发动机部分，其中包含很大一部分，并包含在大量的超级平面中。用于此类配置的点hyperplane事件图具有较大的完整两部分子图。尺寸2-Polylog（D），其中每列是恒定的。从平行K分区的边界到平行（K-1）的边界。我们在没有结构性假设的点（即存在分区的存在）中重新研究了点杂化的几何形状。在任何D维构型中，密度ω（ε2D/d）的子图具有起入率密度ε的质量，质量上与先前的结果相匹配，这是使用复杂的几何技术证明的。其完整的两分子图呈指数级，其入射密度为ω（1/√D）。带有发病率密度ω（1）和完整的两部分子图密度（√D）的布尔材料的产物，并在我们的框架的替代语言中对此特殊情况提出了几个问题。阐明了改善洛夫特（√等级（f））的困难[20]，尤其是对数秩的猜想。平行3分期配置的二分子尺寸尺寸范围，这些配置击败了我们的通用范围，以进行非结构化配置。
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝd that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2–polylog(d)) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank-d matrix containing at most O(1) distinct entries in each column contains a submatrix of fractional size 2–polylog(d), in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel k-partitions to bounds for parallel (k-1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density Ω (ε 2d/d) in any d-dimensional configuration with incidence density ε, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir [2], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is Ω (1/√ d). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density Ω (1) and complete bipartite subgraph density 2-Ω (√ d), and pose several questions for this special case in the alternative language of extremal set combinatorics. Our framework and results may help shed light on the difficulty of improving Lovett’s Õ(√ rank(f)) bound [20] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations.