Tight paths in convex geometric hypergraphs

Abstract

In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz, Sutherland, Kupitz and Perles for convex geometric graphs, as well as the classical Erdős-Gallai Theorem for graphs. As a consequence, we obtain the first substantial improvement on the Turán problem for tight paths in uniform hypergraphs.

Present version: 12 pages, 3 figures. We improve results and presentation of an earlier version, and removed results on crossing paths and matchings which will appear in a forthcoming paper