# Tag Info

## Hot answers tagged random-graphs

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

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

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