On Triangles in Colored Pseudoline Arrangements
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910003378520064 |
|---|---|
| author | Radtke, Yan Alves Keszegh, Balázs Lauff, Robert |
| author_facet | Radtke, Yan Alves Keszegh, Balázs Lauff, Robert |
| contents | We consider the faces in pseudoline arrangements in which the pseudolines are colored with two colors. Björner, Las Vergnas, Sturmfels, White, and Ziegler conjecture the existence of a two-colored triangle in such arrangements. We consider variants of this problem. We show that in any non-trivial two-coloring of a pseudoline arrangement there exists a two-colored triangle or quadrangle. We also investigate the existence of a bichromatic triangle assuming certain structures on the coloring.
Previously, several authors investigated the chromatic number and independence number of hypergraphs whose vertices correspond to the pseudolines of an arrangement and the hyperedges correspond to the faces of the arrangement. We show that the maximum of the independence numbers of such hypergraphs is $\lceil \frac{2}{3}n-1\rceil$. We also prove that if we only consider the triangular faces then this maximum becomes $n-Θ(\log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20574 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Triangles in Colored Pseudoline Arrangements Radtke, Yan Alves Keszegh, Balázs Lauff, Robert Combinatorics Computational Geometry We consider the faces in pseudoline arrangements in which the pseudolines are colored with two colors. Björner, Las Vergnas, Sturmfels, White, and Ziegler conjecture the existence of a two-colored triangle in such arrangements. We consider variants of this problem. We show that in any non-trivial two-coloring of a pseudoline arrangement there exists a two-colored triangle or quadrangle. We also investigate the existence of a bichromatic triangle assuming certain structures on the coloring. Previously, several authors investigated the chromatic number and independence number of hypergraphs whose vertices correspond to the pseudolines of an arrangement and the hyperedges correspond to the faces of the arrangement. We show that the maximum of the independence numbers of such hypergraphs is $\lceil \frac{2}{3}n-1\rceil$. We also prove that if we only consider the triangular faces then this maximum becomes $n-Θ(\log n)$. |
| title | On Triangles in Colored Pseudoline Arrangements |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2601.20574 |