Search

A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1981 and conjectured that the maximum number of edges for a matchstick graph on $n$ vertices is $\lfloor 3n-\sqrt{12n-3} \rfloor$. In this paper we prove this conjecture for all $n\geq 1$. The main geometric ingredient of the proof is an isoperimetric inequality related to L'Huilier's inequality., Comment: 12 pages, 3 figures. Minor typos corrected

A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth (1981) proposed the problem of determining whether there exists a matchstick graph in which every vertex has degree exactly $5$. In 1982, Blokhuis gave a proof of non-existence. A shorter proof was found by Kurz and Pinchasi (2011) using a charging method. We combine their method with the isoperimetric inequality to show that there are $\Omega(\sqrt{n})$ vertices in a matchstick graph on $n$ vertices that are of degree at most $4$, which is asymptotically tight.

We study the contact structure of totally separable} packings of translates of a convex body $K$ in $\mathbb{R}^d$, that is, packings where any two touching bodies have a separating hyperplane that does not intersect the interior of any translate in the packing. The separable Hadwiger number $H_{\text{sep}}(K)$ of $K$ is defined to be the maximum number of translates touched by a single translate, with the maximum taken over all totally separable packings of translates of $K$. We show that for each $d\geq 8$, there exists a smooth and strictly convex $K$ in $\mathbb{R}^d$ with $H_{\text{sep}}(K)>2d$, and asymptotically, $H_{\text{sep}}(K)=\Omega\bigl((3/\sqrt{8})^d\bigr)$. We show that Alon's packing of Euclidean unit balls such that each translate touches at least $2^{\sqrt{d}}$ others whenever $d$ is a power of $4$, can be adapted to give a totally separable packing of translates of the $\ell_1$-unit ball with the same touching property. We also consider the maximum number of touching pairs in a totally separable packing of $n$ translates of any planar convex body $K$. We prove that the maximum equals $\lfloor 2n-2\sqrt{n}\rfloor$ if and only if $K$ is a quasi hexagon, thus completing the determination of this value for all planar convex bodies., Comment: 12 pages, 5 figures. Pdf generation issue fixed, no change to first version

We show that a matchstick graph with $n$ vertices has no more than $3n-c\sqrt{n-1/4}$ edges, where $c=\frac12(\sqrt{12} + \sqrt{2\pi\sqrt{3}})$. The main tools in the proof are the Euler formula, the isoperimetric inequality, and an upper bound for the number of edges in terms of $n$ and the number of non-triangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph., Comment: 9 pages, 3 figures

Let $S$ be a set of $n$ points in Euclidean $3$-space. Assign to each $x\in S$ a distance $r(x)>0$, and let $e_r(x,S)$ denote the number of points in $S$ at distance $r(x)$ from $x$. Avis, Erd\H{o}s and Pach (1988) introduced the extremal quantity $f_3(n)=\max\sum_{x\in S}e_r(x,S)$, where the maximum is taken over all $n$-point subsets $S$ of 3-space and all assignments $r\colon S\to(0,\infty)$ of distances. We show that if the pair $(S,r)$ maximises $f_3(n)$ and $n$ is sufficiently large, then, except for at most $2$ points, $S$ is contained in a circle $\mathcal{C}$ and the axis of symmetry $\mathcal{L}$ of $\mathcal{C}$, and $r(x)$ equals the distance from $x$ to $C$ for each $x\in S\cap\mathcal{L}$. This, together with a new construction, implies that $f_3(n)=n^2/4 + 5n/2 + O(1)$., Comment: 10 pages, 4 figures

An ordinary hypersphere of a set of points in real $d$-space, where no $d+1$ points lie on a $(d-2)$-sphere or a $(d-2)$-flat, is a hypersphere (including the degenerate case of a hyperplane) that contains exactly $d+1$ points of the set. Similarly, a $(d+2)$-point hypersphere of such a set is one that contains exactly $d+2$ points of the set. We find the minimum number of ordinary hyperspheres, solving the $d$-dimensional spherical analogue of the Dirac--Motzkin conjecture for $d \geqslant 3$. We also find the maximum number of $(d+2)$-point hyperspheres in even dimensions, solving the $d$-dimensional spherical analogue of the orchard problem for even $d \geqslant 4$., Comment: 10 pages. Final version

Given a set of sources and a set of sinks as points in the Euclidean plane, a directed network is a directed graph drawn in the plane with a directed path from each source to each sink. Such a network may contain nodes other than the given sources and sinks, called Steiner points. We characterize the local structure of the Steiner points in all shortest-length directed networks in the Euclidean plane. This characterization implies that these networks are constructible by straightedge and compass. Our results build on unpublished work of Alfaro, Campbell, Sher, and Soto from 1989 and 1990. Part of the proof is based on a new method that uses other norms in the plane. This approach gives more conceptual proofs of some of their results, and as a consequence, we also obtain results on shortest directed networks for these norms., Comment: 21 pages, 14 figures. To appear in Graphs and Combinatorics

Let $P$ be a set of $n$ points in real projective $d$-space, not all contained in a hyperplane, such that any $d$ points span a hyperplane. An ordinary hyperplane of $P$ is a hyperplane containing exactly $d$ points of $P$. We show that if $d\ge 4$, the number of ordinary hyperplanes of $P$ is at least $\binom{n-1}{d-1} - O_d(n^{\lfloor(d-1)/2\rfloor})$ if $n$ is sufficiently large depending on $d$. This bound is tight, and given $d$, we can calculate the exact minimum number for sufficiently large $n$. This is a consequence of a structure theorem for sets with few ordinary hyperplanes: For any $d \ge 4$ and $K > 0$, if $n \ge C_d K^8$ for some constant $C_d > 0$ depending on $d$ and $P$ spans at most $K\binom{n-1}{d-1}$ ordinary hyperplanes, then all but at most $O_d(K)$ points of $P$ lie on a hyperplane, an elliptic normal curve, or a rational acnodal curve. We also find the maximum number of $(d+1)$-point hyperplanes, solving a $d$-dimensional analogue of the orchard problem. Our proofs rely on Green and Tao's results on ordinary lines, our earlier work on the $3$-dimensional case, as well as results from classical algebraic geometry., Comment: 34 pages

An ordinary plane of a finite set of points in real 3-space with no three collinear is a plane intersecting the set in exactly three points. We prove a structure theorem for sets of points spanning few ordinary planes. Our proof relies on Green and Tao's work on ordinary lines in the plane, combined with classical results on space quartic curves and non-generic projections of curves. This gives an alternative approach to Ball's recent results on ordinary planes, as well as extending them. We also give bounds on the number of coplanar quadruples determined by a finite set of points on a rational space quartic curve in complex 3-space, answering a question of Raz, Sharir and De Zeeuw [Israel J. Math. 227 (2018)].

The dimension of a graph $G$ is the smallest $d$ for which its vertices can be embedded in $d$-dimensional Euclidean space in the sense that the distances between endpoints of edges equal $1$ (but there may be other unit distances). Answering a question of Erd\H{o}s and Simonovits [Ars Combin. 9 (1980) 229--246], we show that any graph with less than $\binom{d+2}{2}$ edges has dimension at most $d$. Improving their result, we prove that that the dimension of a graph with maximum degree $d$ is at most $d$. We show the following Ramsey result: if each edge of the complete graph on $2d$ vertices is coloured red or blue, then either the red graph or the blue graph can be embedded in Euclidean $d$-space. We also derive analogous results for embeddings of graphs into the $(d-1)$-dimensional sphere of radius $1/\sqrt{2}$., Comment: 11 pages

A set of points in d-dimensional Euclidean space is almost equidistant if among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in $\mathbb{R}^d$ has cardinality $O(d^{4/3})$., Comment: 6 pages

For a positive integer $d$, a set of points in $d$-dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let $f(d)$ denote the largest size of an almost-equidistant set in $d$-space. It is known that $f(2)=7$, $f(3)=10$, and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that $f(5) \ge 16$. We further show that $12\leq f(4)\leq 13$, $f(5)\leq 20$, $18\leq f(6)\leq 26$, $20\leq f(7)\leq 34$, and $f(9)\geq f(8)\geq 24$. Up to dimension $7$, our work is based on various computer searches, and in dimensions $6$ to $9$, we give constructions based on the known construction for $d=5$. For every dimension $d \ge 3$, we give an example of an almost-equidistant set of $2d+4$ points in the $d$-space and we prove the asymptotic upper bound $f(d) \le O(d^{3/2})$., Comment: 24 pages, 9 figures. Accepted by Graphs and Combinatorics

A family of homothets of an o-symmetric convex body K in d-dimensional Euclidean space is called a Minkowski arrangement if no homothet contains the center of any other homothet in its interior. We show that any pairwise intersecting Minkowski arrangement of a d-dimensional convex body has at most $2\cdot 3^d$ members. This improves a result of Polyanskii (arXiv:1610.04400). Using similar ideas, we also give a proof the following result of Polyanskii: Let $K_1,\dots,K_n$ be a sequence of homothets of the o-symmetric convex body $K$, such that for any $i

We survey problems and results from combinatorial geometry in normed spaces, concentrating on problems that involve distances. These include various properties of unit-distance graphs, minimum-distance graphs, diameter graphs, as well as minimum spanning trees and Steiner minimum trees. In particular, we discuss translative kissing (or Hadwiger) numbers, equilateral sets, and the Borsuk problem in normed spaces. We show how to use the angular measure of Peter Brass to prove various statements about Hadwiger and blocking numbers of convex bodies in the plane, including some new results. We also include some new results on thin cones and their application to distinct distances and other combinatorial problems for normed spaces., Comment: 43 pages, 4 figures, New Trends in Intuitive Geometry, Springer, to appear

Answering a question of F\"uredi and Loeb (1994), we show that the maximum number of pairwise intersecting homothets of a $d$-dimensional centrally symmetric convex body $K$, none of which contains the center of another in its interior, is at most $O(3^d d\log d)$. If $K$ is not necessarily centrally symmetric and the role of its center is played by its centroid, then the above bound can be replaced by $O(3^d\binom{2d}{d}d\log d)$. We establish analogous results for the case where the center is defined as an arbitrary point in the interior of $K$. We also show that in the latter case, one can always find families of at least $\Omega((2/\sqrt{3})^d)$ translates of $K$ with the above property., Comment: 13 pages, 2 figures. Accepted by Mathematika

An ordinary circle of a set $P$ of $n$ points in the plane is defined as a circle that contains exactly three points of $P$. We show that if $P$ is not contained in a line or a circle, then $P$ spans at least $\frac{1}{4}n^2 - O(n)$ ordinary circles. Moreover, we determine the exact minimum number of ordinary circles for all sufficiently large $n$ and describe all point sets that come close to this minimum. We also consider the circle variant of the orchard problem. We prove that $P$ spans at most $\frac{1}{24}n^3 - O(n^2)$ circles passing through exactly four points of $P$. Here we determine the exact maximum and the extremal configurations for all sufficiently large $n$. These results are based on the following structure theorem. If $n$ is sufficiently large depending on $K$, and $P$ is a set of $n$ points spanning at most $Kn^2$ ordinary circles, then all but $O(K)$ points of $P$ lie on an algebraic curve of degree at most four. Our proofs rely on a recent result of Green and Tao on ordinary lines, combined with circular inversion and some classical results regarding algebraic curves., Comment: 28 pages, 6 figures. Post-publication corrections to Theorems 1.3 and 1.5 with corresponding updates to Sections 4.1 and 4.2. The earlier preprint arXiv:1412.8314 is subsumed by this paper and will not be published independently

An approximate Steiner tree is a Steiner tree on a given set of terminals in Euclidean space such that the angles at the Steiner points are within a specified error e from 120 degrees.This notion arises in numerical approximations of minimum Steiner trees (W. D. Smith, Algorithmica, 7 (1992), 137--177). We investigate the worst-case relative error of the length of an approximate Steiner tree compared to the shortest tree with the same topology.Rubinstein, Weng and Wormald (J. Global Optim. 35 (2006), 573--592) conjectured that this relative error is at most linear in $e$, independent of the number of terminals. We verify their conjecture for the two-dimensional case as long as the error $e$ is sufficiently small in terms of the number of terminals. We derive a lower bound linear in $e$ for the relative error in the two-dimensional case when $e$ is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error for larger values of $e$, and calculate exact values in the plane for three and four terminals., Comment: 24 pages, 9 figures

A double-normal pair of a finite set $S$ of points from Euclidean space is a pair of points $\{p,q\}$ from $S$ such that $S$ lies in the closed strip bounded by the hyperplanes through $p$ and $q$ that are perpendicular to $pq$. A double-normal pair $pq$ is strict if $S\setminus\{p,q\}$ lies in the open strip. We answer a question of Martini and Soltan (2006) by showing that a set of $n\geq 3$ points in the plane has at most $3\lfloor n/2\rfloor$ double-normal pairs. This bound is sharp for each $n\geq 3$. In a companion paper, we have asymptotically determined this maximum for points in $R^3$. Here we show that if the set lies on some 2-sphere, it has at most $17n/4 - 6$ double-normal pairs. This bound is attained for infinitely many values of $n$. We also establish tight bounds for the maximum number of strict double-normal pairs in a set of $n$ points in the plane and on the sphere., Comment: 19 pages, 10 figures

A double-normal pair of a finite set $S$ of points from $R^d$ is a pair of points $\{p,q\}$ from $S$ such that $S$ lies in the closed strip bounded by the hyperplanes through $p$ and $q$ perpendicular to $pq$. A double-normal pair $pq$ is strict if $S\setminus\{p,q\}$ lies in the open strip. The problem of estimating the maximum number $N_d(n)$ of double-normal pairs in a set of $n$ points in $R^d$, was initiated by Martini and Soltan (2006). It was shown in a companion paper that in the plane, this maximum is $3\lfloor n/2\rfloor$, for every $n>2$. For $d\geq 3$, it follows from the Erd\H{o}s-Stone theorem in extremal graph theory that $N_d(n)=\frac12(1-1/k)n^2 + o(n^2)$ for a suitable positive integer $k=k(d)$. Here we prove that $k(3)=2$ and, in general, $\lceil d/2\rceil \leq k(d)\leq d-1$. Moreover, asymptotically we have $\lim_{n\rightarrow\infty}k(d)/d=1$. The same bounds hold for the maximum number of strict double-normal pairs., Comment: 15 pages, 1 figure

We say that a family ${x_i|i\in[m]}$ of vectors in a Banach space $X$ satisfies the $k$-collapsing condition if $|\sum_{i\in I}x_i|\leq 1$ for all $k$-element subsets $I\subseteq{1,2,...,m}$. Let $C(k,d)$ denote the maximum cardinality of a $k$-collapsing family of unit vectors in a $d$\dimensional Banach space, where the maximum is taken over all spaces of dimension $d$. Similarly, let $CB(k,d)$ denote the maximum cardinality if we require in addition that $\sum_{i=1}^m x_i=o$. The case $k=2$ was considered by F\"uredi, Lagarias and Morgan (1991). These conditions originate in a theorem of Lawlor and Morgan (1994) on geometric shortest networks in smooth finite-dimensional Banach spaces. We show that $CB(k,d)=\max{k+1,2d}$ for all $k,d\geq 2$. The behaviour of $C(k,d)$ is not as simple, and we derive various upper and lower bounds for various ranges of $k$ and $d$. These include the exact values $C(k,d)=\max{k+1,2d}$ in certain cases. We use a variety of tools from graph theory, convexity and linear algebra in the proofs: in particular the Hajnal-Szemer\'edi Theorem, the Brunn-Minkowski inequality, and lower bounds for the rank of a perturbation of the identity matrix., Comment: 41 pages

The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell partitions. Their algorithm produces an optimal solution within $O(n^2)$ time. In this paper we generalise their approach in order to solve the $k$-Steiner tree problem, in which the Steiner minimum tree may contain up to $k$ Steiner points for a given constant $k$. We also extend their approach further to encompass other normed planes, and to solve a much wider class of problems, including the $k$-bottleneck Steiner tree problem and other generalised $k$-Steiner tree problems. We show that, for any fixed $k$, such problems can be solved in $O(n^{2k})$ time.

A subset of a normed space $X$ is called equilateral if the distance between any two points is the same. Let $m(X)$ be the smallest possible size of an equilateral subset of $X$ maximal with respect to inclusion. We first observe that Petty's construction of a $d$-dimensional $X$ of any finite dimension $d\geq 4$ with $m(X)=4$ can be generalised to give $m(X\oplus_1\mathbb{R})=4$ for any $X$ of dimension at least 2 which has a smooth point on its unit sphere. By a construction involving Hadamard matrices we then show that for any set $\Gamma$, $m(\ell_p(\Gamma))$ is finite and bounded above by a function of $p$, for all $1\leq p<2$. Also, for all $p\in[1,\infty)$ and $d\in\mathbb{N}$ there exists $c=c(p,d)>1$ such that $m(X)\leq d+1$ for all $d$-dimensional $X$ with Banach-Mazur distance less than $c$ from $\ell_p^d$. Using Brouwer's fixed-point theorem we show that $m(X)\leq d+1$ for all $d$-dimensional $X$ with Banach-Mazur distance less than 3/2 from $\ell_\infty^d$. A graph-theoretical argument furthermore shows that $m(\ell_\infty^d)=d+1$. The above results lead us to conjecture that $m(X)\leq 1+\dim X$ for all finite-dimensional normed spaces $X$., Comment: 15 pages. This version incorporates some suggestions from a referee obtained after galley proofs. Equations (18) and (23) are corrected

Let $S$ be a set of $n$ points in $d$-dimensional Euclidean space. Assign to each $x\in S$ an arbitrary distance $r(x)>0$. Let $e_r(x,S)$ denote the number of points in $S$ at distance $r(x)$ from $x$. Avis, Erd\"os and Pach (1988) introduced the extremal quantity $f_d(n)=\max\sum_{x\in S}e_r(x,S)$, where the maximum is taken over all $n$-point sets $S$ in $d$-dimensional space and all assignments $r\colon S\to(0,\infty)$ of distances. We give a quick derivation of the asymptotics of the error term of $f_d(n)$ using only the analogous asymptotics of the maximum number of unit distance pairs in a set of $n$ points, which improves on previous results of Avis, Erd\"os and Pach (1988) and Erd\"os and Pach (1990). Then we prove a stability result for $d\geq 4$, asserting that if $(S,r)$ with $|S|=n$ satisfies $e_r(S)=f_d(n)-o(n^2)$, then, up to $o(n)$ points, $S$ is a Lenz construction with $r$ constant. Finally we use stability to show that for $n$ sufficiently large (depending on $d$) the pairs $(S,r)$ that attain $f_d(n)$ are up to scaling exactly the Lenz constructions that maximise the number of unit distance pairs with $r\equiv 1$, with some exceptions in dimension 4. Analogous results hold for the furthest neighbour digraph, where $r$ is fixed to be $r(x)=\max_{y\in S} |xy|$ for $x\in S$., Comment: 17 pages

Let $E_d(n)$ be the maximum number of pairs that can be selected from a set of $n$ points in $R^d$ such that the midpoints of these pairs are convexly independent. We show that $E_2(n)\geq \Omega(n\sqrt{\log n})$, which answers a question of Eisenbrand, Pach, Rothvo\ss, and Sopher (2008) on large convexly independent subsets in Minkowski sums of finite planar sets, as well as a question of Halman, Onn, and Rothblum (2007). We also show that $\lfloor\frac{1}{3}n^2\rfloor\leq E_3(n)\leq \frac{3}{8}n^2+O(n^{3/2})$. Let $W_d(n)$ be the maximum number of pairwise nonparallel unit distance pairs in a set of $n$ points in some $d$-dimensional strictly convex normed space. We show that $W_2(n)=\Theta(E_2(n))$ and for $d\geq 3$ that $W_d(n)\sim\frac12\left(1-\frac{1}{a(d)}\right)n^2$, where $a(d)\in N$ is related to strictly antipodal families. In fact we show that the same asymptotics hold without the requirement that the unit distance pairs form pairwise nonparallel segments, and also if diameter pairs are considered instead of unit distance pairs., Comment: 7 pages

A Latin square of side n defines in a natural way a finite geometry on 3n points, with three lines of size n and n^2 lines of size 3. A Latin square of side n with a transversal similarly defines a finite geometry on 3n+1 points, with three lines of size n, n^2-n lines of size 3, and n concurrent lines of size 4. A collection of k mutually orthogonal Latin squares defines a geometry on kn points, with k lines of size n and n^2 lines of size k. Extending work of Bruen and Colbourn (J. Combin. Th. Ser. A 92 (2000), 88-94), we characterise embeddings of these finite geometries into projective spaces over skew fields., Comment: 11 pages. This is the revised final preprint version. Added journal reference and doi

A hollow axis-aligned box is the boundary of the cartesian product of $d$ compact intervals in R^d. We show that for d\geq 3, if any 2^d of a collection of hollow axis-aligned boxes have non-empty intersection, then the whole collection has non-empty intersection; and if any 5 of a collection of hollow axis-aligned rectangles in R^2 have non-empty intersection, then the whole collection has non-empty intersection. The values 2^d for d\geq 3 and 5 for d=2 are the best possible in general. We also characterize the collections of hollow boxes which would be counterexamples if 2^d were lowered to 2^d-1, and 5 to 4, respectively., Comment: 7 pages. Old paper from 1999

A directed network connecting a set A to a set B is a digraph containing an a-b path for each a in A and b in B. Vertices in the directed network not in A or B are called Steiner points. We show that in a finitely compact metric space in which geodesics exist, any two finite sets A and B are connected by a shortest directed network. We also bound the number of Steiner points by a function of the sizes of A and B. Previously, such an existence result was known only for the Euclidean plane [M. Alfaro, Pacific J. Math. 167 (1995) 201-214]. The main difficulty is that, unlike the undirected case (Steiner minimal trees), the underlying graphs need not be acyclic. Existence in the undirected case was first shown by E. J. Cockayne [Canad. Math. Bull. 10 (1967) 431-450]., Comment: 6 pages. An old paper from 2000

Theorem A. Let $x_1,...,x_{2k+1}$ be unit vectors in a normed plane. Then there exist signs $\epsi_1,...,\epsi_{2k+1}\in\{\pm 1\}$ such that $\norm{\sum_{i=1}^{2k+1}\epsi_i x_i}\leq 1$. We use the method of proof of the above theorem to show the following point facility location result, generalizing Proposition 6.4 of Y. S. Kupitz and H. Martini (1997). Theorem B. Let $p_0,p_1,...,p_n$ be distinct points in a normed plane such that for any $1\leq i

A subset of a metric space is a k-distance set if there are exactly k non-zero distances occuring between points. We conjecture that a k-distance set in a d-dimensional Banach space (or Minkowski space), contains at most (k+1)^d points, with equality iff the unit ball is a parallelotope. We solve this conjecture in the affirmative for all 2-dimensional spaces and for spaces where the unit ball is a parallelotope. For general spaces we find various weaker upper bounds for k-distance sets., Comment: 7 pages, 2 figures

We show that the maximum number of unit distances or of diameters in a set of n points in d-dimensional Euclidean space is attained only by specific types of Lenz constructions, for all d >= 4 and n sufficiently large, depending on d. As a corollary we determine the exact maximum number of unit distances for all even d >= 6, and the exact maximum number of diameters for all d >= 4, for all $n$ sufficiently large, depending on d.

We present a self-contained proof that the number of diameter pairs among n points in Euclidean 3-space is at most 2n-2. The proof avoids the ball polytopes used in the original proofs by Grunbaum, Heppes and Straszewicz. As a corollary we obtain that any three-dimensional diameter graph can be embedded in the projective plane., Comment: 4 pages

We present some elementary ideas to prove the following Sylvester-Gallai type theorems involving incidences between points and lines in the planes over the complex numbers and quaternions. (1) Let A and B be finite sets of at least two complex numbers each. Then there exists a line l in the complex affine plane such that l intersects AxB in exactly two points. (2) Let S be a finite noncollinear set of points in the complex affine plane. Then there exists a line l intersecting S in 2, 3, 4 or 5 points. (3) Let A and B be finite sets of at least two quaternions each. Then there exists a line l in the quaternionic affine plane such that l intersects AxB in 2, 3, 4 or 5 points. (4) Let S be a finite noncollinear set of points in the quaternionic affine plane. Then there exists a line l intersecting S in at least 2 and at most 24 points., Comment: 5 pages

We develop a general method of proving that certain star configurations in finit e-dimensional normed spaces are Steiner minimal trees. This method generalizes the results of Lawlor and Morgan (1994) that could only be applied to differentiable norms. The generalization uses the subdifferential calculus from convex analysis. We apply this method to two special norms. The first norm, occurring in the work of Cieslik, has unit ball the polar of the difference body of the n-simplex (in dimension 3 this is the rhombic dodecahedron). We determine the maximum degree of a given point in a Steiner minimal tree in this norm. The proof makes essential use of extremal finite set theory. The second norm, occuring in the work of Mark Conger (1989), is the sum of the ell_1-norm and a small multiple of the ell_2 norm. For the second norm we determine the maximum degree of a Steiner point., Comment: 22 pages, 3 figures. Corollary 8 of the previous version is the new Theorem 7

We give a complete proof that in any finite-dimensional normed linear space a finite set of points has a minimal spanning tree in which the maximum degree is bounded above by the strict Hadwiger number of the unit ball, i.e., the largest number of unit vectors such that the distance between any two is larger than 1., Comment: 5 pages

Let F be a family of subsets of an n-element set not containing four distinct members such that A union B is contained in C intersect D. It is proved that the maximum size of F under this condition is equal to the sum of the two largest binomial coefficients of order n. The maximum families are also characterized. A LYM-type inequality for such families is given, too., Comment: 6 pages

A Sylvester-Gallai (SG) configuration is a finite set S of points such that the line through any two points in S contains a third point of S. According to the Sylvester-Gallai Theorem, an SG configuration in real projective space must be collinear. A problem of Serre (1966) asks whether an SG configuration in a complex projective space must be coplanar. This was proved by Kelly (1986) using a deep inequality of Hirzebruch. We give an elementary proof of this result, and then extend it to show that an SG configuration in projective space over the quaternions must be contained in a three-dimensional flat., Comment: 13 pages, 3 figures