Finitely forcible graph limits are universal
Finitely forcible graph limits are universal
复制标题
有限强制图极限是通用的
DOI：
10.1016/j.aim.2018.10.019
复制
发表时间：
2018
影响因子：
1.7
通讯作者：
Cooper J
中科院分区：
文献类型：
--
作者：
Cooper J
图极限理论通过称为图子的分析对象来表示大型图。图的极限由许多图的密度决定，这些密度由非强制图子表示，出现在各种情况下，特别是在极值组合学中。Lovász和Szegedy指出，所有这样的graphons都具有简单的结构，例如，它们的典型顶点的空间总是有限维的;这被几个特别构造的复可插强制图子所否定。我们证明了任何图子都是可迫图子的子图子。这就打消了任何希望，即证明非强制性图偶子具有简单的结构，并且与非强制性图偶子在所有图偶子的空间中形成一个微薄的集合的事实相比，这是令人惊讶的。此外，由于任何非强制图子都表示子图密度的线性组合的唯一极小值，我们的结果还表明，这种极小化问题，在概念上是极值图论中最简单的一类，实际上可能具有任意复杂结构的唯一最优解。
The theory of graph limits represents large graphs by analytic objects called graphons. Graph limits determined by finitely many graph densities, which are represented by finitely forcible graphons, arise in various scenarios, particularly within extremal combinatorics. Lovász and Szegedy conjectured that all such graphons possess a simple structure, e.g., the space of their typical vertices is always finite dimensional; this was disproved by several ad hoc constructions of complex finitely forcible graphons. We prove that any graphon is a subgraphon of a finitely forcible graphon. This dismisses any hope for a result showing that finitely forcible graphons possess a simple structure, and is surprising when contrasted with the fact that finitely forcible graphons form a meager set in the space of all graphons. In addition, since any finitely forcible graphon represents the unique minimizer of some linear combination of densities of subgraphs, our result also shows that such minimization problems, which conceptually are among the simplest kind within extremal graph theory, may in fact have unique optimal solutions with arbitrarily complex structure.
登录
查看更多内容
具有最少三角形数量的图的渐近结构
DOI：
10.1017/s0963548316000110
发表时间：
2012
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
O. Pikhurko;A. Razborov
通讯作者：
A. Razborov
图正则性和移除引理的界限
影响因子：
2.2
作者：
D. Conlon;J. Fox
通讯作者：
J. Fox
2/3猜想的一个解
DOI：
10.1137/130926614
发表时间：
2013
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
R. Baber;John M. Talbot
通讯作者：
John M. Talbot
测试图形和函数的属性
影响因子：
1
作者：
L. Lovász;Balázs Szegedy
通讯作者：
Balázs Szegedy
弱正则性和有限强制图极限
影响因子：
1.3
作者：
Cooper J
通讯作者：
Cooper J