##### Department of Mathematics,

University of California San Diego

****************************

### Math 288 - Probability Seminar

## Steven Heilman

#### USC

## Independent Sets in Random Graphs and Random Trees

##### Abstract:

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.

Host: Jason Schweinsberg

### February 27, 2020

### 10:00 AM

### AP&M 6402

****************************