First-order logic axiomatization of metric graph theory
From MaRDI portal
Publication:6196830
DOI10.1016/J.TCS.2024.114460arXiv2203.01070OpenAlexW4392005262MaRDI QIDQ6196830FDOQ6196830
Authors: J. Chalopin, Manoj Changat, Victor Chepoi, Jeny Jacob 
Publication date: 15 March 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
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 -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.
Full work available at URL: https://arxiv.org/abs/2203.01070
Cites Work
- A Characterization of Certain Ptolemaic Graphs
- Local recognition of Tits geometries of classical type
- Title not available (Why is that?)
- Transitivities of Betweenness
- Matroid basis graphs. I
- Pseudo-median graphs are join spaces
- A set of postulates for plane geometry, based on scale and protractor
- Netlike partial cubes, IV: Fixed finite subgraph theorems
- Netlike partial cubes II. Retracts and netlike subgraphs
- A convexity lemma and expansion procedures for bipartite graphs
- Isometric subgraphs of Hamming graphs and d-convexity
- Characterizing almost-median graphs. II.
- Characterizing almost-median graphs
- Pseudo-modular graphs
- On tope graphs of complexes of oriented matroids
- A general set-separation theorem
- On the definability of properties of finite graphs
- Separation of two convex sets in convexity structures
- A forbidden subgraph characterization of some graph classes using betweenness axioms
- COMs: complexes of oriented matroids
- Cellular bipartite graphs
- Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
- Title not available (Why is that?)
- Graphs with connected medians
- On the Helly property working as a compactness criterion on graphs
- Obstructions to a small hyperbolicity in Helly graphs
- On two conjectures of maurer concerning basis graphs of matroids
- Axiomatic characterization of the interval function of a block graph
- Weakly Modular Graphs and Nonpositive Curvature
- Basis graphs of even delta-matroids
- Invariant Arcs, Whitney Levels, and Kelley Continua
- Netlike partial cubes III. The median cycle property
- Modular Interval Spaces
- Minimal extensions of graphs to absolute retracts
- Graphs with convex balls
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- A note on the interval function of a disconnected graph
- Distance-preserving subgraphs of Johnson graphs
- On distance-preserving elimination orderings in graphs: complexity and algorithms
- 1-safe Petri nets and special cube complexes. Equivalence and applications
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- A counterexample to Thiagarajan's conjecture on regular event structures
- Axiomatic characterization of the interval function of a bipartite graph
- Title not available (Why is that?)
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- Title not available (Why is that?)
- Buildings of spherical type and finite BN-pairs
- Geometry of the complex of curves. I: Hyperbolicity
- Title not available (Why is that?)
- Title not available (Why is that?)
- The geometry and topology of Coxeter groups.
- On the Addressing Problem for Loop Switching
- On local convexity in graphs
- On bridged graphs and cop-win graphs
- Petri nets, event structures and domains. I
- A canonical decomposition theory for metrics on a finite set
- Bridged graphs are cop-win graphs: An algorithmic proof
- Vertex-to-vertex pursuit in a graph
- Algorithmic graph theory and perfect graphs
- Graphs of some CAT(0) complexes
- 1-slim triangles and uniform hyperbolicity for arc graphs and curve graphs
- Six theorems about injective metric spaces
- Handbook of product graphs
- Title not available (Why is that?)
- Uniform hyperbolicity of the graphs of curves
- The geometry of the disk complex
- Title not available (Why is that?)
- The complexity of satisfiability problems
- Dismantlability of weakly systolic complexes and applications
- Characterizations of derived graphs
- Title not available (Why is that?)
- Medians and Betweenness
- Geometry of cuts and metrics
- Simplicial nonpositive curvature
- The theory of convex geometries
- Dual polar spaces
- Netlike partial cubes. I. General properties
- Les immeubles des groupes de tresses généralises
- Infinite median graphs, (0, 2)-graphs, and hypercubes
- Retracts of hypercubes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Isometric embedding in products of complete graphs
- Convexity in partial cubes: the hull number
- Hyperplane arrangements with a lattice of regions
- Distance-hereditary graphs
- Oriented matroids
- Distance-preserving subgraphs of hypercubes
- Graphs with intrinsic s3 convexities
- Median Algebra
- Isometric embeddings in Hamming graphs
- Title not available (Why is that?)
- An application of games to the completeness problem for formalized theories
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quasi‐median graphs and algebras
- Title not available (Why is that?)
- Defect Sauer results
- Metric Ternary Distributive Semi-Lattices
- A characterization of ptolemaic graphs
- Clique graphs and Helly graphs
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- 1-Hyperbolic Graphs
- Greedy algorithm and symmetric matroids
- On scale embeddings of graphs into hypercubes
- A characterization of the interval function of a connected graph
- Dismantling absolute retracts of reflexive graphs
- Intersection numbers and the hyperbolicity of the curve complex
- Title not available (Why is that?)
- Title not available (Why is that?)
- Axiomatic characterization of the interval function of a graph
- Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
- Ternary spaces, media, and Chebyshev sets
- Tarski's System of Geometry
- Title not available (Why is that?)
- Trees, Lattices, Order, and Betweenness
- Medians, Lattices, and Trees
- Coxeter matroids. With illustrations by Anna Borovik
- Decomposition and \(l_1\)-embedding of weakly median graphs
- A Helly theorem in weakly modular space
- Metric graph theory and geometry: a survey
- Conditions for invariance of set diameters under d-convexification in a graph
- Bucolic complexes
- Title not available (Why is that?)
- Some Elementary Properties of Interval Convexities
- Lopsided sets and orthant-intersection by convex sets
- Combinatorics of lopsided sets
- Title not available (Why is that?)
- Pseudomatroids
- On weak \(\epsilon\)-nets and the Radon number
- On Distance-Preserving and Domination Elimination Orderings
- A ternary operation in distributive lattices
- Points and lines. Characterizing the classical geometries
- Title not available (Why is that?)
- Some combinatorial properties of discriminants in metric vector spaces
- Median graphs and Helly hypergraphs
- Weak hyperbolicity of cube complexes and quasi-arboreal groups
- Nice labeling problem for event structures: a counterexample
- Median graphs, parallelism and posets
- Quasi-almostmedian graphs
- Title not available (Why is that?)
- Orientability of matroids
- Axioms for maximal vectors of an oriented matroid: A combinatorial characterization of the regions determined by an arrangement of pseudohyperplanes
This page was built for publication: First-order logic axiomatization of metric graph theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196830)
