The following conversation is a fictional version of a real conversation.
Bill, Wed August 18, 2010 is
100th birthday. We should post on it.
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.
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
Even though he is dead can we still celebrate?
Is there cake someplace? How about a free lunch?
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.
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
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.)
If G is a graph with n vertices and e edges then
G has an independent set of size at least
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.
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.
for more on the conjecture.
Posted By GASARCH to Computational Complexity at 8/18/2010 09:59:00 AM