Radon Numbers for Trees

2013/02/06 by Shoham Letzter, Letzter, Shoham
Mathematics · #05C05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05

paper · pdf · doi:10.48550/arxiv.1302.1599

17 pages, 13 figures

arxiv created 2013/02/06 · arxiv updated 2013/02/08

Abstract

Many interesting problems are obtained by attempting to generalize classical results on convexity in Euclidean spaces to other convexity spaces, in particular to convexity spaces on graphs. In this paper we consider P₃-convexity on graphs. A set U of vertices in a graph G is P₃-convex if every vertex not in U has at most one neighbour in U. More specifically, we consider Radon numbers for P₃-convexity in trees. Tverberg's theorem states that every set of (k-1)(d+1)-1 points in ℝ^d can be partitioned into k sets with intersecting convex hulls. As a special case of Eckhoff's conjecture, we show that a similar result holds for P₃-convexity in trees. A set U of vertices in a graph G is called free, if no vertex of G has more than one neighbour in U. We prove an inequality relating the Radon number for P₃-convexity in trees with the size of a maximal free set.

Related

• Radon partitions in convexity spaces
• Helly Number, Radon Number and Rank in Δ-Convexity on Graphs
• Helly type problems in convexity spaces
• Radon numbers grow linearly
• Algorithms for Tverberg's theorem via centerpoint theorems