Weak regularity and finitely forcible graph limits
Weak regularity and finitely forcible graph limits
复制标题
弱正则性和有限强制图极限
DOI：
10.1090/tran/7066
复制
发表时间：
2018
影响因子：
1.3
通讯作者：
Cooper J
中科院分区：
文献类型：
--
作者：
Cooper J
图子是表示图的收敛序列的极限的分析对象。Lovász和Szegedy指出，每个非强制图子，即由许多图密度决定的任何图子，都有一个简单的结构。特别地，他们的一个推论暗示，每一个可迫图子都有一个弱正则划分，其部分的个数由中的多项式限定。我们构造了一个强有力的图子，使得在中的任何弱正则划分中的部分数至少是指数的。这个界几乎与已知的图的上界相匹配，并且在某种意义上，是图子的最佳可能界。引用
Graphons are analytic objects representing limits of convergent sequences of graphs. Lovász and Szegedy conjectured that every finitely forcible graphon, ie, any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak-regular partition with the number of parts bounded by a polynomial in. We construct a finitely forcible graphonsuch that the number of parts in any weak-regular partition ofis at least exponential in. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons. References
登录
查看更多内容
具有最少三角形数量的图的渐近结构
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
排列序列的极限
DOI：
10.1016/j.jctb.2012.09.003
发表时间：
2011
期刊：
J. Comb. Theory B
影响因子：
--
作者：
C. Hoppen;Y. Kohayakawa;Carlos Gustavo T. de A. Moreira;Balázs Ráth;R. Sampaio
通讯作者：
R. Sampaio