Tayzwi

Should be reading more and writing less, but well...

Thursday, May 03, 2007

 

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?

Labels: ,


Comments:
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.....
 
Then there are these   two books.
 
Your post reminded me of something I read elsewhere. Someone recently disproved the Riemann hypothesis. So he wasn't that great a mathematician huh?
 
Similar experience with reductions. Coming up with the widget for the hamiltonian or from 3-SAT to vertex cover.

Non-Euclidean geometry anybody :).
 
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
 
There is an extremely celebrated book devoted to counter examples in topology by Steen and Seebach. Although I don't think it relates to graph theory (or TSP, for that matter) in any sense, but it deals with a more general subject -- topology.
 
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?
 
>> 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?
 
@Deeps: I had forgotten to add that the graphs are constrained by the triangular inequality.
 
Post a Comment

<< Home

Archives

February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page