## Speaker:

## Speaker Link:

## Institution:

## Time:

## Host:

## Location:

An independent set of size k in a finite undirected graph is a set of k vertices of the graph, no two of which are connected by an edge. The structure of independent sets of size k as k varies is of interest in probability, statistical physics, combinatorics, and computer science. In 1987, Alavi, Malde, Schwenk and Erdos conjectured that the number of independent sets of size k in a tree is a unimodal sequence (this number goes up and then it goes down), and this problem is still open. A variation on this question is: do the number of independent sets of size k form a unimodal sequence for Erdos-Renyi random graphs, or random trees? By adapting an argument of Coja-Oghlan and Efthymiou, we show unimodality for Erdos-Renyi random graphs, random bipartite graphs and random regular graphs (with high probability as the number of vertices in the graph goes to infinity, when the expected degree of a single vertex is large). The case of random trees remains open, as we can only show weak partial results there.