17 votes
Accepted

Number of connected components of a random nearest neighbor graph?

For $n$ uniformly random points in a unit square the number of components is $$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$ See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-...
David Eppstein's user avatar
11 votes

Number of connected components of a random nearest neighbor graph?

EDIT 2: Made explicit the underlying non-asymptotic bounds in the calculation. EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the ...
Neal Young's user avatar
  • 9,595
10 votes
Accepted

Connectivity of a random regular graph of degree $d$

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed ...
Yuval Filmus's user avatar
  • 14.3k
7 votes
Accepted

Which graph parameters are NOT concentrated on random graphs?

Many parameters of the largest connected component are not concentrated for $G(n,p)$ if $p=1/n$ and more generally if $p$ is in the critical window. Examples are the diameter and the size of the ...
Yuval Peres's user avatar
6 votes

Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For ...
Joshua Grochow's user avatar
6 votes

Which graph parameters are NOT concentrated on random graphs?

Failure to concentrate happens for some counting ($\#\mathsf{P}$) properties, and maybe for many of them. A simple example is the number of spanning subgraphs ($2^m$). The number of edges of a random ...
David Eppstein's user avatar
6 votes
Accepted

Separating words with random DFAs

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, ...
mathworker21's user avatar
6 votes
Accepted

How long does it take to find a short cycle in a random graph?

No, you can't beat $\Theta(\sqrt{n})$ queries. I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms. This is all anticipated in exfret's answer; ...
D.W.'s user avatar
  • 11.7k
5 votes

How long does it take to find a short cycle in a random graph?

Let’s assume we can only query the $i$th edge of a given vertex’s adjacency list (which I am assuming is not sorted) or whether two given vertices are adjacent. In this case it should take $\sqrt n$ ...
exfret's user avatar
  • 643
5 votes
Accepted

Relationship between Random Graph Theory and TCS

There are interesting open algorithmic problems in random graphs, which might even lead to nontrivial results about complexity classes. For the sake of an example, consider the simplest random graph ...
Andras Farago's user avatar
3 votes

Relationship between Random Graph Theory and TCS

One very natural application of random graph theory in computer science comes from the analysis of cuckoo hashing. In the most basic form of cuckoo hashing (with one key per cell and two possible ...
David Eppstein's user avatar
3 votes
Accepted

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

Feldman et al. [1] give several references to methods for e.g., finding cliques of size $k = \Omega(\sqrt{n})$, including spectral methods, SDPs, combinatorial methods, nuclear norm minimization, and ...
Juho's user avatar
  • 3,160
3 votes

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

To answer the first part of your question, a conjecture in Karp'76 states that there is no efficient algorithm to find cliques of size $(1+ \epsilon)\log(n)$ for $G(n, 1/2)$. This conjecture is still ...
Ainesh Bakshi's user avatar
3 votes

Relationship between Random Graph Theory and TCS

Phase transitions in NP-complete (and other) problems. See this nice recent survey/intro by Cris Moore: https://arxiv.org/abs/1702.00467. Many constructions in TCS (eg expanders come to mind) can be ...
Joshua Grochow's user avatar
3 votes
Accepted

Probability of two vertices being connected by some path in a random directed graph

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of ...
Yuval Filmus's user avatar
  • 14.3k
2 votes
Accepted

Probability of a $k$-path in a random graph

When $k$ is a constant, the threshold probability for a path of length $k$ is $p \sim \dfrac{1}{n^{1+1/k}}$. The same is true for any tree with $k$ edges. The general result is that the threshold ...
Aravind's user avatar
  • 321
2 votes

Relationship between Random Graph Theory and TCS

One famous connection of random graphs to TCS is network connectivity. Random graphs such as the Erdős–Rényi model - https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model have the property ...
Avi Tal's user avatar
  • 1,596
2 votes

Relationship between Random Graph Theory and TCS

Another interesting connection between random graphs and TCS can be found in the concept of de-randomization. Generally, de-randomization means the approximation of truly random structures by ...
Andras Farago's user avatar
1 vote

Spectral sparsification of graphs with negative edge weights

I personally do not work in spectral graph theory. I write this from a linear algebra perspective. This definition seems to apply naturally to graphs which are permitted to have negative edge weights ...
BrownieInMotion's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible