## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, June 15, 2004, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Dieter Mitsche

## Reconstructing a Large Clique in a Random Graph

In 1998 Alon, Krivelevich and Sudakov showed how to find a clique of size k=c √n in a random graph G(n,1/2,k), which is generated in the following way: add each edge with probability 1/2 independently, then choose a random subset Q of size k and force it to be a clique by joining each pair of vertices of Q with an edge.

This talk generalizes the problem of reconstructing a clique in the G(n,p,q,k) model: choose a random subset Q of size k; each edge incident to two vertices of Q is included with probability p, each other edge is included with probability q, where p > q.

Information for students and suggested topics for student talks