Sparse Incidence Geometries and Pebble Game Algorithms

2023/06/08 by Lundqvist, Signe, Randrianarisoa, Tovohery, Stokes, Klara +1
#52-08 #52C25 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2306.05050

Abstract

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.

Related

• Sparse Hypergraphs and Pebble Game Algorithms
• Sparsity-certifying Graph Decompositions
• Pebble Game Algorithms and Sparse Graphs
• An Analytic Approach to Sparse Hypergraphs: Hypergraph Removal
• New Notions and Constructions of Sparsification for Graphs and Hypergraphs