IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Independent sets in regular graphs

  • March 16, 2017
  • 4:30 p.m.
  • LeConte 412

Abstract

A sum-free set in a group is a subset A of elements with the sum of any two elements of A falling outside A. In 1988 Andrew Granville asked "at most how many sum-free sets can a group of order n have?''

One approach is to transform the question into one about independent sets (sets of mutually non-adjacent vertices) in a graph, and ask "at most how many independent sets can a regular graph with n vertices have?'' This question is related not just to combinatorial group theory, but also coding theory, statistical physics, and even Dedekind's question on the number of monotone Boolean functions.

It took twenty years for the independent set question to be fully answered (by Yufei Zhao, at the time an undergraduate), but in the interim there were some lovely partial results, using techniques from probability, combinatorics, and information theory (entropy).

The question is still an active one, with two new proofs of the main result having been found recently, and with lots of associated open questions.

In this talk I'll review the history, sketch some of the proof methods, and mention some of my favorite open problems.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC