Tag Archives: graph theory

When the intuition is correct

Standard

Before starting college I read Paul Zeitz’s The Art and Craft of Problem Solving (a must read book along with the books by Arthur Engel and Terence Tao) and after the first example to illustrate Psychological Strategies he writes (pp. 15):

Just because a problem seems impossible does not mean that it is impossible. Never admit defeat after a cursory glance. Begin optimistically; assume that the problem can be solved. Only after several failed attempts should try to prove impossibility. If you cannot do so, then do not admit defeat. Go back to the problem later.

And today I will share a problem posed by August Ferdinand Möbius around 1840:

Problem of the Five Princes:
There was a king in India who had a large kingdom and five sons. In his last will, the king said that after his death the sons should divide the kingdom among themselves in such a way that the region belonging to each son should have a borderline (not just a point) in common with the remaining four regions. How should the kingdom be divided?

The hint is in the title of this blog post. The solution is easy, hence I won’t discuss it here. The reader is invited to write the solution as a comment to this post.

What is Topology?

Standard

A couple of years ago, I was introduced to topology via proof of Euler’s Polyhedron formula given in the book “What is Mathematics?” by Richard Courant and Herbert Robbins. Then I got attracted towards topology by reading the book “Euler’s gem – the polyhedron formula and the birth of topology” by David S. Richeson. But now after doing a semester course on “introduction to topology” I have realized that all this was a lie. These books were not presenting the real picture of subject, they were presenting just the motivational pictures. For example, this is my favourite video about introduction to topology by Tadashi Tokieda (though it doesn’t give the true picture):

Few months ago I read the book “The Poincaré Conjecture” by Donal O’Shea and it gave an honest picture of algebraic topology. But, then I realized that half of my textbook on topology is about point-set topology (while other half was about algebraic topology). This part of topology has no torus or Möbius strip (checkout this photo) but rather dry set theoretic arguments. So I decided to dig deeper into what really Topology is all about? Is is just a fancy graph theory (in 1736, both Topology and graph theory started from Euler’s Polyhedron formula) or it’s a new form of Geometry which we study using set theory, algebra and analysis.

The subject of topology itself consists of several different branches, such as:

  • Point-Set topology
  • Algebraic topology
  • Differential topology
  • Geometric topology

Point-set topology grew out of analysis, following Cauchy’s contribution to the foundations of analysis and in particular trigonometric representation of a function (Fourier series). In 1872, Georg Cantor desired a more solid foundation for standard operations (addition, etc.) performed on the real numbers. To this end, he defined a Cauchy sequence of rational numbers. He creates a bijection between the number line and the possible limits of sequence of rational numbers. He took the converse, that “the geometry of the straight line is complete,” as an axiom (note that thinking of points on the real line as limits of sequence of rational numbers is “for clarity” and not essential to what he is doing). Then Cantor proved following theorem:

If there is an equation of form \displaystyle{0=C_0+C_1+\ldots +C_n+\ldots} where C_0 = \frac{d_0}{2} and C_n = c_n\sin{(nx)} +d_n\cos{(nx)} for all values of x except those which correspond to points in the interval (0,2\pi) give a point set P of the \nuth kind, where \nu signifies any large number, then d_0=1, c_n=d_n=0

This theorem lead to definition of point set to be a finite or infinite set of points. This in turn lead to definition of cluster point, derived set, …. and whole of introductory course in topology. Modern mathematics tends to view the term “point-set” as synonymous with “open set.” Here I would like to quote James Munkres (from point-set topology part of my textbook):

A problem of fundamental importance in topology is to find conditions on a topological space that will guarantee that it is metrizable…. Although the metrization problem is an important problem in topology, the study of metric spaces as such does not properly belong to topology as much as it does to analysis.

Now, what is generally publicised to be “the topology” is actually the algebraic topology. This aspect of topology is indeed beautiful. It lead to concepts like fundamental groups which are inseparable from modern topology. In 1895, Henri Poincaré topologized Euler’s proof of Polyhedron formula leading to what we call today Euler’s Characteristic. This marked the beginning of what we today call algebraic topology.

For long time, differential geometry and algebraic topology remained the centre of attraction for geometers.But, in 1956, John Milnor discovered that there were distinct different differentiable structures (even I don’t know what it actually means!) on seven sphere. His arguments brought together topology and analysis in an unexpected way, and doing so initiated the field of differential topology.

Geometric topology has borrowed enormously from the rest of algebraic topology it has returned very scant interest on this “borrowed” capital. It is however full of problems with some of the simplest, in formulation, as yet unsolved. Knot Theory (or in general low-dimensional topology) is one of the most active area of research of this branch of topology. Here I would like to quote R.J. Daverman and R.B. Sher:

Geometric Topology focuses on matters arising in special spaces such as manifolds, simplicial complexes, and absolute neighbourhood retracts. Fundamental issues driving the subject involve the search for topological characterizations of the more important objects and for topological classification within key classes.
Some key contributions to this branch of topology came from Stephen Smale (1960s), William Thurston (1970s), Michael Freedman (1982), Simon Donaldson (1983), Lowell Edwin Jones (1993), F. Thomas Farrel (1993), … and the story continues.

References:

[1] Nicholas Scoville (Ursinus College), “Georg Cantor at the Dawn of Point-Set Topology,” Convergence (May 2012), doi:10.4169/loci003861

[2] André Weil, “Riemann, Betti and the Birth of Topology.” Archive for History of Exact Sciences 20, no. 2 (1979): 91–96. doi:10.1007/bf00327626.

[3] Johnson, Dale M. “The Problem of the Invariance of Dimension in the Growth of Modern Topology, Part I.” Archive for History of Exact Sciences 20, no. 2 (1979): 97–188. doi:10.1007/bf00327627.

[4] Johnson, Dale M. “The Problem of the Invariance of Dimension in the Growth of Modern Topology, Part II.” Archive for History of Exact Sciences 25, no. 2–3 (December 1981): 85–266. doi:10.1007/bf02116242.

[5] Lefschetz, Solomon. “The Early Development of Algebraic Topology.” Boletim Da Sociedade Brasileira de Matemática 1, no. 1 (January 1970): 1–48. doi:10.1007/bf02628194.

Cross Diagonal Cover – IV

Standard

While discussing this problem with Dr. Shailesh Shirali, he commented that there has to be a way to phrase the problem in terms of a ray of light being reflected off the walls of the rectangle, bouncing around, proceeding from one corner to some other corner.

The problem in re-stating my problem in “light reflection” form was that reflections must be from center of squares and this is not the way light “actually” reflects from surfaces. But, I clubbed that idea with “graph theory” (directed graphs), which actually answers the first question I asked in my previous post:

Why no filled square has more than 2 crosses?

As per my “Cross diagonal cover algorithm” we can’t retrace a path and each square has just two diagonals. Hence, if we replace all the squares by their centers then each center is of degree two (i.e. can allow intersection of at most two distinct paths). Hence proving that no filled square can have more than 2 crosses. For example:

New Doc 22_1

Now moving to the bigger question of counting the total number of filled squares, there hasn’t been much progress yet (even on arriving at a concrete conjecture). But, Prof. Amritanshu Prasad wrote a SageMath  program for my algorithm which enables us to find number of the filled squares for individual cases without actually drawing them! For Example: for m=101 , n=102 grid, there will be 5151 = (101 * 102 )/ 2 filled squares. Pretty cool 🙂

SageMath is is an open source implementation of mathematics and scientific software based on Python 2.  Unfortunately, since the SageMath program is essentially a Python script I am not allowed to embed  it in my WordPress.com blog. But, motivated by my discussions with Ms. Marina Ibrishimova, I tweaked Prof. Prasad’s original source-code and added comments (initialized by #) to make it self explanatory.

Here is the SageMath (or Python) code to count the number of filled squares for 2 \leq m\leq n\leq 10

#-----START OF PYTHON FUNCTION FOR CROSS DIAGONAL COVER ALGORITHM-----

def cover(m,n):
#a function to count the number of squares covered in a grid with m rows
#and n columns
    xinc = 1
#we will use this variable to increment (or decrement) the value of
#x-coordinate (row position) by 1 unit after each step
    yinc = 1
#we will use this variable to increment (or decrement) the value of
#y-coordinate (column position) by 1 unit after each step
    pos = [1, 1]
#we are assuming our grid to have at least 2 rows and 2 columns
#and will initialize counting from (1,1) position.
    visited = [[0, 0], [1, 1]]
#since we start from (1,1) position, we implicitly assume to have
#counted (0,0) position.
    while pos != [m-1, 0] and pos != [0, n-1] and pos != [m - 1, n - 1]:
#whenever we reach any corner the algorithm terminates, so need to include
#position of other three corners apart from starting corner in condition.
          if pos[0] in [0, m-1]:
#evaluates to true if x-coordinate of current position is a
#member of the collection [0,m-1]
             xinc = - xinc
#if x-coordinate is either 0 or m-1 then we will switch diagonal
#by switching the sign of xinc
          if pos[1] in [0, n-1]:
#evaluates to true if y-coordinate of current position is a member
#of the collection [0,n-1]
             yinc = -yinc
#if y-coordinate is either 0 or n-1 then we will switch diagonal
#by switching the sign of yinc
          pos[0] += xinc
#update the x-coordinate of new position as x(new) = x(old) + xinc,
# where xinc = 1 or -1.
          pos[1] += yinc
#update the y-coordinate of new position as y(new) = y(old) + yinc,
# where yinc = 1 or -1.
          if not (pos in visited):
#if this new state is not there in visited positions list
             visited.append([pos[0], pos[1]])
#then add this new position to the list of visited positions.
    return visited 

#---------------END OF FUNCTION---------------

#we will write a small code to be able to use above function to find number of
#filled squares for all grids where m,n lie between 1 and 11 (both excluded).

for i in range (2, 11):
#The range() function provides an easy way to construct a list of integers.
#The range() function only does numbers from the first to the last,
#not including the last.
    for j in range(i, 11):
        print i, j, len(cover(i, j))
# len(indata) counts the bytes of data in indata here it
#counts the number of elements is visited list.

To run the above code, please copy-paste it in SageMathCell and click evaluate button. You will get the list displaying m, n and the number of filled squares in each of the grid (with 1<m,n<11).

In case you want to understand above Python function, here is an illustration when m=3 and n=4:

New Doc 23_1

Note that though (1,1) position is encountered twice but it is added to “visited squares” list only once.

So far I haven’t been able to derive a useful interpretation even after getting access to lot of data. I hope to formulate a conjecture soon…

 

Bringing Maths out of Marriage

Standard

I will consider following definition of marriage:

the legally or formally recognized union of a man and a woman as partners in a relationship.

It can be difficult, due to the emotions we have, to find suitable partner. But mathematicians have tried to solve this problem. Pretty cool, huh!

(1) Hall’s Marriage Theorem:  We have n boys, each of whom has several girlfriends, under what conditions can we marry off the boys in such a way that each boy marries one of his girlfriends?

We claim that this problem has a solution if and only if for every k, 1\leq k\leq n, every set of k boys has collectively at least k girlfriends.

hall

The connecting lines indicate whether this man and woman like each other. (boyfriend-girlfriend relationship) [By Greg Graviton , Applications of Measure, Integration and Banach Spaces to Combinatorics]

Mathematically, we can restate it in graph theoretic language as

Let G be a bipartite graph with bipartition V = X \cup Y. Then G contains a matching that saturates every vertex in X if and only if |N(S)| \geq |S| for every subset S of X

where, N(S) is defined to be the set of all vertices adjacent to any set S of vertices in graph G and |.| denotes “the number of elements in”.

The proof of this theorem is by Induction on n. See this Cut the Knot article for proof. 

 

(2) Stable Marriage Problem:  There are n women and n men in a community. Each woman ranks each man in accordance with her preference for that man as a spouse. No ties are allowed, so that if a woman is indifferent between two men, we nonetheless require that she express some preference. The preferences are to be purely ordinal, and thus each woman ranks the men in order 1,2, …, n. Similarly, each man ranks the woman in the order 1,2,…, n.

We would like to arrange marriages between the men and women so that there is not a man and a woman who prefer one another to their spouses. Such marriages are  called stable. Does there always exist a stable marriage?

We claim that the answer to this question is YES! We just need to follow Gale–Shapley algorithm.  Watch this awesome Numberphile video explaining this

 

Other articles in same spirit: 

 

Maze

Standard

Solving mazes is a great time-pass, if you “too” have nothing to do just try to solve this maze made by me (very easy one, can be solved within few seconds)

New Doc 8_1

Very easy example of maze

Since I am writing about mazes, there must be something mathematical about them. Indeed “solving a maze” is a NP-complete problem [Non-deterministic Polynomial-time solvable problem], one of most popular class of problems in Theoretical Computer Science. But, no surprise here, since lot of puzzles like Minesweeper, sudoku etc. too are NP-complete.

Leonhard Euler was one of the first to analyze plane mazes mathematically, and in doing so made the first significant contributions to the branch of mathematics known as topology.

Mazes containing no loops are known as “standard”, or “perfect” mazes, and are equivalent to a tree in graph theory. Thus many maze solving algorithms are closely related to graph theory. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree (dead ends become the leaves of the tree.).

To make my maze I used “adding walls algorithm” i.e. I laid a set of obstructions within an open area.  Can you tell whether my maze above is “perfect” one??

As it turns out, there are various maze generation as well as maze solving algorithms. A detailed discussion of these can be found at: http://www.astrolog.org/labyrnth/algrithm.htm

Also, there is an interesting article on Maze solving using image analysis: http://www.crisluengo.net/index.php/archives/277