The normalized matching property in random and pseudorandom bipartite graphs (Q2034078)

Summary: A bipartite graph \(G(X,Y,E)\) with vertex partition \((X,Y)\) is said to have the Normalized Matching Property (NMP) if for any subset \(S\subseteq X\) we have \(\frac{|N(S)|}{|Y|}\geqslant\frac{|S|}{|X|} \). In this paper, we prove the following results about the Normalized Matching Property. \par 1.) The random bipartite graph \(\mathbb{G}(k,n,p)\) with \(|X|=k,|Y|=n\), and \(k\leqslant n<\exp(k)\), and each pair \((x,y)\in X\times Y\) being an edge in \(\mathbb{G}\) independently with probability \(p\) has \(p=\frac{\log n}{k}\) as the threshold for NMP. This generalizes a classic result of \textit{P. Erdős} and \textit{A. Rényi} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5, 17--61 (1960; Zbl 0103.16301)] on the \(\frac{\log n}{n}\) threshold for the existence of a perfect matching in \(\mathbb{G}(n,n,p)\). \par 2.) A bipartite graph \(G(X,Y)\), with \(k=|X|\leqslant |Y|=n\), is said to be Thomason pseudorandom (following \textit{A. Thomason} [Discrete Math. 75, No. 1--3, 381--386 (1989; Zbl 0721.05051)]) with parameters \((p,\varepsilon)\) if every \(x\in X\) has degree at least \(pn\) and every pair of distinct \(x, x'\in X\) have at most \((1+\varepsilon)p^2n\) common neighbours. We show that Thomason pseudorandom graphs have the following property: Given \(\varepsilon>0\) and \(n\geqslant k\gg 0\), there exist functions \(f,g\) with \(f(x), g(x)\to 0\) as \(x\to 0\), and sets \(\text{Del}_X\subset X, \text{Del}_Y\subset Y\) with \(|\text{Del}_X|\leqslant f(\varepsilon)k, |\text{Del}_Y|\leqslant g(\varepsilon)n\) such that \(G(X\setminus \text{Del}_X,Y\setminus \text{Del}_Y)\) has NMP. Enroute, we prove an `almost' vertex decomposition theorem: Every Thomason pseudorandom bipartite graph \(G(X,Y)\) admits -- except for a negligible portion of its vertex set -- a partition of its vertex set into graphs that are spanned by trees that have NMP, and which arise organically through the Euclidean GCD algorithm.