Talk:Matroid parity problem

GA review

This review is transcluded from Talk:Matroid parity problem/GA1. The edit link for this section can be used to add comments to the review.

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

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

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)