We changed our privacy policy. Read more.
17

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-neighbor graphs", Disc. Comput. Geom. 17: 263–282, https://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf For points in any fixed higher dimension it is $\...


13

You don't need to calculate the variance to prove the concentration of tw(G(n,p)) around its expectation. If two graphs G' and G differ by one vertex then their treewidth differs by at most one. You can use the standard method, the Hoeffding-Azuma inequality applied to the vertex exposure martingale to show, for example, $\mathbb{P}( | tw(G(n,p)) - \mathbb{...


10

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 values. I'd like to add an informal sketch of how David's very elegant result can be calculated. (To be clear, I suggest selecting his answer as the "correct&...


10

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 that a random $d$-regular graph has nearly optimal spectral gap, with high probability.


7

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 largest component, the size of the second largest component, the number of leaves the component has, etc. See e.g. Aldous, David. "Brownian excursions, critical ...


6

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976). Since an ER random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.


6

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, in particular, there exists a pair $x,y$ such that a random DFA on $n/5$ states fails to separate $x,y$ with high probability.


6

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 graph fluctuates by $\pm \Theta(n)$ so the number of spanning subgraphs fluctuates by a factor of $2^{\Theta(n)}$, well away from the $(1+\epsilon)$ factor you ...


6

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 example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to ...


6

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; I am just filling in some of the details. Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $...


5

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$ queries to even find a cycle. This is because there is a $1-o(1)$ chance that all our queries of the first type return different vertices and that all of our ...


5

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 model: take $n$ vertices, and put in each edge randomly and independently with probability 1/2. This model is often denoted by $G(n,1/2)$. It is a known result ...


3

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 shown to exist by the probabilistic method. Getting efficient deterministic constructions to do the same is often challenging, interesting, and useful, but the ...


3

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 cells per key) the state of a cuckoo hash table can be described as a random graph with a vertex for each cell and an edge for each key. The ability to place all ...


3

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 all vertices), and set $V_{i+1}$ to consist of all vertices reached in this fashion; their number has a binomial distribution which can easily be calculated. ...


3

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 belief propagation. They also say the quasipolynomial-time algorithm is the fastest one known for planted $k$-clique detection for any $k=O(n^{1/2−\delta})$, ...


3

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


2

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 probability for the appearance of a subgraph $H$ is $max_{J \subseteq H} n^{-|V(J)|/E(J)|}$, which happens to be the same as $n^{-|V(H)|/E|(H)|}$ for balanced ...


2

(Answer-in-progress, according to comments.) I will look at a special case, and then discuss how it relates to the general case. The special case is $m=1$ and $V(G)=\{0\}$ with no edge. The added vertices, in order, are $1,2,\ldots,n$, starting from $1$. Let $d_{i,n}$ be the degree of vertex $i$ divided by $2n$. So $\sum_{i=0}^n d_{i,n}=1$. Let $l_i$ be ...


2

Another answer to the first question: Line graphs form another natural class of independent node degree 2. More general, claw-free graphs if they are natural enough for you.


2

Answer to your first question. Proper(Unit) Interval graphs have independent node degree of 2.


2

Concerning the third question, triangle-free graphs have $\Delta^i(G) = \Delta(G)$. From Turán's theorem, we know that the maximum number of edges on a triangle-free graph is $\big\lfloor\frac{n}{4}\big\rfloor$, and this bound is tight for the complete bipartite graph $K_{n/2,n/2}$. Hence, at least in this case, you can have a dense graph with a large ...


2

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 deterministic ones. In TCS these random structures are often random bit sequences, which play an important role in randomized algorithms. There is much interest in ...


1

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 that they are “well connected” - with high probability, most subsets of vertices have many edges across them. See here: https://www.math.cmu.edu/~af1p/...


1

[Edit: this answer does not work, see comments.] This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless. I will suppose that ...


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