On dual-ABAB-free and related hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917699409412096 |
|---|---|
| author | Keszegh, Balázs Pálvölgyi, Dömötör |
| author_facet | Keszegh, Balázs Pálvölgyi, Dömötör |
| contents | Geometric motivations warranted the study of hypergraphs on ordered vertices that have no pair of hyperedges that induce an alternation of some given length. Such hypergraphs are called ABA-free, ABAB-free and so on. Since then various coloring and other combinatorial results were proved about these families of hypergraphs. We prove a characterization in terms of their incidence matrices which avoids using the ordering of the vertices. Using this characterization, we prove new results about the dual hypergraphs of ABAB-free hypergraphs. In particular, we show that dual-ABAB-free hypergraphs are not always proper $2$-colorable even if we restrict ourselves to hyperedges that are larger than some parameter $m$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13321 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On dual-ABAB-free and related hypergraphs Keszegh, Balázs Pálvölgyi, Dömötör Combinatorics Computational Geometry Geometric motivations warranted the study of hypergraphs on ordered vertices that have no pair of hyperedges that induce an alternation of some given length. Such hypergraphs are called ABA-free, ABAB-free and so on. Since then various coloring and other combinatorial results were proved about these families of hypergraphs. We prove a characterization in terms of their incidence matrices which avoids using the ordering of the vertices. Using this characterization, we prove new results about the dual hypergraphs of ABAB-free hypergraphs. In particular, we show that dual-ABAB-free hypergraphs are not always proper $2$-colorable even if we restrict ourselves to hyperedges that are larger than some parameter $m$. |
| title | On dual-ABAB-free and related hypergraphs |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2406.13321 |