Talk:Matroid parity problem/GA1

GA review

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

Nominator: David Eppstein (talk · contribs) 07:53, 14 January 2025 (UTC)[reply]

Reviewer: Gramix13 (talk · contribs) 04:33, 30 July 2025 (UTC)[reply]

Hello! I want to preface that this will be my first review of a Good Article. If you prefer to have a more experienced GA reviewer look at this article, I won't mind "failing" this article to allow for a different reviewer, or asking for a second opinion. My goal will be to finish this review within a week, but if I need more time I will communicate that here. Gramix13 (talk) 04:33, 30 July 2025 (UTC)[reply]

Summary of review

Rate	Attribute	Review Comment
1. Well-written:
	1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct.
	1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation.
2. Verifiable with no original research, as shown by a source spot-check:
	2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline.
	2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose).	There's at least one citation per paragraph, which I find sufficent for this criteria.
	2c. it contains no original research.
	2d. it contains no copyright violations or plagiarism.
3. Broad in its coverage:
	3a. it addresses the main aspects of the topic.
	3b. it stays focused on the topic without going into unnecessary detail (see summary style).
	4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each.
	5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute.	According to Xtools, this article has only 3 editors (excluding bots), one of which being David Eppstein the nominator, and the other two having made only single edits each in 2017. In short, this article is (vacuously) stable from the absence of any other major contributor other than Eppstein.
6. Illustrated, if possible, by media such as images, video, or audio:
	6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content.	Both images are uploaded by the nominator with CC0 1.0 Universal license.
	6b. media are relevant to the topic, and have suitable captions.
	7. Overall assessment.

Discussion

Here's an outline of how I plan to handle the review. I'll first do an initial read of the article to check criteria 1a (ensuring the prose is understandable), 2b (ensuring citations are included for anything that could be challenged), 4 (which as a non-BLP mathematics article, I doubt this would fail), and 6 (since I want to judge the illustrations as I understand the article to see if I find them useful and relevant). This would be followed by a second read for criteria 1b as I check the MOS against the article. I'll then be performing a spot check of the articles (I'll try to include a good number of the open access sources in that spot check) to ensure the article meets criteria 2 in being verifiable, while also checking if it satisfies criteria 3 in being broad. Once that is completed, I'll be able to give my overall assessment if there are no pending changes that should be made. I have already rated criteria 5 as a pass, with my rationale written above. Gramix13 (talk) 04:33, 30 July 2025 (UTC)[reply]

Prose comments

Below are my (threaded) comments on the prose as I'm doing a first pass. Feel free to comment on each individual one if you prefer that over making one message addressing each of these points. Gramix13 (talk) 04:42, 30 July 2025 (UTC)[reply]

In terms of the lead, I noticed that the main subject of this problem, Matroids, aren't defined (even loosely) in the leading paragraphs. The lead currently is on the shorter side in my view, so I don't think a brief explanation (even if not precise) on matroids would cause issues in terms of length. There are other terms here that aren't defined, but as the lead is supposed to be a summary, I don't really think those other terms provide an issue in the goal of summarizing. I mainly bring up Matroid since, without an idea as to what it is, its difficult to understand the question posed by the problem.

I also want to bring up early some things I've noticed per MOS:LEADREL. I noticed that matroid oracle isn't mentioned outside of the lead, which might be significant enough to warrant a mention in the body. This goes for the compactly-represented matroids as well, mentioned in the same sentence as the oracle. Also not mentioned outside the lead is Lawler's formulation of the problem (his name is only written in the article in the lead and his citation), so a short mention of this in the Formulation section would suffice. Gramix13 (talk) 05:03, 30 July 2025 (UTC)[reply]

After reading MOS:INTRO, I now think the article should make a better effort to briefly explain some of the terminologies used in the lead section. To quote the guideline, Make the lead section accessible to as broad an audience as possible. Where possible, avoid difficult-to-understand terminology, symbols, mathematical equations and formulas. Where uncommon terms are essential, they should be placed in context, linked, and briefly defined. The subject should be placed in a context familiar to a normal reader... Readers should not be dropped into the middle of the subject from the first word; they should be eased into it. If you are to rewrite the lead in a way that concisely defines the terms used in the lead, that would greatly help the article meet criteria 1 of being a Good Article. Gramix13 (talk) 01:04, 2 August 2025 (UTC)[reply]

The image in the lead does illustrate the problem, but I do think the caption could elaborate on what a graphic matroid is so the reader can recognize the matroid evident in the problem (which I presume is represented as the colored edges of this graph). I think a small elaboration of a forest being a collection of trees would be helpful, especially since the image only shows a tree as the solution, when the reader should keep in mind we allow for multiple trees in the solution to the problem if necessary. Gramix13 (talk) 05:19, 30 July 2025 (UTC)[reply]

A matroid can be defined from a finite set of elements and from a notion of what it means for subsets of elements to be independent... I think this particular wording is fine as an introductory definition of a matroid, but I do think a more formal definition of a matroid should be included, in particular, what is the finite set we want to consider the matroid over, and what do we label as the set of independent sets. The main article has a good formulation of this under the independent sets definition that could be borrowed or modeled after. Gramix13 (talk) 05:28, 30 July 2025 (UTC)[reply]

Another seemingly more general variation, in which the allowable pairs form a graph rather than having only one pair per element, is equivalent: an element appearing in more than one pair could be replaced by multiple copies of the element, one per pair. This wording is admittedly confusing to me. What exactly do we mean by replacing an element with multiple copies? How exactly is this graph formed in the generalization, and could it be more precise as to what makes up this graph? Gramix13 (talk) 05:34, 30 July 2025 (UTC)[reply]

I think the terms "minimum-weight solution" and "maximum-weight paired independent set" need further clarification, its unclear as to what is being weighted in these solutions and why we would want to find them. Gramix13 (talk) 23:32, 30 July 2025 (UTC)[reply]

I think "indeterminate" should be replaced with "variable" since the later term is what's primarily used to describe each

t_{i}

, and the former term threw me off when I was trying to understand what it was referring to before I realized that the variables are in correspondence to each pair. Making that correspondence more clear would also help alleviate that issue I experienced. Gramix13 (talk) 23:45, 30 July 2025 (UTC)[reply]

I would appreciate adding an example demonstrating the use of an algorithm to solve the matroid parity problem. It doesn't need to be the state-of-the-art algorithm, just something that's relatively easy to explain to the reader so they have an idea of how it would be solved in practice. Gramix13 (talk) 23:52, 30 July 2025 (UTC)[reply]

The same problem can also be described as one of finding the largest Berge-acyclic sub-hypergraph of a 3-uniform hypergraph. Lots of jargon being used here that I feel a reader might not immediately know. Taking some time to define what Berge-acyclic and 3-uniform mean would be helpful for them, and possibly also defining the term hypergraph if it feels necessary. Gramix13 (talk) 03:13, 31 July 2025 (UTC)[reply]

I feel like there needs to be more background information explaining what rigid bars are in the combinatorial rigidity, I find that the section makes no effort to explain what rigid bars are, and it makes it difficult to understand what some of the vague terms used in the paragraph refer to. Gramix13 (talk) 03:26, 31 July 2025 (UTC)[reply]

The optimal embedding can then be obtained by pairing edges within each component and embedding each pair in such a way that it increases the genus by one. I feel like this could be elaborated on how this is creating a cellular embedding. That term should also probably be explained (if briefly) as well. Gramix13 (talk) 03:34, 31 July 2025 (UTC)[reply]

To formulate the problem of finding a Xuong tree as a matroid parity problem, first subdivide each edge

e

of the given graph into a path, with the length of the path equal to the number of other edges incident to

e

. I'm struggling to understand how this is formed, could this be clarified to explain the path in more detail, as well as how the subdivision is occurring? Gramix13 (talk) 03:43, 31 July 2025 (UTC)[reply]

In cubic graphs, this problem is closely related to connected domination. Both terms should be defined.

There is a linear equation relating the number of vertices, cyclomatic number, number of connected components, size of a minimum connected dominating set, and size of a minimum feedback vertex set. Sounds significant, is there a reasonable way to include this linear equation onto the article?

The same expansion of each vertex and each edge into a two-edge path, used for connected dominating sets, produces an expanded graph with paired edges. I feel like this would benefit from explaining what we mean by a graph expansion, as well as dominating sets. Gramix13 (talk) 03:54, 31 July 2025 (UTC)[reply]

The paving matroid should probably be defined when explaining hardness, its a new type of matroid to the reader. Maybe also define what a randomly-permuted graph is (what is being permuted to justify its name?). Gramix13 (talk) 03:59, 31 July 2025 (UTC)[reply]

That concludes my first read of the article. Overall, I mainly want to point out ways the article could better explain the subject and results, especially any terms that might be unfamiliar. My perspective has been of someone who is unfamiliar with matroids (which I admit that I was before reading this article). I also think some advanced terminology relating to graph theory could be explained more clearly, since I also wouldn't expect a reader to fully grasp some of those concepts. I'll wait to hear from you addressing these points before I considering passing criteria 1a.

As for the illustrations, I will wait to see if the caption on the lead image can be improved as I suggested above before passing criteria 6b. I do think additional illustrations might be helpful in the applications section so the reader can see visualization of how we are creating these matroids to solve those problems, but I think such a request would go beyond a GA review, so I won't hold the review against this suggestion. Gramix13 (talk) 04:09, 31 July 2025 (UTC)[reply]

Thanks for the in-depth review! It looks like responding properly will take a chunk of time that I might not have until Sunday or Monday (I am at a conference, giving a talk tomorrow, in transit all day Saturday, and late for reviewing a paper that I promised to get done by Saturday), so please don't be surprised if I don't do much about it until then. —David Eppstein (talk) 04:00, 1 August 2025 (UTC)[reply]

That sounds good to me! Sunday should probably give me enough time to review the MOS criteria for this article, as well as time to look at some of the sources for the spot check. If you see any further comments from me, don't worry about them until Sunday/Monday, when you do have time for the review. I hope your talk goes well by the way! Gramix13 (talk) 04:12, 1 August 2025 (UTC)[reply]

MOS comments

Here are my comments relating to the MOS criteria for this article. Gramix13 (talk) 23:54, 1 August 2025 (UTC)[reply]

This might not be necessary, but I noticed this article is lacking a See Also section, so I think some though should be put into adding one for this article. Maybe it could lead to other articles related to matroids perhaps, or maybe it can lead to articles related to the applications of the problem. I won't make this a requirement since MOS doesn't do so, but its worth considering. Gramix13 (talk) 23:58, 1 August 2025 (UTC)[reply]

I'm not sure if I agree with the use of the {{glossary}} template in the applications section, since to me it reads less like definitions of the problems and more like detailed explanations of how those problems can be transformed into matroid parity problems. Each of them is roughly a paragraph. If we can make those subsections of the Applications section instead of glossary terms, I think it would also improve the navigability of the article as the reader to jump to a specific application they might be interested in. This is the first time I've encountered this template, so if there is precedent for using the template in this fashion, please let me know and I can reconsider this suggestion if it is reasonable to use it in this context. Gramix13 (talk) 00:13, 2 August 2025 (UTC)[reply]

It might also be worth consider the use of {{See also}} in these new subsections as an easy way for the reader to jump to the main article of that application. Yes, most of the applications have the main article linked at the start, but since there's more to these subjects than what can be said in this article, I think being helpful to the reader by pointing them to their respective articles does more good than the harm of redundancy, but feel free to challenge me on this. Gramix13 (talk) 00:22, 2 August 2025 (UTC)[reply]

Putting a {{Further}} template in the Formulation section towards Matroids could help the reader find more information about matroids if they so wish, or if they need to see more about matroids before they feel reader to understand the parity problem. Gramix13 (talk) 00:25, 2 August 2025 (UTC)[reply]

I think having the lead image with upright=1.35 might be too large per WP:IMGSIZE since it just displays a graph, which I would argue does not have fine detail that would justify the large size. Per MOS:LAYIM, this size is at the limit of what's acceptable for a lead image size, so while the article might satisfy the size limit, it might be safe to make it smaller even if it already meets the MOS. Gramix13 (talk) 00:43, 2 August 2025 (UTC)[reply]

Overall, I think MOS:LAYOUT is met for this article, but as I elaborated above, there might be some room for improvement in this regard. Gramix13 (talk) 00:45, 2 August 2025 (UTC)[reply]

Per MOS:LEADCITE, the citations used in the last paragraph in the lead are unneeded if that information is also stated in the Applications section. The citation in the first sentence of the lead also could be safely removed since the definition of the problem is explained in the Formulation section. Now the same guideline doesn't necessarily prohibit those citations, so leaving the citations as is would be fine. Gramix13 (talk) 00:57, 2 August 2025 (UTC)[reply]