“Intellectual growth should commence at birth and cease only at death.” [Albert Einstein]
“Intellectual growth should commence at birth and cease only at death.” . As an academic, the importance of keeping current on the modern developments in Mathematics is self evident. Often times, the best researchers are the best teachers. Research and publications also promotes the good name of the College and benefits the society as a whole. This statement will serve to demonstrate how I, James Hammer, have demonstrated these important qualities through research in the past and will serve as a road map for where I would like to take my research in the future.
Participating in conferences helps keep an academic abreast of the current trends in mathematics. Attending big conferences in Combinatorics and Graph Theory such as the Southeastern International Conference on Combinatorics, Graph Theory, and Computing (SEICCGC) both helps keep the academic up to date as well as provides an opportunity to collaborate with other academics in his/her field. The SEICCGC has been a wonderful avenue for me personally to present research on Edge Regular graphs, Diameter Regular graphs, Inverse Graph Domination, and Factor Pair Latin Squares.
This statement will be presented on two fronts: Graph Theory, and Design Theory (sometimes called Design of Experiments). Within each of these topics, I will delve into the research I have done in the past within each topic. Afterwards, I will briefly outline where I plan on going within each of my fields of interest.
A graph $G = (V,E)$ is a set $V$ of vertices (sometimes called nodes) along with a set $E$ of edges which link two vertices together. Two vertices that have an edge between them are said to be adjacent. We say that a vertex $v$ has degree $d$ if there are $d$ vertices that are adjacent to $v$. Moreover, a graph is said to be regular if every vertex has the same degree. A graph can represent many things in the real world. For example, one can think of data centers within a network as vertices and cables between two data centers as edges.
An Edge Regular graph is a regular graph where every two adjacent vertices have exactly $\lambda$ vertices that are adjacent to both. These graphs are a superset of a larger family of graphs that are of interest called Strongly Regular graphs. Strongly Regular graphs are regular graphs where every pair of adjacent vertices have $\lambda$ vertices that are adjacent to both (often called common neighbors) and every pair of non-adjacent vertices (i.e. vertices that do not have an edge between them) have exactly $\mu$ vertices that are adjacent to both. At the SEICCGC, we mainly concerned ourselves with Edge Regular graphs with $\lambda = 1$ and $\lambda = 2$. When $\lambda = 2$, we narrowed our interest a bit to Regular Clique Assemblies. Regular Clique Assemblies is a regular graph $G$ satisfying two conditions: (1) every maximal complete graph (often called a clique) in $G$ is also maximum and (2) each edge in $G$ belongs to exactly one maximum complete graph. These graphs give rise to a set of Edge Regular graphs with the property that the closed neighborhood (that is the graph formed by taking the vertex of interest and all of it’s neighbors) is a set of disjoint complete graphs. In doing this, we classified all of the Edge Regular graphs with $\lambda = 1$ as well as came up with an infinite family of graphs for higher $\lambda$ values. This is a topic that has been close to my heart for a long time; however, I do believe that we have exhausted what we can do with it for the moment. There is a pending publication on this topic in the works.
Diameter Regular Graphs
Diameter Regular graphs are the other side of the Edge Regular graphs. That is to say that a Diameter Regular graph is a regular graph where every two non-adjacent vertices have exactly $\mu$ vertices that are adjacent to both. A colleague of mine and I have some conjectures on the table regarding the classification of when $\mu \leq 3$; however, these have not been completely fleshed out. This is a topic of ongoing research for me.
Inverse Graph Domination
In Inverse Graph Domination, we are concerned with picking the least number of vertices, called a minimum dominating set, so that each vertex in the graph is either in the dominating set or is adjacent to at least one vertex in the minimum dominating set. There are many different kinds of graph domination; however, a few colleagues and I have focused mainly on the inverse domination conjecture formally posed by Hedetniemi (the conjecture was originally posed as a theorem with a false proof provided by Kulli and Sigarkanti). The inverse domination number is the least number of vertices out of all minimum dominating sets which dominates the graph while forbidding vertices from the minimum dominating set of interest. The inverse dominating conjecture states that the minimum inverse dominating set is no bigger than the biggest set of vertices that are mutually non-adjacent, called an independent set of vertices. This problem in particularly is useful in modeling social networks on the Internet as well as determining how to distribute data among data centers (as you want to have a backup if the primary nodes go off-line).
In the same vein as the inverse domination conjecture of Hedetniemi, it has been shown that the only graphs that can possibly be a counterexample are DI-pathological graphs. DI-pathological graphs are graphs in which every maximal independent set of vertices intersects every minimum dominating set of vertices. These graphs are interesting in either as they could provide counterexamples to Hedetniemi’s conjecture if one exists; so, it is natural to try to bound the size of these graphs in some way. Along with two of my contemporaries, we have found a bound on the size of these graphs from below (it is not hard to show that these graphs can be arbitrarily large) using the size of the minimum dominating set. Of course, what do we mean by ‘the size of the graph’? There are two ways to take this statement. Either we primarily minimize the number of vertices and then secondarily minimize the number of edges, or vice versa. We have found lower bounds in both regards in a paper that has been sent to the Journal of Combinatorial Mathematics and Combinatorial Computing.
Two colleagues of mine and I have been trying to generalize results in traditional domination theory to cover a different type of domination, which doesn’t seem to have been heavily explored. A distance $m$-dominating set of a graph $G$ is a set of vertices where every vertex is either in the distance $m$-dominating set or it is within a distance $m$ of a vertex in the distance $m$-dominating set. We have results for a number of particular families of graphs; however, we are looking to generalize as many of the classic results from domination theory as we can. This is an on-going process.
I am also quite fond of Design Theory. Before going into what I do, perhaps it would behoove us to explore what we are interested in when it comes to Design Theory, or the Design of Experiments as it is sometimes called. Design Theory is a fairly young field; so, there are naturally many ways to approach it. A design can be thought of as taking a set of size $n$ and placing each symbol into $r$ sets (called blocks) of a certain size $k$ so that every pair of elements occur in exactly $\lambda$ blocks together. This is a very natural definition; however, designs can also be looked at as decomposing a graph (usually a complete graph) into edge disjoint copies of a certain subgraph of interest. The most common type of these decompositions are called Steiner Triple Systems where we are interested in decomposing $K_n$ (the complete graph on $n$ vertices) into edge disjoint copies of $K_3$ (that is the complete graph on three vertices). Most notably, the Fano Plane is a Steiner Triple System of order $7$. Both ways of course have their merit, and both are interesting to me; however, what I mainly deal with are Latin Squares. A Latin Square is an $n \times n$ grid whose every row and every column has every symbol $1$ through $n$ exactly once. Latin squares are used for many things in regards to designing experiments where there are a number of nuisance variables that cannot be combined or need to be kept separate.
Latin Squares are an $n \times n$ grid where each row and each column see each symbol $1$ through $n$ exactly once. We call this property of seeing each symbol $1$ through $n$ exactly once being latin. Many additional quantification (such as idempotent and commutative) can be put on latin squares to make constructions for many designs such as Steiner Triple Systems. Possibly the most renowned examples of adding a quantification to a latin square is a Sudoku puzzle. A Sudoku puzzle is a latin square with the added condition that each $3 \times 3$ block is also latin.
In my dissertation, I am concerned with generalizing the ever popular Sudoku puzzle. If $n = a \times b$, we say that $a \times b$ is an ordered factor pair of $n$. We call an $n \times n$ grid a factor pair latin square of order $n$ (denoted FPLS$(n)$) if one can tile the $n \times n$ grid with rectangles whose size is determined by the ordered factor pairs of order $n$. The goal, of course, is to find necessary and sufficient conditions for when there exists a factor pair latin square. In my dissertation, I have found some necessary conditions; however, they are seldom not sufficient. This seems to be a tough problem that I plan on working on for a very long time. I find this problem incredibly interesting and spend a lot of my time thinking about different ways to attack it. Moreover, applications of these types of designs are something that interest me. Preliminary work has been done in finding applications; however, there is much to still be done.
In addition to having several negative results as to when factor pair latin squares do not exist, I also have several results saying when they do exist. Among these constructions is a construction for orders which are twice a prime number. I would like to be able to generalize this to three times a prime number as well as the product of prime numbers. In addition, I would like to prove some asymptotic results on these designs in the near future. I have conjectured that asymptotically, factor pair latin squares only exist for prime orders, powers of primes, and the product of primes.
Since factor pair latin squares do not always exists, we can define a quasi-factor pair latin square as the maximum number of ordered factor pairs one can take such that there exists an $n \times n$ grid where the tiling with every ordered factor pair in the natural sense is latin. Very little is known about these squares. In the near future, I would like to nail down when these exist.
In the recent months, two colleagues of mine and I have been looking into embedding path designs in other designs; however, this research is still in it’s infancy. We have done some preliminary work as to when a path design of length $k$ can be extended to a bigger path design, but we are far from our goal.
Although I have been concentrating mostly on Graph Theory (namely structural graph theory) and Design Theory as of late, there are other interests of mine when it comes to research. Discrete Geometry and Convexity has always been an interest of mine. I would love to find someone to collaborate with to work on some problems in that as well. The projects listed above as well as any other project that might peak my interest as I continue to attend conferences are things which I intend to research in collaboration with others or on my own in the times to come. Thank you for all of your time and consideration!
- M. Jackson, D.D. Ignatavicius, and B. Case, Conversations in critical thinking and clinical judgment, Jones and Bartlett Publishers, 2005.