The complexity of minimum difference cover

The complexity of searching minimum difference covers, both in Z⁺ and in Z_n, is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Z⁺ and in Z_n, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms.     

关于Gerber不等式的一个猜想

本文证明了陈计-单墫关于Ｇｅｒｂｅｒ不等式的一个猜想，作为其应用，导出了单形内一点到顶点的距离与到面的距离的两个不等式．     

具有唯一4度最大度点的图的全色数

一个图Ｇ的全色数χ_T（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）中相邻或相关联元素均染不同颜色的最少颜色数．文中证明了，若图Ｇ只有唯一的一个４度最大度点，则χ_T（Ｇ）＝Δ（Ｇ）＋１．     

Diagrams,orientations, and varieties

One of the central problems in the theory of ordered sets is to describe the orientations of the covering graph of an ordered set. We show that the particular operation called inversion, together with the classical constructions of retraction and product, provide a context for the classification of all such orientations. AMS subject classifications (1980). 06A10, 05C75, 05C20.     

Covering with blocks in the non-symmetric case

Considering an infinite string of i.i.d. random letters drawn from a finite alphabet we define the cover timeW _n as the number of random letters needed until each pattern of lenghtn appears at least once as a substring. Sharp weak and a.s. limit results onW _n are known in the symmetric case, i.e., when the random letters are uniformly distributed over the alphabet. In this paper we determine the limit distribution ofW _n in the nonsymmetric case asn. Generalizations in terms of point processes are also proved.Dedicated to Endre Csáki on his 60th birthday.     

q-Hypergeometric Series and Macdonald Functions

We derive a duality formula for two-row Macdonald functions by studying their relation with basic hypergeometric functions. We introduce two parameter vertex operators to construct a family of symmetric functions generalizing Hall-Littlewood functions. Their relation with Macdonald functions is governed by a very well-poised q-hypergeometric functions of type ₄₃, for which we obtain linear transformation formulas in terms of the Jacobi theta function and the q-Gamma function. The transformation formulas are then used to give the duality formula and a new formula for two-row Macdonald functions in terms of the vertex operators. The Jack polynomials are also treated accordingly.     

A note on differentiability of the cluster density for independent percolation in high dimensions

The cluster density function of independent percolation in ad-dimensional lattice is considered. For eachn, it is shown that(p) has finitenth leftderivative at critical probabilityp _c ifd is sufficiently large. This result agrees with the Bethe lattice approximation, where thenth one-sided derivative of(p) is bounded atp _c for alln.     

Weak Graph Map Homotopy and Its Applications∗

The authors introduce a notion of a weak graph map homotopy (they call it M-homotopy), discuss its properties and applications. They prove that the weak graph map homotopy equivalence between graphs coincides with the graph homotopy equivalence defined by Yau et al in 2001. The difference between them is that the weak graph map homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over the graph homotopy transformation. As its applications, they investigate the mapping class group of a graph and the 1-order MP-homotopy group of a pointed simple graph. Moreover, they show that the 1-order MP-homotopy group of a pointed simple graph is invariant up to the weak graph map homotopy equivalence.     

空间微小碎片对低轨道航天器太阳电池表面撞击损伤研究

低轨道空间微小碎片密度相对较高,对太阳电池等大面积暴露材料的累积撞击损伤效应是航天器设计中应考虑的主要问题之一.以典型的太阳同步轨道为例分析和计算了太阳电池表面所遭遇的微小碎片通量,进行了微小碎片的撞击损伤模拟实验,并建立了撞击损伤方程.根据碎片通量分布及撞击损伤方程计算了微小碎片的超高速撞击所产生的太阳电池表面的面积损伤率,通过光学透射率的实验测试并结合理论模型,对碎片导致的太阳电池光学透射率衰减进行了计算和分析.结果表明,10a累积撞击导致的太阳电池表面的面积损伤率平均约为0.61%,严重时达到2.3 关键词： 微小碎片 超高速撞击 太阳电池 玻璃盖片     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).