Improved Bounds for the Expected Number of k-Sets
Improved Bounds for the Expected Number of k-Sets
复制标题
改进 k 集预期数量的界限
DOI：
10.1007/s00454-022-00469-7
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Rademacher, Luis
中科院分区：
文献类型：
--
作者：
Leroux, Brett;Rademacher, Luis
给定一个有限点集，AK-Set of S是能被超平面严格分离的Size的一个子集。类似地，在一般位置上的点集的AK-面是SIZED的子集，使得Haskpoint从一侧跨越的超平面。对于概率分布Pon，我们研究了来自P的n个随机点样本的K-面的期望数目。当P是一种分布，使得每条直线的度量都为0时，我们证明了这一点。我们的论点是基于Bárány和Steiger的技巧。我们研究了如何使用多项式分割定理的连续版本来改进这一界。这就引出了一个关于代数曲线的交点和一组点的k边图的问题。我们还研究了值域集合由平面上某一严格凸体的所有平移组成的集合系统的k-集合问题的一种变形。其动机是为了证明Bárány和Steiger的技术对于集合系统的自然家族是紧的。对于任何这样的集合系统，我们确定了紧到对数因子的K-集合的期望个数的界。
Given a finite set of points, ak-setofSis a subsetof sizekwhich can be strictly separated fromby a hyperplane. Similarly, ak-facetof a point setSin general position is a subsetof sizedsuch that the hyperplane spanned byhaskpoints fromSon one side. For a probability distributionPon, we study, the expected number ofk-facets of a sample ofnrandom points fromP. WhenPis a distribution onsuch that the measure of every line is 0, we show that. Our argument is based on a technique by Bárány and Steiger. We study how it may be possible to improve this bound using the continuous version of the polynomial partitioning theorem. This motivates a question concerning the points of intersection of an algebraic curve and thek-edge graph of a set of points. We also study a variation on thek-set problem for the set system whose set of ranges consists of all translations of some strictly convex body in the plane. The motivation is to show that the technique by Bárány and Steiger is tight for a natural family of set systems. For any such set system, we determine bounds for the expected number ofk-sets which are tight up to logarithmic factors.
登录
查看更多内容
DOI：
10.1090/ulect/064
发表时间：
2016-07
期刊：
--
影响因子：
--
作者：
L. Guth
通讯作者：
L. Guth
凸体正同位族的横截数和VC维数
影响因子：
0.8
作者：
M. Naszódi;Steven Taschuk
通讯作者：
Steven Taschuk
平面 k 集和相关问题的改进界限
影响因子：
0.8
作者：
T. Dey
通讯作者：
T. Dey
改进了平面 k 集和 k 水平的界限
DOI：
--
发表时间：
1997
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
T. Dey
通讯作者：
T. Dey
当代数学一种改进的、简单的许多减半边的构造
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
Gabriel Nivasch
通讯作者：
Gabriel Nivasch