## [Computational Complexity] Today is Paul Turan's 100th Birthday!

Expand Messages
• The following conversation is a fictional version of a real conversation. Lance: Bill, Wed August 18, 2010 is Paul Turan s 100th birthday. We should post on
Message 1 of 1 , Aug 18, 2010
• 0 Attachment
The following conversation is a fictional version of a real conversation.

Lance: Bill, Wed August 18, 2010 is Paul Turan's 100th birthday. We should post on it.

GASARCH: WOW, he's still alive? Will there be a conference in his honor? Will he go to it? Will he enjoy it? Lance, I see you have one of those gizmos that lets you insert pointers into your speech.

Lance: Uh, Paul Turan is dead, but if he were alive it would be his 100th birthday. And of course I have one of those gizmos--- I am a firstblocker

GASARCH: Even though he is dead can we still celebrate? Is there cake someplace? How about a free lunch?

Lance: No cake. And the economists I hang out with say there is no such thing as a free lunch. But we should post about it.

GASARCH: Okay. I know a nice proof of Turan's theorem and two applications, so I'll post about it.

When Lance first asked me to do this post my first reaction (after I found out there would be no cake or free lunch) was Paul Turan- Turan's theorem in graph theory. I know a nice proof of it that is not on Wikipedia. I also know two applications of Turan's theorem that I don't think are well known. I'll write those up as part of my post. (I will do this later in the post.) But then I looked at his Wikipedia Entry and I saw that he did so much more than graph theory. He also worked in Analysis, Number Theory, and Analytic Number Theory. Moreover, Wikipedia claims that Number Theory was his main interest. In addition he, along with Paul Erdos, made the Erdos-Turan Conjecture which has inspired so much later work (I will state it later.)

Is it good to have a theorem named after you? While we would mostly think YES, it may overshadow all of your other work in peoples memory of you. On the other hand, if it was not for Turan's theorem I would not know who he was and I doubt Lance would ask me to post on Turan's 100th birthday.

Is it good to have a conjecture named after you? It is so long as its open. Once someone proves it your name will vanish from the literature. Just ask Baudet or Vazsonyi (Baudet's conjecture is now van der Warden's theorem, and Vazsonyi's conjecture is now the Kruskal Tree Theorem.)

Turan's theorem:
If G is a graph with n vertices and e edges then G has an independent set of size at least n2/(2e+n)
Here is an application:
If S is any set of points in the unit disc (including the boundary) then there exist n2/6 - n/2 pairs of points such that each pair is of points that are ≤ sqrt(2) apart.
Here is my write up of a nice proof of both Turan's theorem and the application. The proof is from the Alon-Spencer book on Prob method. I do not know whose proof it is. I don't know where I read the application; however, it was by Paul Turan. If you know of other applications please leave comments about them.

Here is another application:
Assume you want to find the MAX of n elements and you get to ask k rounds of questions. It is know (without Turan's theorem) that you can do this with O(n(1+(1/(2k-1))) questions-per-round. Using Turan's theorem you can show this is optimal. (The exponent is 1+(1/(2k-1)) in case its hard to read.)
A write up of the case of k=2 is in the manuscript pointed to above. Once you read that you should be able to generalize it to k rounds easily.

The Erdos-Turan conjecture is the following:
Let A be a set of natural numbers. If &Sigmax ∈ A 1/x diverges then A has arbitrarily long arithmetic sequences.
Some have suggested that this replace Poincare's conjecture on the list of Millennium prizes. See here for more on the conjecture.

--
Posted By GASARCH to Computational Complexity at 8/18/2010 09:59:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.