Talk:Erdős–Ko–Rado theorem

From Wikipedia, the free encyclopedia

The last edit is wrong - the theorem is only true in general for l=1. What is written now is true for large n, but not for small n (c.f Ahlswede-Khachatrian 1997). Counterexample: n=8, r=4, l=2, when n-l choose r-l is 15, but e.g. 1234,1235,1236,1237,1238,1245,1246,1247,1248,1345,1346,1347,1348,2345,2346,2347,2348 is 2-intersecting of size 17. I've reverted it RM, 27 May 07

I was using the Deza/Frankl survey from 1983 which states the theorem in the more general form. They also point out that the theorem fails for n < (k − l + 1)(l + 1), which is certainly the case for the example given. Will try find time to extract the fixes in my edit and reapply them separately.--Ott2 22:19, 11 June 2007 (UTC)

No doubt I am revealing my abysmal ignorance about this article about things I don't understand and don't want to. But this showed up with strange characters, a ` instead of a ', and CamelCaps in both the main page which links to it, and the page itself. I suspect the name of The characters on the page itself are inconsistent between the title and the article itself:

ErdÅ?s-Ko-Rado Theorem
From Wikipedia, the free encyclopedia.
The Erd?s-Ko-Rado-Theorem

Not sure what I should be reading here, or the name of the person who wrote this theorem whatever he or she is, but I suspect I ain't gettin' it. -- IHCOYC 13:39, 14 Aug 2003 (UTC)

A typographical note:

The guy's name is actually Erdős. However, the title of the article has to be Erdös-Ko-Rado theorem because the English wikipedia still can't handle general Unicode in article titles, and ö is the nearest we can do in the ISO 8859-1 character set. -- The Anome 13:50, 14 Aug 2003 (UTC)

Nearest doesn't cut it. The page should be Erdos-Ko-Rado Theorem until en.wikipedia goes Unicode. Meanwhile, the titlelacksdiacritics banner clears up the title problem.
Urhixidur 04:13, 2005 Mar 25 (UTC)

The proof says:

Now arrange the elements of X in a cyclic order

X has not previously been mentioned, and it is not mentioned again. I'm not sure what to replace it with. Dominus 15:40, 14 Aug 2003 (UTC)

I think X = {1, 2, ..., n}. However, what is a cyclic order? I'm not familiar with the term. Oh, is it just a permutation of X when we consider permutations equal when one a cyclic permutation of the other? That would explain the r!(n-r)! term. - Molinari 07:18, 15 Aug 2003 (UTC)
Also, I don't immediately see how the proof establishes that when equality holds then there is an x such that A consists of exactly the r-element subsets of X containing x. - Molinari 07:22, 15 Aug 2003 (UTC)
Perhaps I am missing something, but why do we need to assume that |A| >= \choose(n-1, r-1) at the start of the proof? There are at most r elements of A represented in each cyclic order, so the average number per order is no larger than r. This, combined with the calculation of the average in the next step gives a bound on |A| of \choose(n-1, r-1).
Taking the system consisting of all r-element subsets of A which contain 1 as an element shows that the bound is sharp. I don't yet see how to show that all systems of the maximal size are of this form, though. - Molinari 21:02, 17 Aug 2003 (UTC)

The recent formatting changes displaying the binomial coefficients on separate lines lead to an awkward reading. Was there a particular reason for these changes? Molinari 23:11, 11 Aug 2004 (UTC)

Contents

[edit] Completing proof?

I fixed up the proof, made it (I hope) clearer. I'm pretty sure the condition n > 2r can be weakened to n\geq2r. I only see one place in the proof that uses the condition, and it uses the weaker one.

Don't you hate the mathematical use of "the result quickly follows" or "as the reader can easily show"? I finished the end of the proof, showing that if A is maximal size, there's a common element x. This might be considered original research, since I figured out a proof, instead of looking it up.

By the way, a counterexample for the case n < 2r: Take n = 6, r = 4, and let A consist of the sets 1234, 1235, 1236, 1245, 1246, 1256, 2345, 2346, 2356, 2456, 3456. (5 choose 3 is 10.) With the cyclic order 123456, we have the five intervals

1234
 2345
  3456
    5612
     6123.

--Dbenbenn 00:40, 3 Dec 2004 (UTC)

I'm not convinced by this part of the proof. See my my user talk page for my comments. Molinari 01:05, 4 Dec 2004 (UTC)
Erp, you're right. What I tried to prove, that a, b, and c are all intervals in some order, is blatently false. I'll remove what I added, and keep thinking about it. --Dbenbenn 03:35, 4 Dec 2004 (UTC)
(*I am going to but in!*) Also, don't provide original research, even if it is valid. You should at least find something that is accepted that has the argument in it before you submit the argument.

[edit] Weaker condition doesn't work for second part of theorem

I believe that the first part of the theorem is true in the case n = 2r. The proof given appears to only assume n\geq2r. But the second part is not true in that case! Consider n = 6, r = 3, and the sets 123, 124, 134, 145, 146, 234, 245, 246, 345, 346. Every set but the first has a 4. (5 choose 2 is 10.) --Dbenbenn 05:26, 4 Dec 2004 (UTC)


[edit] Gyula Katona

Since this page was created, it has referred to "Gyula Katona's proof", with no citation. I suspect Gyula Katona is Gyula O. H. Katona, a mathematician at the Alfréd Rényi Institute of Mathematics in Hungary. He published "A simple proof of the Erdős-Chao Ko-Rado theorem" in J. Combin. Theory Ser B 13 (1972), pages 183--184. I'll try to check this reference, and add it to the article. --Dbenbenn 06:45, 7 Dec 2004 (UTC)

Thanks for adding the references. Do you have access to these journals? If so, does Katona's paper prove part 2 of the theorem? Cheers. Molinari 21:21, 11 Dec 2004 (UTC)
Oh, I see that the second part has been removed from the page. Is that statement not part of the theorem after all? Molinari 21:23, 11 Dec 2004 (UTC)
Sorry for the slow response; the page slipped thought my watch list. I checked both papers, and couldn't find the second part stated in either of them. (If you're interested, I have them in PDF and could email them.) Dbenbenn 07:01, 3 Jan 2005 (UTC)

[edit] Statement of the theorem

If all sets have the same size, why to assume that none is a proper subset of the other?Kope 17:20, 19 March 2007 (UTC)