2

In my recent study about random graphs, I learned that there are numerous models:Bernoulli, Binomial, Watts-Strogatz, Barabasi-Albert, exponential models...etc. Now I have an idea about random graphs, what I have a problem with are "non random graphs", I can't picture them. Can anybody give me an example of a "non random graphs"?

Toney Shields
  • 195
  • Can you give an example of a non-random number? – D Poole Aug 15 '16 at 19:03
  • @DPoole You mean variable? any chosen number is non random – Toney Shields Aug 15 '16 at 21:31
  • 1
    What does it mean for something to be non-random? And specifically what do you mean by non-random graphs? – D Poole Aug 16 '16 at 18:07
  • @DPoole, I see your point, but I still have some calrifications to do.Now, for something to be non random means, that it takes only one value (if we're talking about variables), a random variable can take a finite or infinite number of values. Concerning graphs, we all know what a random graph, let's consider a graph with 10 vertices that represent 10 friends, each person is told to write a letter to their best friend. Now, is this a random graph? – Toney Shields Aug 16 '16 at 18:18
  • 1
    It depends. If I say that a number $X$ is at least 4 but at most 7, does that mean that $X$ is a random variable? or just that I haven't given the information necessary to uniquely determine $X$? It all depends on context. If you want to describe some entity as random, you must define an underlying probability distribution. For instance, the definition of $G(n,p)$ is that it is a random graph with vertex set $V={1, 2, \ldots, n}$, where for any graph $G_0$ on $V$, $P(G(n,p) = G_0) = p^{e(G_0)} (1-p)^{{n \choose 2}-e(G_0)}$ ($e(G_0)=$ number of edges of $G_0$). – D Poole Aug 17 '16 at 12:59
  • @DPoole I understand, so for an entity to be random, it has to have a defined underlying distribution, if it didn't, then it's not random. For your question about $X$, I don't see how it depends on context, if $X$ is at least 4 but at most 7, doesn't this mean that $X$ is random?! – Toney Shields Aug 17 '16 at 13:34
  • 1
    Random does not mean unknown. Colloquially, the terms "random" and "arbitrary" are often interchanged. This is not the case in formal mathematics. You need an underlying probability distribution for random variables. If $X$ here is a random variable, then how is it distributed? Is $X$ uniformly distributed on [4,7] OR Poisson($\pi$)-distributed conditioned on being in [4,7] OR $4+\frac{3}{1+e^{\mathcal{N}(0,1)}}$-distributed OR... – D Poole Aug 17 '16 at 15:42
  • I see, so here, $X$ is arbitrary, not random, to be random, $X$ must have a distribution that uniquely determine it. – Toney Shields Aug 17 '16 at 15:56
  • 1
    Correct. (I would say "describe" instead of "determine" though) – D Poole Aug 18 '16 at 14:13

1 Answers1

0

There are millions of such graphs, just naming a few:

  • Complete Graphs,
  • Petersen Graph,
  • Queen Graphs,
  • Grötzsch Graph,
  • Mycielski Graphs,
  • ...

You can find many graphs here: Wolfram Math World

Xin Cheng
  • 111