Pith. sign in

REVIEW 1 cited by

First-order logic axiomatization of metric graph theory

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2203.01070 v1 pith:2H6KHAFP submitted 2022-03-02 math.CO cs.DMcs.LO

Jérémie Chalopin , Manoj Changat , Victor Chepoi , Jeny Jacob This is my paper · ORCID
classification math.COcs.DMcs.LO
keywords graphsaxiomatizationcubesmatroidspartialgraphmetrictheory
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

The main goal of this note is to provide a First-Order Logic with Betweenness (FOLB) axiomatization of the main classes of graphs occurring in Metric Graph Theory, in analogy to Tarski's axiomatization of Euclidean geometry. We provide such an axiomatization for weakly modular graphs and their principal subclasses (median and modular graphs, bridged graphs, Helly graphs, dual polar graphs, etc), basis graphs of matroids and even $\Delta$-matroids, partial cubes and their subclasses (ample partial cubes, tope graphs of oriented matroids and complexes of oriented matroids, bipartite Pasch and Peano graphs, cellular and hypercellular partial cubes, almost-median graphs, netlike partial cubes), and Gromov hyperbolic graphs. On the other hand, we show that some classes of graphs (including chordal, planar, Eulerian, and dismantlable graphs), closely related with Metric Graph Theory, but defined in a combinatorial or topological way, do not allow such an axiomatization.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Bow Metrics and Hyperbolicity

    math.CO 2024-11 accept novelty 7.0 of 10

    Graphs satisfying a (lambda,mu)-bow metric are shown to be delta-hyperbolic for several major graph families, with bounds linear in lambda and mu.

Pith tools