Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs

Details Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs

2012-03-07

arxiv.org/abs/1203.1506v1

Computer Science

Discrete Mathematics

Scientific paper

Consider a random bipartite multigraph $G$ with $n$ left nodes and $m \geq n \geq 2$ right nodes. Each left node $x$ has $d_x \geq 1$ random right neighbors. The average left degree $\Delta$ is fixed, $\Delta \geq 2$. We ask whether for the probability that $G$ has a left-perfect matching it is advantageous not to fix $d_x$ for each left node $x$ but rather choose it at random according to some (cleverly chosen) distribution. We show the following, provided that the degrees of the left nodes are independent: If $\Delta$ is an integer then it is optimal to use a fixed degree of $\Delta$ for all left nodes. If $\Delta$ is non-integral then an optimal degree-distribution has the property that each left node $x$ has two possible degrees, $\floor{\Delta}$ and $\ceil{\Delta}$, with probability $p_x$ and $1-p_x$, respectively, where $p_x$ is from the closed interval $[0,1]$ and the average over all $p_x$ equals $\ceil{\Delta}-\Delta$. Furthermore, if $n=c\cdot m$ and $\Delta>2$ is constant, then each distribution of the left degrees that meets the conditions above determines the same threshold $c^*(\Delta)$ that has the following property as $n$ goes to infinity: If $cc^*(\Delta)$ then there exists no left-perfect matching with high probability. The threshold $c^*(\Delta)$ is the same as the known threshold for offline $k$-ary cuckoo hashing for integral or non-integral $k=\Delta$.

Affiliated with

Also associated with

No associations

Rating

Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394367