All Questions
Tagged with random-graphs erdos
5 questions
1
vote
0
answers
147
views
Inequalities in the classic proof of perfect matching in Erdős–Rényi graph
I am checking the classic paper by Erdős and Rényi, "On the existence of a factor of degree one of a connected random graph" with the link here. I am curious about the computation of the ...
3
votes
1
answer
333
views
Probabilistic bound to the number of edge disjoint triangles in a random graph
Let $G$ be a random graph with $n$ vertices, and let $\delta(G)$ be the maximum number of triangles in $G$.
Question. How to prove the bound $$P(\delta(G)) \leq m - t \sqrt{f(m)}) \leq 2e^{-t^2 / 4}$...
0
votes
1
answer
1k
views
Random graphs- Erdos and Renyi 1959 paper
Please refer to this link. It is Erdos and Renyi's first paper on Random Graphs (1959). I am trying to work through it.
I'm struggling with equations (16), (17) and (21).
(16)
I'm not sure why ...
2
votes
0
answers
220
views
mixing time of random walks on dense Erdos Renyi graphs
Is there anything known about the mixing time of a simple random walk on an Erdos-Renyi graph with parameter $\langle n,d \rangle$ where $d=n^a (0<a<1 )$. I know about Reed et al and Benjamini ...
2
votes
1
answer
727
views
When an Erdos-Renyi graph is locally tree like?
I would like to know when an ER graph is locally treeing like. In this post.
I found this comment:
I think $N$ is $\log2|V|$, or something like that, in that paper.
They consider binary vectors ...