Pith. sign in

REVIEW 3 major objections 7 minor 29 references

The neighbourhood convexity

T0 review · 3 major / 7 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Star vertices appear exactly in odd-order n-convex geometries.

desk verdict Genuinely new graph convexity with a clean parity theorem; the central proof chain is sound and the main soft spots are editorial. read the letter →

arxiv 2608.25912 v1 pith:OLMQJI5Y submitted 2026-08-26 math.CO

Daniela Bubboloni , José Cáceres This is my paper · ORCID
classification math.CO MSC 05C7506A0652A01
keywords NeighbourhoodconvexityConvexgeometrypreorderQuasi-starStarvertexGraphTruetwinsParity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a graph convexity—neighbourhood convexity, or n-convexity—in which a set is convex exactly when it is the set of vertices adjacent to every member of some chosen set. The central result is a parity dichotomy: if a graph forms an n-convex geometry under this convexity, then it contains a star vertex (a vertex adjacent to all others) exactly when the number of vertices is odd. Every odd-order geometry therefore decomposes uniquely as an even-order geometry with one universal vertex attached, while the even-order case remains open. The paper also connects n-convexity to the neighbourhood preorder, where vertices are ordered by inclusion of closed neighbourhoods, and shows that n-convex sets are upsets of that preorder and that quasi-stars—vertices of degree |V|−2—are the maximal elements in star-free geometries.

What carries the argument

The machinery has four interlocking pieces. The first is the neighbourhood closure operator, $\widehat{X}=N[N[X]]$, where $N[X]$ is the common closed neighbourhood $\bigcap_{x\in X}N[x]$; the fixed points of this closure are exactly the n-convex sets. The second is the class of quasi-stars, $D=\{x:d(x)=|V|-2\}$, together with the map $v(x)$ returning the unique vertex outside $N[x]$; under true-twin-freeness this map is a bijection from $D$ onto the extreme vertices of the geometry. The third is the reduction theorem: in a star-free n-convex geometry of order at least three, deleting a quasi-star $x$ and its paired vertex $v(x)$ yields a smaller n-convex geometry without stars. The fourth is the star-augmentation construction $G^*$, which adds one universal vertex and passes the n-convex-geometry property back and forth between a star-free graph and its star-augmented version.

What would settle it

Run a brute-force search over all graphs with up to, say, eight vertices: compute the n-convex sets, check the convex-geometry property via anti-exchange, and test whether any even-order n-convex geometry has a non-empty star set $N[V]$; the paper predicts none exists, so a single such graph would refute the parity theorem.

Watch

Extended reading notes

Core claim

The paper establishes that n-convex geometries are almost never hereditary: the only hereditary examples are K1 and 2K1. It then proves a structural dichotomy controlled by parity: an n-convex geometry has a star vertex if and only if its order is odd, and when a star exists it is unique, so the whole geometry is the star-augmentation of the even-order geometry obtained by deleting that star. The proof route is structural. First, n-convex geometries must be free of true twins. Then, every extreme vertex is matched to a quasi-star, a vertex whose closed neighbourhood misses exactly that one vertex, giving a bijection between quasi-stars and extreme vertices. Removing a quasi-star together with its unique non-neighbour preserves the convex-geometry property and reduces the order by two; iterating that reduction leaves a two-vertex graph, which is why odd order forces a star.

Load-bearing premise

The load-bearing step is the claim that an n-convex geometry cannot contain two true twins, meaning two vertices with identical closed neighbourhoods; that lemma underpins the bijection between quasi-stars and extreme vertices and hence the parity theorem, and the printed proof of the lemma contains a stray sentence that appears to assume the conclusion while it is still being established.

Editorial extensions

If this is right

  • Every odd-order n-convex geometry is uniquely described as the star-augmentation of an even-order star-free n-convex geometry, so classifying n-convex geometries reduces completely to the even-order case.
  • The reduction theorem provides a recursive way to shrink any star-free n-convex geometry down by two vertices at a time, suggesting a generation scheme for building n-convex geometries if the reduction can be reversed.
  • Any n-convex geometry with at least four vertices must contain an induced $P_4$ or $C_4$, because the only quasi-threshold and threshold n-convex geometries are $K_1$, $2K_1$, and $P_3$.
  • In star-free n-convex geometries, every non-empty n-convex set contains a quasi-star, and the quasi-stars are exactly the maximal elements of the neighbourhood poset.
  • The only disconnected graph that is an n-convex geometry is $2K_1$, so the usual component-wise hereditary analysis used for path-based convexities cannot be applied to n-convexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The parity dichotomy suggests a recursive generation program: first produce all even-order n-convex geometries by inverting the quasi-star reduction, then obtain every odd-order geometry by attaching a star vertex; Section 9 shows one such inversion but leaves the full family of even-order constructions open.
  • Because n-convex sets are upsets of the neighbourhood poset, computational problems such as computing the n-convex hull or recognizing an n-convex geometry may be approachable through order-theoretic reachability in $P(G)$, a direction the paper leaves for future work.
  • If the true-twins-free lemma is repaired, the same proof skeleton—quasi-star bijection plus pairwise reduction—could extend to other closure operators built from intersection-closed set systems, giving a general parity theorem for such convexities.
  • The unavoidable presence of an induced $P_4$ or $C_4$ in every n-convex geometry of order at least four constrains any search for additional even-order constructions, since a construction that produces only sparse graphs will never generate all even-order geometries.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The paper establishes that n-convex geometries are almost never hereditary: the only hereditary examples are K1 and 2K1. It then proves a structural dichotomy controlled by parity: an n-convex geometry has a star vertex if and only if its order is odd, and when a star exists it is unique, so the whole geometry is the star-augmentation of the even-order geometry obtained by deleting that star. The

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. The paper introduces neighbourhood convexity (n-convexity) on finite graphs, defined through the common closed-neighbourhood closure operator, and studies when the resulting convexity space is a convex geometry. The main structural results are: n-convex geometries are true-twins free (Theorem 14); the only disconnected n-convex geometry is 2K1 (Theorem 15); there is a surjective map, bijective for true-twins-free graphs, from quasi-stars D to extreme points (Theorem 23); star-free geometries admit a two-vertex deletion reduction (Theorem 33); star augmentation preserves the geometry property (Theorem 36); and a parity dichotomy holds, namely an n-convex geometry has a star vertex if and only if its order is odd (Corollary 38), with odd-order geometries uniquely decomposed as star-augmentations of even-order ones (Proposition 39). The paper also connects n-convexity to the neighbourhood preorder P(G), classifies paths, cycles, fans, complete bipartite graphs, and quasi-threshold/threshold graphs among n-convex geometries, and discusses quasi-star augmentation as a construction for even-order geometries.

Significance. The parity characterization in Corollary 38 is clean, striking, and, as far as I can check, correct. The central line of proof, from Theorem 14 through Theorem 23 and Theorem 33 to Corollary 38, is derived from the definitions without fitted parameters or external assumptions, and the paper is careful to separate open questions from proved statements in several places. The result also contributes to the small literature on non-hereditary convex geometries. The connection with the neighbourhood preorder and the explicit construction of n-convex geometries of every order are useful additions. The main weaknesses are completeness issues: an unproved theorem in Section 9 and an unreproduced computer check in Proposition 21(ii), neither of which affects the parity theorem but both of which must be fixed before the paper can be accepted in its current form.

major comments (3)
  1. [Section 4.1, Theorem 14] The final sentence of the proof reads "against the fact that no pairs of true twins exists," but that fact is exactly what the theorem is proving. This is a circular step. The circular sentence is not needed: the preceding argument already shows that for every y in [x]_N^hat, the set [x]_N^hat \ {y} has neighbourhood closure [x]_N^hat, so [x]_N^hat is a non-empty n-convex set with no extreme points, contradicting the definition of a convex geometry. Please delete or correct the final sentence, since Theorem 14 is foundational for the rest of the paper.
  2. [Section 9, Theorem 46] Theorem 46 is stated as a result, but its proof is omitted with the sentence "The proof of Theorem 46 is technical and we omit it." An unproved theorem in the main body cannot be accepted as a proved contribution. This result is load-bearing for the discussion of constructing even-order geometries: it is what licenses the claim that a quasi-star-augmented graph is again an n-convex geometry. Please provide a complete proof, move the statement to the conjectures, or remove the claim.
  3. [Section 4.2, Proposition 21(ii)] The proof of Proposition 21(ii) reduces the claim to cases 5 <= k <= 8 and states that these are "checked by computer," but no code, input data, output, or verifiable certificate is provided, and Reiman's theorem is invoked without a reference. Since Proposition 21(ii) is used to conclude that forests of order at least 5 are not n-convex geometries, this unsubstantiated computational check is a real gap. Please replace it with a human-verifiable proof or supply a reproducible computational appendix.
minor comments (7)
  1. [Section 3, Definition 5] The phrase "a a graph" should read "a graph."
  2. [Section 2.2, Theorem 1(4)] "It does not exists a C-copoint" should be "There does not exist a C-copoint."
  3. [Section 3, proof of Proposition 6(9)] The reference "By (10)" should be "By (8)", since the proposition has only parts (1) through (9).
  4. [Section 4.2, proof of Theorem 18(2)] The text cites "Theorem 16" for the statement that a complete graph is not an n-convex geometry, but the result is Proposition 16; the same incorrect citation appears in the proof of Proposition 40.
  5. [Section 4.3, after Corollary 24] The sentence "the graph obtained by C4 adding a star are both n-convex geometries" is grammatically unclear; please state precisely which graph is being constructed and use consistent singular/plural agreement.
  6. [Section 6, proof of Theorem 36] In the case Y = empty, the notation "ex*(s)" should be "ex*({s})" to denote the extreme points of the singleton set {s}.
  7. [Conclusions and future work] The two conjectures mention computational verification for graphs up to 9 vertices, but no details of the check are given; if these checks are intended as evidence, please describe them or make code available.

Circularity Check

1 steps flagged · score 1.0 of 10

No load-bearing circularity: the only circular-looking line is a removable stray sentence in Theorem 14; the parity characterization is independently derived.

  1. other [Section 4.1, Theorem 14 (final paragraph)]
    "Finally, assume, by contradiction, that there exists ̸=s ′∈S. Thens,s ′ are a pair of true twins, becauseN[s] =V=N[s ′], against the fact that no pairs of true twins exists."

    The theorem's proof is a contradiction argument meant to establish that G has no true twins. Its final sentence finds s,s' with N[s]=V=N[s'] and calls them true twins 'against the fact that no pairs of true twins exists', i.e. it invokes the very statement being proved. Read literally, that branch is circular. But the preceding argument already proved that every K\{y} fails to be n-convex via \hat{S}⊇[x]_N^V≠S, so the sentence is redundant and can be deleted without affecting the proof. It is an editing artifact, not a load-bearing circular step.

full rationale

After checking the derivation chain for Corollary 38 and Proposition 39, I find no load-bearing circularity. The foundational Theorem 14 contains a stray final sentence that literally invokes 'no pairs of true twins exists' while proving that fact; read literally this would be circular, but the sentence is not needed. The valid part of the proof lets K=[x]_N^V; for any y∈K, S=K\{y} contains a non-empty subset of the twin class [x]_N\{y}, so \hat{S}⊇[x]_N^V=K≠S, hence S is not n-convex; therefore K is a non-empty n-convex set with no extreme point, contradicting the convex-geometry property. This establishes true-twins-freeness without the stray sentence. Theorem 23 (bijection between quasi-stars and extreme vertices) uses only that valid part; Theorem 33 deletes a quasi-star pair; Theorem 36 gives the star-augmentation equivalence; Corollary 38 iterates the deletion to get the parity result; Proposition 39 restates the unique-star construction. No fitted parameter is renamed as a prediction, no quantity is defined in terms of the result it is used to prove, and the only self-citation ([6]) supplies the closure operator and its elementary properties—the object of study, not the target theorem. The omitted proof of Theorem 46 and the computer check in Proposition 21(ii) are editorial gaps, but neither is used for Corollary 38 or Proposition 39. The conjectures at the end are explicitly conjectural and not load-bearing. Therefore the appropriate finding is 'no significant circularity' apart from the removable artifact, scored at 1.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

Pure mathematics with no fitted parameters. The axioms are the standard convex geometry results and external facts (Reiman's theorem, a computer check, and an external thesis) that the paper invokes without proof. No new physical or structural entities are postulated; n-convexity and quasi-stars are definitions, not unexplained assumptions.

assumptions (4)
  • standard math Standard convex geometry machinery: Theorem 1 equivalences (anti-exchange, extensibility, copoints) and Lemma 2 (copoint lemma).
    Imported from [15,27] and used throughout Sections 4 and 5; the paper does not reprove these facts.
  • standard math Reiman's theorem on C4-free graphs (Zarankiewicz bound) is correct and applies as stated.
    Used in Proposition 21(ii) with the bound |E| > k/4 (1 + sqrt(4k-3)); cited as 'Reiman's Theorem' without proof.
  • domain assumption The computational verification for 5 <= k <= 8 in Proposition 21(ii) is correct.
    The paper states 'The small cases 5 <= k <= 8 are checked by computer' and provides no code or data, so the reader must accept the result on faith.
  • domain assumption Results borrowed from Mori's Master's thesis [22] are correct and are used with permission.
    Acknowledged in the Acknowledgements section, but the specific results from the thesis are not identified, so the dependency cannot be audited.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The neighbourhood convexity." pith.science (2026). https://pith.science/paper/OLMQJI5Y

@misc{pith2026260825912,
  author       = {Pith},
  title        = {Pith review of: The neighbourhood convexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OLMQJI5Y}},
  note         = {Machine review of arXiv:2608.25912}
}
abstract

In this paper, we investigate the neighbourhood convexity ($n$-convexity) on graphs, a new finite convexity space grounded in the common closed neighbourhood closure operator. Unlike standard path-based graph convexities, $n$-convexity shows a non-canonical behaviour, giving rise to compelling structural properties and being almost never hereditary. Focusing on the properties of graphs that form $n$-convex geometries, a parity distinction emerges: an $n$-convex geometry contains a star vertex if and only if the number of its vertices is odd. Every odd-order $n$-convex geometry can be uniquely constructed by attaching a star vertex to an even-order one. We introduce the concept of quasi-stars (vertices of degree $\vert{}V\vert{}-2$) and prove a reduction property that allows systematically reducing an $n$-convex geometry by removing a pair of vertices, one of which is a quasi-star. Finally, we explore the connections between $n$-convexity and $P(G)$, the neighbourhood preorder, demonstrating that $n$-convex sets are upsets of $P(G)$ and that, in star-free $n$-convex geometries, quasi-stars correspond precisely to the maximal elements of $P(G)$. We complete our study by classifying quasi-threshold and threshold $n$-convex geometries.

Figures

Figures reproduced from arXiv: 2608.25912 by the authors.

Figure 1
Figure 1. The clique ↑ 0 is not maximal. 5.3 Convex geometries and neighbourhood poset Proposition 30. Let G = (V, E) be an n-convex geometry with no star. Then D = Max(V ). Proof. Let k := |V |. Then k ≥ 2. To start with, recall that, since G is an n-convex geometry, P(G) = (V, ≤) is a poset. We show D = Max(V ). We first show D ⊆ Max(V ). Let x ∈ D and let y ∈ V be such that x ≤ y, that is, N[x] ⊆ N[y]. We want to show that… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Armstrong,The Sorting Order on a Coxeter Group, Journal of Combinatorial Theory, Series A 116 (2009), no

    D. Armstrong,The Sorting Order on a Coxeter Group, Journal of Combinatorial Theory, Series A 116 (2009), no. 8, pp. 1285–1305. DOI: 10.1016/j.jcta.2009.03.009

    work page doi:10.1016/j.jcta.2009.03.009 2009

  2. [2]

    Convex Geometry of Building Sets

    S. Backman, R. Danner,Convex Geometry of Building Sets, arXiv:2403.05514, 2024

    work page Pith review arXiv 2024

  3. [3]

    Bertsimas, I

    D. Bertsimas, I. Popescu,Optimal inequalities in probability theory: a convex optimization approach, SIAM Journal on Optimization, 15(3) (2005), pp. 780–804

    work page 2005

  4. [4]

    J. M. Bilbao, P. H. Edelman,The Shapley value on convex geometries, Discrete Applied Mathematics 103 (2000), pp. 33–40

    work page 2000

  5. [5]

    Boesch, C

    F. Boesch, C. Suffel, R. Tindell,The neighborhood inclusion structure of a graph, Mathe- matical and Computer Modelling, 17(11) (1993), pp. 75–28

    work page 1993

  6. [6]

    Bubboloni, N

    D. Bubboloni, N. Pinzauti,Critical classes of power graphs and reconstruction of directed power graphs, Journal of Group Theory 28 (2025), pp. 713–739. https://doi.org/10.1515/jgth-2023-018. 26

    work page doi:10.1515/jgth-2023-018 2025

  7. [7]

    Bubboloni, N

    D. Bubboloni, N. Pinzauti,Critical groups and partitions of finite groups, Mediterranean Journal of Mathematics 22(131) (2025). https://doi.org/10.1007/s00009-025-02865-8

    work page doi:10.1007/s00009-025-02865-8 2025

  8. [8]

    Cáceres, O

    J. Cáceres, O. Oellermann,On3-Steiner simplicial orderings, Discrete Mathematics 309 (2009), pp. 5828–5833

    work page 2009

Show all 29 references
  1. [9]

    Chalopin, V

    J. Chalopin, V. Chepoi, K. Knauer,Geometry of convex geometries, arXiv:2405.12662v2

  2. [10]

    B. A. Davey, H. A. Priestley, Introduction to Lattices and Order, 2nd edition Cambridge University Press (2002)

    2002

  3. [11]

    M. C. Dourado, J. G. Gimbel, J. Kratochvíl, F. Protti, J. L. Szwarcfiter,On the computa- tion of the hull number of a graph, Discrete Math. 309 (2009), pp. 5668–5674

    2009

  4. [12]

    M. C. Dourado, M. Gutierrez, F. Protti, R. Sampaio, S. Tondato,Characterizations of graph classes via convex geometries: A survey, Discrete Applied Mathematics 360 (2025), pp. 246–257

    2025

  5. [13]

    F. F. Dragan, F. Nicolai, A. Brandstädt,Convexity and HHD-free graphs, SIAM Journal on Discrete Mathematics 12 (1999), pp. 119–135

    1999

  6. [14]

    Duchet, Convexity in combinatorial structures, Proceedings of the 14th Winter School on Abstract Analysis, Publisher: Circolo Matematico di Palermo (Palermo), No.14 (1987), pp

    P. Duchet, Convexity in combinatorial structures, Proceedings of the 14th Winter School on Abstract Analysis, Publisher: Circolo Matematico di Palermo (Palermo), No.14 (1987), pp. 261–293

    1987

  7. [15]

    P. H. Edelman, R. E. Jamison,The theory of convex geometries, Geometriae Dedicata 19 (1985), pp. 247–270. https://doi.org/10.1007/BF00149365

    1985 doi

  8. [16]

    M.Farber, R.E.Jamison,Convexity in graphs and hypergraphs, SIAMJournalonAlgebraic Discrete Methods 7 (1986), pp. 433–444

    1986

  9. [17]

    Földes, P

    S. Földes, P. L. Hammer,The Dilworth number of a graph, Annals of Discrete Mathematics 2 (1978), 211–219

    1978

  10. [18]

    Knauer, W

    K. Knauer, W. T. Trotter,Concepts of Dimension for Convex Geometries, SIAM Journal on Discrete Mathematics 38 (2024), no. 2, pp. 1566–1585. DOI: 10.1137/23M1559853

    2024 doi

  11. [19]

    L. Li, J. Wang, M. Brunetti,Seidel matrices, Dilworth number and an eigenvalue- free interval for cographs, Linear Algebra and its Applications 698 (2024), 56–72. https://doi.org/10.1016/j.laa.2024.05.022

    2024 doi

  12. [20]

    D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, Springer International Publishing AG Switzerland, 2016

    2016

  13. [21]

    Ma,Enumeration of Hopf Monoids and Supersolvable Convex Geometries, arXiv:2506.00380, 2025

    Y. Ma,Enumeration of Hopf Monoids and Supersolvable Convex Geometries, arXiv:2506.00380, 2025

    2025 arXiv

  14. [22]

    Mori, Convexity in graphs, Master’s Thesis in Mathematics (thesis supervisor D

    F. Mori, Convexity in graphs, Master’s Thesis in Mathematics (thesis supervisor D. Bub- boloni), DIMAI, University of Florence (Italy), 2024

    2024

  15. [23]

    K. Murota,Discrete convex analysis: A tool for economics and game theory, The Journal of MechanismandInstitutionDesign, SocietyforthePromotionofMechanismandInstitution Design, University of York, vol. 1(1) (2016), pp. 151–273. 27

    2016

  16. [24]

    I. M. Pelayo, Geodesic Convexity in Graphs, Springer-Verlag, 2013

    2013

  17. [25]

    U. N. Peled, M. K. Srinivasan,Vicinal orders of trees, Discrete Applied Mathematics 29 (1990), 211–219

    1990

  18. [26]

    F. P. Preparata, M. I. Shamos, Computational Geometry: An Introduction, Springer- Verlag, New York, NY, 1985

    1985

  19. [27]

    Van de Vel, Theory of Convex Structures, North-Holland, Amsterdam, MA, 1993

    M. Van de Vel, Theory of Convex Structures, North-Holland, Amsterdam, MA, 1993

    1993

  20. [28]

    D. B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1999

    1999

  21. [29]

    Yan, J-J

    J-H. Yan, J-J. Chen, G. J. Chang,Quasi-threshold graphs, Discrete Applied Mathematics 69 (3) (1996), 247–255. 28

    1996

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.