Victor Falgas-Ravry; Finding large full subgraphs

Tuesday, December 8, 2015, 4:00 pm
GUG 204

Victor Falgas-Ravry, University of Washington .
Finding large full subgraphs

Abstract: A graph is a pair G=(V,E), where V is a set of vertices and E is a set of pairs from V forming the edges of G. Suppose G is a graph on n vertices in which a proportion p of all possible edges are present, for some fixed p: 0 \leq p \leq 1. We call a subgraph H of G on m vertices \emph{full} if every vertex in H is connected by an edge to at least p(m-1) other vertices in H. In other words, a subgraph H is full if its minimum degree is at least the expected average degree for an m-vertex subgraph. If we think of the graph G as representing a network, then its full subgraphs correspond to `cliquey’ communities within that network.

In this talk I shall consider the question of how large a full subgraph I can be guaranteed to find. Improving on earlier work of Erd\H{o}s, \L uczak and Spencer, I shall give a simple algorithm for finding full subgraphs of order at least n^{2/3}, and show that this order is best possible for infinitely many values of p.

Joint work with Klas Markstr\”om and Jacques Verstra\”ete.