The normalized matching property in random and pseudorandom bipartite graphs

Niranjan Balachandran¹ ; Deepanshu Kush²

¹Indian Institute of Technology Bombay
²University of Toronto

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

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|}\geq\frac{|S|}{|X|}$. In this paper, we prove the following results about the Normalized Matching Property. The random bipartite graph $\mathbb{G}(k,n,p)$ with $|X|=k,|Y|=n$, and $k\leq 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 Erdős-Rényi on the $\frac{\log n}{n}$ threshold for the existence of a perfect matching in $\mathbb{G}(n,n,p)$. 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 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\geq k\gg 0$, there exist functions $f,g$ with $f(x), g(x)\to 0$ as $x\to 0$, and sets $\mathrm{Del}_X\subset X, \ \mathrm{Del}_Y\subset Y$ with $|\mathrm{Del}_X|\leq f(\varepsilon)k,\ |\mathrm{Del}_Y|\leq g(\varepsilon)n$ such that $G(X\setminus \mathrm{Del}_X,Y\setminus \mathrm{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. Addendum added September 21, 2021.

Détail

DOI : 10.37236/9148

Classification : 05C80, 05C70, 06A07, 60C05
Mots-clés : Thomason pseudorandom bipartite graphs, random bipartite graph