Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004     

Testing for independence by the empirical characteristic function

Tests of total independence of d (≥2) random variables are proposed using the empirical characteristic function. The approach is parallel to that of Hoeffding, Blum, Kiefer, and Rosenblatt.     

强相互作用味道无关性的检验

通过比较不同味道初始夸克碎裂的带电粒子多重数可以对强相互作用味道无关性进行检验.计算了e+e–湮没成轻味夸克u,d,s碎裂的粒子多重数,发现不同味道夸克事例中,平均粒子产率,同位旋对称性,由奇异与非奇异粒子多重数比值确定的奇异抑制因子等都与初始夸克味道有关,而且这种依赖性在低能时更加明显.但3种轻味夸克事例的平均带电粒子多重数近似相等,这与QCD强相互作用与味道无关的预言一致.     

A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints

In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified easily. This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to an anonymous referee for critical comments.     

Some properties of record values coming from the geometric distribution

The independence between spacings of record values and of individual record values is well known when the records come from a geometric distribution. Here we examine the form a function of two record values must have if we require independence from a lower record value. Also similar questions are examined in relation to conditional expectation and conditional variance.     

二元极值分布的独立性检验及在沪深股市分析中的应用

提出了二元极值分布的一个独立性检验统计量 T5,导出了它的渐近分布 ,得出了模拟分位点 ,并在小样本情况下 ,与其它已有的统计量进行比较 .结果说明本文给出的统计量 T5具有与似然比检验统计量 T3几乎相同的功效 ,且比其它检验方法有效 .最后对中国沪深两市的股票收盘指数的极值进行了独立性检验 ,认为具有显著的相关性 .     

Tail behaviour of Gaussian processes with applications to the Brownian pillow

In this paper we investigate the tail behaviour of a random variable S which may be viewed as a functional T of a zero mean Gaussian process X, taking special interest in the situation where X obeys the structure which is typical for limiting processes occurring in nonparametric testing of (multivariate) independency and (multivariate) constancy over time. The tail behaviour of S is described by means of a constant a and a random variable R which is defined on the same probability space as S. The constant a acts as an upper bound, and is relevant for the computation of the efficiency of test statistics converging in distribution to S. The random variable R acts as a lower bound, and is instrumental in deriving approximation for the upper percentage points of S by simulation.     

Separation logic and logics with team semantics

Separation logic is a successful logical system for formal reasoning about programs that mutate their data structures. Team semantics, on the other side, is the basis of modern logics of dependence and independence. Separation logic and team semantics have been introduced with quite different motivations, and are investigated by research communities with rather different backgrounds and objectives. Nevertheless, there are obvious similarities between these formalisms. Both separation logic and logics with team semantics involve the manipulation of second-order objects, such as heaps and teams, by first-order syntax without reference to second-order variables. Moreover, these semantical objects are closely related; it is for instance obvious that a heap can be seen as a team, and the separating conjunction of separation logic is (essentially) the same as the team-semantical disjunction. Based on such similarities, the possible connections between separation logic and team semantics have been raised as a question at several occasions, and lead to informal discussions between these research communities. The objective of this paper is to make this connection precise, and to study its potential but also its obstacles and limitations.     

On elementary logics for quantitative dependencies

We define and study logics in the framework of probabilistic team semantics and over metafinite structures. Our work is paralleled by the recent development of novel axiomatizable and tractable logics in team semantics that are closed under the Boolean negation. Our logics employ new probabilistic atoms that resemble so-called extended atoms from the team semantics literature. We also define counterparts of our logics over metafinite structures and show that all of our logics can be translated into functional fixed point logic implying a polynomial time upper bound for data complexity with respect to BSS-computations.     

On the Presburger fragment of logics with multiteam semantics

In team semantics, which is the basis of modern logics of dependence and independence, formulae are evaluated on sets of assignments, called teams. Multiteam semantics instead takes mulitplicities of data into account and is based on multisets of assignments, called multiteams. Logics with multiteam semantics can be embedded into a two-sorted variant of existential second-order logics, with arithmetic operations on multiplicities. Here we study the Presburger fragment of such logics, permitting only addition, but not multiplication on multiplicities. It can be shown that this fragment corresponds to inclusion-exclusion logic in multiteam semantics, but, in contrast to the situation in team semantics, that it is strictly contained in independence logic. We give different characterisations of this fragment by various atomic dependency notions.