Talk:Logic of graphs

Logic of graphs 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: March 3, 2023. (Reviewed version).

GA Review

Passed. Bryan Rutherford (talk) 01:15, 3 March 2023 (UTC)[reply]

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

This review is transcluded from Talk:Logic of graphs/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Bryanrutherford0 (talk · contribs) 15:07, 1 March 2023 (UTC)[reply]

GA review (see here for what the criteria are, and here for what they are not)

It is reasonably well written.
a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):
The prose standard is excellent, and the article complies with all the indicated section of MoS.
It is factually accurate and verifiable.
a (reference section): b (citations to reliable sources): c (OR): d (copyvio and plagiarism):
The article has a reference section with citations to reliable published sources. The PDF link for Fagin (1976) is dead and should be either fixed or removed. The first paragraph of "Second order" could use a citation supporting the definitions of MSO₁ and MSO₂ (maybe one borrowed from the article Monadic second-order logic?). I think the "handle" link for Nešetřil & Ossona de Mendez (2012) points to a different work than the one cited (a paper called "A model theory approach to structural limits", rather than the book Sparsity: Graphs, Structures, and Algorithms).
It is broad in its coverage.
a (major aspects): b (focused):
From what I can see, this article covers the major aspects of graph logic (first-order and monadic second-order logic), along with a section on fixed-point logic. It doesn't stray into trivia or tangents.
It follows the neutral point of view policy.
Fair representation without bias:
The presentation is appropriately neutral, not e.g. overblowing the topic's significance or privileging one rival view over another.
It is stable.
No edit wars, etc.:
The article is stable, with no significant changes since nomination.
It is illustrated by images and other media, where possible and appropriate.
a (images are tagged and non-free content have non-free use rationales): b (appropriate use with suitable captions):
The article is illustrated by relevant images with suitable captions and licenses. ~~More illustrations would be helpful, but they aren't necessary to meet the GA standard.~~
Overall:
Pass/Fail:
A well-written and rich article! As a non-expert, the most challenging part of the article was the "Fixed point" section, and it would be very helpful to have some sort of simple illustration of a small graph with its "least fixed point" spelled out, along the lines of the (very helpful) illustration at the beginning of "First order". I can't tell how easy or difficult that would be to add, and I won't require it for GA, though it should probably be necessary for FA. Likewise, a simple illustration for the "Second order" section would be beneficial, though not as impactful as one in "Fixed point". ~~Beyond those suggestions, just a couple of tiny niggles on the sources.~~ Great work! -Bryan Rutherford (talk) 16:31, 1 March 2023 (UTC)[reply]

@Bryanrutherford0: Ok, references updated. I haven't added an illustration for the fixed point and second-order sections, but I'll try thinking about whether I can come up with a property that is nontrivial (not merely first-order) and easily illustrated. —David Eppstein (talk) 18:31, 2 March 2023 (UTC)[reply]

Fixed-point illustration added. —David Eppstein (talk) 19:49, 2 March 2023 (UTC)[reply]
Those changes look great! I also notice that one of the "handle" links seems not to lead to the book that's being cited? Finally, I apologize for being slow, but, an IP editor changed the word "hereditary" to "monotone" near the end of "Parameterized complexity", and I'm struggling to find the spot in any of the three works cited in [15] that confirms either of those assertions. Can you point me to the right spot? Thanks! -Bryan Rutherford (talk) 20:07, 2 March 2023 (UTC)[reply]
It's in the abstract of https://arxiv.org/abs/1311.3899: "At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption)." Here, "closed under taking subgraphs" = "monotone": the IP's correction was correct. —David Eppstein (talk) 23:59, 2 March 2023 (UTC)[reply]
I'm satisfied! Excellent work! -Bryan Rutherford (talk) 01:14, 3 March 2023 (UTC)[reply]

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Satisfiability: Trakhtenbrot's theorem

Hello, I suggest to refer to Trakhtenbrot's theorem in the Section Logic of graphs#Satisfiability. This page helped me a lot to get quickly into the subject, many thanks! 2001:861:35C0:9DC0:FE:398E:8827:8A4 (talk) 19:19, 3 November 2023 (UTC)[reply]

Ok, added. —David Eppstein (talk) 20:51, 3 November 2023 (UTC)[reply]

Great, thanks! Actually there is a complete proof of this corollary of Trakhenbrot's theorem for the case of undirected graphs, in the book of Ebbinghaus and Heinz-Dieter "Finite Model Theory" (1995): Proposition 10.3.4 page 289-290. This book is cited in the article Trakhtenbrot's_theorem. Maybe you can update the citation ? huacayacauh (talk) 09:10, 6 November 2023 (UTC)[reply]