Stability and exact Turán numbers for matroids
Stability and exact Turán numbers for matroids
复制标题
拟阵的稳定性和精确图兰数
DOI：
10.1016/j.jctb.2019.11.004
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Liu H
中科院分区：
文献类型：
--
作者：
Liu H
我们考虑如下Turán-type问题：一个不包含给定固定集n≥k的线性副本的集合M的规模限定问题，其中n比k大。在这种情况下，一个Erdős-Stone类型定理[5]给出了一个严格到0 （2n）误差项的范围；我们的第一个主要结果给出了这个定理的稳定性版本，表明这样一个M在大小上接近于[5]的上界，在对称差分意义上接近于明显的极值例子。我们的第二个结果表明，[5]中的误差项是由一类“稀疏”极值问题的解精确控制的，并给出了一些例子，在这些例子中，误差项可以完全消除，从而给出| M|的一个明显的上界。
We consider the Turán-type problem of bounding the size of a set M⊆ F 2 n that does not contain a linear copy of a given fixed set N⊆ F 2 k, where n is large compared to k. An Erdős-Stone type theorem [5] in this setting gives a bound that is tight up to a o (2 n) error term; our first main result gives a stability version of this theorem, showing that such an M that is close in size to the upper bound in [5] is close to the obvious extremal example in the sense of symmetric difference. Our second result shows that the error term in [5] is exactly controlled by the solution to one of a class of ‘sparse’extremal problems, and gives some examples where the error term can be eliminated completely to give a sharp upper bound on| M|.
登录
查看更多内容
线性形式的一般系统：均分布和真实复杂性
DOI：
--
发表时间：
2014
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Hamed Hatami;Pooya Hatami;Shachar Lovett
通讯作者：
Shachar Lovett
Andrásfai-Erdős-Sós 定理的几何版本
影响因子：
1.1
作者：
J. Geelen
通讯作者：
J. Geelen
PG(n, 2) 中最小非平凡阻塞集的分类
DOI：
--
发表时间：
2006
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
P. Govaerts;L. Storme
通讯作者：
L. Storme
密集无三角形二元拟阵的临界数量
DOI：
--
发表时间：
2014
期刊：
J. Comb. Theory B
影响因子：
--
作者：
J. Geelen;P. Nelson
通讯作者：
P. Nelson
如何解决 Turán 型极值图问题（线性分解）？
DOI：
--
发表时间：
1997
期刊：
Contemporary Trends in Discrete Mathematics
影响因子：
--
作者：
M. Simonovits
通讯作者：
M. Simonovits