Return to Colloquia & Seminar listing
On crossings, k-edges, and at most k-sets of generalized configurations of points.
Algebra & Discrete Mathematics| Speaker: | Bernardo Abrego, CSU Northridge |
| Location: | 2212 MSB |
| Start time: | Thu, May 19 2011, 4:10PM |
Description
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$.