Skip to main content

All Questions

Tagged with
Filter by
Sorted by
Tagged with
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 ...
Nicole's user avatar
  • 97
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}$...
user avatar
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 ...
Curious_Mel's user avatar
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 ...
shahrzad haddadan's user avatar
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 ...
fdesmond's user avatar