  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.
