The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Global and exploding solutions in a model of self-gravitating systems

We study asymptotic properties of solutions to an extension to arbitrary dimensions of the astrophysical model proposed by Chavanis et al. to explain phenomena of gravitational collapse in clouds of self-gravitating particles. In particular, we show that in the two-dimensional case the solutions can be continued to global ones, while in three space dimensions large data of negative energy blow up in a finite time. Relations between isothermal, Streater's energy-transport and the present models are also studied.     

A note on conservation laws for a multiclass service queueing system with setup times

This paper derives a conservation law for mean waiting times in a single-server multi-class service queueing system (M ^X/G/1 type queue) with setup times which may be dependent on multiple customer classes and its arrival batch size by using the work decomposition property in the queueing system with vacations.     

核内核子－核子非弹散射截面（Ⅰ）

在与平均场、核内核子－核子弹性散射截面以及输运方程相统一的理论框架内推导了核内核子－核子非弹散射截面的解析表达式．其数值结果能很好地重现自由非弹截面的实验值，所计算的有效非弹截面与Ｄｉｒａｃ－Ｂｒｕｅｃｋｎｅｒ的计算结果相一致．     

纯量反馈系统同时强镇定的充分条件

一个稳定的补偿器可同时镇定n个对象(同时强镇定)等价于一个补偿器(不一定稳定)同时镇定n 1个对象(同时镇定)．两个以上对象的同时强镇定和三个以上对象的伺时镇定是线性系统中一个急待解决的公开问题．文中所作的基本假定是所有的对象具有相同的简单不稳定零点，在此条件下给出了n个对象同时强镇定的一个充分条件．当仅有一个不稳定零点时．容易检验是否同时强镇定，否则仅需确定n个对象的不稳定零点并且判定由不稳定零点导出一个相应矩阵是正定的，就能判定n个对象同时强镇定．因此是一个易于检验的充分条件．文章同时给出了n个对象同时强镇定的算法，丰富了同时强镇定的充分条件．     

An invariance of geometric mean with respect to Lagrangian means

The invariance of the geometric mean G with respect to the Lagrangian mean-type mapping (Lf,Lg), i.e. the equation G○(Lf,Lg)=G, is considered. We show that the functions f and g must be of high class regularity. This fact allows to reduce the problem to a differential equation and determine the second derivatives of the generators f and g.     

ℙmax variations related to slaloms

We prove the iteration lemmata, which are the key lemmata to show that extensions by Pmax variations satisfy absoluteness for Π₂-statements in the structure 〈H (ω ₂), ∈, NS_{ω 1}, R 〉 for some set R of reals in L (ℝ), for the following statements: (1) The cofinality of the null ideal is ℵ₁. (2) There exists a good basis of the strong measure zero ideal. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

向量变分不等式的严格可行性问题

本篇文章首先定义了向量变分不等式的严格可行点概念,其次在假设了映射是强(D)-伪单调的情况下,证明了向量变分不等式解集非空有界与其严格可行点存在的等价性问题,推广了在数量变分不等式上得到的相应结果．     

Supercompactness and measurable limits of strong cardinals II: Applications to level by level equivalence

We construct models for the level by level equivalence between strong compactness and supercompactness in which for κ the least supercompact cardinal and δ ≤ κ any cardinal which is either a strong cardinal or a measurable limit of strong cardinals, 2^δ > δ ⁺ and δ is < 2^δ supercompact. In these models, the structure of the class of supercompact cardinals can be arbitrary, and the size of the power set of κ can essentially be made as large as desired. This extends and generalizes [5, Theorem 2] and [4, Theorem 4]. We also sketch how our techniques can be used to establish a weak indestructibility result. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Regularity of Bunimovich’s stadia

Stadia are popular models of chaotic billiards introduced by Bunimovich in 1974. They are analogous to dispersing billiards due to Sinai, but their fundamental technical characteristics are quite different. Recently many new results were obtained for various chaotic billiards, including sharp bounds on correlations and probabilistic limit theorems, and these results require new, more powerful technical apparatus. We present that apparatus here, in the context of stadia, and prove “regularity” properties.