Consider a host hypergraph $G$ which contains a spanning structure due to minimum degree considerations. We collect three results proving that if the edges of $G$ are sampled at the appropriate rate then the spanning structure still appears with high probability in the sampled hypergraph. We prove such results for perfect matchings in hypergraphs above Dirac thresholds, for $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition, and for bounded-degree spanning trees. In each case our proof is based on constructing a spread measure and then applying recent results on the (fractional) Kahn--Kalai conjecture connecting the existence of such measures with probabilistic thresholds. For our second result we give a shorter and more general proof of a recent theorem of Allen, B\"ottcher, Corsten, Davies, Jenssen, Morris, Roberts, and Skokan which handles the $r=3$ case with different techniques. In particular, we answer a question of theirs with regards to the number of $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition.


翻译:暂无翻译

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
RoBERTa中文预训练模型:RoBERTa for Chinese
PaperWeekly
57+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年7月3日
Arxiv
0+阅读 · 2023年7月3日
Arxiv
0+阅读 · 2023年6月29日
VIP会员
相关VIP内容
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
RoBERTa中文预训练模型:RoBERTa for Chinese
PaperWeekly
57+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员