Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Paul Erdős and Rényi's 1959 paper On Random Graphs I, they describe the number of edges in a random graph by the function

(1) Nc = [1/2 * nlogn + cn]

where n is the number of nodes in the graph, c is "an arbitrary fixed real number" and [x] denotes the integer part of x. They go on to use a number of graphs of the form G(n, Nc), where G(n, Nc) denotes a random graph with n nodes and Nc edges.

Nc appears to be an arbitrary (?) function to return a number of edges based on some c and n, but I don't understand how c is selected or why the function is relevant. When the authors discuss graphs of the type G(n, Nc), is there any special property besides the graph just having some arbitrary number of edges? I.e, could I replace Nc with some function for a random number of edges between 0 and the maximum possible edges for the graph with the same results?

share|cite|improve this question
Note that characters with and without diacritical marks rarely represent similar phonemes. "Erdos" is about as badly misspelled as "Erdis", though it may look more similar. If you can't produce a character with a diacritical mark on your keyboard, you can copy it from the Web. – joriki May 10 '12 at 17:56
In that case, Rényi has a diacritical mark too. – anonymous May 10 '12 at 18:05
Added, thank you for pointing that out. – pleiotrope May 10 '12 at 18:53
up vote 1 down vote accepted

$N_c$ is a more-or-less arbitrary function, but its choice defines the class of random graphs being studied. So you could replace it with a different function, but it would change the correct statements of all their theorems. Note that the statements of the theorems depend on $c$, so you don't have to worry about choosing a specific $c$.

share|cite|improve this answer
I see, thank you. However, in the proof of the Lemma, they state that for some graph G(n, $N_c$) with r connected components and $l_i$ points on each component (i = 1,2,...,r), that the sum of all the possible edge choices for each component is ≥ $N_c$. (This is better described in the paper on p 293). However, for a graph G(5, 10) (with $c$=1.15) having two connected components of 2 and 3 points each, that sum is 4 while $N_c$ is 10. Should I take that relation as a condition bounding c, or does it fall from a property of the graph that I'm missing? – pleiotrope May 10 '12 at 18:50
A graph $G(5,10)$ can't have two connected components of 2 and 3 points each -- to be a $G(5,10)$ means you have 10 edges, and (as you've noted) such a graph would have at most 4 edges. – Micah May 10 '12 at 19:06
Oh, of course. Thank you. – pleiotrope May 10 '12 at 19:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.