## Improved Bounds for the Number of (<=k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n
Balogh, József and Salazar, Gelasio
(2004)
Full text not available from this repository. ## AbstractWe use circular sequences to give an improved lower bound on the minimum number of (<=k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number $\square(S)$ of convex quadrilaterals determined by the points in S is at least $0.37553\binom{n}{4} + O(n^3)$. This in turn implies that the rectilinear crossing number $\overline{\hbox{\rm cr}}(K_n)$ of the complete graph K_n is at least $0.37553\binom{n}{4} + O(n^3)$. These improved bounds refine results recently obtained by Ábrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.
Repository Staff Only: item control page References |