ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K1,8,n

The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph K_m,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤ 6. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K_1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.     

Spanning Trees Crossing Few Barriers

We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of $m$ barriers. We obtain the following results: (i) if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost $O(\min(m^2,m\sqrt{n}))$; (ii) if the barriers are disjoint line segments, then there is always a spanning tree of cost $O(m)$; (iii) ] if the barriers are disjoint convex objects, then there is always a spanning tree of cost $O(n+m)$. All our bounds are worst-case optimal, up to multiplicative constants.     

二部图形式的Erd\H{O}s-S\'{o}s猜想

二部图形式的Erd\H{O}s-S\''{o}s猜想     

$K_{5}\times S_{n}$ 的交叉数

把完全图$K_{5}$的五个顶点与另外$n$个顶点都联边得到一类特殊的图$H_{n}$.文中证明了$H_{n}$的交叉数为$Z(5,n)+2n+\lfloor \frac{n}{2}\rfloor+1$,并在此基础上证明了$K_{5}$与星$K_{1,n}$的笛卡尔积的交叉数为$Z(5,n)+5n+\lfloor\frac{n}{2} \rfloor+1$.     

Illumination in the presence of opaque line segments in the plane

What is the minimal number of light sources which is always sufficient to illuminate the plane in the presence of n disjoint opaque line segments? For n5, O'Rourke proved that 2n/3 light sources are always sufficient and sometimes necessary, if light sources can be placed on the line segments and thus they can illuminate both sides of a segment.

We prove that 2(n+1)/3 light sources are always sufficient and sometimes necessary, if light sources cannot be placed on the line segments. An O(nlogn) time algorithm is presented which allocates at most 2(n+1)/3 light sources collectively illuminating the plane.     

五阶图与星图的笛卡尔积交叉数

In this paper, we compute the crossing number of a specific graph Hn, and then by contraction, we obtain the conclusion that cr（G13 × Sn） = 4[n/2] [n-1/2]＋[n/2] . The result fills up the blank of the crossing numbers of Cartesian products of stars with all 5-vertex graphs presented by Marian Klesc.     

图的距离无符号拉普拉斯谱半径的关于色数的下界

Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.     

关于图符号的边控制 (英)

设γ's(G)和γ'ι(G)分别表示图G的符号边和局部符号边控制数,本文主要证明了:对任何n阶图G(n≥4),均有γ's(G)≤[11/6n-1]和γ'ι(G)≤2n-4成立,并提出了若干问题和猜想．     

一个关于近-三角剖分嵌入的内插定理

一个近三角剖分嵌入是指一个图嵌入在一个曲面上,使得至多可能有一个面不是三角面。在本文中我们证明了如下结果：如果一个图G在某个可定向曲面S_h上有三角剖分嵌入,那么G在S_k上有一个近三角剖分嵌入,这里k=h,h 1,…,[β(G)/2],而β(G)是图G的Betti数。     

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis-parallel rectangles of various dimensions. (a) We construct a set of $n$ disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least $2n-o(n)$, almost matching an upper bound of dAmore and Franciosa. (b) We establish a similar lower bound of $7n/3-o(n)$ for disjoint rectangles in the plane. (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in $\reals^d$ and disjoint rectangles in $\reals^3$. (d) We derive a worst-case bound of $\Theta(n^{5/3})$ for the size of BSPs of disjoint $2$-rectangles in $4$-space. (e) For disjoint $k$-rectangles in $d$-space, we prove the worst-case bound $\Theta(n^{d/(d-k)})$, for any $k<d/2$; this bound holds for all $k<d$ if the rectangles are allowed to intersect.     

Stabbing Delaunay Tetrahedralizations

A Delaunay tetrahedralization of $n$ vertices is exhibited for which a straight line can pass through the interiors of $\Theta(n^2)$ tetrahedra. This solves an open problem of Amenta, who asked whether a line can stab more than $O(n)$ tetrahedra. The construction generalizes to higher dimensions: in $d$ dimensions, a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$ Delaunay $d$-simplices. The relationship between a Delaunay triangulation and a convex polytope yields another result: a two-dimensional slice of a $d$-dimensional $n$-vertex polytope can have $\Theta(n^{\lfloor d / 2 \rfloor})$ facets. This last result was first demonstrated by Amenta and Ziegler, but the construction given here is simpler and more intuitive.     

图的上可嵌入性与独立顶点的新度和

Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable.     

树和单圈图的斜谱矩

给定图$G$,对图$G$的每条边确定一个方向,称为$G$的定向图$G^\sigma$, $G$称为$G^\sigma$的基础图. $G^\sigma$的斜邻接矩阵$S(G^\sigma)$是反对称矩阵,其特征值是0或纯虚数. $S(G^\sigma)$所有特征值的$k$次幂之和称为$G^\sigma$的$k$阶斜谱矩,其中$k$是非负整数.斜谱矩序列可用于对图进行排序.本文主要研究定向树和定向单圈图的斜谱矩,并对这两类图的斜谱矩序列依照字典序进行排序.首先确定了直径为$d$的树作为基础图的所有定向树中,斜谱矩序最大的$2\lfloor\frac{d}{4}\rfloor$个图; 然后确定以围长为$g$的单圈图作为基础图的所有定向单圈图中, 斜谱矩序最大的$2\lfloor\frac{g}{4}\rfloor+1$个图.     

一个关于球面和环面上嵌入图的近-三角剖分嵌入的内插定理(I)

一个近-三角剖分嵌入是指一个曲面上的嵌入图使得几乎所有的面都是三角形,至多只有一个可能的例外.文中作者证明了如下结论:如果一个图G 在球面S₀(或环面S₁)上有近-三角剖分嵌入,那么G在每一个可定向曲面S_k有近-三角剖分嵌入,其中k=h,h+1,\cdots ,\lfloor\frac{\beta(G)}{2}\rfloor$, 而h=0(或1)并且β(G)是图G的Betti数.特别地,G是上可嵌入的.     

ON A PROBLEM OF SUMS OF MIXED POWERS （II）

ＯＮＡＰＲＯＢＬＥＭＯＦＳＵＭＳＯＦＭＩＸＥＤＰＯＷＥＲＳ（Ｉ）ＬＵＭＩＮＧＧＡＯＹＵＧＡＮＧＡｂｓｔｒａｃｔＬｅｔＲｂ，ｃ（ｎ）ｄｅｎｏｔｅｔｈｅｎｕｍｂｅｒｏｆｒｅｐｒｅｓｅｎｔａｔｉｏｎｓｏｆｎａｓｔｈｅｓｕｍｏｆｏｎｅｓｑｕａｒｅ，ｆｏ...     

An addition to art galleries with interior walls

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Each interior wall has an arbitrarily placed, arbitrarily small doorway. It is shown in [5] that the minimum number of guards that suffice to guard all art galleries with n vertices and m interior walls is \min{ \lfloor (2n-3)/3\rfloor, \lfloor (2m+n)/3\rfloor, \lfloor (2n+m-2)/4\rfloor} . The proofs for the first two bounds lead to linear-time guard placement algorithms, while this is not known for the third case. We present an alternative short proof for the third upper bound \lfloor(2n+m-2)/4\rfloor that also leads to a linear-time guard placement algorithm. Received March 2, 2000, and in revised form April 28, 2000. Online publication October 10, 2000.     

Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为t(g(V)≤l≤c(G))的圈,其中g(G),c(v)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[n2/4]-n 5的n阶非二部图为弱泛圈图.1999年Bollobas和Thomason证明了边数不小于[n2/4]-n 59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[n2/4]-n 12,则G为弱泛圈图.     

参数函数$\epsilon$取边际值时的$GCF_\epsilon$集

Let ∈ :N → R be a parameter function satisfying the condition ∈(k) + k + 1 > 0and let T∈ :(0,1] →(0,1] be a transformation defined by T∈(x) =-1 +(k + 1)x1 + k-k∈x for x ∈(1k + 1,1k].Under the algorithm T∈,every x ∈(0,1] is attached an expansion,called generalized continued fraction(GCF∈) expansion with parameters by Schweiger.Define the sequence {kn(x)}n≥1of the partial quotients of x by k1(x) = ∈1/x∈ and kn(x) = k1(Tn-1∈(x)) for every n ≥ 2.Under the restriction-k-1 < ∈(k) <-k,define the set of non-recurring GCF∈expansions as F∈= {x ∈(0,1] :kn+1(x) > kn(x) for infinitely many n}.It has been proved by Schweiger that F∈has Lebesgue measure 0.In the present paper,we strengthen this result by showing that{dim H F∈≥12,when ∈(k) =-k-1 + ρ for a constant 0 < ρ < 1;1s+2≤ dimHF∈≤1s,when ∈(k) =-k-1 +1ksfor any s ≥ 1where dim H denotes the Hausdorff dimension.     

On Factorisations and Generators in Transformation Semigroups

It is shown that the classical decomposition of permutations into disjoint cycles can be extended to more general mappings by means of path-cycles, and an algorithm is given to obtain the decomposition. The device is used to obtain information about generating sets for the semigroup of all singular selfmaps of $X_{n} = \{1, 2, \dots, n\}$. Let $T_{n,r} = S_{n}\cup K_{n,r}$, where $S_{n}$ is the symmetric group and $K_{n,r}$ is the set of maps $\alpha\,:\, X_{n} \to X_{n}$ such that $|im(\alpha)| \le r$. The smallest number of elements of $K_{n,r}$ which, together with $S_{n}$, generate $T_{n,r}$ is $p_{r}(n)$, the number of partitions of $n$ with $r$ terms.     

Disjoint empty convex pentagons in planar point sets

In this paper we obtain the first non-trivial lower bound on the number of disjoint empty convex pentagons in planar points sets. We show that the number of disjoint empty convex pentagons in any set of n points in the plane, no three on a line, is at least $\left\lfloor {\tfrac{{5n}} {{47}}} \right\rfloor $ . This bound can be further improved to $\tfrac{{3n - 1}} {{28}} $ for infinitely many n.