On a set that detects the convergence of a sum of reciprocals using relative density: A proposal for an indicator set and a proof of its nonexistence.

Natural Density

Suppose we take a subset A = \{a_1, a_2, \dots \} of the natural numbers \mathbb{N} = \{1, 2, \dots \} and look at the sum of the reciprocals of its elements:

\sum\limits_{n = 1}^{\infty} \frac{1}{a_n}.

One question we can ask here is: for which subsets A \subset \mathbb{N} does this sum converge? Though there are many routes one can take to try to answer this question, we look towards density.

The natural density of A \subset \mathbb{N} is defined to be

\delta(A) = \lim\limits_{n \rightarrow \infty} \frac{|A \cap [1,n]|}{n}.

We think of this essentially as the probability of choosing an element of A from the natural numbers. Let’s do some examples!

  • We certainly have \delta(\mathbb{N}) = 1.
  • If A \subset B, then \delta(A) \leq \delta(B).
  • Let k\mathbb{N} = \{k, 2k, 3k, \dots \}. There are \lfloor n/k\rfloor elements of k\mathbb{N} less than n, so

\delta(k\mathbb{N}) = \lim\limits_{n \rightarrow \infty} \frac{\lfloor n/k\rfloor}{n} = \lim\limits_{n \rightarrow \infty} \frac{1}{k} = \frac{1}{k}.

  • Let A = \{1, 4, 9, \dots \}. Then we need to know how many squares there are less than n. If k^2 < n, then k < \sqrt{n}, so there are \lfloor \sqrt{n}\rfloor squares less than n. Therefore

\delta(A) = \lim\limits_{n \rightarrow \infty} \frac{\lfloor \sqrt{n}\rfloor}{n} = \lim\limits_{n \rightarrow \infty} \frac{1}{\sqrt{n}} = 0.

Notice that \sum_{n = 1}^{\infty} \frac{1}{n} (being the harmonic series) diverges and \delta(\mathbb{N}) \neq 0. Also,\sum_{n = 1}^{\infty} \frac{1}{n^2} (being the Riemann zeta function evaluated at 2) converges to \pi^2/6 and we just showed \delta(\{1, 4, 9, \dots \}) = 0. Perhaps this is our connection!

(Wishful-Thinking “Theorem”) For any A \in \mathbb{N},

\delta(A) = 0 ~~\text{if and only if}~~\sum_{n = 1}^{\infty} \frac{1}{a_n} < \infty.

As the name of the above “theorem” hints at, this statement is not true. Our counterexample is a prevalent character: the primes. Recall the prime number theorem, which states that the number of primes less than some number n is asymptotically n/\log(n). Then the natural density of the primes P = \{2, 3, 5, \dots \} must be

\delta(P) =\lim\limits_{n \rightarrow \infty}\frac{n/\log(n)}{n} =\lim\limits_{n \rightarrow \infty}\frac{1}{\log(n)} = 0.

But in 1737, Euler proved that\sum_{p \in P} \frac{1}{p} diverges! So our wishful-thinking theorem is not true. We call a set A \subset \mathbb{N} bad if it doesn’t satisfying our wishful-thinking theorem.

Relative Density

To me, this failure means that the natural numbers are too “large” to detect all sets whose sum of reciprocals diverge. So what if we shrank it? For A,B \subset \mathbb{N}, let’s define the relative density of A in B to be

\rho(A,B) = \lim\limits_{n \rightarrow \infty} \frac{|A \cap B \cap [1,n]|}{|B \cap [1,n]|}.

Like the natural density, we think of the relative density of A in B to be the probability that we choose an element of A out of B. In fact, notice that

\delta(A) = \rho(A, \mathbb{N}).

As such, we get similar properties as the natural density, with some interesting twists!

  1. If A \subset B, then \rho(B,A) = 1.
  2. If A \cap B = \emptyset, then \rho(A,B) = \rho(B,A) = 0.
  3. If A \subset B \subset C, then \rho(A,C) = \rho(A,B)\rho(B,C).
  4. If A \subset B and A \subset C, then \rho(A,B)\rho(B,C) = \rho(A,C)\rho(C,B).
  5. Most generally, given any A, B, C \subset \mathbb{N}, we have

\rho(A,B)\rho(B,C)\rho(C,A) = \rho(A,C)\rho(C,B)\rho(B,A).

As all other properties follow from 5, we will only prove that fact.

(Proof of 5)  This is essentially just a reordering of multiplication:

\rho(A, B)\rho(B,C)\rho(C,A) = \lim\limits_{n \rightarrow \infty} \frac{|A \cap B \cap [1,n]|}{|B \cap [1,n]|}\frac{|B \cap C \cap [1,n]|}{|C \cap [1,n]|}\frac{|C \cap A \cap [1,n]|}{|A \cap [1,n]|}.

We shift all denominators to the right (cycling at the end) and find

\rho(A, B)\rho(B,C)\rho(C,A) = \lim\limits_{n \rightarrow \infty} \frac{|A \cap B \cap [1,n]|}{|A \cap [1,n]|}\frac{|B \cap C \cap [1,n]|}{|B \cap [1,n]|}\frac{|C \cap A \cap [1,n]|}{|C \cap [1,n]|}.

= \rho(B,A)\rho(C,B)\rho(A,C).

Indicator Sets

Our main purpose in studying relative density is the hope that it will lead to an indicator set. We call a set S \subset \mathbb{N} an indicator set if for all A  \subset \mathbb{N}, we have

\rho(A,S) = 0 ~~\text{if and only if}~~ \sum\limits_{a \in A} \frac{1}{a} < \infty.

So S is an indicator set if our wishful-thinking “theorem” is true when \mathbb{N} is replaced by S. We call it this because while \mathbb{N} is “too large”, S is “small enough” to indicate the convergence of the sum of reciprocals of elements of A. There are a lot of interesting properties that indicator sets must have if they exist, but it turns out we can prove their nonexistence with two simple propositions.

(Proposition 1) If \mathcal{U} is an indicator set, then \rho(\mathcal{U}, \mathbb{N}) = 1.

(Proof) If \rho(\mathcal{U},\mathbb{N}) < 1, we must have \rho(\mathcal{U}^c, \mathbb{N}) = 1 -\rho(\mathcal{U},\mathbb{N})  > 0, implying \sum_{v \in \mathcal{U}^c} \frac{1}{v} = \infty. But \rho(\mathcal{U}^c, \mathcal{U}) = 0, so by the definition of \mathcal{U}, we must have \sum_{v \in \mathcal{U}^c} \frac{1}{v} < \infty. This is a contradiction, so \rho(\mathcal{U},\mathbb{N}) = 1.

The second proposition is not even a statement on indicator sets, but on relative density in general.

(Proposition 2) Given any A,B \subset \mathbb{N}, we have \rho(A \cap B, \mathbb{N}) = \rho(A,B)\rho(B,\mathbb{N}).

(Proof)  We have

\rho(A \cap B, \mathbb{N}) = \lim\limits_{n \rightarrow \infty} \frac{|A \cap B \cap [1,n]|}{n} = \lim\limits_{n \rightarrow \infty} \frac{|A \cap B \cap [1,n]|}{n}\frac{|B \cap [1,n]|}{|B \cap [1,n]|}.

We swap the denominators to find

\rho(A \cap B, \mathbb{N}) = \lim\limits_{n \rightarrow \infty} \frac{|A \cap B \cap [1,n]|}{|B \cap [1,n]|}\frac{|B \cap [1,n]|}{n} = \rho(A,B)\rho(B,\mathbb{N}).

We can now prove our main theorem!

(Main Theorem) There does not exist an indicator set. That is, there does not exist a set \mathcal{U} such that for all A \subset \mathbb{N}, we have \rho(A,\mathcal{U}) = 0 if and only if \sum\limits_{a \in A} \frac{1}{a} < \infty.

(Proof) Suppose there exists an indicator set \mathcal{U}. Let A be any bad set (like the primes, for example). Then proposition 1 and 2 together tell us that \rho(A, \mathcal{U}) = \rho(A \cap \mathcal{U}, \mathbb{N}). Since A is bad, we have \rho(A, \mathcal{U}) > 0 and \rho(A, \mathbb{N}) = 0. But since A \cap \mathcal{U} \subset A, we also have \rho(A \cap \mathcal{U}, \mathbb{N}) \leq \rho(A, \mathbb{N}). Together, these give

0 < \rho(A, \mathcal{U}) = \rho(A \cap \mathcal{U}, \mathbb{N}) \leq \rho(A, \mathbb{N}) = 0,

which is clearly a contradiction. Therefore, \mathcal{U} cannot exist.

Final Remarks

Note that a “left-indicator set” (as opposed to the “right-indicator set” discussed above) can quickly be shown to not exist as well. Suppose \mathcal{U} was a set such that for all A \subset \mathbb{N}

\rho(\mathcal{U},A) = 0 ~~\text{if and only if}~~ \sum\limits_{a \in A} \frac{1}{a} < \infty.

Then property 1 tells us that for any subset \mathcal{U}^{\prime}, we have \rho(\mathcal{U},\mathcal{U}^{\prime}) = 1, which would imply that \sum_{u^{\prime} \in\mathcal{U}^{\prime}} \frac{1}{u^{\prime}} = \infty for all subsets \mathcal{U}^{\prime} \subset \mathcal{U}, which certainly cannot be true.

While the proof of the nonexistence of these indicators sets ended up being fairly short, there are still interesting things going on here. There has been a lot of work relating natural density, sum of reciprocals, and the containment of arbitrarily long arithmetic progressions (ALAPs). These relate as follows.

Screen Shot 2017-05-21 at 9.13.16 PM

If the text inside a box is green, it indicates that the row implies the column (with the text referencing the proof). If it is red, then it implies the row does not imply the column (with the text giving a counterexample). Blue text indicates that the implication is currently an open question.

\sum\limits_{k = 0}^{\infty} \sum\limits_{t = 0}^{k} \frac{1}{10^k + t} \leq \sum\limits_{k = 0}^{\infty} \frac{k+1}{10^k} = \frac{19}{10}.

Clearly there’s a lot to look at here, so hopefully this is not the last time you will read about relative densities on this blog!

 

Thanks for reading,

Jonathan Gerhard

Posted in MathematicalADD, Random | Tagged , , , , , , , , | Leave a comment

Integration By Parts Table Method and Strange Sums

Today, I will be writing about calculus. How many of you have heard of the table method for integration by parts? Not many, if my tutees at the Science and Math Learning Center are any indication. If it sounds unfamiliar, then let me show you something awesome! Otherwise, stick around to the end and we’ll put a slight twist in the idea and see what happens…

Table Method

Suppose we wanted to solve the following integral:

\int x^3\sin(x) dx.

The usual method would be integration by parts. We set u = x^3 and dv = \sin(x)dx, and find du = 3x^2dx and v = -\cos(x). Then

\int x^3\sin(x)dx = (x^3)(-\cos(x)) - \int (3x^2)(-\cos(x))dx.

Then we do it again, letting u = 3x^2 and dv = -\cos(x)dx, so that du = 6x and v = -\sin(x). Therefore

\int x^3 \sin(x)dx = (x^3)(-\cos(x)) - ((3x^2)(-\sin(x)) - \int(6x)(-\sin(x))dx).

Again, we’ll let u = 6x and dv = -\sin(x), so du = 6dx and v = \cos(x), and

\int x^3 \sin(x)dx = (x^3)(-\cos(x)) - (3x^2)(-\sin(x)) + (6x)(\cos(x)) - \int(6)(\cos(x))dx

= (x^3)(-\cos(x)) - (3x^2)(-\sin(x)) + (6x)(\cos(x)) - (6)(\sin(x)).

Phew. The way I wrote out this integral in the end is no accident – it reveals a pattern that becomes the Table Method. Let D^k(f) be the k^{th} derivative of f and I^k(f) the k^{th} integral of f. Then we can rewrite the above as

{\small \int x^3\sin(x)dx = D^0(x^3)I^1(\sin(x)) - D^1(x^3)I^2(\sin(x)) + D^2(x^3)I^3(\sin(x)) - D^3(x^3)I^4(\sin(x))}.

Let’s do it in general. We set up a table, with D (for differentiation) in the first column and I (for integration) in the second column. We choose the “u” term (the one we would be taking the derivative of) and put it in the first spot in the D column. Then we put the “dv” term (which we’ll be integrating) in the first spot in the I column.

Then we keep taking derivatives of the term in the D column, placing each derivative in the next row of the D column, until we reach 0. Then we keep taking integrals of the term in the I column, also placing them in successive rows of the I column.

Screen Shot 2017-05-16 at 1.00.26 AM

Then we alternate labeling the rows with + and -, always starting a +. Then we take the product of the term in the k^{th} row of D and the (k+1)^{st} row of I and add these together over all rows, taking into account the sign we just put next to that row.

Screen Shot 2017-05-16 at 1.00.44 AM

This allows us to quickly see that

\int x^3 \sin(x)dx = (x^3)(-\cos(x)) - (3x^2)(-\sin(x)) + (6x)(\cos(x)) - (6)(\sin(x)).

At this point, you could leave and employ the table method at your will, excited to have a quick shortcut for integration by parts in your toolkit. Or you could read on to see how we can use this method to produce strange sums, like Grandi’s Series 1 – 1 + 1 – 1 + … = 1/2.

Strange Sums

Notice an important aspect of the previous example was that the derivative of x^3 was eventually zero. Integration by parts tells us that if D^t(f) = 0 for some t \in \mathbb{N} (and therefore all k \geq t), then

\int fg~dx = \sum\limits_{k = 0}^{\infty} (-1)^kD^k(f)I^{k+1}(g),

But what if we didn’t force the derivative of f to eventually be zero? Let’s start simple, \int e^xdx. Let f = e^x and g = 1. Then our table would be (extending infinitely downward)

Screen Shot 2017-05-16 at 4.33.15 PM

If the table method worked out, we’d have

\int e^x dx = \sum\limits_{k = 0}^{\infty} (-1)^ke^x\frac{x^{k+1}}{(k+1)!}

= -e^x\sum\limits_{k = 0}^{\infty}(-1)^{k+1}\frac{x^{k+1}}{(k+1)!}

= -e^x\sum\limits_{k = 0}^{\infty}\frac{(-x)^{k+1}}{(k+1)!}

= -e^x(-1 + e^{-x})

= e^x - 1

But we know the lefthand side is e^x, so we find that

e^x = e^x - 1,

or 0 = -1. That makes no sense…let’s try again. This time, let’s solve \int e^{2x}dx by setting f  = g = e^x. Then our table becomes

Screen Shot 2017-05-16 at 4.39.24 PM

and we find

\int e^{2x}dx = \sum\limits_{k = 0}^{\infty} (-1)^ke^xe^x = e^{2x}\sum\limits_{k = 0}^{\infty}(-1)^k.

The lefthand side we know to be (1/2)e^{2x}, so canceling out the e^{2x} from both sides gives us

\frac{1}{2} = \sum\limits_{k = 0}^{\infty} (-1)^k.

This is exactly Grandi’s series! So the first attempt massively failed, whereas the second produced an interesting well-known series. What other interesting things can you come up with using the table method?

Thanks for reading,

Jonathan Gerhard

Posted in MathematicalADD, Random | Tagged , , , , , | Leave a comment

The Picture Post

This post will consist almost entirely of pictures of the objects created during the past year while using my Shapeways Education Grant. Check out my summary post for more words…

The 3 by 3 Rook’s Graph

The 4 by 4 Rook’s Graph

The Shrikhande Graph modeled to look like the 4 by 4 Rook’s Graph

The “Drum” Shrikhande Graph

The “Playground” Shrikhande Graph

The “Straight Edge” Shrikhande Graph

NOTE: The four different-looking versions of the Shrikhande Graph above are all isomorphic!

A book embedding of K5


The Perko Pair on a Praxinoscope

Thanks for reading,

Jonathan Gerhard

Posted in 3D-Printing, MathematicalADD | Tagged , , , , , , , , , , | 1 Comment

3D Printing Graphs, Knots, and…Books?

It’s just about at that point where I am hit with nostalgia of the past year and excitement for the coming year. This time around, however, that excitement is accompanied by sadness – I will be graduating from James Madison University and leaving many of the good friends I’ve made here to continue on in my graduate studies.

But this post isn’t to dwell on such things; instead, I wanted to do a recap of something which has brought me great joy in the past year – my project on 3D printing mathematical objects!

Update (5/16/17): Check out my picture post to see high resolution pictures of all the objects I printed during this project!

The Start of an Idea

Здравствуйте! That means “Hello” in Russian – but forget that, I’m sure we can go with a much more informal Привет at this point! I was in the Math in Moscow program in the Spring of 2016, taking courses in Algebraic Geometry, Commutative and Homological Algebra, and Algebraic Topology. It was there that I learned about a fascinating concept: homotopy equivalence. Two topological spaces are considered homotopy equivalent if there exists a homotopy between them…just kidding – that’s a ridiculous (albeit technically correct) definition! Think about topological spaces as geometric objects, a ball, a square, a donut, or even your shoe. Then one object is homotopy equivalent to another if you can shape the first – bending, stretching, or shrinking, but never cutting or glueing – into the second. Note this can transcend dimension, a 3D ball is homotopy equivalent to a point! The classic example of a two objects that are homotopy equivalent is a donut and a coffee cup (see below). More information is given in my first blog post on this project.

mug_and_torus_morph

Upon learning about some wildly unintuitive homotopies (one of my favorites is that a 3-sphere minus a torus is homotopy equivalent to the disjoint union of two solid tori), I had the idea to utilize 3D printing. I had done a project on 3D printing knot invariants with Laura Taalman at JMU my freshman year (final results pictured below), so I thought it was only right to finish off my undergraduate career by doing another 3D printing project with her.

conformations_all_preview_featured

She encouraged me to apply for the Shapeways Education Grant, which I was very happy to end up receiving. I want to thank Shapeways for this grant that allowed me to utilize their fantastic resources and focus on the designing process instead of the troubleshooting that is so often necessary when working with 3D printers! Once the year began, we got started!

Let the Printing Began!

We wanted to start off simple: a sphere minus a point is homotopy equivalent to a single point. We used Mathematica to create an animation of this homotopy, but I quickly became enamored with Fusion 360. Though Mathematica 11 has some nice 3D printing features built into it, you can attribute the decision to switch to my laziness – Fusion 360 had such a nice user interface with a ton of very useful (and easy to learn) tools.

I began to design a whole array of objects: The Perko Knots on a praxinoscope, the Rook’s Graph and (in the case of n = 4) the strangely non-isomorphic Shirkhande Graph, all the while making time for some interesting mathematics. As the fall semester wore on, we approached the first major capstone of this project: An invited talk at the 2017 Joint Mathematics Meetings in January. Not only was it a thrill to be able to share what I had been working on, but I found it to be an invaluable experience to learn from some of the people I consider to be pioneers in the field of mathematical 3D printing.

Let the Printing End!

Alas, this cannot be a complete summary, for the year has not finished! But I will wrap up this post by describing what my plans for the end of the semester are. The math community here at JMU has given so much to me, so I thought it would be nice for the second capstone of my project to involve giving back to that community.

BookEmbedding

Book embedding of the complete graph on five vertices

The idea of a book embedding of a graph is, in my opinion, very interesting. The entire concept deals not necessarily with some abstract graph, but investigates the possibilities of embedding that graph in what looks like a – well – book! I believe my final goal is a perfect mix of mathematics and 3D printing – I want to

  1. Design and 3D print book embeddings of the Rook’s Graph and the Shrikhande graph, and
  2. Characterize the book thickness of these two graphs, i.e. the minimal number of pages needed to embed the graph.

I want to give these last two prints to the JMU math department to hang in the lobby of Roop Hall, along with a plaque describing the mathematical wonders behind both the graphs and their book embeddings.

Once I finish that, I will finally feel like I put the Shapeways Education Grant to good use! I wanted to finish by again thanking Shapeways for that grant, thanking Laura for agreeing to work on this project with me, and of course, thanking you the reader. I hope you enjoyed!

Jonathan Gerhard

Posted in 3D-Printing, MathematicalADD | Tagged , , , , , , , , , , , , , | 1 Comment

On the Book Embeddings of the Rook’s Graph and the Shrikhande Graph

I’ve already 3D printed one book embedding, which was of K_5, the complete graph on 5 vertices, which looks like this:

Just so we’re all on the same page, let me define a book embedding again. An n-page book embedding of a graph G is

  1. A embedding of the vertices of G along a “spine” in some order.
  2. An embedding of the edges onto the pages such that each edge is contained in exactly one page, and no two edges cross.

The book thickness of a graph G is the minimal number of pages needed to have a book embedding of G. We usually denote this as BT(G). Notice the order of the vertices on the spine could change the book thickness, so if we fix a printing cycle \sigma = (v_1, \dots, v_k), then we define BT(G, \sigma) to be the minimal number of pages needed to have a book embedding of G with the vertices embedded on the spine in the order given by \sigma. Thus,

BT(G) = \min_{\sigma} BT(G, \sigma).

A simple example of the printing cycle affecting book thickness is with the square. Label its vertices starting at the top-left and going clockwise with 1,2,3,4. Then notice that

BT(G, (1,2,3,4)) = 1

but

BT(G, (1,3,2,4)) = 2.

We present two goals, one of which will be explored here in slightly more detail, and the other will be explored more later.

The 4 \times 4 Rook’s graph R_4 and the Shrikhande graph S are both strongly-regular on the same parameters (16,6,2,2) but are not isomorphic. The classic way of seeing this is that the neighborhood of a vertex of R_4 is two disjoint triangles, whereas the neighborhood of a vertex S is a 6-cycle. Certainly, the neighborhood of a vertex influences possible book embeddings, which leads to our first goal.

Goal 1) Determine the book thickness of both the Rook’s graph and the Shrikhande graph. If they are different, then this would be a cool new way to distinguish them!

The second goal is closer aligned with my 3D printing project. Since the beginning, I have been interested in creating a 3D printed book embedding of some graph to give to the JMU math department so that they can display it in the lobby of Roop Hall. This leads to the second goal.

Goal 2) Create 3D models of a book embedding of both of R_4 and S, such that each model actually looks like a book. Then, in addition to being a cool object to have in the lobby of Roop Hall, these could be used to show the various people coming through about Graph Theory and how cool it is! I’d like to make up a little plaque that details the similarities and differences of these graphs, and how you might see that in the book embeddings.

Goal One

I’ll expand a bit more on the first goal. There are three results I think will be useful, all of which come from a paper by Frank Bernhart entitled “The book thickness of a graph”. The first is

Theorem 1) Given a graph G on p vertices and q edges, we have

BT(G) \geq \lceil\frac{q - p}{p - 3}\rceil.

Theorem 2) Let \theta(G) be the smallest number of planar graphs whose union is G. Then

\theta(G) \leq \lceil \frac{\textbf{BT}(G)}{2} \rceil.

Theorem 3) We have

BT(G) \leq 1 if and only if G is outerplanar.

BT(G) \leq 2 if and only if G is a subgraph of a Hamiltonian planar graph.

We’ll demonstrate how these are useful by showing that BT(R_3) = 3.

Recall that R_3 is the 3 \times 3 Rook’s graph, and so it has 9 vertices and 18 edges. Then by Theorem 1,

BT(R_3) \geq \lceil\frac{18 - 9}{9 - 3}\rceil = 2.

But by Theorem 3, we know that \textbf{BT}(R_3) \geq 3, since R_3 isn’t planar, and therefore can’t be a subgraph of a Hamiltonian planar graph.

Another way we could’ve achieved this bound is by Theorem 2. Notice that \theta(R_3) = 2, so

2\leq \lceil \frac{\textbf{BT}(R_3)}{2} \rceil

which means BT(R_3) must be at least 3. Finally, it isn’t too difficult to provide a book embedding of R_3 with three pages, cementing the fact that BT(R_3) = 3. We hope to go into similar analysis for R_4 and the Shrikhande graph in a later post. The next post will address Goal 2 and detail some progress in creating the actual 3D models of these book embeddings!

Thanks for reading,

Jonathan Gerhard

Posted in 3D-Printing, MathematicalADD, Random | Tagged , , , , | 2 Comments

The Perko Praxinoscope and the Shrikhande Graph

As I mentioned in my previous update, I fixed the design for the Perko knots on the pegs, and made a decision on designing the Shrikhande graph so that it looked like the Rook’s graph. Well I sent them off to Shapeways and was overjoyed when I received them a week or so later: they were perfect!

First, the pegs for the Perko knots fit very well on the Praxinoscope. Also, the knots were still attached to the pegs when I received them, which is nice! Here they are laid out:

IMG_5541

And here they are on the actual praxinoscope:

IMG_5542

And here’s a video of it in action! Though we only have ten frames, you can still see the knot morphing as the praxinoscope spins.

On top of the Perko knot project working out really nicely, the Shrikhande graph came out perfectly! Here is a picture of it:

IMG_5535

I think this fulfills its purpose – if you hold this print and the 4 \times 4 Rook’s graph together, then you can really see the similarities and differences between the two.

In terms of plans for the future, I am hoping to 3D print a book embedding of a graph that really looks like a book! Here’s a sneak preview of the book design:

Screen Shot 2017-03-19 at 9.12.29 PM

Thanks for reading,

Jonathan Gerhard

Posted in 3D-Printing, MathematicalADD | 4 Comments

Crossless Edge-Colorings

Introduction

This post is an exploration of something I brought up in my last post: in order to nicely design the Shrikhande for 3D printing, I decided to draw it up (using Tikz) and use color to denote the orientation of the edges. I ended up using three colors, blue to indicate strands upwards out of the plane, red to indicate strands downwards out of the plane, and green to indicate strands in the plane. Here’s a picture:

screen-shot-2017-02-22-at-12-56-57-am

After doing so, I noticed something really cool (and helpful): There is never an instance where two edges of the same colors cross! For 3D printing purposes, this meant that I could draw the edges exactly as I pleased, without worrying about small maneuvers to avoid intersections in 3D like I ran into with the Rook’s Graph:

screen-shot-2017-02-13-at-3-10-26-pm

As the name of this blog would suggest, I quickly became wrapped up in this question: What is the minimal number of colors needed to color the edges of the graph so that no two edges of the same color cross? First, let’s define these terms a bit more explicitly.

Definitions

We begin with a simple graph G = (V,E) and an embedding \varepsilon: G \rightarrow \mathbb{R}^2. For us, an embedding is a pair of functions \varepsilon = (\varepsilon_V, \varepsilon_E). We want these to have certain properties:

1) The map \varepsilon_V: V \rightarrow \mathbb{R}^2 is injective. This means we want to see all the vertices independently, we don’t want one to be sitting on top of another. We’ll usually just write v instead of \varepsilon_V(v), to avoid clutter.

2) For e = uv \in E, we have \varepsilon_E(e) = f_e: [0,1] \rightarrow \mathbb{R}^2. such that

  • f_e is continuous.
  • f_e is injective. This means f_e(t_1) \neq f_e(t_2) if t_1 \neq t_2, for any t_1, t_2 \in [0,1]. So we don’t allow an edge to intersect itself.
  • f_e(0) = u
  • f_e(1) = v

We say that two edges d,e\in E intersect (or cross) if there exists t_1, t_2 \in (0,1) such that f_d(t_1) = f_e(t_2). Note the open interval – we don’t consider two incident edges to cross.

A k-coloring of the edges E is a surjective map c: E \rightarrow \{1, 2, \dots, k\}. We call a coloring crossless if any two crossing edges are not assigned the same color. That is, if d and e intersect, then c(d) \neq c(e).  Note we use crossless instead of non-crossing, as the latter term often describes a graph embedding in which no edges cross. I think we’re finally ready to state the question we’re interested in!

Let \mathcal{C}(G,\varepsilon) be the minimal number of colors needed to have a crossless coloring of the embedded graph (G,\varepsilon). Since we’re interested in describing a property of the graph itself, we naturally try to get away from any specific embedding by defining

\mathcal{C}(G) = \min\limits_{\varepsilon} \mathcal{C}(G,\varepsilon).

And now our question is clear: Given a graph G, what is \mathcal{C}(G)?

Some Quick Results

For lack of a better term, let’s call \mathcal{C}(G) the crossless-coloring number of G. One family of graphs that quickly give an answer is that of planar graphs. A graph is planar is there exists an embedding \varepsilon into \mathbb{R}^2 in which no two edges intersect. For such an embedding, we’d have \mathcal{C}(G,\varepsilon) = 1, which means \mathcal{C}(G) = 1.

This concept seems like it should be related to the crossing number of a graph, denoted cr( G). This is the minimal number of crossings a graph has over all its embeddings. Though it might be tempting to say that \mathcal{C}(G) \geq cr(G), this is actually false! Consider the complete graph on 6 vertices:

k6threecrossing

It is known that cr(K_6) = 3, and from the above picture, we see that we can find a colorless crossing of K_6 with only two colors. Further, since it is nonplanar, we know that \mathcal{C}(K_6) \geq 2. Together, this establishes that \mathcal{C}(K_6) = 2.

We see that we only need two colors because, while there are three crossings, each crossing occurs between a different pair of edges. This leads us to define the crossing-neighborhood of an edge e (with respect to an embedding \varepsilon) to be

CN_\varepsilon(e) = \{ d \in E ~|~ d\text{ and }e\text{ cross}\}.

We then define the edge-crossing number of an embedded graph (G,\varepsilon) to be

\Gamma(G,\varepsilon) = \max\limits_{e \in E} |CN_\varepsilon(e)|

and define the edge-crossing number of an abstract graph G to be

\Gamma(G) = \min\limits_{\varepsilon} \Gamma(G,\varepsilon).

To finish this post, we pose the following conjectures:

Conjecture 1) Given an embedded graph (G, \varepsilon), we have

\mathcal{C}(G, \varepsilon) = \Gamma(G,\varepsilon) + 1.

Conjecture 2) Given a graph G, we have

\mathcal{C}(G) = \Gamma(G) + 1.

We certainly have that conjecture 1 implies conjecture 2, but I’m not yet convinced that conjecture 2 would imply conjecture 1.

EDIT: Not surprisingly, these hastily-made conjectures are false!

I’d also like to note that these conjectures are inspired by Vising’s theorem on edge-colorings. In fact, if there was some construction to reduce this problem to the usual edge-coloring problem and then allow an application of Vising’s theorem, that would be really interesting! I hope to have more on this soon.

Thanks for reading,

Jonathan Gerhard

Posted in MathematicalADD, Random | 2 Comments

Quick Update on the 3D Printing Project

As the title suggests, this is just a quick update on the 3D printing project I’ve been doing this year.

First, after multiple failed attempts to print the Perko knots attached to pegs for the praxinoscope, I have finally created a model that passed all of Shapeways’ tests! The link to its page is here. Here are some changes from previous models:

  • Constant diameter peg. The tapering of the edge where the knot connects seemed to 1) cause it to fail Shapeways’ test for object thickness, and 2) cause the knot to separate from the peg when exploring the Print-It-Anyways option.
  • Knot loop embedded in the peg. Similar to the first point, having the knot just on the edge of the peg (which has the benefit of actually seeing the entirety of the knot) usually caused problems with printing. So this time, I put the strand completely inside the peg, both for stability, and I think it actually kind of looks better stylistically…you be the judge!
  • Knot orientation/positioning. I aligned all of the knots to the same height, expanding the peg length when necessary, and made sure that the same strand was embedded in the peg at each stage of the isotopy. This will hopefully make the “animation” on the praxinoscope smoother.
  • Instead of attaching physical numbers to the bottom of the pegs, I drilled the corresponding number of holes into the peg. Hopefully these will be visible upon printing!

screen-shot-2017-02-22-at-12-45-18-am

Switching gears, let’s talk about the Shrikhande graph again! Recall that it is the only graph that shares the strongly-regular parameters with the square Rook’s graph R_n (in the case where n = 4). Last post, I mentioned trying to recreate the Shrikhande graph as closely as possible to the Rook’s graph. My previous thought was this:

The left is the Rook’s graph for comparison, and the right is the Shrikhande graph. Note that the blue edges indicate upward (rising above the plane) loops and red edges indicate downwards (dipping below the plane) loops. For the Rook’s graph, this worked beautifully. But for the Shrikhande, as you can see, it became a bit of a mess.

Note that whenever two edges of the same color cross, we have to manipulate those loops so that they don’t actually cross in the 3D printed object. If two edges of different color cross, it’s no problem. So while the coloring of the Shrikhande graph on the right preserved the number of blue and red edges incident to each vertex, it also caused many troublesome crossing.

To alleviate this problem, I thought to introduce a third edge color, green, that indicated strands lying in the plane. Here is that graph:

screen-shot-2017-02-22-at-12-56-57-am

Note that there are in fact NO edges of the same color crossing! I can’t help but get coerced by the mathematics lurking close by: What is the minimal number of colors you need to color the edges of a graph in a certain configuration so that no two crossing edges have the same color? What is the minimal number of colors you need to color the edges of a graph for any configuration? If two edges of the same color must cross, can you minimize the number of times it occurs? How?

But that is a topic I will have to wait to explore; for now, it’s time to design it and print it!

Thanks for reading,

Jonathan Gerhard

Posted in 3D-Printing, MathematicalADD | 4 Comments

Visualizing the difference between the 4×4 Rook’s graph and the Shrikhande graph

In the summer of 2015, I did a research project characterizing the critical groups of the Rook’s graph and its complement. I won’t be talking much about that specific project here – instead, I just want to look at the structure of the Rook’s graph.

The n \times m Rook’s graph is a specific type of chessboard graph. We take an n \times m grid and put a vertex in each cell. We then connect a vertex (x_1,y_1) to a vertex (x_2, y_2) if you can get from the first to the second through a Rook’s move, i.e. if they are in the same row or column.

When n = m, the Rook’s graph is a strongly-regular graph with parameters (n^2, 2n - 2, n - 2, 2). We denote this by R_n. This means it has n^2  vertices, each of degree 2n-2. Additionally, any two adjacent vertices share n-2 neighbors (which comes from the fact that two adjacent vertices must be in the same row or column, and there must be n-2 other vertices in that row or column) and any two non-adjacent vertices share 2 neighbors (if we draw a square with the two non-adjacent vertices at its corners, they will both be adjacent to the vertices lying at the other two corners).

For all n \neq 4, these parameters are uniquely satisfied by the n \times n Rook’s graph. And yet, for n = 4, there is exactly one other non-isomorphic graph that satisfies the same parameters: The Shrikhande graph. We occasionally call this graph S.

So what goes wrong with n = 4? A nice way to distinguish R_4, the 4 \times 4 Rook’s graph, and the Shirkhande graph is by the neighborhood of a vertex in each graph. The neighborhood of a vertex v is the set of all vertices adjacent to it. We can look at the subgraph induced by the neighborhood of v by removing all vertices not adjacent to v and any edges adjacent to a vertex we removed.

The subgraph induced by the neighborhood of any vertex in R_4 is connected in two triangles (in other words, it looks like the wedge of two tetrahedra), while the subgraph induced by the neighborhood of any vertex in the Shrikhande graph is connected in a 6-cycle (so it looks like the cone of a hexagon).

I wanted to compare these graphs by laying out the Shrikhande graph in the same way that I did R_4, shown below

screen-shot-2017-02-05-at-4-19-28-pm

The way I decided to do this was by using the algebraic definition of these two graphs. We can define the Shrikhande graph and the Rook’s graph as follows. We label the vertices of the grid with elements of \mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z} in the natural way, and connect two vertices if:

  • (Rook’s graph) their difference lies in the set \{\pm (0,1), \pm (1,0) , (2,0), (0,2) \}.
  • (Shrikhande graph) their difference lies in the set \{ \pm (0,1), \pm (1,0),(1,1), (3,3)\}.

This gives us a nice way to transition from the Rook’s graph, which we already have, and the Shrikhande graph. We simply remove all the edges whose difference is (2,0) or (0,2), and add in edges whose difference is (1,1) or (3,3).

 

Notice that both R_4 \backslash S and S \backslash R_4 are isomorphic to the disjoint union of four 4-cycles. Despite this,

(S \cap R_4) \cup (R_4 \backslash S) \ncong (S \cap R_4) \cup (S\backslash R_4),

since the first is R_4 and the second is S. So what we see here is that graph homomorphisms don’t necessarily mesh well with unions of graphs. Of course, this isn’t too crazy of a thing, even something as simple as adding an edge to a graph can result in non-isomorphic graphs depending on the placement of the edges.

Anyways, we use this decomposition to put the Shrikhande graph together in a configuration similar to the Rook’s graph, and hope it prints well!

For a bit more fun, here is the Shrikhande graph and the Rook’s graph, created by putting together the pictures above.

Thanks for reading!

Jonathan Gerhard

 

Posted in 3D-Printing, MathematicalADD | 3 Comments

JMM and an Update

This post is just a quick update on the 3D printing project (with a few pictures from JMM, the Joint Mathematics Meetings) and some plans for the future!

At this past JMM in Atlanta, Georgia, I gave an invited talk at the session entitled “MAA Invited Paper Session on Technical Tools for Mathematical 3D Printing.” Before then, I was able to print out a few different objects: A book embedding of K5, the 3×3 and 4×4 Rook’s graph, a few different configurations of the Shrikhande graph, and a failed version of the Perko pair isotopy on pegs for the praxinoscope. Here are some pictures!

JMM was (as always) such an amazing time, and I’m happy to say I’m continuing this project through my last semester at JMU! My plans moving forward are to fix the Perko Pair, and create a large book embedding that actually looks like a book, as a gift to the JMU math department in appreciation of everything they’ve done for me.

Thanks for reading,

Jonathan Gerhard

Posted in 3D-Printing, MathematicalADD | 1 Comment