Counter Example

Finding counter examples to conjectures can be notoriously hard (pun? I think not). This is an area of creativity that mostly goes unappreciated.

Here’s a personal anecdote: my father once came up with an algorithm to solve a hugely constrained version of the traveling salesman problem. The greedy proof was slightly hand-wavy, and I felt it would be an easier thing to find a counter example where his algorithm wouldn’t find the optimal tour. Of course, I was just trying to tell him that he couldn’t have solved TSP (or even approximated it). I learnt two lessons that day.

Lesson One: One must always speak sweet, because one underestimates the number of times one has to eat his own words.

Lesson Two: Finding counter examples can get quite tricky – and if I may, I would admit that it’s not just tricky, it’s quite hard – requires tons of patience, and a deep understanding of the problem and the algorithm we are out to disprove. I had learnt a similar lesson earlier in Sundar’s Approximation Algorithms class. Sundar let us spend one hour counter-exampling that a minimum spanning tree over the vertex set wouldn’t give us a minimum Steiner tree. The counter example used a ‘construct’ that was quite simple, and took a few minutes of dedicated thought to find. But what amazed me today was this fact about Tait’s conjecture:

Tait’s conjecture states that “Every polyhedron has a Hamiltonian cycle (along the edges) through all its vertices“. It was proposed in 1886 by P. G. Tait and disproved in 1946, when W. T. Tutte constructed a counterexample with 25 faces, 69 edges and 46 vertices.

Imagine the patience, creativity, deep understanding of the problem, and the [least appreciated of them all] ability to borrow from related problems and areas – it takes to come up with such a counter example. And I keep wondering: why research?

9 thoughts on “Counter Example

  1. Imagine the patience, creativity, deep understanding of the problem, and the [least appreciated of them all] ability to borrow from related problems and areas – it takes to come up with such a counter example. And I keep wondering: why research?

    More than the patience it is about a “gut feel” and a motivation which comes with a familiarity (which can be experienced at the beginning or somewhere down the lane) while studying a problem which makes a mathematician/scientist set to disprove something. Exceptions to rules are not a good thing….There are more like Kabaab mein haddi…But if there are too many exceptions, the rule itself may be screwed up.

    The bottomline is if you try to “generalize” a counter-example, there could be a counter-example to a counter-example (which can be called a counter-counter example??).

    PS:- I am not drunk.Sumne timepass ge barde…..

  2. Similar experience with reductions. Coming up with the widget for the hamiltonian or from 3-SAT to vertex cover.

    Non-Euclidean geometry anybody :).

  3. There is an urban legend about a professor (some say he is none other than Prof Diwan). An undergraduate was giving a seminar and the prof was in the audience. The student made a cavalier claim of some sort which the prof was not comfortable with. After about 30 seconds, the prof stood up and drew a 17-node weighted graph to disprove the claim.

    Not as good as Tutte’s polyhedron, but impressive none the same.

    Rahul

  4. The bigger question is, don’t examples suffice? Why do we need counter-examples? Examples show us that we can get some wok done. So “let’s get it done”, with apologies to Citigroup. If our algorithm cannot get something done, let’s try a trick older than mathematics – money! If we cannot solve the traveling salesperson problem, let’s ask him not to travel – we can establish retail outlets, start selling online or organize a customer event where potential customers travel, wine, dine and hopefully write a check.

    Pragmatism aside, I do realize that the traveling salesperson problem is an important problem that’s better solved than unsolved. So let me make an effort propose a solution. Since the traveling salesperson problem is NP hard (I got to know what it means, courtesy you), can we not make the hardware that executes the NP hard algorithm scale up as the number of nodes scales up?

  5. >> a minimum spanning tree over the vertex set wouldn’t give us a minimum Steiner tree

    why one hour? take a triangle ABC with edge weights AB=1, BC=1, AC=3. min spanning tree of {A,C} is of cost 3 where as min steiner tree over {A,C} is of cost 2.

    Did I understand the question wrong?

Leave a Reply

Your email address will not be published.