关于平行三角形集簇直线横截的Helly数

We prove two results about the problem of finding the Helly number for line transversals to a family of parallel triangles in the plane: (1) If each three triangles of a family of parallel right triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all the triangles of the family; (2) If each three triangles of a family of parallel obtuse triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all the triangles of the family. We also obtain that the Helly number of a family of parallel right or obtuse triangles is 3.     

On the Helly Number for Hyperplane Transversals to Unit Balls

We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R ^d . Received January 25, 1999, and in revised form July 7, 1999.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

Optimal Multipliers for Linear Congruential Pseudo-Random Number Generators with Prime Moduli: Parallel Computation and Properties

Two systematic search methods are employed to find multipliers for linear congruential pseudo-random number generation which are optimal with respect to an upper bound for the discrepancy of pairs of successive pseudo-random numbers. The efficiency of these search procedures when executed on parallel systems is assessed by experimental results of a MIMD parallel implementation on a Meiko CS-2 and a workstation cluster. Furthermore the quality of the computed multipliers is evaluated by using the spectral test in dimensions 2–8 and by calculating the actual discrepancy of pairs of the resulting full-period sequences.     

当绝热指数很大时气体的一种非定常平面平行运动的渐近解

文献[1]在气体的速度分量只与极角θ及时间t有关,而与极距r无关的条件下求解理想气体的非定常平面平行具势运动方程组(1.2)～(1.3).文献[1]指出,在一般的情况下,不能得到解的显式表示式,只是对于二种特殊情况得到了显式解.本文研究了文献[1]的同样问题.第一部分,对音速作了一些补充限制,从而得到了方程组的显式解.第二部分,假设气体的绝热指数γ>>1,求得了方程组的一级近似解.     

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x∈V(G) the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O(mlogn) time whether G is a median graph with geodetic number 2.     

关于Ramsey数下界的部分结果

本文得到 Ramsey数下界的一个计算公式 :R( l,s+ t-2 )≥ R( l,s) + R( l,t) -1 ,(式中 l、s、t≥ 3) .用此公式算得的 Ramsey数的下界比用其它公式算得的下界好 .     

On the Jump Number of Lexicographic Sums of Ordered Sets

Let Q be the lexicographic sum of finite ordered sets Q _x over a finite ordered set P. For some P we can give a formula for the jump number of Q in terms of the jump numbers of Q _x and P, that is, , where s(X) denotes the jump number of an ordered set X. We first show that where w(X) denotes the width of an ordered set X. Consequently, if P is a Dilworth ordered set, that is, s(P) = w(P)–1, then the formula holds. We also show that it holds again if P is bipartite. Finally, we prove that the lexicographic sum of certain jump-critical ordered sets is also jump-critical.     

On the transversal number and VC-dimension of families of positive homothets of a convex body

Let F be a family of positive homothets (or translates) of a given convex body K in Rⁿ. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number τ(F) of F in terms of n and the independence number ν(F). This question is motivated by a problem of Grünbaum [L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 101-180]. Our bound is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan [S.-J. Kim, K. Nakprasit, M.J. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Math. 306 (18) (2006) 2166-2173], which was of order nⁿ. By a lower bound, we show that the right order of magnitude is exponential in n.Next, we consider another measure of complexity, the Vapnik-?ervonenkis dimension of F. We prove that vcdim(F)≤3 if n=2 and is infinite for some F if n≥3. This settles a conjecture of Grünbaum [B. Grünbaum, Venn diagrams and independent families of sets, Math. Mag. 48 (1975) 12-23]: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in Rⁿ is n+1. This conjecture was disproved by Naiman and Wynn [D.Q. Naiman, H.P. Wynn, Independent collections of translates of boxes and a conjecture due to Grünbaum, Discrete Comput. Geom. 9 (1) (1993) 101-105] who constructed a counterexample of dual VC-dimension . Our result implies that no upper bound exists.     

Genetic Algorithm for the Jump Number Scheduling Problem

This paper introduces genetic algorithms for the jump number scheduling problem. Given a set of tasks subject to precedence constraints, the problem is to construct a schedule to minimize the number of jumps. We show that genetic algorithms outperform the previously known Knuth and Szwarcfiter's exhaustive search algorithm when applied to some classes of orders in which no polynomial time algorithms exist in solving the jump number problem. Values for various parameters of genetic jump number algorithms are tested and results are discussed.     

On the length of longest alternating paths for multicoloured point sets in convex position

Let P be a set of points in R² in general position such that each point is coloured with one of k colours. An alternating path of P is a simple polygonal whose edges are straight line segments joining pairs of elements of P with different colours. In this paper we prove the following: suppose that each colour class has cardinality s and P is the set of vertices of a convex polygon. Then P always has an alternating path with at least (k-1)s elements. Our bound is asymptotically sharp for odd values of k.     

An equivalent condition for the self similar sets on the real line to have best coverings

In this paper, an equivalent condition for the self similar sets on the real line to have best coverings is given. As a result, it partly gives answer to the conjecture which was posed by Zhou and Feng [Zhou, Z. L., Feng, L.： Twelve open problems on the exact value of the Hausdorff measure and on topological entropy： A brief survey of recent results. Nonlinearity, 17（2）, 493-502 （2004）].     

Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

For any graph G, let be the number of spanning trees of G, be the line graph of G, and for any nonnegative integer r, be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e. In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on for such a graph G.     

On the clique number of the square of a line graph and its relation to maximum degree of the line graph

In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph , that is, , can be colored with colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is, , is at most . In 2015, Śleszyńska-Nowak proved that . In this paper, we prove that . This theorem follows from our stronger result that where .     

On Testing for the Number of Components in a Mixed Poisson Model

Poisson mixtures are usually used to describe overdispersed data. Finite Poisson mixtures are used in many practical situations where often it is of interest to determine the number of components in the mixture. Identifying how many components comprise a mixture remains a difficult problem. The likelihood ratio test (LRT) is a general statistical procedure to use. Unfortunately, a number of specific problems arise and the classical theory fails to hold. In this paper a new procedure is proposed that is based on testing whether a new component can be added to a finite Poisson mixture which eventually leads to the number of components in the mixture. It is a sequential testing procedure based on the well known LRT that utilises a resampling technique to construct the distribution of the test statistic. The application of the procedure to real data reveals some interesting features of the distribution of the test statistic.     

基于Copula的部件相依并联系统可靠性分析

应用Copula函数,研究了部件相依的并联系统可靠性问题,给出了F-G-M Copula函数下并联系统的可靠度、平均寿命、失效率的表达式,讨论了部件下象限相关下并联系统的平均寿命与部件独立时系统的平均寿命的关系,通过算例分析了部件个数与部件相依关系对系统平均寿命的影响。     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.     

快速造P(n,k)大表的左肩法则和斜线法则

设Ｐ（ｎ,ｋ）为整数ｎ分为ｋ部的无序分拆的个数,每个分部≥１,它为大师欧拉所建立（１７０７－１７８３）．它是组合图论和数论里最重要的数据之一．然而,它却十分难于计数和造表．本文,由公式Ｐ（ｎ,ｋ）＝Ｐ（ｎ－１,ｋ－１）＋Ｐ（ｎ－ｋ,ｋ）定义了Ｐ（ｎ,ｋ）的左肩数和锐角数,并由此得到求Ｐ（ｎ,ｋ）的左肩法则（第一法则）．还根据本文作者［５］的一些重要定理得到求 Ｐ（ｎ,ｋ）的斜线法则（第二法则）．使用这些法则得到造Ｐ（ｎ,ｋ）大表的有趣原理．为方便计,我们仅用第一法则设计了计算机程序,用此程序即可快速造出任意大的Ｐ（ｎ,ｋ）表．