# Tag Info

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-...
• 51.1k
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.5k

### 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 ...
• 10.9k
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 ...
• 451

### 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 ...
• 37.8k

### 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 ...
• 51.1k
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
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; ...
• 12.3k

### 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$ ...
• 653
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.4k

### 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 ...
• 51.1k
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,170

### 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 ...

### 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 ...
• 37.8k
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

### 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,616