# 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 Rebeschini for scribing these lectures! In the following we discuss some results from the paper “Connectivity and equilibrium in random games” by Daskalakis, … 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