# Tag Info

## Hot answers tagged random-graphs

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.5k
10 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,380
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.2k
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.3k
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.5k
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, ...
• 225
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.1k
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$ ...
• 633
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 ...
• 10.8k
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.5k
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 ...
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.3k
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.2k
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,526
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 ...
• 10.8k
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 ...

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