Videos

Full Subgraphs

Presenter
September 11, 2014
Keywords:
  • DNA sequences
MSC:
  • 92D20
Abstract
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.