Paper Info
Title
The Normalized Matching Property In Random And Pseudorandom Bipartite Graphs
Abstract
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 subset of X, we have vertical bar N(S)vertical bar/vertical bar Y vertical bar >= vertical bar S vertical bar/vertical bar X vertical bar. In this paper, we prove the following results about the Normalized Matching Property.1. The random bipartite graph G(k, n, p) with vertical bar X vertical bar = k, vertical bar Y vertical bar = n, and k <= n < exp(o(k)), and each pair (x, y) is an element of X x Y being an edge in G independently with probability p has p = log n/k as the threshold for NMP. This generalizes a classic result of Erdos-Renyi on the log n/n threshold for the existence of a perfect matching in G(n, n, p).2. A bipartite graph G(X, Y), with k = vertical bar X vertical bar <= vertical bar Y vertical bar = n, is said to be Thomason pseudorandom (following A. Thomason (Discrete Math., 1989)) with parameters (p, epsilon) if every x is an element of X has degree at least pn and every pair of distinct x, x' is an element of X has at most (1 + epsilon)p(2)n common neighbors. We show that Thomason pseudorandom graphs satisfy the following: Given epsilon > 0 and n >= k both sufficiently large, there exist functions f, g with f (x), g (x) -> 0 as x -> 0, and sets Del(X) subset of X, Del(Y) subset of Y with vertical bar Del(X)vertical bar <= f (epsilon)k, vertical bar Del(Y)vertical bar <= g(epsilon)n such that G(X\Del(X), Y\Del(Y)) has NMP. En route, we prove an "almost" vertex decomposition theorem: Every Thomason pseudorandom bipartite graph G(X, Y) admits - excluding 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.
Year
DOI
Venue
2021
10.37236/9148
ELECTRONIC JOURNAL OF COMBINATORICS
DocType
Volume
Issue
Journal
28
2
ISSN
Citations 
PageRank 
1077-8926
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Niranjan Balachandran100.34
Deepanshu Kush201.35