Category Archives for Random graphs
Lecture 8. Games on random graphs (2)
The last part of this lecture will take place on Monday, May 6 at 3 PM in Bendheim Classroom 103. The full scribe notes for this lecture will be posted sometime after that date.
Lecture 7. Games on random graphs (1)
The next two lectures by Rene Carmona will be on games on random graphs. Many thanks to Patrick Rebeschini for scribing these lectures! In the following we discuss some results from the paper “Connectivity and equilibrium in random games” by … Continue reading
Giant component: final remarks
The past three lectures were devoted to the giant component theorem: Theorem Let be the connected component of that contains . If , then in probability. If , then in probability, for some . If , then in distribution. We … Continue reading
Lecture 6. Giant component (3)
Let us begin with a brief recap from the previous lecture. We consider the Erdös-Rényi random graph in the supercritical case . Recall that denotes the connected component of the graph that contains the vertex . Our goal is to … Continue reading
Lecture 5. Giant component (2)
Consider the Erdös-Rényi graph model , and denote as usual by the connected component of the graph that contains the vertex . In the last lecture, we focused mostly on the subcritical case , where we showed that . Today … Continue reading
Lecture 4. Giant component (1)
Consider the Erdös-Rényi graph model . In previous lectures, we focused on the “high complexity regime”, i.e., as goes to infinity, is fixed. We discussed topics such as clique numbers and chromatic numbers. From now on, we shall consider the … Continue reading
Lecture 3. Chromatic number
Let be set of integers that represent colors. A vertex coloring of a graph is an assignment of a color to each vertex . Furthermore a vertex coloring is said to be proper if for all . The chromatic number of a graph is the … Continue reading
Lecture 2. Clique number
In this lecture all logs are in base . We will prove the following. Theorem For the centered and normalized clique number That is, as , the clique number of the Erdös-Rényi graph is . Proof: The proof is divided into two … Continue reading
Lecture 1. Introduction
There are many interesting models of random graphs, and there a lot of different questions that can be asked about them. In this seminar we will only have the time cover a few of the most classical results. The goal … Continue reading
Spring 2013: Random graphs
Complex graphs and networks are ubiquitous throughout science and engineering, and possess beautiful mathematical properties. The goal of these informal lectures is to provide an introduction to some of the most basic results in the theory of (Erdos-Renyi) random graphs … Continue reading
