{
  "id": "1511.00113",
  "version": "v1",
  "published": "2015-10-31T11:30:52.000Z",
  "updated": "2015-10-31T11:30:52.000Z",
  "title": "Adjacency matrices of random digraphs: singularity and anti-concentration",
  "authors": [
    "Alexander E. Litvak",
    "Anna Lytova",
    "Konstantin Tikhomirov",
    "Nicole Tomczak-Jaegermann",
    "Pierre Youssef"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Let ${\\mathcal D}_{n,d}$ be the set of all $d$-regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\\ln^{3} d/\\sqrt{d}$ for $C\\leq d\\leq cn/\\ln^2 n$, where $c, C$ are positive absolute constants. To this end, we establish a few properties of $d$-regular directed graphs. One of them, a Littlewood-Offord type anti-concentration property, is of independent interest. Let $J$ be a subset of vertices of $G$ with $|J|\\approx n/d$. Let $\\delta _i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $\\delta = (\\delta_1, \\delta_2, ..., \\delta_n)\\in \\{0, 1\\}^n$. Then for every $v\\in\\{0,1\\}^n$ the probability that $\\delta=v$ is exponentially small. This property holds even if a part of the graph is \"frozen\".",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-10-31T11:30:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60B20",
      "05C80",
      "15B52",
      "46B06"
    ],
    "keywords": [
      "adjacency matrix",
      "random digraphs",
      "regular directed graphs",
      "singularity",
      "littlewood-offord type anti-concentration property"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151100113L"
    }
  }
}