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

From MaRDI portal
scientific article
Language Label Description Also known as
English
The normalized matching property in random and pseudorandom bipartite graphs
scientific article

    Statements

    The normalized matching property in random and pseudorandom bipartite graphs (English)
    0 references
    0 references
    0 references
    21 June 2021
    0 references
    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.
    0 references
    Thomason pseudorandom bipartite graphs
    0 references
    random bipartite graph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references