On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Noise sensitivity of Boolean functions and applications to percolation

It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on ann+1 byn grid. A configuration is a function that assigns to every edge the value 0 or 1. Let ω be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges ℓ with ω(ℓ)=1. By duality, the probability for having a crossing is 1/2. Fix an ɛ ∈ (0, 1). For each edge ℓ, let ω′(ℓ)=ω(ℓ) with probability 1 − ɛ, and ω′(ℓ)=1 − ω(ℓ) with probability ɛ, independently of the other edges. Letp(τ) be the probability for having a crossing in ω, conditioned on ω′ = τ. Then for alln sufficiently large,P{τ : |p(τ) − 1/2| > ɛ}<ɛ.     

Uncountable admissibles II: Compactness

AssumeV=L. Let κ be a cardinal and forX⊆κ, n<ω let α _n (X) denote the least ordinal α such thatL _α[X] is Σ _n admissible. In our earlier paperUncountable admissibles I: forcing, we characterized those ordinals of the form σ _n (X) when κ is regular. This paper treats the singular case using Barwise compactness, an effective version of Jensen's covering lemma and β-recursion theory.     

The weighted Herz-type Hardy spaces hK q α,p (ω1,ω2)

Let 1<q<∞, n(1−1/q)≤α<∞, 0<p<∞ and ω₁,ω₂ ɛA ₁(R ⁿ ) (the Muckenhoupt class). In this paper, the author introduce the weighted Herz-type Hardy spaces hk _q ^α,p (gw₁,ω₂) and present their atomic decomposition. Using the atomic decomposition, the author find out their dual spaces, establish the boundedness on these spaces of the pseudo-differential operators of order zero and show thatD(R ⁿ ), the class of C^∞(Rⁿ)-functions with compactly support, is dense inhK _q ^α,p (ω₁,ω₂) and there is a subsequence, which converges in distrbutional sense to some distribution ofhK _q ^α,p (ω₁,ω₂), of any bounded sequence inhK _q ^α,p (ω₁,ω₂). In addition, the author also set up the boundedness of some non-linear quantities in compensated compactness. Supported by the NECF and the NECF and the NNSF of China.     

Random ergodic theorems and real cocycles

We study mean convergence of ergodic averages associated to a measure-preserving transformation or flow τ along the random sequence of times κ _n (ω) given by the Birkhoff sums of a measurable functionF for an ergodic measure-preserving transformationT. We prove that the sequence (k _n(ω)) is almost surely universally good for the mean ergodic theorem, i.e., that, for almost every, ω, the averages (*) converge for every choice of τ, if and only if the “cocycle”F satisfies a cohomological condition, equivalent to saying that the eigenvalue group of the “associated flow” ofF is countable. We show that this condition holds in many natural situations. When no assumption is made onF, the random sequence (k _n(ω)) is almost surely universally good for the mean ergodic theorem on the class of mildly mixing transformations τ. However, for any aperiodic transformationT, we are able to construct an integrable functionF for which the sequence (k _n(ω)) is not almost surely universally good for the class of weakly mixing transformations.     

On the monadic theory ofω 1 without A.C.

Buchi inLecture Notes in Mathematics, Decidable Theories II (1973) by using A.C. characterized the theoriesMT[β, <] forβ<ω ₁ and showed thatMT[ω ₁, <] is decidable. We extend Buchi’s results to a larger class of models of ZF (without A.C.) by proving the following under ZF only: (1) There is a choice function which chooses a “good” run of an automaton on countable input (Lemma 5.1). It follows that Buchi’s results cocerning countable ordinals are provable within ZF. (2) Let U.D. be the assertion that there exists a uniform denumeration ofω ₁ (i.e. a functionf: ω ₁ → ω ₁ ^ω such that for everyα<ω ₁,f(α) is a function fromω ontoα). We show that U.D. can be stated as a monadic sentence, and thereforeω ₁ is characterizable by a sentence. (3) LetF be the filter of the cofinal closed subsets ofω ₁. We show that if U.D. holds thenMT[ω ₁, <] is recursive in the first order theory of the boolean algebraP (ω ₁)/F. (We can effectively translate each monadic sentence Σ to a boolean sentenceσ such that [ω ₁, <] ⊨ Σ iffP(ω ₁)/F⊨σ). (4) As every complete boolean algebra theory is recursive we have that in every model of ZF+U.D.,MT[ω ₁, <] is recursive. All our proofs are within ZF. Buchi’s work is often referred to. Following Buchi, the main tool is finite automata. We don’t deal withMT[ω ₁, <] forω ₁ which doesn’t satisfy U.D. The results in this paper appeared in the author’s M.Sc. thesis, which was prepared at the Hebrew University under the supervision of Professor M. Rabin.     

Some divisibilities amongst the terms of linear recurrences

Let (u_n)n≥0 be a non-degenerate linear recurrence sequence of integers. We show that the set of positive integersn such that either ω)(n) orΩ(n) dividesu _n is of asymptotic density zero, where ω(n) and Ω(n) are the numbers of prime and prime power divisors ofn, respectively. The same also holds for the set of positive integersn such that τ(n)u _n , where τ(n) is the number of the positive integer divisors of n, provided thatu _n satisfies some mild technical conditions.     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

An extension of Hawkes theorem on the Hausdorff dimension of a Galton–Watson tree

Let ? be the genealogical tree of a supercritical multitype Galton–Watson process, and let Λ be the limit set of ?, i.e., the set of all infinite self-avoiding paths (called ends) through ? that begin at a vertex of the first generation. The limit set Λ is endowed with the metric d(ζ, ξ) = 2 ⁻ⁿ where n = n(ζ, ξ) is the index of the first generation where ζ and ξ differ. To each end ζ is associated the infinite sequence Φ(ζ) of types of the vertices of ζ. Let Ω be the space of all such sequences. For any ergodic, shift-invariant probability measure μ on Ω, define Ω_μ to be the set of all μ-generic sequences, i.e., the set of all sequences ω such that each finite sequence v occurs in ω with limiting frequency μ(Ω(v)), where Ω(v) is the set of all ω′?Ω that begin with the word v. Then the Hausdorff dimension of Λ∩Φ⁻¹ (Ω_μ) in the metric d is

Growth and recurrence of stationary random walks

 Let (X _n ,n≥1) be a real-valued ergodic stationary stochastic process, and let (Y _n =X ₁ +…+X _n ,n≥1) be the associated random walk. We prove the following: if the sequence of distributions of the random variables Y _n /n,n≥1, is uniformly tight (or, more generally, does not have the zero measure as a vague limit point), then there exists a real number c such that the random walk (Y _n −nc,n≥1) is recurrent. If this sequence of distributions converges to a probability measure ρ on ℝ (or, more generally, has a nonzero limit ρ in the vague topology), then (Y _n −nc,n≥1) is recurrent for ρ−a.e.cℝ. Received: 24 September 2001 / Revised version: 1 August 2002 / Published online: 24 October 2002 The first author was partially supported by the FWF research project P14379-MAT. Mathematics Subject Classification (2000): 37A20, 37A50, 60G10, 60G50 Key words or phrases: Recurrent stationary random walks – Recurrent cocycles     

Uniformly converging random variables for weakly converging laws

 Let {P _n , n ?ℕ} be a sequence of Borel probability measures on a compact and connected metric space X. We show that in case the measures P _n converge weakly to a fully supported limit measure P, there exist uniformly converging random variables X _n , n ?ℕ with these given laws. Connectivity and compactness are necessary conditions for our theorem to hold. We also present a decent generalization. We prove our theorem by means of a comparison of the Prokhorov and the so-called minimal L ^∞ metric. Then we only need to use the Strassen-Dudley theorem and Kellerer's measure extension theorem for decomposable families. Received: 2 November 2000 / Revised version: 5 January 2002/ Published online: 1 July 2002     

Cramér-type conditions and quadratic mean differentiability

Summary Let (Ω,A) be a measurable space, let Θ be an open set inR ^k , and let {P _θ; θ∈Θ} be a family of probability measures defined onA. Let μ be a σ-finite measure onA, and assume thatP _θ≪μ for each θ∈Θ. Let us denote a specified version ofdP _θ /d _μ byf(ω; θ). In many large sample problems in statistics, where a study of the log-likelihood is important, it has been convenient to impose conditions onf(ω; θ) similar to those used by Cramér [2] to establish the consistency and asymptotic normality of maximum likelihood estimates. These are of a purely analytical nature, involving two or three pointwise derivatives of lnf(ω; θ) with respect to θ. Assumptions of this nature do not have any clear probabilistic or statistical interpretation. In [10], LeCam introduced the concept of differentially asymptotically normal (DAN) families of distributions. One of the basic properties of such a family is the form of the asymptotic expansion, in the probability sense, of the log-likelihoods. Roussas [14] and LeCam [11] give conditions under which certain Markov Processes, and sequences of independent identically distributed random variables, respectively, form DAN families of distributions. In both of these papers one of the basic assumptions is the differentiability in quadratic mean of a certain random function. This seems to be a more appealing type of assumption because of its probabilistic nature. In this paper, we shall prove a theorem involving differentiability in quadratic mean of random functions. This is done in Section 2. Then, by confining attention to the special case when the random function is that considered by LeCam and Roussas, we will be able to show that the standard conditions of Cramér type are actually stronger than the conditions of LeCam and Roussas in that they imply the existence of the necessary quadratic mean derivative. The relevant discussion is found in Section 3. This research was supported by the National Science Foundation, Grant GP-20036.     

Une Remarque sur une Formule Sommatoire liée à la Somme des Chiffres

Let g ≥ 2 be an integer, and let s(n) be the sum of the digits of n in basis g. Let f(n) be a complex valued function defined on positive integers, such that ?_{n ￡ x} f(n)=o(x)\sum_{n\le x} f(n)=o(x) . We propose sufficient conditions on the function f to deduce the equality ?_{n ￡ x} f(s(n))=o(x)\sum_{n\le x} f(s(n))=o(x) . Applications are given, for instance, on the equidistribution mod 1 of the sequence (s(n))^α, where α is a positive real number.     

An ℵ1-dense ideal on ℵ2

This paper establishes the consistency of a countably complete, uniform, ℵ₁-dense ideal on ℵ₂. As a corollary, it is consistent that there exists a uniform ultrafilterD on ω₂ such that |ω ₁ ^ω2 D|=ω₁. A general “transfer” result establishes the consistency of countably complete uniform ideal K on ω₂ such thatP(ω₂)/K≅P(ω₁)/ {countable sets}. Partially supported by an NSF grant.     

On a superatomic Boolean algebra which is not generated by a well-founded sublattice

Let b denote the unboundedness number of ω^ω. That is, b is the smallest cardinality of a subset such that for everyg∈ω^ω there isf ∈ F such that {n: g(n) ≤ f(n)}is infinite. A Boolean algebraB is wellgenerated, if it has a well-founded sublatticeL such thatL generatesB. We show that it is consistent with ZFC that , and there is a Boolean algebraB such thatB is not well-generated, andB is superatomic with cardinal sequence 〈ℵ₀, ℵ₁, ℵ₁, 1〉. This result is motivated by the fact that if the cardinal sequence of a Boolean algebraB is 〈ℵ₀, ℵ₀, λ, 1〉, andB is not well-generated, then λ≥b.     

A superatomic Boolean algebra with few automorphisms

Assuming GCH, we prove that for every successor cardinal μ > ω₁, there is a superatomic Boolean algebra B such that |B| = 2^μ and |Aut B| = μ. Under ◊_ω1, the same holds for μ = ω₁. This answers Monk's Question 80 in [Mo]. Received: 1 January 1998 / Revised version: 18 May 1999 / Published online: 21 December 2000     

On Some Properties of Randomly Indexed Sequences of Random Elements

Let be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N _n ,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F _k ,k≥1} be a family of probability laws and let X be some random element defined on and taking values in (S,ρ). In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X _n,k ,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that , and moreover as  n→∞. Furthermore, we consider the speed of convergence to X as n→∞.      

On large deviations and density functions

Suppose thatX ₁,X ₂, ... is a sequence of absolutely continuous or integer valued random variables with corresponding probability density functionsf _n (x). Let {φ _n } _n=1 ^∞ be a sequence of real numbers, then necessary and sufficient conditions are given forn ⁻¹ logf _n (φ _n )-n ⁻¹ log P (X _n >φ _n )=0(1) asn→∞.     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

Discrepancy of Certain Kronecker Sequences Concerning Transcendental Numbers

Let ω1,..., ωs be a set of real transcendental numbers satisfying a certain Diophantine inequality. The upper bound for the discrepancy of the Kronecker sequence （{nω1},..., {nωs}）（1 ≤ n ≤ N） is given. In particular, some low-discrepancy sequences are constructed.