For fixed integers k ≥ 3 and hypergraphs Q on N vertices, which contain edges of cardinalities at most k, and are uncrowded, i.e., do not contain cycles of lengths 2,3, or 4, and with average degree for the i-element edges bounded by O(T~(i-1) · (lnT)~((k-i)/(k-1)), i = 3,...,k, for some number T ≥ 1, we show that the independence number a(g) satisfies α(g) = Ω((N/T) · (lnT)~(1/(k-1)). Moreover, an independent set I of size |I| = Ω((N/T) · (lnT)~(1/(k-1)) can be found deterministically in polynomial time. This extends a result of Ajtai, Komlos, Pintz, Spencer and Szemeredi for uncrwoded uniform hypergraphs. We apply this result to a variant of Heilbronn's problem on the minimum area of the convex hull of small sets of points among n points in the unit square [0,1]~2.
展开▼
