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