Talk:Perfect graph/GA2

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

Reviewer: Jakob.scholbach (talk · contribs) 13:08, 17 March 2024 (UTC)[reply]

I will start reviewing this article! Other comments welcome! Jakob.scholbach (talk) 13:08, 17 March 2024 (UTC)[reply]

I think it would be easy to finish off this GA nomination by mechanically checking the GA criteria and finding that they are all satisfied. I have however never liked this way of approaching such a GA nomination, so I will offer some comments that come to my mind while reading the article. As you will immediately notice from the comments, I'm very much not into this area of mathematics, so I acknowledge beforehand that some of these comments may be missing the point, so please tell me if this is the case.

• I find the definitions section very short. It almost sends the reader away to other articles, which it should not. Is it possible to include a few illustrations or other explanatory text to make the article more self-contained? The later section on bipartite graphs contains some information that would be easy enough to digest as an illustration of the notion of clique number and chromatic number, for example. Another idea: is it sensible / possible to make little "zoo" of examples with graphs with small clique number and chromatic number? Or give examples of some graphs that fail to be perfect very badly / fail for interesting reasons.
• "The perfect graph theorem has a short proof," -- does this refer to the first proof in 1972, or did it get simplified later on?
• In several spots the word "perfection" is seemingly referred to the property of being perfect. Is this intentional (in my non-native English unterstanding, perfection refers to the process of rendering something perfect)?
• I'm not sure how actionable this is, but somehow the article doesn't convey (to me) the importance of the concept. Is it possible to shed light on why this is a difficult / interesting / noteworthy topic?
• The paragraph "The strong perfect graph theorem gives a different ..." has as a reference what seems to be the original article on the proof of the theorem. Is there a text-book account of this?
• The paragraph "Finite comparability graphs (and their complementary incomparability graphs) ..." could make better use of the illustration by referring to it. E.g. it could point out that A-B-D is a chain etc.
• "Mirsky's theorem is easier than Dilworth's theorem to prove directly" - maybe reword to "Mirsky's theorem is easier to prove directly than Dilworth's theorem" ?
• To an uninitiated reader (like me), lists such as "They include as subclasses the trees, even-length cycle graphs, lattice graphs, knight's graphs, modular graphs, median graphs, and partial cubes, among many others.[16]" are not so valuable. Maybe consider highlighting what is really crucial (to this article), and consider removing some such mentions that might be secondary?
• In the secion on split graphs, it would be beautiful to color the illustration in order to match the text. Or at least label the vertices, and refer to them in the text? (OR the image caption?)
• Inspired by the heading "random perfect graphs" -- I take it that the condition of being perfect is a rather strong condition. Is there any honest statement in such a direction?
• This may be another not-so-actionable comment, but I can't quite refrain from pointing it out: the section on families of perfect graphs is very long, and it just fails to catch me. E.g. "The threshold graphs are formed from an empty graph ..." this section seems (from the little I understand) to be a relatively trivial observation (right?) If this is true, it is just the n+1-st mention of several classes of graphs being contained in one another. If it is possible to highlight more of a red thread throughout, that would greatly improve the article. (I can imagine this is difficult though.)
• I will continue reviewing the rest of the article as soon as I can. Jakob.scholbach (talk) 22:12, 23 March 2024 (UTC)[reply]

Some responses to I think all of the above:

I'm much happier with a GA review that produces a dialogue about the article (even with points I might disagree with) than with one that just mechanically checks the criteria — ideally the process should end up improving the article and not merely certifying that it was already good enough. So thanks for that!

Re the definitions section being too short: Are you maybe thinking only of the first paragraph of the section, the one defining coloring number, clique number, and perfect graphs as (1) having those numbers equal in all induced subgraphs? It glosses all those topics, and also provides wikilinks to our separate articles on those topics, as it should. What part of it is not self-contained? Or are you referring to the later paragraphs of this section, the ones that provide equivalent definitions of perfect graphs in terms of (2) equal independence number and clique cover number, (3) no odd holes or their complements, or (4) product of clique number and independence number? That is, we have four paragraphs each providing a different definition of these graphs. I am not sure from your comment which part of this you think is too short.

I was referring to the first paragraph in the section "Definitions and characterizations". I think it does define all necessary preliminary notions, and does give links to the subtopics. However, to 95+% of readers who are not already familiar with these topics you basically have to follow these links to the subpages in order to get a better idea, and this need not (and IMO should not) be so. Why not include a few more sentences about these preliminary notions, maybe with a few illustrations? Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re the perfect graph theorem has a short proof: I was mostly referring to the proof through the product characterization of perfect graphs, Lovasz (the other 1972 paper) and Gasparyan. I added footnotes to clarify that point.

Thanks. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re "perfection" meaning "being perfect" rather than "making perfect" or "becoming perfect": in colloquial English it can have any of these three meanings. "Perfecting", instead, would only mean "making perfect". Google Scholar claims to have 634 hits for the combination of "perfect graph" and "perfection" and I suspect most or all of them are about being perfect rather than becoming perfect.

OK, alright Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re why perfection is difficult / interesting / noteworthy: these are three different questions. Re difficult, see history: "The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years ... the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition". Re interesting, see lead "include many important families of graphs and serve to unify results relating colorings and cliques in those families ... several important minimax theorems in combinatorics". Re noteworthy, see the many publications listed as references and the much larger number of publications not listed.

With my comment I didn't intend to say that I find this not difficult / not interesting or not noteworthy, but just that the difficulty / interest / noteworthyness of the topic didn't come across to me so well. But I agree that the snippets you cite do adress these, so maybe this is just me. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re "Is there a text-book account" of the proof of the strong perfect graph theorem? I added another reference, Cornuéjols' 2002 overview of the proof. You might expect it to be in the 2004 edition of Golumbic's book Algorithmic Graph Theory and Perfect Graphs but I don't have a copy of that edition and from my limited previous I suspect it's not there. Diestel's Graph Theory states the theorem but then immediately says "the proof...is long and technical, and it would not be too illuminating to attempt to sketch it".

OK! Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re comparability graphs: added examples of chains and antichains to 2nd paragraph; reordered sentence about Mirski being easier to prove than Dilworth per your suggestion.

OK. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re lists [of graph classes] not being valuable, and re "the section on families of perfect graphs is very long": this goes back to the lead's "The perfect graphs include many important families of graphs". For many decades a central subtopic of graph theory research was the push to prove special cases of the strong perfect graph theorem for special classes of graphs, and in turn many now-important special classes of graphs were identified as part of this push. It is central to the topic. In drafting this article, I tried to keep this part of the article organized into logical subsections, and to reduce its length by avoiding some not-very-important subclasses, but it is still long. Expanding out sentences like "They include as subclasses the trees, even-length cycle graphs, lattice graphs, knight's graphs, modular graphs, median graphs, and partial cubes, among many others" to detail the relations among these graphs would make it even longer.

Later, I trimmed the list of bipartite graph classes, and found some other changes to tighten the section on families of perfect graphs and focus it more clearly on properties related to perfection: [1]. It's not much shorter than it was before, though. —David Eppstein (talk) 18:20, 27 March 2024 (UTC)[reply]

Yes, I think trimming it there was a good decision. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re "on split graphs, it would be beautiful to color the illustration": I replaced the illustration with a new one depicting the coloring method.

Great, thanks! Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

Re random graphs, you mean, if one chooses a random graph without prior restrictions on its structure, is it extremely unlikely to be perfect? Yes, at least in the basic version of the Erdős–Rényi model where all graphs on the same vertex set are equally likely, because for any subset of vertices all induced subgraphs are equally likely. So each five-vertex set has some constant probability of inducing a hole and there are so many five-vertex sets that the probability of avoiding a hole becomes exponentially small. The same thing would be true for any nontrivial hereditary family of graphs. Probably it's difficult to source, though, because it's not very interesting (it doesn't have anything specific to do with being perfect). For very sparse random graphs, the graph will be a forest and therefore perfect. Random graphs with a linear number of edges below the threshold of a giant component are pseudoforests with a constant expected number of cycles, and I suspect that there is a constant probability of remaining bipartite (decreasing with edge density) up to the threshold, and therefore a constant probability of being perfect. But again finding a source that says anything about this specifically with respect to perfection is likely to be difficult.

OK, if this is trivial for an insider, then it's fine, it just came to my mind while reading. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)[reply]

It is mostly trivial. The part that is nontrivial (but I think doable) is proving that critical random graphs (that is, with edge probability ${\displaystyle {\tfrac {1}{n}}}$) are whp imperfect. All other probabilities are easy. But without sources, I can't add anything about this to the article. —David Eppstein (talk) 06:39, 9 April 2024 (UTC)[reply]

—David Eppstein (talk) 19:01, 26 March 2024 (UTC)[reply]

@Jakob.scholbach: I expanded the first paragraph of the definitions section and moved up an image to illustrate it. Was that the last unfinished business, or did you still have more to review? —David Eppstein (talk) 07:04, 14 April 2024 (UTC)[reply]

Sorry @David Eppstein, I meant to read the rest of the article but I have not found the time to do that. I will try to allocate some time to this until the weekend. If I don't manage, I'll just content myself with the GA criteria proper. Sorry for the delay! Jakob.scholbach (talk) 12:28, 25 April 2024 (UTC)[reply]