A new discrete theory of pseudoconvexity

Keszegh, Balázs (2023) A new discrete theory of pseudoconvexity. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 25 (1). ISSN 1462-7264

Preview

Text 2202.07697v4.pdf - Published Version Available under License Creative Commons Attribution. Download (714kB) | Preview

Abstract

Recently geometric hypergraphs that can be defined by intersections ofpseudohalfplanes with a finite point set were defined in a purely combinatorialway. This led to extensions of earlier results about points and halfplanes topseudohalfplanes, including polychromatic colorings and discrete Helly-typetheorems about pseudohalfplanes. Here we continue this line of research and introduce the notion of convexsets of such pseudohalfplane hypergraphs. In this context we prove severalresults corresponding to classical results about convexity, namely Helly'sTheorem, Carath\'eodory's Theorem, Kirchberger's Theorem, Separation Theorem,Radon's Theorem and the Cup-Cap Theorem. These results imply the respectiveresults about pseudoconvex sets in the plane defined using pseudohalfplanes. It turns out that most of our results can be also proved using orientedmatroids and topological affine planes (TAPs) but our approach is differentfrom both of them. Compared to oriented matroids, our theory is based on alinear ordering of the vertex set which makes our definitions and proofs quitedifferent and perhaps more elementary. Compared to TAPs, which are continuousobjects, our proofs are purely combinatorial and again quite different inflavor. Altogether, we believe that our new approach can further ourunderstanding of these fundamental convexity results.

Actions (login required)

Edit Item