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) 美元 。