Separable partitions

DOI10.1016/S0166-218X(98)00142-5MaRDI QIDQ1283783zbMATH OpenOpenAlexFDO

Publication date 2 November 1999

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(98)00142-5

Davenport-Schinzel sequences extremal problems hyperplane arrangements moment curve point configurations separable partitions VC-dimension

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Review text

For any fixed \(d\geq 1\) and \(p\geq 2\), this paper provides tight asymptotic bounds on \(r_{p,d}(n)\), the maximal number of partitions of an \(n\)-subset of \({\mathbb{R}}^d\) into \(p\) parts withs disjoint convex hulls (``separable \(p\)-partitions of an \(n\)-subset of \({\mathbb{R}}^d\)). Namely, \(r_{p,1}(n)=p!{n-1\choose p-1}=\Theta (n^{p-1})\) in the \(1\)-dimensional case, \(r_{p,2}(n)=\Theta(n^{3p-6})\) corresponding to the fact that a suitable planar dual graph with \(p\) vertices has at most \(3p-6\) edges, and \(r_{p,d}(n)=\Theta(n^{d{p\choose 2}})\) for \(d\geq 3\) corresponding to the existence of neighborly configurations. Similar results are given for the more general situation of \(n\)-point spaces of Vapnik-Chervonenkis dimension \(d+1\). The special case where the \(n\) points lie on a moment curve is considered as well.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Separable partitions

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