tag:blogger.com,1999:blog-3722233.post4305992721665166751..comments2024-07-18T10:10:20.703-05:00Comments on Computational Complexity: Today is Paul Turan's 100th Birthday!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-16266507524626684222011-02-28T15:31:22.791-06:002011-02-28T15:31:22.791-06:00(Yair Caro emailed me more on the history of the P...(Yair Caro emailed me more on the history of the Prob Proof of<br />Turan's theorem. Yair has given me permission to<br />edit his letter and post it as a comment.)<br /><br /><br />I and read your blog with much interest and noticed the discussion with Ravi<br />Boppana who mentioned I gave the proof in 1979 - which is true.<br />You asked for more exact references to Caro and Wei .<br />The story as I remember it after 32 years is as follows :<br /><br /><br><br /><br><br /><br />In 1978 I was in an undergraduate in Tel-Aviv university and I attended <br />a course on graph theory by Prof. Johanan Schonheim who later became <br />my Ph.D supervisor and a reading course on number theory where I was personally mentored by <br />Prof. Moshe Jarden .<br />Learning about Turan's theorem in graph theory and the prime number <br />theorem in number theory I set myself to try some problem solving .<br />Soon I found a generalization of Pillai's result in number theory and <br />wrote a proof and eventually this became my first published paper :<br /><br />1. Caro, Y. <i>On a division property of consecutive integers.</i> Israel <br />Jour. of Mathematics, 33 (1) (1979) 32-36.<br /><br /><br><br /><br><br /><br />I also found the proof of the theorem now called Caro-Wei and wrote a =<br />paper called <i>new results on the independence number</i> ( a technical <br />report 4/1979 )<br />which was soon edited as a research paper and sent to a journal.<br />Prof Johanan Schonheim told me he circulated some copies of this paper <br />among other people including Prof. Marcel Hertzog who said he gave a <br />copy to Prof. Ed Bertram<br />And then the paper spread out without control!<br /><br /><br><br /><br><br />A referee responded unfavourably because as he explained <br /><i>Caro gave a proof via deleting vertices of maximum degree and induction and I can <br />give an easier proof using a result of Erdos</i> (which he did but was not easier at all) . <br />I myself found another really easier proof deleting vertices of minimum degree, after sending the paper .<br /><br /><br><br /><br><br /><br />Prof. Schonheim told me he wrote a very angry letter to the editor <br />(mentioning the ethic of this event and that there are other results <br />worth publishing ) but that was in vain.<br />I decided not to submit it again after sending most of the copies I <br />hold to friends and so the paper remains as is - Technical report <br />4/1979 !!<br /><br /><br><br /><br><br /><br />Two years later the technical memorandum of V. Wei appears with the same <br />result ( 1981 ) without reference to my result , and so today the<br />theorem is called Caro - Wei .<br /><br /><br><br /><br><br /><br />Best - Yair CaroGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19482201376313769232010-08-20T14:57:32.880-05:002010-08-20T14:57:32.880-05:00Bill and Lance: would it not be possible to NUMBER...Bill and Lance: would it not be possible to NUMBER the comments? The references the would be less ambiguous.<br /><br />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!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44125337857332513272010-08-20T10:15:49.327-05:002010-08-20T10:15:49.327-05:00Last Anon- YES, WOW, there is no Gap.
I will amend...Last Anon- YES, WOW, there is no Gap.<br />I will amend writeup.<br />I had miscounted.<br />THANKS!GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68742766619222511712010-08-20T09:17:51.129-05:002010-08-20T09:17:51.129-05:00(Anon #10 here)
I'm sorry, I should have spoke...(Anon #10 here)<br />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.<br /><br />By my count, every point is close to exactly (n/3 - 1) other points. Thus, the total number of close pairs is<br /><br />n*(n/3 - 1)/2 = n^2/6 - n/2Anon #10noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67216943906436214332010-08-20T09:03:59.940-05:002010-08-20T09:03:59.940-05:00Anon who refers to Mantel's theorem.
Wikipedia...Anon who refers to Mantel's theorem.<br />Wikipedia states Turan's theorem diff then I do (though its equivlent) and says<br />that Mantel's theorem is a special case.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85980390237130354392010-08-20T09:00:38.384-05:002010-08-20T09:00:38.384-05:00Lsst anon-
Turan's theorem gives that there
M...Lsst anon- <br />Turan's theorem gives that there<br />MUST be n^2/6 - n/2 pairs.<br /><br />By your construction there IS a way to place n points so that there are<br />n^2/6 -O(1) such pairs.<br /><br />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?<br /><br />communicating by commens is awkward- feel<br />free to email me.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23802327680485230752010-08-20T06:00:55.346-05:002010-08-20T06:00:55.346-05:00I don't understand the nature of the "gap...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23230515860548546822010-08-19T17:05:36.646-05:002010-08-19T17:05:36.646-05:00Here is the complete reference - Turan is credited...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<br />http://tiny.cc/62l62<br /><br />This is for completeness sake - nothing elsemskmoorthyhttps://www.blogger.com/profile/04521212767155230436noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52244319846597385872010-08-19T17:01:45.645-05:002010-08-19T17:01:45.645-05:00This comment has been removed by the author.mskmoorthyhttps://www.blogger.com/profile/04521212767155230436noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82134527597119664082010-08-19T16:57:08.608-05:002010-08-19T16:57:08.608-05:00This comment has been removed by the author.mskmoorthyhttps://www.blogger.com/profile/04521212767155230436noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12506626931608037162010-08-19T13:48:50.373-05:002010-08-19T13:48:50.373-05:00To Anon 9:02 AM, August 19, 2010
I've seen th...To Anon 9:02 AM, August 19, 2010<br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18493104376356807132010-08-19T09:17:40.252-05:002010-08-19T09:17:40.252-05:00Anon 3- I was refering to, in the conversation bet...Anon 3- I was refering to, in the conversation between Lance and GASARCH,<br />Lance has a pointer to the wikipedia entry<br />on Paul Turan in what I typed.<br /><br />Anon 4- If you know of a good free online<br />writeup of this, email it to me or comment about it and I will add it to this post.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82134267392246629202010-08-19T09:02:37.583-05:002010-08-19T09:02:37.583-05:00Turan's extremal result of the maximum number ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38613665882373738882010-08-18T18:25:53.229-05:002010-08-18T18:25:53.229-05:00insert pointers into your speech?insert pointers into your speech?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46965107322025453252010-08-18T11:47:15.164-05:002010-08-18T11:47:15.164-05:00THANKS for the information- I updated
the post and...THANKS for the information- I updated<br />the post and the writeup appropriately.<br />If you have a more exact ref to<br />Caro or Wei please email them to me.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69862376997841304012010-08-18T11:15:39.054-05:002010-08-18T11:15:39.054-05:00In your writeup, the result that the independence ...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.<br />--Ravi BoppanaRavi Boppanahttps://www.blogger.com/profile/08439913421610643876noreply@blogger.com