A simple generalization of the Hall's condition in bipartite graphs, the Normalized Matching Property (NMP) in a graph $G(X,Y,E)$ with vertex partition $(X,Y)$ states that for any subset $S\subseteq X$, we have $\frac{|N(S)|}{|Y|}\ge\frac{|S|}{|X|}$. In this paper, we show the following results about having the Normalized Matching Property in random and pseudorandom graphs. 1. We establish $p=\frac{\log n}{k}$ as a sharp threshold for having NMP in $\mathbb{G}(k,n,p)$, which is the graph with $|X|=k,|Y|=n$ (assuming $k\le n\leq \exp(o(k))$), and in which each pair $(x,y)\in X\times Y$ is an edge independently with probability $p$. This generalizes a classic result of Erd\H{o}s-R\'enyi on the $\frac{\log n}{n}$ threshold for having a perfect matching in $\mathbb{G}(n,n,p)$. 2. We also show that a pseudorandom bipartite graph - upon deletion of a vanishingly small fraction of vertices - admits NMP, provided it is not too sparse. More precisely, a bipartite graph $G(X,Y)$, with $k=|X|\le |Y|=n$, is said to be Thomason pseudorandom (following A. Thomason (Discrete Math., 1989)) with parameters $(p,\varepsilon)$ if each $x\in X$ has degree at least $pn$ and each pair of distinct $x, x'\in X$ has at most $(1+\varepsilon)p^2n$ common neighbors. We show that for any large enough $(p,\varepsilon)$-Thomason pseudorandom graph $G(X,Y)$, there are "tiny" subsets $\mathrm{Del}_X\subset X, \ \mathrm{Del}_Y\subset Y$ such that the subgraph $G(X\setminus \mathrm{Del}_X,Y\setminus \mathrm{Del}_Y)$ has NMP, provided $p \gg\tfrac{1}{k}$. En route, we prove an "almost" vertex decomposition theorem: Every such Thomason pseudorandom graph admits - excluding a negligible portion of its vertex set - a partition of its vertex set into graphs that we call Euclidean trees. These are trees that have NMP, and which arise organically through the Euclidean GCD algorithm.


翻译:Xpartite 图形中的 Hall 状态简单一般化 { xpite 图形中的 X2, 普通化匹配属性 (NMP) 。 1. 我们以 $G(X, Y, E) 平面分配 $(X, Y) 表示, 对于任何子集的 $S\ subseqeq X$, 我们有$frac%N(S) {Y\\ ge\ frac} 平面匹配属性的以下结果 。 我们以 随机和假的图解图中显示 普通化 $(xx) 美元, 普通化的 美元 $(y) 美元, 普通化的 美元(xxx) 美元 。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
大神 一年100篇论文
CreateAMind
15+阅读 · 2018年12月31日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年8月26日
Arxiv
0+阅读 · 2021年8月26日
Arxiv
0+阅读 · 2021年8月25日
Arxiv
0+阅读 · 2021年8月25日
Arxiv
6+阅读 · 2021年6月4日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
大神 一年100篇论文
CreateAMind
15+阅读 · 2018年12月31日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员