Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a bidirectional edge to each of the vertices it selects. My question is, what is the expected diameter of the bipartite graph generated this way? Thank you!
3
-
$\begingroup$ Is there a particular range of $K$ you care about? E.g. $K = \sqrt{n}$? $\endgroup$– mathworker21Commented Dec 22, 2023 at 3:28
-
$\begingroup$ What I focus on is the case where $K$ is a constant, such as $K=5$. Maybe my expression was not clear, sorry. $\endgroup$– Zijian WangCommented Dec 22, 2023 at 4:49
-
$\begingroup$ The graph is disconnected with nonzero probability, so the expected diameter is infinite. This silly thing apart, I believe that it is known that it is an expander graph with probability going to $1$ with $n$, so the typical diameter is of order $\log(n)$. $\endgroup$– Mikael de la SalleCommented Dec 22, 2023 at 14:47
Add a comment
|