For a graph whose vertex set is a finite set of points in $\mathbb R^d$, consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any $ n $ red and $ n $ blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Also, we prove that (iii) for any even set of points in $ \mathbb R^d $, there exists a perfect matching that is an open Tverberg graph; (iv) for any $ n $ red and $ n $ blue points in $ \mathbb R^d $, there exists a perfect red-blue matching that is a Tverberg graph.


翻译:对于其顶点设置为 $mathbb R ⁇ d$ 的有限点数的图形, 请考虑其边缘引导直径的封闭( 开放) 球球。 如果这些闭( 开放) 球相互交错, 则该图称为( 开放) Tverberg 图形。 我们使用将线减半的想法, 显示 (一) 对于飞机上的任何有限点数, 存在一个汉密尔顿周期, 即 Tverberg 图形 ;(二) 对于飞机上的任何 n 美元 红色 和 n 美元 蓝点, 都存在完美的红蓝色匹配, 即 Tverberg 图形 。 另外, 我们还证明 (三) 对于任何以 $\ mathbbr R ⁇ d $ 的甚至一组点数, 都存在一个完美的匹配; (四) 对于任何 n 美元 红和 n 美元 蓝点, 以 $\ mathb R ⁇ d$ 的, 存在一个完美的红蓝色匹配, 即 Tverberg 图形 。

0
下载
关闭预览

相关内容

【ICLR2021】常识人工智能,77页ppt
专知会员服务
75+阅读 · 2021年5月11日
专知会员服务
27+阅读 · 2021年5月2日
专知会员服务
84+阅读 · 2020年12月5日
【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
155+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
人工智能 | 国际会议信息6条
Call4Papers
4+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【泡泡一分钟】一种实用且高效的多视图匹配方法
泡泡机器人SLAM
6+阅读 · 2018年11月19日
计算机视觉的不同任务
专知
5+阅读 · 2018年8月27日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年12月3日
Query Embedding on Hyper-relational Knowledge Graphs
Arxiv
4+阅读 · 2021年6月17日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Hyperbolic Graph Attention Network
Arxiv
6+阅读 · 2019年12月6日
Arxiv
6+阅读 · 2019年11月14日
Arxiv
4+阅读 · 2019年2月8日
VIP会员
相关VIP内容
【ICLR2021】常识人工智能,77页ppt
专知会员服务
75+阅读 · 2021年5月11日
专知会员服务
27+阅读 · 2021年5月2日
专知会员服务
84+阅读 · 2020年12月5日
【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
155+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
人工智能 | 国际会议信息6条
Call4Papers
4+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【泡泡一分钟】一种实用且高效的多视图匹配方法
泡泡机器人SLAM
6+阅读 · 2018年11月19日
计算机视觉的不同任务
专知
5+阅读 · 2018年8月27日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年12月3日
Query Embedding on Hyper-relational Knowledge Graphs
Arxiv
4+阅读 · 2021年6月17日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Hyperbolic Graph Attention Network
Arxiv
6+阅读 · 2019年12月6日
Arxiv
6+阅读 · 2019年11月14日
Arxiv
4+阅读 · 2019年2月8日
Top
微信扫码咨询专知VIP会员