Featured

The Fundamentals of Topology dealt with less math and more intuition

Introduction:

Ever thought that a cup and a donut are similar – Yeah, me neither (though I dunk donuts in cups of coffee regularly). However, it turns out that these two seemingly unrelated bodies share many properties in common. Let’s talk about that.

In school, you must have heard that circles are just special cases of ellipses. How’s that so? Well for the math geeks here, you could easily prove that using the equations of their shape, but let’s think of it in another way – Deformation.
A circle is just a compressed version of a larger ellipse, you can compress any ellipse into a circle (Fig 1) or you can stretch any circle into an ellipse. When you compress an ellipse you get an infinite number of more ellipses, a circle is just one of them, a special compression. If this thought tickles your curiosity, think about this: if circles are just a special case of ellipses, can it mean that there are some properties which are preserved during these “deformations”.

Figure 1: An ellipse (Purple) can be compressed into infinite number of ellipses which includes circles (the ones coloured black and red). It can also be thought that the central circle (red) is stretched to form larger ellipses or in fact it can also be compressed to form smaller ellipses (not shown in the figure)

What might be the properties that both an ellipse and circle have in common? The answer is surprisingly simple: No matter how the ellipses are deformed, they are still conic sections. Conic sections are basically the sections formed in a cone when a plane cuts through it, this encompasses all of the basic curves we know: Circles, Parabolas, Hyperbolas and Ellipses.

Figure 2: The Conic sections. We can also see here, how a circle is a special case of an ellipse. A conic section becomes a circle if and only if the plane that cuts through the cone is parallel to the base of the cone and also does not pass through the base. But for a conic section to be an ellipse it just has to not pass through the base of the cone, it doesn’t necessarily need to be parallel to the base.
Courtesy: Magister_Mathematicae, CC BY-SA 3.0, Link

If you expected some other property, like maybe a special point being equidistant from something on the curve, it turns out that it actually isn’t the case. The only property that carries over is that they are conic sections. Since a parabola or a hyperbola are also conic sections, does that mean that they can be deformed into one another and into ellipses. Yes, they can easily be deformed into one another for example in a parabola take the two bottom points (the points touching the base of the cone) now just slowly bring them closer. You will notice that the final shape formed when both the points touch is, you guessed it, an ellipse. So any conic section can be deformed into one another and the only property that is preserved is that they still are conic sections even though they are deformed.

Let us go back to the initial question: Are a cup and a donut equivalent? It turns out that the donut can be deformed into a cup, you probably wont believe me so see this well known Gif:

Figure 3: A Donut being morphed into a cup and vice versa

Isn’t that Gif trippy. It is very interesting to see how a cup and a donut, formally called a torus, are morphed into one another. Let’s see another example of this deformation, a cow into a sphere.

Figure 4: A cow being morphed into a Sphere
Courtesy: Keenan Crane, CC BY-SA 4.0, Link

When three dimensional objects are deformed to form other three dimensional objects it begs the question what properties of one are transferred over to other and what objects other than a sphere for example, can be morphed into a cow. All these questions are answered by Topology, the study of properties of an object which are preserved through deformations.

Before we dive deep into a few basic concepts of topology, I have to address a small note, topology is the study of objects when they are deformed i.e stretching, bending, crumpling, twisting but we cannot tear something away from the object or glue something to the object.

A Topological Space:

A Topological space when thought in the form of sets has this definition:
A Topological space is a set (X, T) where T is a collection of subsets of X such that:

1. The empty set “{ }” and the set “X” are present in the set T.
2. The intersection of any number of sets in T must be present in T.
3. The Union of any number of sets must be present in T.
T is called a “topology on X”.

Take a moment to understand these rules, you might not understand them completely, but you will after seeing a few examples.
X = {-2, -1, 0, 1, 2}, can T be :
1. { { }, {-2, -1, 0, 1, 2} } , yes T can be such a set as it obeys all the three rules stated above this is also called a trivial set as it only contains the empty set and X, any topology on X other than this builds upon this set as a framework adding more sets to this while still obeying the rules if this basic framework is absent it is not a topology.
2. { { }, {-2}, {-2, -1, 0, 1, 2} }, yes check it yourself
3. { { }, {-2}, {-1}, {-2, -1, 0, 1, 2} }, no T cannot be this set as the union {-1,-2} is absent
4. { { }, {-2,-1,0}, { 0, 1, 2}, {-2, -1, 0, 1, 2} }, no T cannot be this set, though the union between {-2,-1,0} and { 0, 1, 2} is present (namely {-2, -1, 0, 1, 2} ). This is because the intersection between {-2,-1,0} and { 0, 1, 2}: {0} is absent in the set this can be called a topology only if that set is present.

After understanding this slightly tricky definition of a topological space the majority of you will ask what is the use of all this mathematical jargon? Well, this mathematical jargon is used to fuel another more convoluted but a lot more interesting concept which is the life and soul of topology – homeomorphism.

Homeomorphism:

Remember I told you that a circle can be morphed into an ellipse, well it can even be morphed into a square, a rectangle, a parallelogram etc. So what is the underlying law that governs what shapes a circle can take, or for that matter any 3 dimensional shape, when deformed. What is the relation between the deformed shape and the original shape ? It is Homeomorphism. When a shape is morphed into a new shape, then the new shape and the original shape are called Homeomorphic. So, it follows that if any two shapes, which can be seemingly unrelated are homeomorphic, then one of those two shapes can be deformed into another.

So how can we say if two functions are homeomorphic:
Let us say there are topological spaces X and Y, if there exists a function f: X →Y such that:

  1. Function f is a bijection
  2. Function f is continuous
  3. Function f-1 , i.e the inverse function is also continuous.

These rules might seem a little complicated if you are not familiar with the terms used, but it is actually simple, let’s look at each of these rules carefully. Before we do that we need to revise what a function is – it is basically like a box in which you input a variable, in this case it is X and you get an output, Y.
Rule one says a function is a bijection which essentially means that every input you give to the function is mapped to a unique output in such a way that there are no inputs which aren’t mapped to an output and vice versa. Basically no unpaired elements.
As for Rule 2 it is very easy it just means that the graph of the function is continuous with no breaks.
Rule 3 is also simple it is essentially saying that when the input is Y and the output is X even in that case the graph of the function should be continuous just to make sure that continuity holds from both sides.

Figure 5: An example of a bijective mapping

Let us look at a few examples of homeomorphic spaces:

  1. Any interval, open or closed, for example (a1, a2) is homeomorphic to the set of real numbers R. How so? Because there are infinite real numbers between a1and a2 and there are also infinite real numbers in the set of real numbers so you can take a bijective mapping in such a way that you map the first number of (a1, a2), “a1” to the first number in the set of real numbers i.e “-∞” and you can continue this mapping till you map a2 to infinity, remember here we use the fact that there are infinite numbers between any two real numbers.
  2. Another example as I have mentioned earlier is homeomorphism between a unit square and a unit disc one can be deformed into another. There exists a bijective function between them.

There are lot more examples of homeomorphic objects, but their bijective functions and the analyses for each one of them is out of reach of this blog as it is involves a little bit of complex math which is what I am trying to avoid. But if one is interested in learning them there are countless resources available online. Why I brought up homeomorphism, even though it is a little complicated, is because, as I have already mentioned, it is the life and soul of topology. It is the only way you can start comparing whether two objects can be morphed into each other, let alone their properties. This is just the beginning of Topology, there are a lot more intricate concepts embossed in it, which is why it is one of the most happening places in research of mathematics. But, no need to fear we will try our best to understand as many of those concepts intuitively as we can without delving deep into the mathematics.

An interesting homeomorphism:

Figure 6: The featured image of this blog: A Trefoil knot
Courtesy: Wiebew – CC BY-SA 3.0, Wikimedia Commons


Look at figure 6, it is formally called a Trefoil knot. It is actually a very beautiful image just look at it closely for a while and you will notice that it is a complete structure with no breaks. Now look at a another figure, a torus:

Figure 7: A Torus
Courtesy: Leonid 2, Wikimedia Commons

Would you believe me if I said the trefoil know in figure 6 and the torus in figure 7 are homeomorphic and can be morphed into one another. I think you wouldn’t cause I didn’t believe it either in fact before we discuss this fact in detail, do you think a rectangular sheet would be homeomorphic to a torus and in turn to a trefoil knot. You would surely say “Abhiram! are you crazy, how can a rectangle and a trefoil know be morphed into one another! The Torus has a hole how in the world can you morph a sheet into a torus!”. Hold your horses for a minute an look at this Gif below:

Figure 8: A Rectangular sheet being morphed into a torus.

It’s fascinating isn’t it, how easily a sheet can be bent into a torus. That simple gif, kind of humbled me. It changed my opinion on what I thought could be morphed into what.
When I read about concepts like this I always think, that Maths is so beautiful, especially when understood intuitively.

Before we go back to the torus knot problem, I want to introduce a term –isotopy. It is fundamentally a path connecting two homeomorphic objects while in turn passing through many other homeomorphisms. So basically, if we take figure 8 for example, when the rectangular sheet is being bent into a cylinder all the objects in between those two shapes are homeomorphic and when the cylinder is being bent to a torus all the shapes in between are also homeomorphic. So, the path you chose to make a sheet of paper into a torus is the isotopy between them, there are many kinds of isotopies in topology but they wont be deal here. Now, let us select the isotopy of figure 8 since it is flowing through an infinite number of shapes the only way you can represent them is a function and like I said earlier, the math of this wont be dealt here. If you see the figure 1 even, the big ellipse (purple) when compressed into the smaller circle (red) you can clearly see the homeomorphic ellipses in between and the isotopy of the conversion.

A Torus Knot:

Since we have already veered away from toruses and knots I would like to introduce an interesting shape, it is also very famous in the world of mathematics – A Torus knot. To construct it, all you have to do is to take a string and continuously loop it around the surface of a torus.

Figure 9 : A torus knot, you can hopefully see a torus shape around which the knot is made.

Let us see the knot in other angles:

Figure 10: Top view of the torus It looks very beautiful in this angle
Figure 11: A Point of view which makes the knot look like a bunch of garbage.

The torus knot is very beautiful, in fact there are so many other kinds of knots in the world of math that there is a whole website dedicated to it : Knot-plot they even have an app for plotting knots and it is dope. I would even like to share an image from their website:

Figure 12: An image consisting of 120 Different Torus-Knots! And they are just torus knots imagine the other types of knots possible, if you want. to actually see many many more knots like this I highly suggest to take a look at www.knotplot.com and download their app to create more knots like these. Disclaimer: Knot_Plot has not sponsored me I just like their website a lot and I just wanted to share it.
Link to Original Image Copyright © 1998-2000 by Robert G. Scharein
Figure 13: A torus knot made on a bagel, it is a funny post and I suggest you check it out:
How to make a mathematically correct breakfast by George Hart

Understanding torus knots is very essential to see how trefoil knots and toruses are linked to each other. Even though trefoil knots and torus knots are completely different knots mathematically they are both still very interesting and beautiful to look at.

Shall we finally answer the question that I have been dodging so far: Homeomorphism between Trefoil Knots and toruses. Well, to convert a Trefoil knot into a torus we have to un-knot it. How do we do that? It is complicated and I felt that if I tried to explain how it is unknotted, I wouldn’t be doing justice to the concept as I am not very familiar with it myself. So I have decided to share a post dedicated to just that: Unknotting the Trefoil
Just bear in mind that he draws the trefoil in a different way than what we discussed but if you look closely you will notice that they are the same.

Conclusion:
You might have noticed that we actually didn’t cover a lot of concepts in this blog for instance there is no detailed mention about what properties are preserved when an object is morphed into another, the main focus of topology. But, we did cover homeomorphism at least up to a basic level. There are so many more interesting topics in topology that I want to cover, the link of topology to quantum field theory or, how the Königsberg Problem is the beginning of topology or, the different types of topology and their specific rules or, materials in which topological rules are broken etc. etc. Trust me, I will cover each and every one of them in my upcoming blogs but until then, be happy that you learnt something new today.

Take Home Message:

A topologist cannot tell the difference between a donut and a coffee mug.

Featured

Rapid growth of pollutant particles in cold urban air

Delhi, one of the most polluted cities in the world, every year around winter a cold toxic smog envelops the city. During the lockdown its air quality had improved, but still as winter came around and the city started to open up, so did the pollution. There are serious health implications because of these kinds of smog. This smog caused because of Particulate Matter (PM) in the atmosphere, it is the leading cause of lung disease and is thought to even contribute to neurological diseases like Alzheimer’s. A better understanding of the particulate matter that is causing smog is very much required to mitigate air-pollution.

The particles in the atmosphere are broadly classified into two categories: primary particles, which form directly from combustion, or other human activities and secondary particles, which form in the atmosphere from other gaseous pollutants like sulphuric acid, ammonia, nitric acid and other volatile organic compounds. The secondary particles condense and stick to the surface of other existing particles. The Winter smog is a mixture of both these kinds of particles. For secondary particles to survive they need to grow rapidly, but how they grow so rapidly in urban areas is still a puzzle. Observations have suggested that in urban air vapour and particles are in equilibrium, so the growth rate is low. But, researchers have found in a laboratory experiment that in the presence of common nitrogen emissions from vehicles the particles grow a lot faster.

These nitrogen compounds are thought to have concentrations near their equilibrium values in atmosphere, so they were thought to not play much of a role in particle growth. In the Upper Atmosphere, typically in cold temperatures, nitric acid and ammonia react to form ammonium nitrate. Ammonium nitrate condenses onto other particles and this significantly adds to the total no of particles.

Any sort of combustion in cities form high atmospheric concentrations of gaseous pollutants, these pollutants readily condense into tiny clusters, around 10nm in diameter. But, it’s a lot harder for these tiny clusters to combine and form larger ones, they just evaporate, because of an effect identified by Kelvin in 1871: Smaller clusters have greater curvatures so they tend to have higher surface vapour pressures in turn implying that they evaporate more readily if the particle is smaller.

As clusters grow, they reach a threshold size where they get caught by a larger particle and stick to its surface. As a result, the number of particles does not increase. The rate at which they condense onto a larger particle (an aerosol) is called the condensation sink rate. The ability of small, new clusters to grow into larger ones depends on the ratio of the condensation sink rate and the growth rate.

Fig. 1
Figure 1a: Particle nucleation and growth (particle growth rate, ddp/dt) at −10 °C from a mixture of 0.44 pptv sulfuric acid and 1,915 pptv ammonia at 60% relative humidity Figure 1b: Particle formation and growth under identical conditions to those in a, but with the addition of 24 pptv of nitric acid vapour formed via NO2 oxidation. After the particles cross 5nm in diameter they grow rapidly.
Figure 1c: Observed growth rates after activation versus the product of measured nitric acid and ammonia levels at +5 °C and −10 °C. 
(Courtesy of Wang, M. et al. Rapid growth of new atmospheric particles by nitric acid and ammonia condensation, Nature)

Figure 1 shows the values observed by researchers working at the CLOUD(Cosmic’s Leaving OUtdoor droplets (does that short form make any sense?)) chamber at CERN, a chamber which essentially simulates the atmosphere by varying the temperatures and gas concentrations. It also contains a proton synchrotron which serves as an artificial source of cosmic rays, also simulating the atmospheric conditions. Now coming back to the figure, Figure 1a is particle diameter growth under normal conditions i.e no activation with any nitrogen compounds whereas, Figure 1b shows the diameter growth when activated with Nitric acid vapour, when particle reaches. a diameter of 5nm it grows very rapidly. Figure 1c, shows the growth rate at -10°C and 5°C. It is clearly evident that we need lesser concentration of nitrogen compounds at -10°C than at 5°C to get the same growth rate, it implies that in colder temperatures particles grow more easily.

Figure 2: The CLOUD chamber at CERN
(Image: Maximillien Brice/ CERN)

Majority of ammonia formed in urban areas is due to the catalytic converters in vehicles and that in rural areas is associated with cow dung. The most common pathway for formation of ammonium nitrate keeps it in chemical equilibrium with ammonia and nitric acid. So, it is unlikely that this mechanism will increase the density of particles, unless the atmosphere is super-saturated with nitric acid and ammonia with respect to ammonium nitrate i.e, nitric acid and ammonia are in a lot higher concentration than the product (ammonium nitrate), they quickly react to restore equilibrium in turn increasing. the number of particles. Even a small amount of supersaturation is enough to increase the growth rate by a lot.

Because ammonium nitrate is semi volatile, it was thought to not play an important role in particle growth, where low vapour pressures are required. So sulphuric acid was thought to be the main constituent for particle growth, but this isn’t true as demonstrated earlier by the researchers at CLOUD, it’s the saturation ratio not the vapour pressure that governs the particle growth rate. Furthermore, nitric acid and ammonia vapours are 1000 times more abundant in the atmosphere than sulphuric acid making the rate of growth a lot higher.

In experiments done at CLOUD, the researchers found that at any temperature lower than 5°C , ammonium nitrate and sulphuric reacted to form small clusters of molecules. Once these clusters of ammonium sulphate reached a certain threshold size, as discussed previously, ammonium nitrate condensed onto this cluster resulting in rapid particle growth above 100nm/hr – as long as the temperature remained higher than -15°C. If the temperature was colder than -15°C, which occurs in humid airflows above certain clouds, then the nitric acid reacted with ammonia forming ammonium nitrate which grew further by additional condensation.

The “threshold size” at which rapid growth happens depends on the concentrations of nitric acid and ammonia. Once that threshold is reached rapid growth happens until the equilibrium is restored.

Why is this observation so important?

In the relatively clean and “cold” upper atmosphere, where nitric acid is abundant due to electrical storms and ammonia, through convection from liquid water in clouds makes this observation all the more important.

More these particles grow, more is the pollution and more are the health risks.

The Königsberg Problem and its relation to graph theory and beyond.

Königsberg, an old city in Prussia, founded in 1255 (Presently Kaliningrad, Russia) had a River passing through it, the River Pregel, which the city divided into a tuning fork shape(see Fig 1). In the early 18th century the citizens of the city roamed through the intricate array of the seven bridges which connected various parts of the city across the Pregel River. These bridges lead to the development of a new mathematical problem called the Königsberg Bridge Problem.

Fig 1: The city of Königsberg dividing the River Pregel into a tuning-fork like shape. There are 7 bridges connecting various parts of the city across the Pregel River.

The Königsberg Bridge Problem and the Euler Analysis:

The Königsberg Bridge Problem was a fun mathematical puzzle that led to many developments in field of mathematics. Here’s how the problem goes:

Is there a path you can take across the Königsberg city by crossing each and every one of the 7 bridges exactly once?

Think about this problem for a minute. It might seem simple at first glance, and it is. But, I highly recommend getting a pen and paper and try out this problem for yourself before reading further.

Fig 2: An easier to understand version of the Königsberg Bridges
CC BY-SA 3.0, Link

Leonhard Euler (1707-1783), a famous mathematician, who lived in nearby St. Petersburg (he has so many things named after him) found a new way of analysing the Königsberg Problem.

Fig 3: Portrait of Leonard Euler

Euler analysed the problem by taking each landmass as a single point, formally called a node. He could do this because movement inside the landmass is irrelevant. The bridges are considered as lines, formally called edges. The length and shape of the edges didn’t matter as it only signifies as connection between two nodes.

Fig 4: The Eulerian Analysis of the Königsberg problem using nodes and edges. The blue circles represent the nodes, the landmass – and the black lines represent the edges, the bridges connecting the landmasses.
(CC BY-SA 3.0, Link)

The Analysis:
If a person enters a landmass through a bridge then he must leave the landmass through a different bridge. In other words the number of bridges leading into a landmass must equal the number of bridges leaving the landmass. Unless, the landmass serves as an endpoint for the path. What this means is that since, the number of bridges leading up to a landmass must equal the number leaving it, in turn implying that the total number of bridges connected to a landmass is even. (n+n = 2n)

Fig 5: An image of one of the Königsberg bridges crossing the Pregel River.

Note: Whether a bridge is considered as leading up to a landmass or leaving a landmass is arbitrary because you can move both sides on a bridge. You arbitrarily chose the direction you want to go in.

Graph Theory

In more mathematical terms, the number of edges connected to a node is called the “degree” of the node. This way of using nodes and edges is called a “graph”, not the kind of graphs you know about like a bar graph, line graph etc. This graph is different, it is essentially “a network of nodes and edges connected to each other.” It is a way of representing how objects are connected without actually worrying about the distance between them. Essentially, the position (i.e the location) is important not the distance. So Euler called this as “The Geometry of Position”.

So, as explained earlier since the number of bridges connected to a bridge should be even, unless it is the end point, this implies that:

“For there to be a path which traverses all the edges exactly once, there can be at most two nodes of odd degree, because there can be at most two end points.”

The above statement was called the Eulerian Assertion, using this assertion it isn’t too hard to prove why no path along the Königsberg is possible wherein all the 4 landmasses have odd degree, implying that no path along these bridges traversing each bridge once is impossible.

Graph Theory and Topology, both born from this Eulerian Assertion, are both areas where extensive research happens to this day. We are going to discuss one of these areas, Graph Theory, the study of graphs. The Eulerian Assertion, after being proved, ended up as the first theorem in Graph theory.

In real-life, these graphs are very useful, for example while drawing a map for the train routes and stations in the city, the distance between the stations is less important, but the connection between the stations is.

Fig 6: The map of the London underground. This map is particularly useful for seeing the connections between the stations, but it isn’t very useful to actually plan a trip because the distances between the stations isn’t actually scaled so many stations are either very close or very far in this map than they actually are in real life.
Taken from tfl.gov.uk

Graph theory has evolved and it now has applications in computer science, chemistry, operations research and even social science. But, we will get to those applications later.

Formal Definitions of a Graph & its types :

A graph as discussed before is a set of nodes and edges, hence it can be represented as:
A graph G is an ordered pair of nodes and edges- (N, E) where N and E can be further defined as :-
N, a set of nodes
E ⊆ {{x, y}⎮x, y ∈ N and x≠y }, i.e a set of edges which are unordered pairs(sets) of two distinct nodes.
This kind of mathematical representation is called a simple graph, where two nodes can be joined by at most one edge.

If a graph is permitted to have multiple edges(or parallel edges) i.e more than one edge having the same end point, then such a graph is called a multi-graph.

There are two types of multi-graphs:
One wherein the edges have no identity, meaning that the identity of the edge is solely defined by the vertices it’s connected to, In this case “multiple edges” means that the same edge occurs many times between two vertices.
Another type is wherein the edges have its own identity, meaning that the edge is considered as a primitive object like the node, so if two or more edges connect two vertices then the edges are considered different.

Fig 7a: A Simple Graph wherein two nodes are joined by at most one edge.
Fig 7b: A multi-graph where two nodes can be joined by more than one edge.

Mathematical Defintion of Multi-graphs:

Multi-graph where Edges have no identity- An ordered pair (N, E) where,
N is a set of nodes
E is a multi-set of nodes, called edges. A “multi-set” allows multiple instances of elements, unlike a normal set where multiple instances of the same elements is prohibited. This basically means the same node can appear multiple times in the set of nodes (the edges). So the same edge connects between two nodes multiple times.

Multi-graph where Edges have their own identity- An ordered pair (N, E, ɸ ) where,
N is a set of nodes
E is a set of edges and ɸ, is where it gets interesting-
ɸ : E → {{x, y}: x, y N}, this means assigning each edge its own set of two nodes. So each edge is assigned two node meaning two different edges can be assigned to the same two nodes, so two or more different edges can appear between two nodes. If you look carefully you can observe that since you are assigning each edge its own set of nodes and an edge cannot be assigned more than one set of nodes it in turn eliminates the case where the edges have no identity.
In the ɸ definition, you might notice that I have not mentioned x≠y, this is because there is a thing called loops in a graph, where a node is connected back to itself. Some authors accept loops in a graph, while others call them as pseudo graphs implying that loops are not acceptable in a multigraph.

Fig 8: A multi pseudo graph with multiple loops(in blue) and also more than one connection (in red) between two vertices.
0x24a537r9CC BY-SA 3.0

There is a graph much more complicated than this, called a hyper graph wherein an edge can join any number of vertices 2, 3, 4 or more, but this is out of reach of this particular blog.

Whenever appropriate you can even assign direction to an edge, representing the direction you can move on the edge, called a directed graph or digraph.

Fig 9: A directed graph or digraph

These kinds of graphs are particularly useful for airplane routes where sometimes you can go from one airport to another in only direction and other times when airplanes go to and fro from one airport to another, where it the plane route can be easily graphed by using parallel edges with opposite directions. In Fig 8, between the middle node and the right node you can see a connection to both sides ⟷ which is a short form for representing two parallel nodes of opposite direction.

A directed multigraph, a multi-digraph as discussed earlier is basically where parallel edges between two nodes are allowed, but the edges have direction.

The mathematical definition: A multi-digraph is an ordered 4-tuple (N, E, S, T):
where,
N is a set of nodes,
E is a set of edges,
S : E→ N, assigning each edge its source node,
T : E → N, assigning each edge its target node.

Paths and Circuits

There is another important characteristic in a graph, a path, any route along the edges of a graph. It could be along only one edge joining two nodes or along multiple edges joining multiple nodes. A Eulerian Path (or Eulerian Trial) is a path (also called a trail) in a graph that moves along every edge exactly once (allows revisiting of nodes) basically, the Königsberg problem. A Eulerian Circuit (or Eulerian Cycle) is a Eulerian Path which starts and ends on the same node and the graph which contains it, is called Eulerian Graph. Every vertex in a Eulerian graph should have even degree, because the Euler’s Assertion says there can be at most two nodes with odd degree but that is true because we have considered 2 end points in a graph. But, in this case there are no end points, the path starts and ends at the same vertex so there is no end point, so there can’t be any node with odd degree in a Eulerian Graph.

Fig 10: Follow along the edges of this graph, in alphabetical order(A –> K) to get an Eulerian circuit. If you observe closely you will notice that each node has an even degree ensuing the existence of a Eulerian Circuit.

The Hamiltonian Circuit:

In 1857, the Irish Mathematician Rowan Hamilton made a puzzle (the Icosian game) which he later sold to a manufacturer for 25€. The game involved finding a special kind of path, a Hamiltonian circuit along the sides of a Dodecahedron, a platonic solid (already discussed in quasicrystals). A Hamiltonian Circuit is basically finding a path which visits each node exactly once and starts and ends at the same point, contrary to a Eulerian Circuit where each edge is visited exactly once.

Fig 11: A Hamiltonian circuit along six nodes.
Janusz.c, CC BY-SA 3.0,
Fig 12: The Platonic Solids

All the platonic solids have a Hamiltonian circuit, which was also proved, but the proof is beyond this blog. Let us a discuss the most popular Hamiltonian Circuit: A Hamiltonian Circuit along a Dodecahedron.

Fig 13: One possible Hamiltonian circuit along a Dodecahedron
cmglee, Arne Nordmann, CC BY-SA 4.0,
Fig 14: A 2D reconstruction of the Hamiltonian Circuit along the Dodecahedron.
Christoph Sommer, CC BY-SA 3.0

The Hamiltonian Circuits are a lot more challenging to characterise than eulerian Circuits and I will not go into detail about it as it involves a lot of math.

Applications of Graph Theory:

Ah yes, finally, the applications of this highly elaborate theory:

In Computer Science, graphs are very helpful to show the flow of communication, data organisation, the flow of computation, Neural Networks etc. (A Neural Network is basically a weighted graph, wherein we assign a weight/ a number to each node which is exactly a Neural Network)
It even has applications in Physics, Chemistry, Biology, Mathematics, GPS’s, Search engines, social sciences and even linguistics.

Graph Theory has many useful real-life applications, it is not just an intellectual ornament.

From Beautiful Tilings to Improbable Crystals

“There are no quasicrystals only quasi-scientists.” Linus Pauling the two time Noble Laureate.

So, what are these quasicrystals, who discovered them and why did Linus Pauling disagree with their existence. We shall begin to answer these questions.

The crystallographic restriction theorem:

A 3 Dimensional Lattice (crystal) can only have 1, 2, 3, 4, or 6-fold rotational symmetry.

Figure 1: Axes of symmetry

Basically, N-fold symmetry happens when u rotate a crystal in an axis by 360˚/N and the corresponding axis is called N-fold axis.

We can see that 5-fold symmetry is conspicuously absent. Why did I not mention a 5-fold symmetry? Its because a 5-fold symmetry isn’t possible, its not too hard to see why:

Figure 2a: Triangular Tiling (3-fold symmetry)
Figure 2b: Square Tiling (2-fold/4-fold symmetry)
Figure 2c: Hexagonal tiling (6-fold symmetry)

We can see that the triangular tiling has a 3-fold symmetry, the square tiling has a 2-fold and 4-fold symmetry and the hexagonal tiling has a 6-fold symmetry.

What if we tile pentagons?

Figure 3a: three pentagons arranged about a point leave a gap
Figure 3b: Four pentagons arranged about a point intersect

This is because interior angle of a pentagon is 108˚ and 3*108˚ is less than 360 so there is a gap and if u put 4 it becomes more than 360 so they overlap, this is the problem with 5 fold symmetry. There are much more comprehensive mathematical proofs on this but I prefer to not get into them.

So, there is a problem with pentagonal tiling and 5-fold symmetry. But this didn’t stop Kepler from trying:


Figure 4: Kepler’s drawings published in his book Harmonice Mundi

These figures have a certain fivefold symmetry, it isn’t too hard to see why, look at the star in the centre (labelled C) around it there are five more stars around it (labelled 1, 2, 3, 4, 5 respectively). The stars (formally named as “pentagrams” by Kepler) form a pentagon with Star C at the centre. Now if u rotate a pentagon about its centre by an angle of 72° (360°/5) it repeats itself, i.e five fold symmetry therefore disproving the crystallographic restriction theorem. But, actually he didn’t disprove the crystallographic restriction theorem because it has an apparent 5-fold symmetry i.e it as a single unit exhibits a five fold symmetry. For example a pentagon as a single unit shows five fold symmetry, but for it to be a crystal it should go on forever, meaning it should tile the plane and the tiling should have a five fold symmetry not a part of the tiling. What I mean is that Kepler made this tiling which has an apparent five fold symmetry but he couldn’t continue the tiling to infinity and if he did, it didn’t have that five fold symmetry. Nonetheless, its still fascinating that Kepler found a pattern with a certain five fold symmetry even though not quite.

“We can make a crystal out of molecules which individually have five fold symmetry but we cannot expect the lattice to have five fold symmetry.”

Another fascinating thing about Kepler is that in his book Denive Sexangula (On the Six Cornered snowflake) he said “There must be a cause why snow has the shape of a six-cornered starlet, it cannot be chance why always six.” The cause is not to be looked for in the material, for vapour is formless and flows, but in an agent. his ‘agent’, he suspected, might be mechanical: the orderly stacking of frozen ‘globules’ that represent “the smallest natural unit of a liquid like water” essentially a water molecule. The fascinating part is that there was no atomic theory in Kepler’s time. But Kepler seemed to be on the verge of understanding it.

Periodic and aperiodic tilings:

Figure 5a: Square Periodic Tiling
Figure 5b: Parallelogram Periodic Tiling

A periodic tiling is one where you can outline a region of the tiling and tile the plane by translating copies of that region (without any rotation or reflection). If the tiling is periodic it in turn means that the pattern will repeat after a fixed number of tiles. Hence the name.

An Aperiodic tiling is when the pattern never repeats till infinity. There are an infinite number of tiles which can tile the plane periodically and non-periodically.

Figure 6: Example of aperiodic tiling

As you can see in figure 6, if we cut each square of a checkerboard (periodic) into quadrilaterals we get an aperiodic pattern, but there is an arrangement of these same quadrilaterals which is periodic.

Wang Tiles:

Hao Wang, a mathematician proposed a type of tile which is modelled visually by equal sized squares with a colour on each edge, the rule was that it can be arranged such that the sides touching each other should have the same colour and also no rotation or reflection, only translation.

Figure 7: A set of 13 Wang tiles

The question with Wang Tiles is that do they tile the plane and if they do in what way (periodic/aperiodic).

Wang conjectured that “if a set of tiles tile the plane, then there exists a periodic tiling of the same tiles.” He also observed that the conjecture would imply an existence of an algorithm to decide whether a finite set of Wang Tiles can tile the plane. The idea of matching adjacent colours of tiles comes from dominoes, so the Wang tiles came to be known as Wang dominoes and the algorithmic problem of whether a set of tiles can tile the plane came to be know as the “domino problem.”

Basically, the domino problem asks whether there is an effective procedure that settles the tiling problem for all the sets.

In 1964 Wang’s student, Robert Berger solved this algorithm and proved that the Wang’s conjecture was wrong. He found a set of 20,426 tiles which can tile the plane but only non-periodically.

The way he proved this is rather interesting, but it is way beyond the scope of this blog.

Robert Berger later reduced his set to 104 tiles, and Hans Lauchlii found a set only requiring 40 Wang Tiles. In 1971 Raphael M Robinson found a set of 6 tiles (Figure 8a) based on Wang tiles which can only tile the plane non-periodically (Figure 8b). If you see Figure 8b a little closely you will observe that it is aperiodic, it doesn’t repeat.It is ordered, but it doesn’t repeat.

Figure 8a: The six Robinson tiles
Figure 8b: A set of Wang Tiles tiling the plane aperioidically © Claudio Rocchini / CC BY-SA

Then came Robert Penrose who reduced the number of times to just two, only two.

Penrose Tilings:

Roger Penrose, a mathematician, initially found a tiling with only two tiles which can tile the plane but only aperiodically. That means that the tiling will go on till infinity but never repeat, it will go on till infinity but the pattern won’t repeat. Fascinating isn’t it. Before Penrose found the set of only two tiles he initially found a set of six tiles which tile only non-periodically. These six tiles are based on pentagons, before we get into that I want to come back to Kepler tiling that we were discussing about. As I discussed earlier tiling three pentagons about a point leaves a gap, that’s why we see stars (pentagrams, sorry Kepler) and octagons in that Kepler tiling. They are actually gaps in the pentagonal tiling. The Original Penrose tiling isn’t too different from the Kepler tiling, the way Penrose constructed the tiling is actually quite interesting.

Figure 9a: Penrose arranged pentagons and clearly noticed the gaps
Figure 9b: He also noticed that these pentagons are part of a larger pentagon

Penrose tiled pentagons around one another and he clearly noticed the gaps, but more importantly he noticed that these pentagons were part of a larger pentagon. This gave him an idea what if he broke the pentagon into smaller pentagons and so on.

The mathematical method of doing this is called substitution, without going into the mathematics and rules of what substitution is lets try to understand it intuitively.

Figure 10: Image of a Substitution Tiling (By Dirk Frettloeh – , CC BY-SA 3.0, Link)

Substitution tiling is basically blowing up the tiling and then breaking it (dissecting.. Yuck) and then blowing it up and then dissect it and so on and so forth. Now, use this substitution in the pentagonal tiling.

Figure 11: The construction of the Penrose Tiling using the Substitution Rules

The figure on the right is the Original Penrose Tiling, it has 6 tiles: Pentagon, Diamond, Star (Pentagram), 3/5th of star (Boat). Wait what, I said 6 tiles but I have mentioned only four. This is because, for ensuring an aperiodic tiling there are some matching rules. Thats why the colour of the tile is important too, hence the 6 tiles (A Red Pentagon, Blue Pentagon, Grey Pentagon, Yellow Diamond, Light Blue Boat and Green Pentagram).

The Second Penrose Tiling:

The 2nd Penrose Tiling is the Kite and Dart Tiling.

Figure 12: The Kite and Dart Tiles used in the Tiling (Geometry guy at English Wikipedia, CC BY-SA 3.0, via Wikimedia Commons)
Figure 13: The combinations possible with the Matching rules(Geometry guy at English Wikipedia, CC BY-SA 3.0, via Wikimedia Commons)

The matching rule: The red and green lines must form circular arcs (as shown in Fig 13) for forming an aperiodic tiling. Another matching rule presenting the same tiling is matching the white and black dots shown in Fig 12 which produces the same combination of tilings as in Fig 13.

Construction:

Figure 14: A Gif showing the Construction of the Kite-Dart Penrose Tiling with (Taktaal, CC BY-SA 4.0)

Fig 14 shows the construction of the tiling using deflations, the resulting tiling has a certain five-fold symmetry. Just bear in mind that i haven’t discussed what inflation and deflation i.e the substitutions in depth, because it isn’t needed in the topic I’m trying to discuss. There are a lot more stuff about inflation and deflation (Deflation of a sun, star etc.)

Quasicrystals:

Before we discuss a quasicrystal, we need to know the definition of a crystal.

A Crystal is a solid composed of atoms which are arranged periodically in all 3 Dimensions.

A Quasicrystal is a structure that is ordered but non periodic, so it is basically a 3D non periodic tiling. A normal crystal is supposed to be a structure that repeats, it is made up of unit cell but Quasicrystals aren’t made up of any unit. This is because the pattern never repeats in an aperiodic tiling so you can never find a unit that can finish the pattern. In any aperiodic pattern since the pattern never repeats you can never find out where you are on the pattern since the pattern never repeats you can zoom out trying to gather as much information as you want but you can never find where you are on the pattern for that you have to see the whole pattern which is impossible as it is infinite.

Mathematically many aperiodic tilings and quasicrystals were made but, no-one had found naturally occurring quasicrystals. The Opening Quote of this Blog: “There are no Quasicrystals only Quasi-scientists” (Linus Pauling). The reason Linus Pauling said this and highly disagreed with the concept of quasicrystals is because crystals are built by putting atoms together locally, but in the case of the Penrose Tiling there seemed to be some long range coordination in order for it to tile the plane, if you place a tile wrongly then you encounter some problems when tiling the plane it just wont tile after a point. So there is a problem because we need long range coordination a quasicrystal can never form.

In 1982, Dan Shechtman observed a distinct ten fold diffraction pattern, this was made during a routine investigation of a rapidly cooled alloy of aluminium and manganese.

Figure 15: The distinct 10 fold diffraction pattern observed by Dan Schechtman (©Materialscientist)

Schecthman got surprised on finding a diffraction pattern with 10-fold symmetry, because a diffraction pattern of a normal periodic crystal can only have 1, 2, 3, 4, 6 fold symmetry, just like the structure of a crystal which also prohibits 5 fold symmetry and anything above 6 fold symmetry. Schechtman got surprised on finding such a pattern which had more than 6 fold symmetry, he didn’t have an explanation for his result.

In the same year Shecthman took his results to Ilan Blech, who said that these diffraction patterns were seen before. This pattern was left unexplained until 1984, when Blech took a second look at the pattern. A common explanation for a 10 fold symmetry is the existence of twins, which makes a pseudo symmetry. What it means is that you take 10 twins (copies) of an alloy, each twin produces a normal diffraction pattern but the superposition of all the 10 diffraction patterns results in a pseudo five fold symmetry.

Figure 16: An example of a pseudo five-fold symmetry made with 10 identical twins of a Al-Fe periodic crystal.

Blech, first disproved the existence of twins in the Al-Mn alloy by a series of experiments. So no twins, Blech was left with only option an aperiodic crystal, a crystal which isnt restrained to form only 2, 3, 4, 6 fold rotational symmetrical diffraction pattern because it is aperiodic.

Blech trying to explain this pattern thought of a completely new structure made up of cells, without translational periodicity (aperiodic). Blech used a computer simulation to calculate the diffraction intensity from such a structure which doesn’t have translational symmetry but isn’t random. He named this structure “polyhedral”. The computer diffraction pattern that arose almost exactly matched the pattern observed by Blech. This gave them the courage to collectively write a paper titled “The Microstructure of Rapidly Solidified Al6Mn” he initially published it in the Journal Of Applied Physics (JAP) but it was rejected and he ended up publishing it in the Physical Review Letters(PRL).

Belch had termed the structure as polyhedral, what does that mean?

Figure 17: The five platonic solids which are the possible crystal structures for a quasicrystal

The five platonic solids shown in Fig 17 are the possible structures for quasicrystals, but before this paper it was well established that these platonic solids cannot be the structures for a crystal as they are full of 5 fold symmetries, which is non probable for a normal crystal but you can have these 5 fold symmetries in quasicrystals.

The publishing of this paper caused a lot of excitement in the scientific community. Not everyone was excited tho, as I mentioned previously Linus Pauling heavily disagreed with the existence of quasicrystals. In fact he spent the last decade of his life trying to prove that quasicrystals are nothing but just twinned periodic crystals but his efforts went in vain as all the models he proposed were disproved. By the time of his passing he was the only prominent opponent to quasicrystals.

I had said that the platonic solids were the possible structures for a quasicrystal but in-fact most of the quasicrystals found in nature are in the icosahedral phase.

Figure 18: Projection of the diffraction pattern using Petrie vectors to form a icosahedron (Jgmoxness)

A year after the paper was published, 12-fold symmetry was found in Ni-Cr particles. Soon after 8-fold symmetry was reported in V-Ni-Si and Cr-Ni-Si alloys. As time passed by hundreds of quasicrystals were reported, many stable quasicrystals were found too, opening the door to applications of the material. In 2011, Paul Steinhardt found a naturally occurring quasicrystal near the Khatykra river. The naturally quasicrystal phase, Al63Cu24Fe13, named icosahedrite was suspected to be of meteoric origin. Further research on the Khatykra meteorites revealed another naturally occurring quasicrystal(Al71Ni24Fe5), it was stable in the temperature range of 1100-1200K suggesting that quasicrystals were formed by rapid quenching of a meteorite during an impact-induced shock.

Schecthman, was awarded the Nobel prize in chemistry in 2011 for his work on quasicrystals, he led a shift in the understanding of structures. Coming to the topic of Nobel prizes, Robert Penrose was awarded a joint Nobel prize in Physics, that had nothing to do with the tilings but was awarded for his theoretical work on black holes.

As you know tiling of plane with pentagons is impossible, but you can tile it on a sphere forming a dodecadron.

Figure 19: A dodecahedral Ho-Mg-Zn quasicrystal, pentagons tiled on a sphere in 3 dimensions

After reading this long blog you might have a question, I had mentioned that there is some long range coordination required for the Penrose tiling, but then how did a quasicrystal form? The reason that quasicrystals can exist is because the matching rules for the curved lines on the tiles aren’t strong enough i.e you cant tile the plane without long range coordination, if you misplace a tile the tiling stops. But, if you put matching rules for the corners of the tiles, those rules are strong enough to ensure no long-range coordination.

Take Home message:

Quasicrystals could have been found long ago, after all they are materials within our reach. Then why weren’t they found? Due to the lack of self belief, they were scared to publish their discovery thinking the scientific community will criticise them forever.


“Never let anyone’s opinion stop you from doing anything”