超树的结构性质
Structural Properties of Hypergraph Trees
摘要
极值图论领域中备受关注的一类问题是普通图的（广义）图兰问题,它研究的是：如何在特定条件下,如禁止某个子图,确定一个图的边（给定子图）的最大数目。Erd\H{o}s 与 S\'{o}s 在1962年做了如下猜想：若一个 $n$ 个顶点的图 $G$,它的边数 $e(G)>\frac{t-2}{2}n$,则 $G$ 包含任意一棵 $t$ 个顶点的树 $T_t$,即 $T_t$ 的图兰数 $\operatorname{ex}(n,T_t)\le \frac{t-2}{2}n$。考虑若干个 $t-1$ 个顶点的完全图的不交并,可知,这个猜想猜测的界对每个自然数 $t$ 都是紧的。树的一个关键性质是它可以递归地定义,这使得它具有特殊的局部性质,例如,如点数大于等于$2$的树至少有两个叶子点。本文将对超树（树在超图中的推广）证明相应的局部性质。
Abstract
A central topic in extremal graph theory is the study of (generalized) Turán-type problems for ordinary graphs. These problems investigate how to determine the maximum possible number of edges (or copies of a given subgraph) in a graph under certain constraints, such as forbidding a specified subgraph. In 1962, Erd\H{o}s and S\'{o}s proposed the following conjecture: for a graph $G$ on $n$ vertices, if the number of edges satisfies$e(G) > \frac{t-2}{2}n,$then $G$ contains every tree $T_t$ on $t$ vertices. Equivalently, the Turán number of $T_t$ satisfies$\operatorname{ex}(n, T_t) \le \frac{t-2}{2}n.$By considering the disjoint union of several complete graphs on $t-1$ vertices, one can see that the conjectured bound is tight for every natural number $t$. A key property of trees is that they admit a recursive definition, which endows them with special local structural properties. For example, every tree with at least two vertices has at least two leaves. In this paper, we establish analogous local properties for hypergraph trees, which are natural generalizations of trees in hypergraphs.关键词
树/超图/超树Key words
Tree/Hypergraph/Hypergraph tree引用本文复制引用
曾祥浩,彭岳建.超树的结构性质[EB/OL].(2026-05-09)[2026-05-10].http://www.paper.edu.cn/releasepaper/content/202605-25.学科分类
数学
评论