Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A subset $Q$ of a point-set $P$ is called a $k$-set if $|Q|=k$ and there is a line that separates $Q$ from the rest of the points in $P$. A pair of points in $P$ is called a $k$-edge if the line spanned by them leaves exactly $k$ points of $P$ on one of its sides. In this talk we consider some classical problems in Discrete Geometry, namely the maximum number of $k$-edges, the minimum number of at-most-$k$-sets, and the minimum number of rectilinear crossings determined by geometric drawings of the complete graph on $n$ vertices.

We follow the approach of allowable sequences to prove a recursive inequality for the number of at-most-$k$-sets for generalized configurations of points. As a consequence we improve the previously best known lower bounds on the pseudolinear and rectilinear crossing numbers of $K_n$. We also present, for $n\leq27$, the exact values for the maximum number of halving lines, halving pseudolines, rectilinear crossing number, and pseudolinear crossing numbers determined by the corresponding drawings of $K_n$.