IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Independent Sets in Hypergraphs

  • March 4, 2016
  • 2:30 p.m.
  • LeConte 312

Abstract

Given a graph $G$ an independent set is a subset of the vertices no two of which are adjacent. There has been interest recently in maximizing the number of independent sets in graphs. For example, the Kahn-Zhao theorem gives an upper bound on the number of independent sets in a $d$-regular graph.

We will extend the results about independent sets in graphs to hypergraphs. A hypergraph is a generalization of a graph in which an edge can have any size. In an $r$-uniform hypergraph each edge has size $r$ (so graphs are $2$-uniform hypergraphs). An $s$-independent set is a subset of vertices containing fewer than $s$ vertices from each edge. In this talk we will discuss $1$-independent sets and $r$ independent sets in $r$-uniform hypergraphs and $2$-independent sets in $3$-uniform hypergraphs.

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