Adam Blumenthal - Research

Domination Problems

Chess is played on an 8 by 8 board, with several different pieces with unique movements. The queen is a piece that can move any distance on the board horizontally, vertically, or diagonally. We think about placing queens on a chess board. If a queen could move to a square, we call the square "threatened." If a queen could move on top of another queen, we will call the queens "attacking."

In 1862 de Jaenisch asked the following question: What is the most (or least) number of non-attacking queens you can place on a chessboard to threaten every empty square?

Give it a try (click a square to place or remove a queen):

You might find that there are multiple solutions, both for the maximization and minimization problem! One could also ask how many different solutions there are. In math terms, the maximization problem is asking for a largest independent set in a graph and the minimization problem is asking for a smallest independent dominating set.

Independent domination continues to be studied for its relation to broadcasting with interference like radio networks.

Domination is analogous to threatening every square of a graph. There have been many variations of dominating set problems because of their applications, but a few that I have worked on include independent domination, split domination, and secure domination.

I am currently particularly interested in domination parameters in directed graphs.

Extremal Combinatorics

Extremal combinatorics is often traced back to work of Turán, who determined the structure of the graph that maximizes the number edges while forbidding a complete graph of a certain size.

Extremal combinatorics gives us a link that allows us to use knowledge of small substructures to determine global structure.

One problem that I have worked on in extremal combinatorics concerns graph decompositions. A decomposition of a graph is a family of sets of edges of the graph such that each edge appears exactly once. A group that I participated in at GRWC determined which graphs have the highest minimum triangle and edge decomposition weight.

Additionally, I have worked on a problem much more similar to Turán, to determine which graphs contain the most copies of the net graph.

What Next?

Some fields that I am very interested in getting more involved include math education, computational complexity, and combinatorial optimization.

As a math educator, I have continually tried to expand my teaching repertoire. I have been involved in traditional and active classrooms. Recently, I have become more involved with Team Based Learning particularly in helping teach calculus to non-math majors.

Finding the smallest dominating set is a well known NP-complete problem, as such, much of my research has been influenced by complexity theory. I would like to develop a more intricate tool set to work with computational complexity.

Many of the questions that I work on in extremal combinatorics can be phrased as a combinatorial optimization question. As such, it is important that I continue to learn more about combinatorial optimization techniques to push my research to its limit.