Perfect graph 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: May 6, 2024. ( Reviewed version). |
This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
What is the interest of introducing "1-perfect" here? Is it just for the attached reference? — Preceding unsigned comment added by 88.121.200.153 ( talk) 08:20, 13 October 2021 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Brachy0008 ( talk · contribs) 03:24, 15 January 2024 (UTC)
Hi! Brachy08 here! I will be your reviewer for this GA (because, you know, WikiCup 2024). However, I would take some time to review it (I am a math person, as a disclaimer regarding criterion 1).
Thanks for taking this on! Please ping me when you have concrete improvements that need to be made to the article. Re summarization: there are quite a few short glosses of linked terms already in the article, if that's what you mean; more might be appropriate but to some extent this is limited by Good Article criterion 3b. — David Eppstein ( talk) 08:31, 15 January 2024 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Jakob.scholbach ( talk · contribs) 13:08, 17 March 2024 (UTC)
I will start reviewing this article! Other comments welcome!
Jakob.scholbach (
talk) 13:08, 17 March 2024 (UTC)
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.
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.
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.
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.
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.
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".
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.
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.
Re "on split graphs, it would be beautiful to color the illustration": I replaced the illustration with a new one depicting the coloring method.
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.
— David Eppstein ( talk) 19:01, 26 March 2024 (UTC)
@ 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)
GA review (see here for what the criteria are, and here for what they are not) |
---|
|
Overall: |
· · · |
Perfect graph 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: May 6, 2024. ( Reviewed version). |
This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
What is the interest of introducing "1-perfect" here? Is it just for the attached reference? — Preceding unsigned comment added by 88.121.200.153 ( talk) 08:20, 13 October 2021 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Brachy0008 ( talk · contribs) 03:24, 15 January 2024 (UTC)
Hi! Brachy08 here! I will be your reviewer for this GA (because, you know, WikiCup 2024). However, I would take some time to review it (I am a math person, as a disclaimer regarding criterion 1).
Thanks for taking this on! Please ping me when you have concrete improvements that need to be made to the article. Re summarization: there are quite a few short glosses of linked terms already in the article, if that's what you mean; more might be appropriate but to some extent this is limited by Good Article criterion 3b. — David Eppstein ( talk) 08:31, 15 January 2024 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Jakob.scholbach ( talk · contribs) 13:08, 17 March 2024 (UTC)
I will start reviewing this article! Other comments welcome!
Jakob.scholbach (
talk) 13:08, 17 March 2024 (UTC)
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.
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.
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.
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.
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.
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".
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.
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.
Re "on split graphs, it would be beautiful to color the illustration": I replaced the illustration with a new one depicting the coloring method.
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.
— David Eppstein ( talk) 19:01, 26 March 2024 (UTC)
@ 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)
GA review (see here for what the criteria are, and here for what they are not) |
---|
|
Overall: |
· · · |