{
  "id": "2311.02070",
  "version": "v1",
  "published": "2023-11-03T17:54:27.000Z",
  "updated": "2023-11-03T17:54:27.000Z",
  "title": "Positive discrepancy, MaxCut, and eigenvalues of graphs",
  "authors": [
    "Eero Räty",
    "Benny Sudakov",
    "István Tomon"
  ],
  "comment": "29 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The positive discrepancy of a graph $G$ of edge density $p=e(G)/\\binom{v(G)}{2}$ is defined as $$\\mbox{disc}^{+}(G)=\\max_{U\\subset V(G)}e(G[U])-p\\binom{|U|}{2}.$$ In 1993, Alon proved (using the equivalent terminology of minimum bisections) that if $G$ is $d$-regular on $n$ vertices, and $d=O(n^{1/9})$, then $\\mbox{disc}^{+}(G)=\\Omega(d^{1/2}n)$. We greatly extend this by showing that if $G$ has average degree $d$, then $\\mbox{disc}^{+}(G)=\\Omega(d^{\\frac{1}{2}}n)$ if $d\\in [0,n^{\\frac{2}{3}}]$, $\\Omega(n^2/d)$ if $d\\in [n^{\\frac{2}{3}},n^{\\frac{4}{5}}]$, and $\\Omega(d^{\\frac{1}{4}}n/\\log n)$ if $d\\in \\left[n^{\\frac{4}{5}},(\\frac{1}{2}-\\varepsilon)n\\right]$. These bounds are best possible if $d\\ll n^{3/4}$, and the complete bipartite graph shows that $\\mbox{disc}^{+}(G)=\\Omega(n)$ cannot be improved if $d\\approx n/2$. Our proofs are based on semidefinite programming and linear algebraic techniques. An interesting corollary of our results is that every $d$-regular graph on $n$ vertices with ${\\frac{1}{2}+\\varepsilon\\leq \\frac{d}{n}\\leq 1-\\varepsilon}$ has a cut of size $\\frac{nd}{4}+\\Omega(n^{5/4}/\\log n)$. This is not necessarily true without the assumption of regularity, or the bounds on $d$. The positive discrepancy of regular graphs is controlled by the second eigenvalue $\\lambda_2$, as $\\mbox{disc}^{+}(G)\\leq \\frac{\\lambda_2}{2} n+d$. As a byproduct of our arguments, we present lower bounds on $\\lambda_2$ for regular graphs, extending the celebrated Alon-Boppana theorem in the dense regime.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-11-03T17:54:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "positive discrepancy",
      "regular graph",
      "linear algebraic techniques",
      "complete bipartite graph",
      "average degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}