On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs
On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs
复制标题
关于完全三部图与平衡完全多部图的交数
DOI：
10.1002/jgt.22041
复制
发表时间：
2014
影响因子：
0.9
通讯作者：
Michael Young
中科院分区：
文献类型：
--
作者：
Ellen Gethner;L. Hogben;Bernard Lidický;Florian Pfender;Amanda Ruiz;Michael Young
图G的交叉数cr（G）是指图G在平面上的一个绘图中的最小交叉数，其中不超过两条边相交于任一点，而该点不是顶点。图G的直线交叉数cr ′（G）是图G的边为直线段的图中的最小交叉数。Zarankiewicz在1952年证明了cr n1 −12 n22 n2−12。我们将上界Z（n1，n2）推广到A（n1，n2，n3）：=∑i= 1，2，3 {j，k}={1，2，3}<${i} nj 2nj − 12 nk 2nk −12+ ni 2ni − 12 njnk 2，并证明了cr <$（Kn 1，n2，n3）≤A（n1，n2，n3）.当n足够大时，0.973 A（n，n，n）≤ cr <$（Kn，n，n）和0.666 A（n，n，n）≤ cr（Kn，n，n），并通过使用旗代数建立了更严格的直线下界。一个完全多部图是平衡的，如果所有的部集具有相同的基数。研究了平衡完全r部图的交叉数的渐近性质。1997年，Richter和Kassen证明了当n→∞时，cr（Kn，n）在Kn，n的图中的最大交叉数上的极限是存在的，并且最多为14。我们定义了n（r）：=3（r2−r）8（r2+r−3），并证明了对于一个固定的r和一个平衡的完全r部图，n（r）是图中交叉数除以最大交叉数的极限上级的一个上界.
The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number cr ¯(G) of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that cr ¯(Kn1,n2)≤Z(n1,n2):=⌊n12⌋⌊n1−12⌋⌊n22⌋⌊n2−12⌋ . We generalize the upper bound Z(n1,n2) to A(n1,n2,n3):=∑i=1,2,3{j,k}={1,2,3}∖{i}nj2nj−12nk2nk−12+ni2ni−12njnk2,and prove cr ¯(Kn1,n2,n3)≤A(n1,n2,n3) . We also show that for n large enough, 0.973A(n,n,n)≤ cr ¯(Kn,n,n) and 0.666A(n,n,n)≤ cr (Kn,n,n) , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as n→∞ of cr (Kn,n) over the maximum number of crossings in a drawing of Kn,n exists and is at most 14 . We define ζ(r):=3(r2−r)8(r2+r−3) and show that for a fixed r and the balanced complete r‐partite graph, ζ(r) is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.
排列中长度为 4 的单调子序列的最小数量
DOI：
10.1017/s0963548314000820
发表时间：
2014
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J