Radon numbers for trees

详细信息    查看全文

• 作者：Shoham Letzter ^{s.letzter@dpmms.cam.ac.uk}
• 关键词：Radon number ; Graph convexity ; P3P3-convexity.
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：333-344
• 全文大小：566 K
• 卷排序：340

文摘

We consider P3P3-convexity on graphs, where a set UU of vertices in a graph GG is convex   if every vertex not in UU has at most one neighbour in UU.Tverberg’s theorem states that every set of (k−1)(d+1)+1(k−1)(d+1)+1 points in RdRd can be partitioned into kk sets with intersecting convex hulls. As a special case of Eckhoff’s conjecture, we show that a similar result holds for P3P3-convexity in trees.A set UU of vertices in a graph GG is free   if no vertex of GG has more than one neighbour in UU. We prove an inequality relating the Radon number for P3P3-convexity in trees with the size of a maximum free set.