Sparsity greedoids and pebble game algorithms for posets
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910055345946624 |
|---|---|
| author | Lundqvist, Signe Randrianarisoa, Tovohery Stokes, Klara Vermant, Joannes |
| author_facet | Lundqvist, Signe Randrianarisoa, Tovohery Stokes, Klara Vermant, Joannes |
| contents | We generalise a sparsity condition for hypergraphs and show a result relating sparseness of hypergraphs to the decomposition of a modified incidence graph into edge-disjoint forests. We also give new sparsity conditions for posets and define an algorithm of pebble game type for posets to test when these sparsity conditions hold. Furthermore, we prove that under natural conditions, the sparsity conditions define a greedoid. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_05050 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sparsity greedoids and pebble game algorithms for posets Lundqvist, Signe Randrianarisoa, Tovohery Stokes, Klara Vermant, Joannes Combinatorics 05C85 We generalise a sparsity condition for hypergraphs and show a result relating sparseness of hypergraphs to the decomposition of a modified incidence graph into edge-disjoint forests. We also give new sparsity conditions for posets and define an algorithm of pebble game type for posets to test when these sparsity conditions hold. Furthermore, we prove that under natural conditions, the sparsity conditions define a greedoid. |
| title | Sparsity greedoids and pebble game algorithms for posets |
| topic | Combinatorics 05C85 |
| url | https://arxiv.org/abs/2306.05050 |