论文标题
Helly-type定理用于订购超图的顶点
Helly-type theorems for the ordering of the vertices of a hypergraph
论文作者
论文摘要
令$ h $为完整的$ r $均匀的超图，以便在每个边缘标记两个顶点为“边界”顶点。 $ h $的顶点集的线性顺序称为{\ em同意线性顺序}，前提是$ h $的每个边缘的所有顶点都位于其两个边界顶点之间。我们证明了以下helly-type定理：如果在每一个$ h $的顶点上有一个{同意线性订单}，最多只有$ 2R-2 $ vertices，则在$ h $的顶点集合上有同意的线性订单。我们还表明，在定理中不能减少常数$ 2R-2 $。该定理的$ r = 3 $对中间的公理理论特别感兴趣。对于另外$ r $均匀的超图（$ r \ geq 3 $），获得了类似的结果，其中每个边缘都标记一个或两个顶点，并且线性订单需要满足各种协议规则。在其中一种情况下，我们证明没有这样的Helly型陈述。
Let $H$ be a complete $r$-uniform hypergraph such that two vertices are marked in each edge as its `boundary' vertices. A linear ordering of the vertex set of $H$ is called an {\em agreeing linear order}, provided all vertices of each edge of $H$ lie between its two boundary vertices. We prove the following Helly-type theorem: if there is an {agreeing linear order} on the vertex set of every subhypergraph of $H$ with at most $2r-2$ vertices, then there is an agreeing linear order on the vertex set of $H$. We also show that the constant $2r-2$ cannot be reduced in the theorem. The case $r=3$ of the theorem has particular interest in the axiomatic theory of betweenness. Similar results are obtained for further $r$-uniform hypergraphs ($r\geq 3$), where one or two vertices are marked in each edge, and the linear orders need to satisfy various rules of agreement. In one of the cases we prove that no such Helly-type statement holds.
