solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看92次
Extremal problems on ordered and convex geometric hypergraphs. (arXiv:1807.05104v1 [math.CO])
来源于:arXiv
An ordered hypergraph is a hypergraph whose vertex set is linearly ordered,
and a convex geometric hypergraph is a hypergraph whose vertex set is
cyclically ordered. Extremal problems for ordered and convex geometric graphs
have a rich history with applications to a variety of problems in combinatorial
geometry. In this paper, we consider analogous extremal problems for uniform
hypergraphs, and discover a general partitioning phenomenon which allows us to
determine the order of magnitude of the extremal function for various ordered
and convex geometric hypergraphs. A special case is the ordered $n$-vertex
$r$-graph $F$ consisting of two disjoint sets $e$ and $f$ whose vertices
alternate in the ordering. We show that for all $n \geq 2r + 1$, the maximum
number of edges in an ordered $n$-vertex $r$-graph not containing $F$ is
exactly \[ {n \choose r} - {n - r \choose r}.\] This could be considered as an
ordered version of the Erd\H{o}s-Ko-Rado Theorem, and generalizes earlier
results of 查看全文>>