Wednesday, August 18, 2010

Today is Paul Turan's 100th Birthday!

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? (ADDED LATER FOR CLARIFICATION: Noticing that Lance's mention of Paul Turan is actually a pointer to a Wikipedia Entry on him.) 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. (ADDED LATER: The proof is due to Ravi Boppana- see the comments.) 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 Σx ∈ 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.


    1. In your writeup, the result that the independence number of a graph is at least the sum of 1/(d+1) over all degrees d is due to Caro (1979) and Wei (1981). Back in the late 1980's, I happened to come up with the probabilistic proof that you wrote and showed it to Joel Spencer and Paul Erdos (which explains why it appeared in Alon-Spencer). I don't know what the original proofs of Caro and Wei were, so it is possible that my proof was already known.
      --Ravi Boppana

    2. THANKS for the information- I updated
      the post and the writeup appropriately.
      If you have a more exact ref to
      Caro or Wei please email them to me.

    3. insert pointers into your speech?

    4. Turan's extremal result of the maximum number of edges in a trinagle-free graph to be \floor{n^2/4} is also beautiful and useful. This directly translates that the maximum number of edges in a transitively reduced digraph is \floor{n^2/4}. Is there any non-inductive proof known for the maximum number of edges in a triangle-free graph.

    5. Anon 3- I was refering to, in the conversation between Lance and GASARCH,
      Lance has a pointer to the wikipedia entry
      on Paul Turan in what I typed.

      Anon 4- If you know of a good free online
      writeup of this, email it to me or comment about it and I will add it to this post.

    6. To Anon 9:02 AM, August 19, 2010

      I've seen that at least three non-inductive proofs of Mantel's theorem (what you call Turan's theorem) are given. e.g. in Jukna's book "Extremal combinatorics". The arguments are: Cauchy-Schwarz, arithmetic-geometric mean inequality, weight shifting argument.

    7. This comment has been removed by the author.

    8. This comment has been removed by the author.

    9. Here is the complete reference - Turan is credited as the creator of extremal graph theory after his 1941 paper (in which he proved a more general result) in Jukna's book

      This is for completeness sake - nothing else

    10. I don't understand the nature of the "gap" mentioned after Theorem 3.2 in your writeup. Isn't the tight case of Theorem 3.1 given by dividing the set into three subsets of equal size, and assigning the (elements of the) three subsets to three points on the unit circle at angles 2pi/3? What am I missing?

    11. Lsst anon-
      Turan's theorem gives that there
      MUST be n^2/6 - n/2 pairs.

      By your construction there IS a way to place n points so that there are
      n^2/6 -O(1) such pairs.

      That is a gap. For example, IS there a way to place n points so that the number of pairs is n^2/6 - n/10 pairs?

      communicating by commens is awkward- feel
      free to email me.

    12. Anon who refers to Mantel's theorem.
      Wikipedia states Turan's theorem diff then I do (though its equivlent) and says
      that Mantel's theorem is a special case.

    13. (Anon #10 here)
      I'm sorry, I should have spoken more clearly (the perils of posting when waking up in the middle of the night). I understand what you mean by a gap, I just thought that the example we evidently both had in mind is tight. So (at least) one of us is miscounting.

      By my count, every point is close to exactly (n/3 - 1) other points. Thus, the total number of close pairs is

      n*(n/3 - 1)/2 = n^2/6 - n/2

    14. Last Anon- YES, WOW, there is no Gap.
      I will amend writeup.
      I had miscounted.

    15. Bill and Lance: would it not be possible to NUMBER the comments? The references the would be less ambiguous.

      Turan's theorem speaks about max number of edges in a k-clique-free graph, for *any* k>3. What Mantel proved more than 25 years before him was the case k=3. And that's all. Turan's proof is also not something realy new: just an extension of Mantel's one. More important is that after Turan's result many people have looked at similar questions. An extremal graph theory was born. This is a very important act, which Turan made: to initiate an entire field!

    16. (Yair Caro emailed me more on the history of the Prob Proof of
      Turan's theorem. Yair has given me permission to
      edit his letter and post it as a comment.)

      I and read your blog with much interest and noticed the discussion with Ravi
      Boppana who mentioned I gave the proof in 1979 - which is true.
      You asked for more exact references to Caro and Wei .
      The story as I remember it after 32 years is as follows :

      In 1978 I was in an undergraduate in Tel-Aviv university and I attended
      a course on graph theory by Prof. Johanan Schonheim who later became
      my Ph.D supervisor and a reading course on number theory where I was personally mentored by
      Prof. Moshe Jarden .
      Learning about Turan's theorem in graph theory and the prime number
      theorem in number theory I set myself to try some problem solving .
      Soon I found a generalization of Pillai's result in number theory and
      wrote a proof and eventually this became my first published paper :

      1. Caro, Y. On a division property of consecutive integers. Israel
      Jour. of Mathematics, 33 (1) (1979) 32-36.

      I also found the proof of the theorem now called Caro-Wei and wrote a =
      paper called new results on the independence number ( a technical
      report 4/1979 )
      which was soon edited as a research paper and sent to a journal.
      Prof Johanan Schonheim told me he circulated some copies of this paper
      among other people including Prof. Marcel Hertzog who said he gave a
      copy to Prof. Ed Bertram
      And then the paper spread out without control!

      A referee responded unfavourably because as he explained
      Caro gave a proof via deleting vertices of maximum degree and induction and I can
      give an easier proof using a result of Erdos
      (which he did but was not easier at all) .
      I myself found another really easier proof deleting vertices of minimum degree, after sending the paper .

      Prof. Schonheim told me he wrote a very angry letter to the editor
      (mentioning the ethic of this event and that there are other results
      worth publishing ) but that was in vain.
      I decided not to submit it again after sending most of the copies I
      hold to friends and so the paper remains as is - Technical report
      4/1979 !!

      Two years later the technical memorandum of V. Wei appears with the same
      result ( 1981 ) without reference to my result , and so today the
      theorem is called Caro - Wei .

      Best - Yair Caro