Full Subgraphs

Thursday, September 11, 2014 - 11:30am - 12:20pm
Keller 3-180
Jacques Verstraete (University of California, San Diego)
Let G be a graph of density p on n vertices. Erdös, Luczak and Spencer defined a subgraph H of G to be full if H has m vertices and every vertex of H has degree at least p(m - 1) in H. Let f(G) denote the largest number of vertices in a full subgraph of G and let fp(n) denote the smallest value of f(G) over all graphs G of density p with n vertices. Erdös, Luczak and Spencer proved √2n ≤ f0:5(n) ≤ 2n2/3 (log n)1/3 and also showed f(G) = (n) when G is the random graph Gn,p.

In this talk, I will show that fp(n) ≥ min {p1/2n + 1; 0:1n2/3} for all p ∈ (0; 1), and for p close to the elements of {1/2, 2/3, 3/4; ::::} we show that fp(n) = O(n2/3), which determines the order of magnitude of fp(n) for infinitely many p. We also discuss the value of f(G) when G is a random or pseudorandom graph, as well as full subgraphs of regular graphs.

The methods include spectral techniques and discrepancy, together with some com-
binatorial algorithms to find full subgraphs. Our study was in part originally motivated by questions on bootstrap percolation in graphs. In conclusion, a number of interesting open questions will be presented.

Joint work with Victor Falgas-Ravry and Klas Markstrom during the program on
graphs, hypergraphs and computing at Institut Mittag-Leffler in winter 2014.
MSC Code: