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-...
- 50.9k
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 ...
- 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 ...
- 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 ...
- 441
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 ...
- 36.9k
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 ...
- 50.9k
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, ...
- 321
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; ...
- 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$ ...
- 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 ...
- 11.3k
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 ...
- 50.9k
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 ...
- 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 ...
- 119
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 ...
- 36.9k
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 ...
- 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 ...
- 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 ...
- 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 ...
- 11.3k
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
...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible