Zero-one laws for polynomials in Gaussian random variables: A simple proof

Zero-one laws for polynomials in Gaussian random variables have already been studied.⁽⁷⁾ They are established here by very simple arguments: Fubini's theorem and the rotational invariance of centered Gaussian measures. The proof is built on the Polarization formula that has received much attention in Refs. 1 and 5. Our point of view derives from the deep work of Borell.⁽²⁾ In a natural way, these results extend to finite-order Gaussian chaos processes.     

利用最小调整法求解特殊的二维0-1规划

具有特殊约束的二维0-1规划的实际应用广泛,在解法中多是应用传统算法,或是在它基础上进行改进,但是此类解法计算繁琐不易推广.针对这种情形,本文引入最小调整法处理此类问题,并将其与传统算法进行对比,充分展示了该方法的优越性,呈现出灵活、方便、简单、易行的特点.通过举例验证了方法的有效性.     

A Random Set Extension of a Strong Law of Large Numbers of Cantrell and Rosalsky

Abstract

A strong law of large numbers under conditions irrespective of the joint distribution of the sequence is extended to random sets. The extension is such that the role of events of the form {||V _n || ≤ b _n } (where V _n is a random element of a separable Banach space) is played by events of the form {X _n  ? B _n } (where X _n is a random closed bounded set).     

The Strong Law of Large Numbers for Kaplan–Meier U-Statistics

We introduce a Kaplan–Meier U-statistic of degree two for randomly censored data and prove a strong law for it. We use the technique of Stute and Wang⁽³⁾ by identifying appropriate reverse-time supermartingale processes. This approach avoids the stringent assumptions of Gijbels and Veraverbeke⁽¹⁾ who consider similar functionals.     

The evolution of the min-min random graph process

We study the following min-min random graph process G=(G₀,G₁,…): the initial state G₀ is an empty graph on n vertices (n even). Further, G_M+1 is obtained from G_M by choosing a pair {v,w} of distinct vertices of minimum degree uniformly at random among all such pairs in G_M and adding the edge {v,w}. The process may produce multiple edges. We show that G_M is asymptotically almost surely disconnected if M≤n, and that for M=(1+t)n, constant, the probability that G_M is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside the giant component of G_M for M=(1+t)n. For constant we derive the precise limiting distribution of X. In addition, for n⁻¹ln⁴n≤t=o(1) we show that tX converges to a gamma distribution.     

A zero-one law for a random subset

We consider first order sentences about two logical structures. First we consider 1,…, n with the successor relation and a random unary relation that points satisfy with probability p(n). We then replace the successor relation with less than. For both structures we characterize those p(n) for which a zero-one law holds.     

On sample path properties of semistable processes

This paper contains three main results: In the first result a correspondence principle between semistable measures on L_p, 1 ≤ p < ∞, and Banach space valued semistable processes is established. In the second result it is shown that the paths of a Banach space valued semistable process belong to L_p with probability zero or one, and necessary and sufficient conditions for the two alternatives to hold are given. In the third result necessary and sufficient conditions are given for almost sure path absolute continuity for certain Banach space valued semistable processes.     

Precoloring Extension of Co-Meyniel Graphs

The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs. C.N.R.S. Final version received: January, 2007     

Star saturation number of random graphs

For a given graph $F$, the $F$-saturation number of a graph $G$ is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. Recently, the $F$-saturation number of the Erd?s–Rényi random graph $\mathbb{G}(n,p)$ has been determined asymptotically for any complete graph $F$. In this paper, we give an asymptotic formula for the $F$-saturation number of $\mathbb{G}(n,p)$ when $F$ is a star graph.     

Asymptotics for logical limit laws: When the growth of the components is in an RT class

Compton's method of proving monadic second-order limit laws is based on analyzing the generating function of a class of finite structures. For applications of his deeper results we previously relied on asymptotics obtained using Cauchy's integral formula. In this paper we develop elementary techniques, based on a Tauberian theorem of Schur, that significantly extend the classes of structures for which we know that Compton's theory can be applied.

     

弦图扩张与最优排序

弦图是一类特殊的完美图,以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题,沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

Bernoulli序列无规则性定理的推广

本文目的是要利用随机比较系数的概念和区间的分法,推广关于Bernoulli序列的无规则性定理。     

Limit laws in the generalized random graphs with random vertex weights

In this note we investigate the number of edges and the vertex degree in the generalized random graphs with vertex weights, which are independent and identically distributed random variables.     

On the sizes of large subgraphs of the binomial random graph

We consider the binomial random graph $G(n,p)$, where p is a constant, and answer the following two questions.First, given $e(k)=p\left(\begin{array}{c}k\\ 2\end{array}\right)+O(k)$, what is the maximum k such that a.a.s. the binomial random graph $G(n,p)$ has an induced subgraph with k vertices and $e(k)$ edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small $e(k)$). Moreover, for every constant $C>0$, with probability bounded away from 0, the size of the concentration set is bigger than $C\sqrt{n/\ln ?n}$, and, for every ${\omega }_n\to \infty$, a.a.s. it is smaller than ${\omega }_n\sqrt{n/\ln ?n}$.Second, given $k>\epsilon n$, what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of $G(n,p)$ contains a full interval of length μ? The answer is $\mu =\mathrm{\Theta }\left(\sqrt{(n?k)n\ln ?\left(\begin{array}{c}n\\ k\end{array}\right)}\right)$.     

Continuous-Time Independent Edge-Markovian Random Graph Process

In this paper, the continuous-time independent edge-Markovian random graph process model is constructed. The authors also define the interval isolated nodes of the random graph process, study the distribution sequence of the number of isolated nodes and the probability of having no isolated nodes when the initial distribution of the random graph process is stationary distribution, derive the lower limit of the probability in which two arbitrary nodes are connected and the random graph is also connected, and prove that the random graph is almost everywhere connected when the number of nodes is sufficiently large.     

Zero-One Law for Symmetric Convolution Semigroups of Measures on Groups

Let ( _t ) _t>0 be a symmetric weakly continuous semigroup of probability measures on a nonabelien complete separable group G and let v be its Lévy measure. The purpose of this paper is to provide a relatively simple proof of the zero-one law for semigroups with the Lévy measure satisfying either v(H ^c) = or v(H ^c) = 0.     

On the norms of group-invariant transition operators on graphs

In this paper we consider reversible random walks on an infinite grapin, invariant under the action of a closed subgroup of automorphisms which acts with a finite number of orbits on the vertex-set. Thel ²-norm (spectral radius) of the simple random walk is equal to one if and only if the group is both amenable and unimodular, and this also holds for arbitrary random walks with bounded invariant measure. In general, the norm is bounded above by the Perron-Frobenius eigenvalue of a finite matrix, and this bound is attained if and only if the group is both amenable and unimodular.