Dividing Your Neighbors: not to conquer, just to count

Hello!  I’m Joshua Wagner ’19, a chemistry and mathematics major at Gettysburg College.  Like any good mathematics major, I like to count things, and that’s good because I just spent the summer counting arithmetical structures on graphs with my research advisor, Dr. Glass.

Before we dive into my research topic, I would like to answer an interesting research question: “where is math research done?”  Well, all a researcher needs is a reliable laptop, a few pens (various colors help), a ream of paper (to scribble on before throwing away), some patience, chalk, and a blackboard.  So you can see that on days where the blackboard and chalk aren’t necessary, math research can be done anywhere.

Research can take place on a beautiful patio,

at a National Military Park,

or in Glatfelter Hall surrounded by professors and other students.  Where is the best place to conduct math research?  Gettysburg College, hands down.

Pivoting back to my summer research, to understand what it means to count arithmetical structures on graphs, we need understand two basic definitions.

First, what is a graph?  A graph is a group of nodes that are connected by edges. See the picture below:

Second, what is an arithmetical structure?  We can assign positive integers to each node on a graph, and if each node divides the sum of its neighbors and the greatest common divisor is one, we will call that assignment of integers an arithmetical structure. See the picture below:

There are much more complicated and rigorous ways to define an arithmetical structure using matrices, vectors, and complicated mathematical jargon, but this definition will suffice.

We already knew from a mathematician (Lorenzini) that any graph must have a finite number of valid arithmetical structures.  We also already have an algorithm for finding any arithmetical structures on a line of nodes, which we call a path, or a circle of nodes, which we call a cycle.

Now that you know what an arithmetical structure is, let’s say a few things about arithmetical structures on simple paths and cycles.  As we know, the first node on the end of a path must divide its neighbor.  We know that this second node must divide the third plus the first.  We can then see that the first node divides the third, and we can deduce that the first node must divide every other node evenly too.  (Try this with some scratch paper if you need convincing.)

Why does this matter?  Well, if the greatest common denominator of the values is 1, then the value of the first node must be 1 because it divides all the other nodes.  Similarly, we can see that if two nodes next to each other are equal, then those two nodes must evenly divide all the other nodes, so again we can see that if two neighboring nodes are equal, then they must be 1’s.

So, now we know that any path or cycle either has a local maximum, or is labeled with all ones.  In addition, we know that any local maximum must be the sum of its neighbors and that maximum can be removed to form another valid arithmetical structure.  In this example, 2 is a local maximum, so we can “smooth” the structure by removing it:

We can also do the inverse operation and add in a local maximum to create a more complex arithmetical structure:

From these facts we can make the lemma that any arithmetical structure on a path or cycle can be smoothed down to form a path or a cycle of all ones.  We can then also say that any arithmetical structure can be formed by adding in local maxima (like how we added the node with a 4 in the example above).

My research has been focused on counting how many arithmetical structures can be assigned to a given graph with more complex features.  Like, what would happen if two nodes were connected twice?

This complicates matters, as you can get a graph with a local maximum that is not the sum of its neighbors:

The number of “smooth structures,” or number of structures without a local maximum that is the sum of its neighbors is nontrivial to count.  It’s actually rather difficult to do and even harder to generalize.

How is math research performed?  I spent the first several weeks of the summer writing programs to find all of the arithmetical structures for smaller individual graphs.  From this data, we were able to distinguish patterns emerging.

Continuing through the summer, I spent less time programming, and more time writing proofs of why those patterns existed.  For instance, we noticed that one vertex next to a doubled edge seemed to always divide the sum of its neighbors twice (like 11 divides 2(9)+4 twice in the labeled graph above), so we proved that must happen.

We kept proving small things called lemmas until we were able to count all structures on more general graphs and form theorems.  For instance:

We were hoping that these theorems would piece together nicely and we could generalize our results to any path or cycle with a doubled edge.  We are still looking for a way to do this.

I presented our current findings in a 15 minute talk to professors and students from around the country on July 27th at MathFest, the Mathematical Association of America’s yearly meeting.  While in Chicago, we plan to learn some interesting math from leading mathematicians (and also have some deep dish pizza)!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s