Talk:Erdős–Ko–Rado theorem/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

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]