Talk:Erdős–Ko–Rado theorem

Erdős–Ko–Rado theorem has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it.
Review: November 28, 2022. (Reviewed version).

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)[reply]

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)

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\geq 2r$ . 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

--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.

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\geq 2r$ . 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)

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)

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)[reply]

Removing dubious statement

In the lead section had this:

According to Erdős (1987) the theorem was proved in 1938, but was not published until 1961 in an apparently more general form. The subsets in question were only required to be size at most r, and with the additional requirement that no subset be contained in any other. This statement is not actually more general: any subset that has size less than r can be increased to size exactly r to make the above statement apply.

The first two sentences are correct, with a proviso: I don't know if the condition n≥2r is sufficient for this generalization; it isn't in the 1961 paper. I'll add a citation-needed to this.
The third sentence is not cited and not obvious. The problem is that it requires the sets to be increased to size r in such a way that the increased sets are all different. It is not obvious how to do this and it seems difficult. This issue does not appear to be mentioned in the 1961 paper or in the 1987 survey. Therefore, I'm taking it out. McKay (talk) 08:08, 28 April 2017 (UTC)[reply]

GA Review

This review is transcluded from Talk:Erdős–Ko–Rado theorem/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Bilorv (talk · contribs) 22:11, 27 November 2022 (UTC)[reply]

During my undergraduate degree, what I loved most and hated most about combinatorics was the same fact: the material was elementary but very difficult. It often surprised me how recent many of the proofs were (such as this one), considering how natural the questions of investigation appear to be. Combinatorics wasn't my strongest subject (though I did well on an exam question based on Erdős–Ko–Rado), so go easy on me if I've made any serious maths mistakes.

Lead and general comments

With WP:ONEDOWN in mind, I wonder whether the first paragraph of the lead should be targeted at secondary school students, or perhaps a first-year undergraduate level. I wonder if there's something better to lead with than ... is an upper bound on families of sets in which every pair of sets has a non-empty intersection. Not easy to compose something but here's my go at describing the problem: how many groups of r distinct objects from a selection of n distinct objects can be chosen so that every pair of groups has an item in common? The visual example is helpful but maybe the example of $\{1,2\}$ $\{1,2\}$ , $\{1,3\}$ $\{1,3\}$ , $\{2,3\}$ $\{2,3\}$ from the ground set $\{1,2,3\}$ $\{1,2,3\}$ would be good in prose (to show that it's a pairwise intersection, not an intersection over the whole family).
- I had already put some effort into keeping the lead as simple as possible but I made another attempt to simplify it, in part by emphasizing shared elements rather than set intersections. —David Eppstein (talk) 00:10, 28 November 2022 (UTC)[reply]
I would relegate the mathematician links to a separate sentence (maybe "Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938.") to increase readability of the first sentence.
- Done. —David Eppstein (talk) 00:10, 28 November 2022 (UTC)[reply]
Per MOS:COLON, I think the letter after the colon in the image caption should not be capitalised.
- Changed to a period. —David Eppstein (talk) 00:10, 28 November 2022 (UTC)[reply]
Set (mathematics) might be worth linking somewhere.
- Done, first sentence. —David Eppstein (talk) 00:10, 28 November 2022 (UTC)[reply]
I think anything with a maths expression followed by a hyphen, such as $k$ -dimensional, needs a "nowrap". I noticed a couple missing in the lead and a " $k$ $k$ -dimensional" one in "Analogs".
- I agree. Also mathematics followed by punctuation and references needs a nowrap. I made another pass looking for these and found a few more. —David Eppstein (talk) 00:10, 28 November 2022 (UTC)[reply]

Statement and history

... they did not publish it ... – "it" isn't mentioned in the previous sentence, maybe "they did not publish the result"?
- Ok, done. —David Eppstein (talk) 00:19, 28 November 2022 (UTC)[reply]
The section appears to be three paragraphs of "Statement" with a single "History" paragraph sandwiched in the middle. Is it worth separating "History" to its own section, after "Statement"?
- Ok, done. —David Eppstein (talk) 00:19, 28 November 2022 (UTC)[reply]
An image of a Kneser graph might be nice, like File:Kneser graph KG(5,2).svg, and it has $n\geq 2r$ $n\geq 2r$ so the theorem does apply.
- Ok, done. —David Eppstein (talk) 00:19, 28 November 2022 (UTC)[reply]

Maximum and maximal families

It might be worth spelling out why the first construction makes a family of size ${\binom {n-1}{r-1}}$ ${\binom {n-1}{r-1}}$ : other than x, the sets each have any $r-1$ $r-1$ elements of the remaining $n-1$ $n-1$ to choose from.
- Ok, done. —David Eppstein (talk) 02:59, 28 November 2022 (UTC)[reply]
This is not the characterisation of $n=2r$ $n=2r$ that I was expecting. The one I have seen is this: pair each $(n/2)$ $(n/2)$ -set with its complement; then any of choice of 1 set from each pair is intersecting (if a pair doesn't intersect, their union is size n, so the sets were complements). Each of the $2^{{\frac {1}{2}}{\binom {n}{n/2}}}=2^{\binom {n-1}{r-1}}$ $2^{{\frac {1}{2}}{\binom {n}{n/2}}}=2^{\binom {n-1}{r-1}}$ maximum intersecting families are of this form.
However, the two constructions you give only allow for $2n$ $2n$ of the maximum families: those that contain each $x\in \{1,2,3,\dots ,n\}$ $x\in \{1,2,3,\dots ,n\}$ , and those that are disjoint from $x\in \{1,2,3,\dots ,n\}$ $x\in \{1,2,3,\dots ,n\}$ . For $r=2,n=4$ $r=2,n=4$ this does happen to be all 8 families, but for $r=3,n=6$ $r=3,n=6$ you cannot obtain (e.g.) the family of all 10 sets that contain $1$ $1$ except $\{1,2,3\}$ $\{1,2,3\}$ , which is swapped out for its complement $\{4,5,6\}$ $\{4,5,6\}$ .
- Excellent catch. This was an error. Fixed. —David Eppstein (talk) 02:59, 28 November 2022 (UTC)[reply]
In this case, a family of nearly-maximum size has an element which is common to almost all of its sets. Is "nearly-maximum" meant to have a formal meaning? I understand the intuition of the sentence but not its rigorous meaning.
- There are three references here, each having somewhat different definitions of nearly-maximal size and almost all. Maybe the simplest is the one in Friedgut 2008, which states that when an intersecting family has size at least $1-\varepsilon$ times the size of the EKR bound, then you can remove $\varepsilon {\tbinom {n}{r}}$ sets from it to get a family with a shared element. So here "nearly maximum" is the $1-\varepsilon$ factor lower-bounding the size of the family. Friedgut and Dinur 2009 don't limit the size of the intersecting family, but instead prove some sort of limiting relation as $n$ and $r$ both go to infinity with $r=o(n)$ , showing that in that case you can remove approximately ${\tfrac {r}{n-r}}{\tbinom {n-1}{r-1}}$ sets to get a family with a shared element. In this case, "nearly maximum" is weaker, but you still need a large-enough family for the stuff you remove to be a negligible fraction of it. —David Eppstein (talk) 05:28, 28 November 2022 (UTC)[reply]
(even allowing new elements to be added) – Added to what, the existing sets in the family? New elements from $\{1,2,\dots ,n\}$ $\{1,2,\dots ,n\}$ , or "new" as in elements not previously in the ground set?
- The latter. Rewrote to try to clarify this. —David Eppstein (talk) 05:28, 28 November 2022 (UTC)[reply]

Related results

Could stabilizer be linked to stabilizer subgroup or something else that explains the group theory definition?
- Ok, done. —David Eppstein (talk) 05:54, 28 November 2022 (UTC)[reply]
I understand it from context, but it wasn't clear to me until I read further what it means for two strings to "have a common symbol": it means that they share the same symbol in the same position i.e. s and t have a common symbol iff there exists some index i such that $s[i]=t[i]$ $s[i]=t[i]$ . Could this be explained in the prose? Also, "fixing the symbol" might rightly be "fixing a symbol" (you can choose any symbol from the alphabet).
- Rewrote to clarify. —David Eppstein (talk) 05:54, 28 November 2022 (UTC)[reply]
An unproven conjecture, posed by Gil Kalai and Karen Meagher – The year in which the conjecture was made might be useful.
- Kalai posted this to MathOverflow in November 2012 [1]. He wrote "Remark: This problem was raised independently around the same time by Karen Meagher and by me." It is far from clear whether the time that they both raised it was anywhere near the time that he posted it. —David Eppstein (talk) 05:59, 28 November 2022 (UTC)[reply]

Applications

"subsets with large convex combinations" – What does "large" mean here and what are we taking "subsets" of? My guess is that we mean subsets of the $x_{i}$ $x_{i}$ variables, and "a large number of non-zero coefficients" (perhaps "more than half", so Erdős–Ko–Rado would seem to apply).
- When ${\vec {x}}$ and ${\vec {y}}$ are the indicator vectors of two subsets $X$ and $Y$ , and both $c({\vec {x}})\geq {\tfrac {1}{2}}$ and $c({\vec {y}})\geq {\tfrac {1}{2}}$ (both subsets have large convex combinations), then $X\cap Y\neq \emptyset$ . —David Eppstein (talk) 07:17, 28 November 2022 (UTC)[reply]
I'm not clear on what "improper colorings" means from the link to graph coloring—or perhaps it indicates many different generalisations of colorings?
- An improper coloring is just any assignment of colors to vertices that is not required to respect the edges: some edges may have both endpoints the same color. This is standard terminology in graph coloring. The graph coloring link uses that phrase but without explaining it very well. I don't think we have a better link for the phrase. Graph labeling would be another possibility but it doesn't even mention the phrase. —David Eppstein (talk) 06:10, 28 November 2022 (UTC)[reply]

References

In ref #22, "Godsil & Meagher (2015, p. 22)." has a strangely formatted link, slightly different to the other references in the article.
- I don't know why {{sfnp}} and {{harvtxt}} format page numbers differently. Fixed. —David Eppstein (talk) 06:03, 28 November 2022 (UTC)[reply]
I'm happy to see lots of freely accessible links here and spotchecking a few, all the content in the article looks to be well-sourced and strikes the balance of being verifiable without close paraphrasing of any kind.

A very well-written article, but I've done my best to find suggestions that could be of help. Let me know what you think! — Bilorv (talk) 22:11, 27 November 2022 (UTC)[reply]

I'm happy with all these responses and changes, so it's a

pass for GA. Thanks for the speedy reply and I hope the feedback has been useful! — Bilorv (talk) 22:00, 28 November 2022 (UTC)[reply]