{
  "id": "2005.08103",
  "version": "v1",
  "published": "2020-05-16T21:10:05.000Z",
  "updated": "2020-05-16T21:10:05.000Z",
  "title": "On the second eigenvalue of random bipartite biregular graphs",
  "authors": [
    "Yizhe Zhu"
  ],
  "comment": "36 pages, 3 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We consider the spectral gap of a uniformly chosen random $(d_1,d_2)$-biregular bipartite graph $G$ with $|V_1|=n, |V_2|=m$, where $d_1,d_2$ could possibly grow with $n$ and $m$. Let $A$ be the adjacency matrix of $G$. Under the assumption that $d_1\\geq d_2$ and $d_2=O(n^{2/3}),$ we show that $\\lambda_2(A)=O(\\sqrt{d_1})$ with high probability. As a corollary, combining the results from Tikhomirov and Youssef (2019), we confirm a conjecture in Cook (2017) that the second singular value of a uniform $d$-regular digraph is $O(\\sqrt{d})$ for $1\\leq d\\leq n/2$ with high probability. Assuming $d_2=O(1)$ and $d_1=O(n^2)$, we further prove that $|\\lambda_i^2(A)-d_1|=O(\\sqrt{d_1(d_2-1)})$ for all $2\\leq i\\leq n+m-1$ with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook, Goldstein, and Johnson (2018) for random $d$-regular graphs and several new switching operations we defined for random bipartite biregular graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-05-16T21:10:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random bipartite biregular graphs",
      "second eigenvalue",
      "high probability",
      "second singular value",
      "biregular bipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}