Wolfram Cloud Document

Initialisation

In[]:=

j[i_Integer,k_Integer]:=Mod[i,k,1];sj[i_Integer,s_List]:=s[[j[i,Length@s]]];ai[0,n_Integer,s_List,p_Integer:0]:=p~Mod~n;ai[i_Integer,n_Integer,s_List,p_Integer:0]:=(ai[i-1,n,s,p]+sj[i,s])~Mod~n;t[n_Integer,s_List]:=(n*Length[s])/GCD[n,Total[s]];aiList[n_Integer,s_List,p_Integer:0]:=Table[ai[i,n,s,p],{i,0,t[n,s]}];path[vertices_List,directed_Symbol:Rule]:=directed@@@Partition[vertices,2,1];vertCoords[n_]:=Table[{Cos[(2πi)/n],Sin[(2πi)/n]},{i,n}];esf[el_,___]:={Black,Arrowheads[0.02],Arrow[el,0.05]};Options[graph]={"Union"False};animateGraph[n_Integer,s_List,p_Integer:0]:=DynamicModule[{pathList=path[aiList[n,s,p]],verts=Range[n]-1,coords=vertCoords[n]},Animate[Graph[verts,pathList[[;;i]],VertexLabelsAutomatic,VertexCoordinatescoords,EdgeShapeFunctionesf],{i,0,Length@pathList,1},AnimationRunningFalse,AnimationRepetitions1,AnimationRate1.5],SaveDefinitions->True];

Background

Out[]=

Hi all. I am eager to show you what I created using Mathematica. I do want to state, however, I am just an amateur mathematician, this was just for fun.

Intuition

I was in a lecture one day, and noticed a drawing on the back of the chair in front of me. It looked something like this:

I started doodling it myself, trying different numbers of vertices, and different amounts to “step”.
If the original has

n=5

points, and

step=2

(Because it wraps around every

vertex), we can call it

C(5,{2})

. The reason for the list will become clear later.

Here is

C(5,{1})

And

C(6,{2})

I soon realised the same could be done with graphs:

In[]:=

Grid[Table[Labeled[graph[n,s],Style[Row[{"C(",n,",",s,")"}],20,Bold],Top],{n,5,7},{s,{{1},{2},{3}}}],FrameAll]

Out[]=

We can visualise the process of drawing these same graphs:

In[]:=

Grid[Table[Labeled[animateGraph[n,s],Style[Row[{"C(",n,",",s,")"}],25,Bold],Top],{n,5,7},{s,{{1},{2},{3}}}]]

Formulation

There is a simple formula describing which is the next vertex to move to, given the current vertex, and the step to take:

Example

Step Sets

This works when we have the same step size at each iteration.
But we can also have changing step sizes:

We start by defining the Step Set, an ordered list of integers.

It behaves as we would like.

Examples

Generalisation

In general then, we can now formulate the next vertex to step to for any step set:

Examples

Steps till Completion

You may have noticed that the animations stop when the process no longer adds any new edges to the graph.

But the full animation shows that there are still more edges to add.

And so, the full condition I have been using to decide when the process is complete consists of two checks:

Although I haven’t been able to prove it, the following formula seems to be equivalent:

Informally testing for equivalence:

If anyone knows how to prove this, I would really appreciate your input.

For now, we have a neat way of finding the number of steps it takes for these graphs to complete.

Proof: All Graphs Complete

It is possible to show that all graphs fulfill the criteria after a finite number of steps.

Consider the process playing out.

I use the fact that:

Now:

Therefore the first condition is met.

Constructing Graphs

A useful function for generating random graphs quickly:

Create an EdgeList given an aiList:

This function helps to keep the vertices in order when laying them out along the circumference of the circle. (CircularEmbedding doesn’t always preserve ordering of the vertices, in favour of a layout with fewer edge crossings instead).

Arrow Styles:

Graph generating function:

Create a more aesthetic graph:

Animate

Completed Graph

This method makes for a blurry completedGraph:

This method is just better, I think:

GraphInfo

This shows the some different information about a particular graph. Including the original, artGraph, completedGraph, and the no self-loop versions of each:

CirculantGraph

While researching this, I came across CirculantGraph, which sort of does a similar thing, but not quite. I thought I’d mention this.

Conclusion

Thank you for taking the time to read over this. I would really appreciate any input :)