Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with random-graphs
Search options answers only
not deleted
user 7691
The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.
1
vote
Accepted
how to compute the probability that a random graph has two components?
There are several alternative derivations. It seems that in the derivation you are following, the first component is defined as the component of the node 1, so if this component has size $k$, then onl …
- 14.2k
3
votes
Accepted
Collecting proofs of the birth of the giant component
Nachmias, Asaf, and Yuval Peres. "The critical random graph, with martingales." Israel Journal of Mathematics 176, no. 1 (2010): 29-41.
https://arxiv.org/abs/math/0512201
- 14.2k
5
votes
Accepted
What is the exact definition of a sharp transition?
The parameters $p_n$ are not arbitrary numerical parameters. They represent the expectation of one binary variable in a product space. Changing them additively is very different from changing the powe …
- 14.2k
1
vote
Accepted
Reference request - random regular graphs vs random graphs w/ degree sequence
Simple random walk (and non-backtracking walk) on random regular graphs exhibit the cutoff phenomenon [1]. The extension to graphs with degree sequences came later; see [2] for nonbacktracking walks a …
- 14.2k
1
vote
Accepted
Random Optimization on Graphs: Minimum Cut
As noted in the answer by Puck Rombach, the problem is NP-hard for fixed weights. However the OP asked about random IID weights. In this case finding the mincut or maxcut is still not known to be in P …
- 14.2k
1
vote
What is the expected distance between the sides of a random subgraph of the grid?
See Aizenman, M.; Burchard, A. Hölder regularity and dimension bounds for random curves. Duke Math. J. 99 (1999), no. 3, 419--453.
https://arxiv.org/abs/math/9801027
- 14.2k
1
vote
How to use probability to find a matching in a family of graphs?
See Goel, A., Kapralov, M. and Khanna, S., 2013. Perfect Matchings in O(n\logn) Time in Regular Bipartite Graphs. SIAM Journal on Computing, 42(3), pp.1392-1404
and the references therein.
https:/ …
- 14.2k
0
votes
Which infinite random graphs with percolation threshold $p_c=0$ are transient?
One general method that yields transience of infinite clusters is the existence of paths with exponential intersection tails: See
Benjamini, Itai, Robin Pemantle, and Yuval Peres. "Unpredictable paths …
- 14.2k
4
votes
Accepted
Non-backtracking random walk in regular (finite) graphs
Indeed, understanding non-backtracking walks is often the key to analyzing the simple random walk and random graphs. See e.g. [1], [2] and [3], [4].
Basic properties of the non-backtracking walk are …
- 14.2k