## Real MATHEMATICS – Graphs #5

Cruel Traffic Light

I have to drive past the same crossroad almost every single day. Obviously I stop at the longest-lasting traffic light of the crossroad. Within time I started loving these moments because it gave me a chance to think my life over. Though, it doesn’t take too long for me to start thinking about mathematics.

One of those days I found myself questioning the traffic lights and their relationship with mathematics. (After all mathematics is everywhere; isn’t it?) Soon after I realized that there was my beloved graph theory behind traffic lights.

Light #1

Let’s assume a one-way street with two traffic lights: One for the vehicles (we’ll call it A), other for the pedestrians (we’ll call it B): In such situation we have to avoid accidents. This means whenever A has green light, B must have red light and vice versa. We will not take account of the situation when both lights are red. Because even though there won’t be any accident, neither of the sides will be standing still (which is nonsense): All these can be shown using graph theory: Lights will be represented by dots. Dots in a graph will be connected with lines if they are not in the same color: Same thing can be shown with maps: If A and B are two neighboring countries, they should be colored in different colors to avoid confusion: Light #2

This time we will assume a two-way street with three traffic lights: Two for the vehicles from opposite sides (we’ll call them A and B), and one for the pedestrians (we’ll call that C): In such a situation when C is red, either or both of A and B should be green. When C is green, then both A and B should be red: We’ll skip the situation where all three of them are red as no one would move in such situation.

We can show these using graph theory and map coloring as follows: Since we set all the rules graphs make it much easier and clearer to understand the situations.

Light #3

Finally we have a two-way street (A and B), a right turn (C) and two pedestrian lights (D and E) as follows: This time it is a much complex situation: Although using graph theory makes it all easier for us to understand:

How Many Colors?

We will color the following graphs using the same rules we just established above: If two dots are connected with a line, then those dots must have different colors.

#### Chromatic Numbers: Whenever a graph is being colored, ambition is the use the least number of colors. This number is also known as the chromatic number of a graph.

Here we need 3 colors. Hence chromatic number of the graph is 3. Let’s add one more dot and line to the graph:

This time chromatic number of the graph becomes 2. We’ll add another dot and line:

Now chromatic number becomes 3 again. Let’s add a dot and a line for the last time:

Chromatic number is back to 2.

To be continued…

One Wonders…

What did just happen? What did you notice? Why is it happening?

How can you increase the chromatic number?

M. Serkan Kalaycıoğlu

## Real Mathematics – Strange Worlds #10

Tearing Papers Up

Use a stationery knife and cut an A4 paper. You will end up with pieces that have smooth sides. Hence you can use Euclidean geometry and its properties in order to find the perimeters of those pieces of papers:

However, when you tear a paper up using nothing but your hands you will be getting pieces that have rough sides as follows:

If you pay enough attention you will that the paper on the right looks just like map of an island.

In the previous article I used properties of Euclidean geometry to measure the length of a coastline and found infinity as an answer. Since those two torn papers look like an island or a border of a country, perimeters of those pieces of papers will also tend to infinity. This is indeed a paradox.

This paradox shows that Euclidean geometry is not useful when it comes to measure things/shapes that have roughness.

Birth of Fractals

##### Benoit B. Mandelbrot

There are only shapes consist of dots, lines, curves and such in Euclidean geometry. On the other hand shapes of some natural phenomena can’t be described with Euclidean geometry. They have complex and irregular (rough) shapes. This is where we need a new kind of geometry.

In 1967 mathematician Benoit Mandelbrot (1924-2010) published a short article with the title “How long is the coast of Britain?” where he gave an ingenious explanation to coastline paradox. Furthermore, this article is accepted as the birth of a brand new mathematics branch: Fractal geometry.

The word fractal comes from “fractus” which means broken and/or fractured in Latin. There is still no official definition of what a fractal is. One of their most definitive specialties is “self-similarity”. Fractals look the same at different scales. It means, you can take a small extract of a fractal object and it will look the same as the entire object. This is why fractals are self-similar. ##### Romanesco broccoli has a fractal shape as you zoom in you will see shapes that look the same as the whole broccoli.

Fractals have infinitely long perimeters. Therefore measuring a fractal’s perimeter or area has no meaning whatsoever.

Coastlines are fractals also: As you zoom in on a coastline or a border line, it is possible to see small versions of the whole shape. (Click here for a magnificent example.) This means that if we had a way to measure a fractal’s perimeter, we can solve the coastline paradox.

So the big question is: What can one do to measure a fractal?

Dimension

According to Mandelbrot, it is possible to measure a fractal’s roughness degree; not its perimeter nor its area. Mandelbrot called this degree fractal dimension. He realized that fractals have different dimensions than the shapes we know from Euclidean geometry.

I will be talking about dimensions in Euclidean geometry before moving on to explaining how one can calculate the dimension of a fractal.

In the Euclidean geometry line has 1, plane has 2, space has 3 dimensions and so on. Teachers use specific examples when this is taught in schools. For space, a teacher asks his/her students to observe any corner of a ceiling: There are 3 different directions one can choose to walk from that corner. While this is a valid example, it only shows what 3 dimensions look like.

Q: How can one calculate the dimension degree of an object/shape?

Line

Let’s draw a straight line and cut it into two halves:

If straight line had length 1, each segment now has length 1/2. And there are 2 segments in total.

Continue cutting every segment into two halves: Now each segment has length ¼ and there are 4 line segments in total.

At the point a formula breaks out:

(1/Length of the line segments)Dimension Degree = Number of total line segments

Let me call dimension degree as d.

For 4 line segments:

(1/1/4)d = 4

4d  = 4

d = 1.

This concludes that line has 1 dimension.

Square

Let’s draw a square that has unit side lengths. At first cut each side into two halves:

There will be 4 little replicas of the original square. And each of those replicas has side length ½.

Apply the formula:

(1/1/2)d = 4

2d  = 4

d = 2.

Let’s continue and divide each side into two halves. There will be 16 new squares: Each side of these new squares has length ¼. Apply the formula:

(1/1/4)d = 16

4d = 16

d = 2.

This means that square has 2 dimensions.

To be continued…

One wonders…

Apply the same method and formula to find the dimension of a cube.

M. Serkan Kalaycıoğlu