English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A simple generalization of the Hall's condition in bipartite graphs, theNormalized Matching Property (NMP) in a graph $G(X,Y,E)$ with vertex partition$(X,Y)$ states that for any subset $S\subseteq X$, we have$\frac{|N(S)|}{|Y|}\ge\frac{|S|}{|X|}$. In this paper, we show the followingresults about having the Normalized Matching Property in random andpseudorandom graphs.  1. We establish $p=\frac{\log n}{k}$ as a sharp threshold for having NMP in$\mathbb{G}(k,n,p)$, which is the graph with $|X|=k,|Y|=n$ (assuming $k\len\leq \exp(o(k))$), and in which each pair $(x,y)\in X\times Y$ is an edgeindependently with probability $p$. This generalizes a classic result ofErd\H{o}s-R\'enyi on the $\frac{\log n}{n}$ threshold for having a perfectmatching in $\mathbb{G}(n,n,p)$.  2. We also show that a pseudorandom bipartite graph - upon deletion of avanishingly small fraction of vertices - admits NMP, provided it is not toosparse. More precisely, a bipartite graph $G(X,Y)$, with $k=|X|\le |Y|=n$, issaid to be Thomason pseudorandom (following A. Thomason (Discrete Math., 1989))with parameters $(p,\varepsilon)$ if each $x\in X$ has degree at least $pn$ andeach pair of distinct $x, x'\in X$ has at most $(1+\varepsilon)p^2n$ commonneighbors. We show that for any large enough $(p,\varepsilon)$-Thomasonpseudorandom graph $G(X,Y)$, there are "tiny" subsets $\mathrm{Del}_X\subset X,\ \mathrm{Del}_Y\subset Y$ such that the subgraph $G(X\setminus\mathrm{Del}_X,Y\setminus \mathrm{Del}_Y)$ has NMP, provided $p\gg\tfrac{1}{k}$. En route, we prove an "almost" vertex decomposition theorem:Every such Thomason pseudorandom graph admits - excluding a negligible portionof its vertex set - a partition of its vertex set into graphs that we callEuclidean trees. These are trees that have NMP, and which arise organicallythrough the Euclidean GCD algorithm.

The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs