Properties of closure operators in the plane

arXiv1909.08489MaRDI QIDQ6325562FDOQ6325562

Authors: Pavel Paták 

Publication date: 18 September 2019

Abstract: We prove a general version of Radon's theorem for finite families $mathcalF$ of sets in zero-, one- and two-dimensional (pseudo)manifolds and graphs. The only requirement is that for each $mathcalGsubseteqmathcalF$ the intersection $$ has bounded number of path-connected components. As a consequence we obtain Helly's and Tverberg's theorems, fractional and colorful Helly theorems, existence of weak $varepsilon$-nets and $(p,q)$-theorems. More precisely, if $mathcalF$ is an intersection-closed family in a topological space $X$ and $SsubseteqX$, we define its convex hull $ext{conv}_{mathcalF}(S)$ as the smallest set in $mathcalF$ that contains $S$. The Radon number $r(mathcalF)$ is then the smallest integer $r$ such that every set $SsubseteqX$ of size $r$ can be split into two disjoint subsets with intersecting convex hulls. For every graph $G$ with $n$ vertices we construct a polynomial $p_G(x)$ satisfying the following three conditions. 1) If $n=1$, $p_G(x)=1$. 2) If $ngeq2$, the degree of $p_G(x)$ is at most $2n-3$. 3) If the graph $G$ does not almost-embed into a topological space $X$, and $mathcalF$ is a finite and intersection-closed family of sets in $X$, such that each member of $mathcalF$ has at most $b$ path-connected components, then $r(mathcalF)leq{p}_G(b)$. In particular, if $mathcalF$ is a family of sets in $mathbb{R}^2$, $r(mathcalF)leq{r}_{K_{3,3}}(b)leq2b^6-5b^5+10b^4-10b^3+9b^2-3b+3$. The proof further refines the constrained chain map method introduced by Goaoc, Pat'ak, Pat'akov'a, Tancer and Wagner; and further developed by Pat'akov'a. In the plane, we manage to overcome the use of hypergraph Ramsey theorem and provide polynomial size bounds.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Helly-type theorems and geometric transversal theory (52A35)

This page was built for publication: Properties of closure operators in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325562)