Monthly Archives: March 2016

Mar29

Bringing Maths out of Marriage

Posted on March 29, 2016 by math

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.

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

Colourful complex functions

Posted on March 21, 2016 by math

Standard

Recently I became curious about functions defined from $\mathbb{C}$ to $\mathbb{C}$ and I asked myself following question:

How would the complex functions look like if we try to plot them?

Graphs of complex functions lie in $\mathbb{C}^2$ , which can be identified in a natural way with $\mathbb{R}^4$ , real four-dimensional space.

So I jumped to SageMath and plotted $z^2$


sage: f(z) = z^2
sage: complex_plot(f, (-5, 5), (-5, 5))

graph of z^2 plotted using SageMath Version 7.0

Now this looked like an enigma to me. What do the colours stand for? As usual, there is an interesting entry about this on Wikipedia, Colour wheel graphs of complex functions.

I digged further and discovered that these are called “2D colour maps” and is one of many other ways of visualizing complex functions, like 3D models, 2D vector plots, 4D perspective projection, conformal maps…

1024px-HSL_color_solid_cylinder_alpha_lowgamma

HLS Cylinder (By SharkDderivative [CC BY-SA 3.0 or GFDL], via Wikimedia Commons)

But what is the colour map? The colour map uses the HLS colour system (“hue-lightness-saturation”). HLS is a cylindrical-coordinate representations of points in an RGB color model. In cylinder, the angle around the central vertical axis corresponds to “hue”(i.e. shade of a colour) , the distance from the axis corresponds to “saturation”, and the distance along the axis corresponds to “lightness”.

The argument φ and modulus r locate a point on an Argand diagram i.e. complex plane.(By Kan8eDie [CC BY-SA 3.0, CC BY-SA 3.0 or GFDL], via Wikimedia Commons)

The hue represents the argument (also called phase angle) of the complex number z. The absolute value (also called magnitude or modulus) is given by the lightness of the colour. All colours of the colour map have the maximal saturation (with respect to the given lightness).

HLS Colour Wheel (source: iliasky.com)

Positive real numbers always appear red. The primary colours appear at phase angles $\frac{2 \pi}{3}$ (green) and $\frac{4\pi}{3}$ (blue). The subtractive colours yellow, cyan, and magenta have the phases $\frac{\pi}{3}$ , $\pi$ , and $\frac{5\pi}{3}$ .

The poles of a complex function are white, the zeros are black.

Finally, to conclude [from : Visual quantum mechanics : selected topics with computer-generated animations of quantum-mechanical phenomena by Bernd Thaller.]

This colour map is obtained by a stereographic projection from the surface of the three-dimensional colour space (in the hue-lightness-saturation system) onto the complex plane.

An appropriately colored surface graphics or a density graphics can give a useful graphical representation of a complex valued function. Another example of complex valued function, a wave function, is given here:

Visualizations of a wave function in two dimensions. The left graphic shows the function as a “density plot” with additional contour lines for the absolute value. In the three-dimensional surface plot the height of the surface gives the absolute value of the wave function. (By Bernd Thaller, created using Mathematica. © 2000 Springer-Verlag New York, Inc.)

For more such graphs, visit Bernd Thaller’s Gallery of complex functions .

Mar15

Coq proved four colour theorem

Posted on March 15, 2016 by math

Standard

Coq Proof Assistant

Coq means rooster in French. But it has been named after the name of its inventor, Thierry Coquand. It is an interactive theorem prover. It is not an automated theorem prover but includes automatic theorem proving tactics. It mechanically checks proofs of mathematical assertions. Vladimir Vocvodsky (Fields Medalist) is a big supporter of such proof verification computer programs.

World map with four colours (By Fibonacci [CC BY-SA 3.0], via Wikimedia Commons)

In 1852, Francis Guthrie, a graduate student at University College in London, wrote a letter to his younger brother, containing what he thought would be a simple little puzzle. He wrote

Can every map drawn on the plane be coloured with four colours so that no two regions having a common border have the same colour?

In 1879, Alfred Kempe demonstrated that five colours suffice. Kempe’s proof was an elegant attempt to solve four colour problem, you should read this article by Timothy Sipak (Alma College). In 1922 Philip Franklin proved that all maps with 26 or fewer regions can be 4-coloured. This wasn’t terribly edifying in itself, but Franklin’s method paved the way for the eventual solution by introducing the idea of a reducible configuration.

In 1950, Heinrich Heesch, who had invented a clever method for proving that many configurations are reducible, said that he believed the four-colour theorem could be proved by finding an unavoidable set of reducible configurations. The only difficulty was to find one –and it wouldn’t be easy, because some rule-of-thumb calculations suggested that such a set would have to include about 10,000 configurations. With the computers then available, it would have taken about a century to deal with an unavoidable set of 10,000 configurations. Though modern computers can do the job in a few hours!

In 1976, Kenneth Appel and Wolfgang Haken managed to reduce the number of configurations to be tested to 1,936 cases and went through all of them with aid of a computer program. After running the program for two months they concluded that four colours will always suffice. This proof was controversial because the majority of the cases were checked by a computer program, not by hand.

In 2008, George Gonthier and Benjamin Werner, proved four colour theorem using Coq. Unlike the programs used by Appel and Haken, Coq automatically generates a proof on the basis of the algorithm that has been selected. So we have is a proof of which 0.2% was done by a human being (that matters and must be gotten right) and other 99.8% by a machine (since Coq is certified to be bug free, we can be sure that rest is correct). The shortest known proof of the four colour theorem today still has over 600 cases and is a proof by exhaustion.

For further information, see: http://mathoverflow.net/q/164947

To know more about “automatic theorem proving” see: http://hardmath123.github.io/meet-the-robinson.html

Mar7

Dice & Isohedron

Posted on March 7, 2016 by math

Standard

I enjoyed playing Ludo in my childhood. I believed that the there is only 6 sided dice like these:

source: https://goo.gl/z47G2I

Recently, while studying probability, I came to know that we can make dice corresponding to all platonic solids like:

source: https://goo.gl/y529kw

So, I became curious to explore the mathematics involved behind choosing the number of sides of a dice. As usual, Wikipedia was my starting point. There I discovered a 1989 paper by two Stanford University professors, Persi Diaconis & Joseph B. Keller, titled, “Fair Dice“. Here are few lines which I would like to quote from the paper:

In the beginning they say:

…We shall say that a convex polyhedron is fair by symmetry if and only if it is symmetric with respect to all its faces. This means that any face can be transformed into any other face by a rotation, a reflection, or a combined rotation and reflection, which takes the polyhedron into itself. The collection of all these transformations of a given polyhedron is called its symmetry group….

But towards the end of paper they say:

…There are other fair polyhedra which are not symmetric. To show this we consider, for example, the dual of the n-prism, which is a dipyramid with 2n identical triangular faces. We cut off its two tips with two planes parallel to the base and equidistant from it…. Therefore by continuity there must be cuts for which the two new faces and the 2n old faces have equal probabilities. ….

And the last line reads:

The problem of characterizing all fair dice, not just those which are fair by symmetry or by continuity, is still unsolved.

For the solved part, characterizing all fair dice by symmetry and continuity, we have a specific name for the class of polyhedrons. We call them Isohedron, defined as [source: MathWorld]

An isohedron is a convex polyhedron with symmetries acting transitively on its faces with respect to the center of gravity. Every isohedron has an even number of faces.

There are 30 of isohedrons (including finite solids and infinite classes of solids). All Platonic solids are isohedra.

http://www.mathpuzzle.com/Fairdice.htm contains a complete list of all possible Isohedrons.

If you are also fascinated by the variety of dice available do check out: World’s Largest Dice Collection (Guinness World Record).

Mar4

Cauchy’s Crazy Induction

Posted on March 4, 2016 by math

Standard

Many people know about AM-GM inequality, we have that for any list of $n$ nonnegative real numbers $a_1, a_2, \ldots , a_n$ ,

$\sum_{k=1}^{n} a_k \geq n \sqrt[n]{\prod_{k=1}^{n}a_k}$

While reading about Arithmetic Mean-Geometric Mean Inequality’s proof at Wikipedia, I came across the reference to Augustin Louis Cauchy‘s original proof:

Cauchy, Augustin-Louis (1821). Cours d’analyse [source: https://archive.org/details/coursdanalysede00caucgoog ]

Here Cauchy used a crazy type of induction process, which can be stated as:

Step 1 : [The base case] Show that the statement is true for an integer .
Step 2: [The inductive step] This has two parts:

$P(k) \Rightarrow P(2k)$
$P(k) \Rightarrow P(k-1)$

Completing these two steps proves that the statement is true for all positive integers .

It has a very distinctive inductive step, and though it is rarely used, it is a perfect illustration of how flexible induction can be. The first part of the inductive step shows that the statement is true for larger and larger values of $n$ . But that leaves a lot of gaps in between. The second part ensures that all the gaps are taken care of.

I became curious to know about other instances when we can use this from of induction. So here are some other theorems which can be proved using Cauchy’s Crazy Induction (for proof refer to [2] given at end of this post):

1) Ky Fan inequality: If $x_i$ with $0 \leq x_i \leq \frac{1}{2}$ for $i = 1, \ldots, n$ are real numbers, then