Maximal independent sets in grid-like graphs (Spring 2024)


A graph is a structure built from two sets: a base set of objects, called vertices, and a set of edges which describe connections between pairs of vertices. We can visualize a graph as a set of points (vertices) in the plane, some of which are connected by line segments (edges). In a graph G, a set S of vertices is called independent if no two vertices in S are connected by an edge. We call S a maximal independent set if there is no other independent set T in G such that T properly contains S. Note that G may have many different maximal independent sets. If G has a known structure, can we figure out how many maximal independent sets it contains?


This project will focus on understanding maximal independent sets in graphs which are related to grids. A grid graph can be visualized as a finite (rectangular) subset of the integer lattice; two points are connected by an edge if they are at unit distance. For an m by n grid graph G, there exist recurrence relations which will determine the number of maximal independent sets in G. But what if, instead of looking at a "flat" grid, we take our grid and identify two or more of its "sides"? If we think of the grid as living on a flat rectangle, imagine picking up that rectangle, folding it so that two or more of its sides are touching, and then taping the touching sides together. Depending on how we do so, the resulting graph could have a variety of geometric interpretations: it might be a "grid torus", a "grid cylinder", or a "grid Mobius strip". Can we find recurrence relations or other techniques to count the maximal independent sets in such grid-like graphs? 


For more information contact Anastasia Halfpap (ahalfpap@iastate.edu)

People:


Pre-requisites: