论文标题
准确的结果涉及广义ERDőS-GALLAI问题
Exact results on generalized Erdős-Gallai problems
论文作者
论文摘要
在过去的几十年中，普遍的Turán问题一直是极端组合学研究的中心主题。这样的问题之一是在固定顺序的图中最大化尺寸$ t $的集团数量，该订单不包含至少包含至少给定数字的任何路径（或周期）。最近考虑了无路径和无循环的极端问题，并由LUO渐近地解决。我们通过表征所有可能的极端图来充分解决这些问题。我们通过求解这些问题的边缘变化来进一步扩展这些结果，这些问题是固定边缘数而不是顶点数量的问题。同样，我们为这些边缘变体的极端图获得了精确表征。
Generalized Turán problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants.
