Independent sets in Hypergraphs

Summer Research Interniship (2014), Faculty of Science, University of Manitoba, MB, Canada.

This project is about a class of combinatorial structures called "graphs"; these graphs are not what one might imagine (like charts, or parabolas), but instead are structures more akin to networks -- there are points (called vertices) and connections (called edges) between these points. Graphs are used to model many concepts, including traffic flow, spread of disease, computer networks, and molecules, to name a few; however, this project does not consider any such applications and concentrates only on theoretical formulations. Many famous statements in combinatorics can be expressed in terms of independent sets. A major component of this project is identifying the number and size of independent sets in certain classes of graphs or hypergraphs. One recent thrust in related research is to find as few as possible "sparse sets" (sets that do not induce too many edges) in a graph so that these sparse sets contain all independent sets.

Supervisor: Dr. David S. Gunderson