The normalized matching property in random and pseudorandom bipartite graphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

random bipartite graph Thomason pseudorandom bipartite graphs

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05)

Abstract: 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 s u b s e t e q X

, we have

f r a c | N (S) | | Y | g e f r a c | 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 = f r a c l o g n k

as a sharp threshold for having NMP in

m a t h b b G (k, n, p)

, which is the graph with

| X | = k, | Y | = n

(assuming

k l e n l e q e x p (o (k))

), and in which each pair

(x, y) i n X i m e s Y

is an edge independently with probability

p

. This generalizes a classic result of ErdH{o}s-R'enyi on the

f r a c l o g n n

threshold for having a perfect matching in

m a t h b b 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 | l e | Y | = n

, is said to be Thomason pseudorandom (following A. Thomason (Discrete Math., 1989)) with parameters

(p, v a r e p s i l o n)

if each

x i n X

has degree at least

p n

and each pair of distinct

x, x^{'} i n X

has at most

(1 + v a r e p s i l o n) p^{2} n

common neighbors. We show that for any large enough

(p, v a r e p s i l o n)

-Thomason pseudorandom graph

G (X, Y)

, there are "tiny" subsets

m a t h r m {D e l}_{X} s u b s e t X, m a t h r m {D e l}_{Y} s u b s e t Y

such that the subgraph

G (X s e t m i n u s m a t h r m {D e l}_{X}, Y s e t m i n u s m a t h r m {D e l}_{Y})

has NMP, provided

p g g f r a c 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.

Review text

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.

Recommendations

Cites work

This page was built for publication: The normalized matching property in random and pseudorandom bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034078)