0
votes
0answers
29 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
0
votes
0answers
124 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
1
vote
1answer
154 views

How to generate random graph?

I am new to Graph theory. Please correct me if I am wrong. How do I define the probability of linking nodes to create a random bidirectional network (Erdos Renyi network) with network density of ...
1
vote
0answers
116 views

Connectivity of random graphs

I am studying a problem that I can model as a random graph. In the basic model, I have a set of vertices that I connect by adding edges. At each stage, I randomly select two vertices and add an edge ...
2
votes
1answer
260 views

Number of sinks/sources in a a random directed acyclic graph

Given an arbitrary graph $G = (V,E)$, such that each vertex v is given randomly a unique integer identifier (call it v). An edge (u,v) is directed from u to v if u > v. This creates a DAG. A ...
1
vote
0answers
87 views

Tricky computations in graph theory proof

Let $0 < p < 1$ be a constant, and set $b = 1/p$. Let $0 < \epsilon < 1/2$. Given a natural number $r \ge 2$, let $n_r$ be the maximal natural number for which $\binom{n_r}{r} ...
4
votes
0answers
79 views

Completeness of random walks in multiple dimensions?

I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than ...
1
vote
0answers
50 views

An optimization involving (random) graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
1
vote
1answer
132 views

What is “edge percolation”?

What is the meaning of the term "edge percolation"? Context is graph theory, specifically, random graphs. In general, what does "percolation" mean in the context of random graphs? Thanks.
4
votes
0answers
616 views

Random graph connectivity, and the existence of isolated vertices

Here $G_{n,p}$ represents the Erdős-Rényi random graph model, where the graph has order $n$ and each edge is added independently with probability $p$. I am faced with proving the following claim: ...
5
votes
1answer
70 views

Interpretation of a simple probabilistic term in a calculation

I'm reading through my notes on the evolution of random graphs and have come unstuck trying to figure out the meaning of a probabilistic term which appears, and was hoping you could help - it's not ...