### Simulation of a stochastic evolution of bipartite graphs

(This project was completed by Assad Navi in Spring Semester 2008-2009. For possible follow-up work see project pages)

**Description:**

Bipartite graphs are graphs with two disjoint sets A and B of nodes. The set of edges E connect nodes in A with nodes in B but there are no edges within A or within B. One is interested in large graphs where the number of edges and nodes tend to infinity. The graph is called sparse if the total number of edges is of the same order as the total number of nodes, and if the number of edges is much greater than the number of nodes it is called dense. Such graphical structures commonly arise in problems of computer science, coding theory, biological networks.

**Objective:**

In this project one will study a very specific stochastic process (not explained here) which takes place in a space of bipartite graphs. The process starts with a sparse graph and has a tendency to add edges to the graph. The goal is to investigate, by simulation, the evolution of the graph and notably to what extent it becomes dense or remains sparse. If time permits analytical methods may also be investigated. Gaining insight into this specific stochastic process would be important for problems in coding theory.

**Prerequisites:**

Some familiarity with programming (and some taste for it also!).

**References:**

R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008.

**Supervision:**

Dr. Nicolas Macris (LTHC) * Email: nicolas.macris#epfl.ch * Office: INR 134 *
Tel: 38114

Dr. Olivier Lévêque (LTHI) * Email: olivier.leveque#epfl.ch * Office: INR 132 * Tel: 38112