Sparse Incidence Geometries and Pebble Game Algorithms

We generalize a sparsity condition for hypergraphs and show a result relating sparseness of hypergraphs to the decomposition of a modified incidence graph into edge-disjoint spanning forests. We also give new sparsity conditions for posets, and define an algorithm of pebble game type for recognising...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-03
Main Authors: Lundqvist, Signe, Randrianarisoa, Tovohery, Stokes, Klara, Vermant, Joannes
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Tightness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We generalize a sparsity condition for hypergraphs and show a result relating sparseness of hypergraphs to the decomposition of a modified incidence graph into edge-disjoint spanning forests. We also give new sparsity conditions for posets, and define an algorithm of pebble game type for recognising this sparsity.
ISSN:2331-8422