Category Archives for Random graphs

Lectures 7/8. Games on random graphs

The following two lectures by Rene Carmona are on games on random graphs. Many thanks to Patrick Rebes­chini for scrib­ing these lectures! In the following we discuss some results from the paper “Connectivity and equilibrium in random games” by Daskalakis, … Continue reading

01. May 2013 by Ramon van Handel
Categories: Random graphs | Leave a comment

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

28. April 2013 by Ramon van Handel
Categories: Random graphs | Leave a comment

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

27. April 2013 by Ramon van Handel
Categories: Random graphs | Leave a comment

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

17. April 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

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

06. April 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

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

14. March 2013 by Philippe
Categories: Random graphs | Comments Off

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

07. March 2013 by Sebastien Bubeck
Categories: Random graphs | Comments Off

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

01. March 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

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

25. February 2013 by Ramon van Handel
Categories: Random graphs | Comments Off

css.php