Tuesday, December 30, 2008

Polynomials difference puzzle

Here is a cute puzzle about difference of polynomials.

Thursday, November 20, 2008

My Favorite Math Movies

Here are my top five math movies, along with my favorite quotes. I will not talk about the storylines, because I don't want to spoil the fun.

N is a number : I was sad that I did not see Paul Erdös in person, until I saw this documentary. This is a documentary about Paul Erdös, the wandering mathematician, the man who loved only numbers. Watch this if you want to see him walk, talk, crack math jokes and inspire people around him. You can also see other famous mathematicans collaborating with him.
  • Euler, when he died, he simply collapsed and said "I am finished". An when I told this story, somebody callously remarked : "Another conjecture of Euler's was proven".
  • What is the purpose of life ? "Prove and conjecture and keep the SF's score low".
Pi : I should warn you that this is a disturbing move. Here are couple of quotes.
  • Restate my assumptions: One, Mathematics is the language of nature. Two, Everything around us can be represented and understood through numbers. Three: If you graph the numbers of any system, patterns emerge. Therefore, there are patterns everywhere in nature. Evidence: The cycling of disease epidemics;the wax and wane of caribou populations; sun spot cycles; the rise and fall of the Nile.
  • You want to find the number 216 in the world, you will be able to find it everywhere. 216 steps from a mere street corner to your front door. 216 seconds you spend riding on the elevator. When your mind becomes obsessed with anything, you will filter everything else out and find that thing everywhere.
Proof : This is a perfect math movie with top-notch performances from Gwyneth Paltrow and Anthony Hopkins, an awesome screenplay and a satisfying ending. The following conversation about Hardy-Ramanujan number is aptly placed in the movie.
Robert: Catherine, if every day you lost were a year, it would be a very interesting freaking number.
Catherine: 33 and a quarter years is not interesting.
Robert: Stop it, you know exactly what I mean.
Catherine: 1729 weeks.
Robert: 1729, great number. The smallest number expressed ...
Robert and Catherine: ... as the sum of two cubes in two different ways.
Robert: 123 + 13 = 1729.
Catherine: And 103 + 93. Yes, we've got it, thank you.
Robert: You see? Even your depression is mathematical.
A Beautiful Mind : Well, everybody knows about this oscar-winning movie.
  • Sometimes, our expectations are betrayed by the numbers.
  • Good morning, eager young minds.
  • Find a truly original idea. It is the only way I will ever distinguish myself. It is the only way I will ever matter.
  • [Sol] John, you should go easy. There are other things besides work. [Nash] : What are they ?

Good Will Hunting : In my previous post I mentioned an elementary graph theory problem from this movie. Also, there is a scene in which the characters talk about a math problem and joining two vertices of a tree. Are they talking about 1-trees ? If you don't know what a 1-tree is, read Held-Karp relaxation of Traveling Saleman Problem. The best scenes of the movie are the conversations between Will and Sean.
  • You really hypnotised me, you know.
  • I'm pumped! Let the healing begin!
  • I can't learn anything from you, I can't read in some freaking book. Unless you want to talk about you, who you are.
  • [Will] You just cash in your chips and you walk away ? [Sean] Hey, at least I played a hand.

Btw, Pi, Proof and A Beautiful Mind have excellent soundtracks too. I would like to see more movies of this kind. If you know of any good math movies, leave a comment.

Sunday, November 09, 2008

The Good Will Hunting Problem

Here is a problem from the movie Good Will Hunting, shown in the screenshot below.

For the the graph G(V,E) shown above, find the following :

  • The adjacency matrix A :
  • The matrix giving the number of 3 step walks in G : [Ak]ij is the number of paths of length k from i to j. So, the answer is A3.
  • The generating function for walks from point i to j : The generating function is as follows. Here are more examples of generating functions.
  • The generating function for walks from points 1 to 3 : Simplify the above formula using cramer's rule for i=1 and j=3.

Tuesday, October 28, 2008

Friendly Numbers

Pythagoras said "220 and 284 are friendly numbers" !! These numbers have a special property : Each is equal to the sum of the other's proper divisors. Proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 (they sum to 284). Proper divisors of 284 are 1, 2, 4, 71 and 142 (they sum to 220). More example include (1184, 1210), (17296, 18416). It is not known whether there are infinitely many friendly numbers. Twin primes are a pair of consecutive odd numbers both of which are prime.
  • Theorem : There are infinitely many friendly numbers. (proof)
  • Conjecture : There are infinitely many twin primes.

Wednesday, July 23, 2008

Common Puzzles

Most of my friends are geeks. So when we get together on a friday night (or) driving to a conference, we don't talk about politics, movies or celebrities. Instead we throw math puzzles at each other. Here are some of the common puzzles I ran into....

  • The Banana-eating Camel : You have 3,000 bananas that must be transported across a desert that is 1,000 kilometers wide. You have a camel that has a 1,000 banana capacity. However, the camel must eat one banana for each kilometer that it walks. What is the largest number of bananas that can be transported across the desert?

  • 12 Balls : There are 12 balls. They all look alike but one of them is faulty; it weights differently. It is not known, if this ball is heavier or lighter than the other balls. How to find the faulty ball by three weighs on a simple balance ?
  • Linked Lists : You are given a pointer to the head of a singly linked list that might (or might not) have a loop somewhere (i.e., an element pointing back to an element). The length of the list is finite, but unknown. Devise an algorithm that detects if there is a loop. You must use only a constant amount of memory space and not destroy the list.
  • Two Integers : I'm thinking of two integer numbers, each if them is more than 1 and their sum is less than 100. I tell my friend A the sum of these two numbers, and another friend B, product of these two numbers. Then such a dialog took place:
    B: I can't determine what are these numbers.
    A: Ah, i knew you wouldn't be able to do this.
    B: Oh, then i know what they are!
    A: Oh, then i know them too!

    Can you determine the numbers?
  • Stick triangle : A stick is broken at random into three pieces. What is the probability that the pieces can form a triangle?

These are the easiest ones (the appetizers). Have fun solving them. I will add more difficult puzzles in future posts...

Thursday, April 24, 2008

List Coloring of Planar Graphs

I have been reading some papers on list-coloring of planar graphs. Here's a quick overview of this topic.

A proper coloring of a graph is an assignment of colors to vertices of a graph such that no two adjacent vertices receive the same color. A graph is k-colorable if it can be properly colored with k colors. For example, the famous Four Color Theorem (4CT) states that "Evey planar graph is 4-colorable". This is tight, since K4 is 4-colorable but not 3-colorable. Deciding if a graph is 3-colorable is NP-hard. It is natural to ask which planar graphs are 3-colorable. Grotzsch's Theorem states that "Every triangle-tree planar graph is 3-colorable".

Given a graph and given a set L(v) of colors for each vertex v, a list coloring is a proper coloring such that every vertex v is assigned a color from the list L(v). A graph is k-list-colorable (or k-choosable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex.

If a graph is k-choosable then it is k-colorable (set each L(v) = {1,...k}). But the converse is not true. Following is a bipartite graph (2-colorable) that is not 2-choosable (corresponding lists are shown).

A graph is k-degenerate if each non-empty subgraph contains a vertex of degree at most k. The following fact is easy to prove by induction :
  • A k-degenerate graph is (k+1)-choosable
Are there k-degenerate graphs that are k-choosable ? Following are some known results and open problems :
  • Every bipartite planar graph is 3-choosable [Alon & Tarsi]. It is easy to prove that every bipartite planar graph is 3-degenerate.
  • Every planar is 5-choosable [Thomassen'94]. Note that every planar graph is 5-degenerate. There are planar graphs which are not 4-choosable [Voigt'93].
  • Every planar graph of girth at least 5 is 3-choosable. This implies grotzsch's theorem in a very cute way [Thomassen'03]. There are planar graphs of girth 4 which are not 3-choosable [Voigt'95].
  • Conjecture : Every 3-colorable planar graph is 4-choosable.

Note : A recent paper [DKT'08], presents a very short proof of Grotzsch's theorem and a linear-time algorithm for 3-coloring such graphs.

References :
  • [Alon & Tarsi'92] N. Alon, M. Tarsi: Colorings and orientations of graphs. Combinatorica 12(2): 125-134 (1992)
  • [Thomassen'94] C. Thomassen: Every Planar Graph Is 5-Choosable. J. Comb. Theory, Ser. B 62(1): 180-181 (1994)
  • [Voigt'93] M. Voigt: List colourings of planar graphs. Discrete Mathematics 120(1-3): 215-219 (1993)
  • [Thomassen'03] C. Thomassen: A short list color proof of Grötzsch's theorem. J. Comb. Theory, Ser. B 88(1): 189-192 (2003)
  • [Voigt'95] M. Voigt : A not 3-choosable planar graph without 3-cycles. Discrete Mathematics 146(1-3): 325-328 (1995)
  • [DKT'08] Z. Dvorak and K. Kawarabayashi and R. Thomas : Three-coloring triangle-free planar graphs in linear time. To appear in SODA 09.

Sunday, April 20, 2008

Testing triangle-freeness

Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ? Cubic time is obvious. Let A be the adjacency matrix of G. We can detect triangle-freeness of G in the same complexity as multiplying two boolean matrices (AxA) (duh !!). This simple algorithm is the best known !! In other words, following is the open problem :
  • Is testing triangle-freeness as difficult as the Boolean multiplication of two |V| x |V | matrices?
A recent paper [1] addressess this problem partially. In a related note, the complexity of all pairs shortest paths (APSP) is still unresolved. Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?

[1] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279–-288, 2006.

Friday, April 18, 2008

Tiling chessboard by L-shaped trominoes

Can you cover all but one square of an n x n chessboard by L-shaped trominoes?

Claim : If n is a power of 2, you can always do it !!

Have fun proving this !!

Wednesday, April 09, 2008

Lipton Symposium and Trotter Conference

I am eagerly waiting for the following two excellent conferences at GeorgiaTech :

Wednesday, April 02, 2008

25 Horses Puzzle

There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.

1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?
2: ..... to find out the fastest one ?
3: ..... to rank all of them from fastest to slowest ?
4: ..... to find the top k fastest horses ?

Wednesday, March 19, 2008

Using Latex with Powerpoint

Next week, I am going to give a talk at DIMACS/DyDAn Workshop on Secure Internet Routing. While preparing slides for my presentation, I realized that I LOVE powerpoint for its support for animation, but I HATE using its equation-editor. Also, I don't like preparing slides in latex (using beamer) due to lack of decent animation tools. I was googling around for a solution and found the following alternatives to combine the best of both worlds :

1) TexPoint : I like its support for inline latex compilation. But it is not free and I found many limitations in math fonts and \displaystyle.

2) Tex4PPT : This does not support Office 2007 yet. So I did not explore it.

3) Inkscape : This is the BEST way to combine latex and powerpoint. Its is FREE and opensource too !! Install Inkscape and follow these instructions to add support for latex. Inkscape allows you to type any crazy latex equation and convert into .eps format. You can even ungroup symbols in an equation and assign different colors to different symbols. Add the .eps file in the ppt file (using Insert -> Picture) and you can zoom-in/zoom-out the image without sacrificing the resolution !!

Thursday, January 03, 2008

Graph Isomosphism

I found another paper claiming that graph isomorphism is in P.