Project description: Imagine you are in charge of security for an art gallery. Your plan is to post a security guard at certain pieces of art to surveil the gallery. Each guard can see other pieces of art, but only the ones in their line of sight, and they can see the piece of art where they are posted. You want to post guards so that each piece of art is seen by at least two guards, in case one guard is away from their post. But the guards' salaries are expensive, so you want to use the smallest number of guards possible. How to do this?

This problem can be translated to a question in graph theory. Represent each piece of art as a vertex (i.e., a node), and represent each line of sight as an edge. Then the question asks how to identify a special set of vertices such that every vertex is "seen" by at least two vertex in the special set, including possibly itself. The special sets are called double dominating sets. (Technically, if V is the vertex set for the graph G, then a subset D of V is a double dominating set provided that for all v in V the closed neighborhood N[v] contains at least two points of D.) Finding all the double dominating sets for a given graph is a hard problem, even for trees (NP-complete).

This project looks at double domination through an algebraic lens. The double domination ideal of a graph G is an ideal D(G) in a polynomial ring defined as an intersection of ideals defined by the double dominating sets of G. We are interested in understanding algebraic properties of D(G) in terms of graph theoretic properties of G. For instance, how does the shape of G determine the generators of D(G)?

The project will begin with a guided review of certain aspects of abstract algebra (polynomial rings, ideals, generators of ideals, etc.). Then students will learn about monomial ideals in polynomial rings and some of their connections with graph theory. Along the way, students will also learn how to use the powerful computer algebra program Macaulay2 to investigate these constructions. Throughout, students will investigate double domination sets and how they connect with monomial ideals.

Prerequisites: a course in abstract algebra; background in graph theory would be an advantage.

Project faculty:

• Graduate Project Leader: Michael Cowen
  Email: mcowen at clemson.edu (change "at" to "@")
  Office hours: TBA
  Bio: Michael joined Clemson as a PhD student in 2016. He earned his BS from North Carolina State University and his MS from University of North Carolina - Wilmington. His research is in combinatorial commutative algebra and its interactions with electrical engineering.
• Project leader: Prof. Sean Sather-Wagstaff
  Email: ssather at clemson.edu (change "at" to "@")
  Office hours: TBA
  Bio: Sean joined Clemson University in 2015, coming from Fargo, ND. He earned his AB degree from UC Berkeley and his MS and PhD degrees from the University of Utah. His research is in combinatorial and homological commutative algebra. He has supervised 14 undergraduate research projects, three of which resulted in peer reviewed research publications.