On the ramsey numbers N(3,3,…3;2)

The main results of this paper are N(3,3,3,3;2) > 50 andf(k+1)≥3 f(k)+f(k?2), where $\text{f(k) = N}\text{3,3,…;2)}\text{k}\text{times}\text{?1 for k ≥ 3}$.     

k-Blocks and ultrablocks in graphs

A k-block is a maximal k-vertex-connected subgraph, and a k-block which does not contain a (k + 1)-block is an ultrablock. It is shown that the maximum total number of k-blocks for all k ≥ 1 in any p-vertex graph is [$\text{(2p ? 1)}\text{3}$], and the maximum number of ultrablocks in any p-vertex graph having maximum subgraph connectivity κ? is $\text{[}\text{(p ?}\text{κ}\text{?}\text{+ 1)}\text{2}\text{]}$. In contrast to the linear growth rate of the maximum number of k-blocks in a p-vertex graph, it is shown that the maximum number of critical k-vertex-connected subgraphs of an ultrablock of connectivity k can grow exponentially with p.     

Polynomial sums over automorphs of a positive definite binary quadratic form

Let P(X) be a homogeneous polynomial in X = (x, y), Q(X) a positive definite integral binary quadratic form, and G the group of integral automorphs of Q(X). Let A(m) = {N ∈ $\text{Z}$ × $\text{Z}$ : Q(N) = m}. It is shown that if Σ_N∈A(m)P(N) = 0 for each m = 1, 2, 3,… then Σ_U∈GP(UX) ≡ 0.     

Primary projections on L2 of a nilmanifold

Let N denote a connected, simply connected nilpotent Lie group with discrete cocompact subgroup Γ. Let U denote the quasi-regular representation on N on $\text{L}{}^2\text{(}\text{N}\text{Γ}\text{)}$. $\text{L}{}^2\text{(}\text{N}\text{Γ}\text{)}$ can be written as a direct sum of primary subspaces with respect to U. A realization for the projections of $\text{L}{}^2\text{(}\text{N}\text{Γ}\text{)}$) onto these primary summands is given in this paper.     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

A representation for self-similar processes

A self-similar process Z(t) has stationary increments and is invariant in law under the transformation Z(i)→c^-HZ(ct), c?0. The choice $\text{1}\text{2}\text{<H<1}$ ensures that the increments of Z(t) exhibit a long range positive correlation.Mandelbrot and Van Ness investigated the case where Z(t) is Gaussian and represented that Gaussian self-similar process as a fractional integral of Brownian motion. They called it fractional Brownian motion. This paper provides a time-indexed representation for a sequence of self- similar processes $\text{Z}\text{?}{}_{\mathrm{m}}\text{(t)}$, m=1,2,…, whose finite-dimensional moments have been specified in an earlier paper. $\text{Z}\text{?}{}_1\text{(t)}$ is the Gaussian fractional Brownian motion but the process$\text{Z}\text{?}{}_{\mathrm{m}}\text{(t)}$ are not Gaussian when m?2.Self-similar processes are being studied in physics, in the context of the renormalization group theory for critical phenomena, and in hydrology where they account for the so-called “Hurst effect”.     

Construction of matroidal families by partly closed sets

A matroidal family of graphs is a set $\text{M}$≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of $\text{M}$ are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n?0, ?2n<r?1, n, $\text{r∈}\text{Z}$, the set $\text{M}\text{(n, r)={G∣G}$ is a graph with β(G)=nα(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of $\text{M}\text{(n, r)}$, s?r, we are able to give sufficient and necessary conditions for a subset $\text{P}\text{(n, r)}$ of $\text{M}\text{(n, r)}$ to yield a matroidal family of graphs when joined with the set $\text{I}\text{(n, s)}$ of all graphs $\text{G∈}\text{M}\text{(n, s)}$ which satisfy: If $\text{H∈}\text{P}\text{(n, r)}$, then H?G. In particular, it is shown that $\text{M}\text{(n, r)}$ is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, $\text{r∈}\text{Z}$, the set of bipartite elements of $\text{M}\text{(n, r)}$ can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1).     

Strong approximation theorems for density dependent Markov chains

A variety of continuous parameter Markov chains arising in applied probability (e.g. epidemic and chemical reaction models) can be obtained as solutions of equations of the form

$\text{X}{}_{\mathrm{N}}\text{(t)=x}{}_0\text{+∑}\text{1}\text{N}\text{lY}{}_1\text{N ∫}{}^{\mathrm{t}}{}_0\text{f}{}_1\text{(X}{}_{\mathrm{N}}\text{(s))ds}$

where $\text{l∈}\text{Z}{}^{\mathrm{t}}$, the Y₁ are independent Poisson processes, and N is a parameter with a natural interpretation (e.g. total population size or volume of a reacting solution).The corresponding deterministic model, satisfies

$\text{X(t)=x}{}_0\text{+ ∫}{}^{\mathrm{t}}{}_0\text{∑ lf}{}_1\text{(X(s))ds}$

Under very general conditions lim_N→∞X_N(t)=X(t) a.s. The process X_N(t) is compared to the diffusion processes given by

$\text{Z}{}_{\mathrm{N}}\text{(t)=x}{}_0\text{+∑}\text{1}\text{N}\text{lB}{}_1\text{N∫}{}^{\mathrm{t}}{}_0\text{ft(Z}{}_{\mathrm{N}}\text{(s))ds}$

and

$\text{V(t)=∑ l∫}{}^{\mathrm{t}}{}_0\text{f}{}_1\text{(X(s))}\text{d}\text{W}\text{?}{}_1\text{+∫}{}^{\mathrm{t}}{}_0\text{?F(X(s))·V(s)}\text{ds.}$

Under conditions satisfied by most of the applied probability models, it is shown that X_N,Z_N and V can be constructed on the same sample space in such a way that

$\text{X}{}_{\mathrm{N}}\text{(t)=Z}{}_{\mathrm{N}}\text{(t)+O}\text{logN}\text{N}$

and

$\text{N}\text{(X}{}_{\mathrm{N}}\text{(t)?X(t))=V(t)+O}\text{log N}\text{N}$

     

Polynomial indexing of integer lattice-points I. General concepts and quadratic polynomials

Denoting the nonnegative integers by N and the signed integers by Z, we let S be a subset of Z^m for m = 1, 2,… and f be a mapping from S into N. We call f a storing function on S if it is injective into N, and a packing function on S if it is bijective onto N. Motivation for these concepts includes extendible storage schemes for multidimensional arrays, pairing functions from recursive function theory, and, historically earliest, diagonal enumeration of Cartesian products. Indeed, Cantor's 1878 denumerability proof for the product N² exhibits the equivalent packing functions $\text{f}{}_{\mathrm{<mtext>Cantor</mtext>}}\text{(x, y) = {}\text{either}\text{x}\text{or}\text{y} +}\text{(x + y)(x + y + 1)}\text{2}$ on the domain N², and a 1923 Fueter-Pólya result, in our terminology, shows f_Cantor the only quadratic packing function on N². This paper extends the preceding result. For any real-valued function f on S we define a density $\text{S ÷ f =}\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{1}\text{n}\text{)\#{S ? f}{}^{\mathrm{?1}}\text{([?n, +n])}}$, and for any packing function f on S we observe the fact S ÷ f = 1. Using properties of this density, and invoking Davenport's lemma from geometric number theory, we find all polynomial storing functions with unit density on N, and exclude any polynomials with these properties on Z, then find all quadratic storing functions with unit density on N², and exclude any quadratics with these properties on Z × N, Z². The admissible quadratics on N² are all nonnegative translates of f_Cantor. An immediate sequel to this paper excludes some higher-degree polynomials on subsets of Z².     

The construction of SL(2, 3)-polynomials

Octic polynomials over $\text{Z}$ with Galois group SL(2, 3) are constructed. This is done via suited quartic totally real polynomials with group A₄ over $\text{Q}$. A table of the cycle patterns of the imprimitive transitive permutation groups of degree 8 is included.     

Extinction probability for a critical general branching process

A general branching process begins with a single individual born at time t=0. At random ages during its random lifespan L it gives birth to offspring, N(t) being the number born in the age interval [0,t]. Each offspring behaves as a probabilistically independent copy of the initial individual. Let Z(t) be the population at time t, and let N=N(∞). Theorem: If a general branching process is critical, i. e E{N}=1, and if $\text{σ}{}^2\text{=E {N(N?1)}<∞, 0<a≡}\text{∫}\text{0}\text{∞}\text{tdE{N(t)}}$,and as t → ∞ both $\text{t}{}^2\text{(1?}\text{E}\text{{N(t)})→0}$ and $\text{t}{}^2\text{P}\text{[L>t]→0}$, then $\text{tP[Z(t)>0]→}\text{2a}\text{σ}{}^2$ as t→∞.     

Random Euclidean embeddings in spaces of bounded volume ratio

Let $\text{(}\text{R}{}^{\mathrm{N}}\text{,6·6)}$ be the space $\text{R}{}^{\mathrm{N}}$ equipped with a norm 6·6 whose unit ball has a bounded volume ratio with respect to the Euclidean unit ball. Let Γ be any random N×n matrix with N>n, whose entries are independent random variables satisfying some moment assumptions. We show that with high probability Γ is a good isomorphism from the n-dimensional Euclidean space $\text{(}\text{R}{}^{\mathrm{n}}\text{,|·|)}$ onto its image in $\text{(}\text{R}{}^{\mathrm{N}}\text{,6·6)}$: there exist α,β>0 such that for all $\text{x∈}\text{R}{}^{\mathrm{n}}$, $\text{α}\text{N}\text{|x|?6Γx6?β}\text{N}\text{|x|}$. This solves a conjecture of Schechtman on random embeddings of ?₂ⁿ into ?₁^N. To cite this article: A. Litvak et al., C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

On the zeros of exponential polynomials

Suppose r = (r₁, …, r_M), r_j ? 0, γ_kj ? 0 integers, k = 1, 2, …, N, j = 1, 2, …, M, γ_k · r = ∑_jγ_kjr_j. The purpose of this paper is to study the behavior of the zeros of the function h(λ, a, r) = 1 + ∑_{j = 1}^Na_je^{?λγ_j · r}, where each a_j is a nonzero real number. More specifically, if $\text{Z}\text{?}\text{(a, r) =}\text{closure}\text{{}\text{Re}\text{λ: h(λ, a, r) = 0}}$, we study the dependence of $\text{Z}\text{?}\text{(a, r)}\text{on}\text{a, r}$. This set is continuous in a but generally not in r. However, it is continuous in r if the components of r are rationally independent. Specific criterion to determine when $\text{0 ?}\text{Z}\text{?}\text{(a, r)}$ are given. Several examples illustrate the complicated nature of $\text{Z}\text{?}\text{(a, r)}$. The results have immediate implication to the theory of stability for difference equations x(t) ? ∑_{k = 1}^MA_kx(t ? r_k) = 0, where x is an n-vector, since the characteristic equation has the form given by h(λ, a, r). The results give information about the preservation of stability with respect to variations in the delays. The results also are fundamental for a discussion of the dependence of solutions of neutral differential difference equations on the delays. These implications will appear elsewhere.     

Weyl's law for the cuspidal spectrum of SLn

Let Γ be a principal congruence subgroup of $\text{SL}{}_{\mathrm{n}}\text{(}\text{Z}\text{)}$ and let σ be an irreducible unitary representation of SO(n). Let N_cus^Γ(λ,σ) be the counting function of the eigenvalues of the Casimir operator acting in the space of cusp forms for Γ which transform under SO(n) according to σ. In this Note we prove that the counting function N_cus^Γ(λ,σ) satisfies Weyl's law. In particular, this implies that there exist infinitely many cusp forms for the full modular group $\text{SL}{}_{\mathrm{n}}\text{(}\text{Z}\text{)}$. To cite this article: W. Müller, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions

A function f(x) defined on $\text{X}$ = $\text{X}$₁ × $\text{X}$₂ × … × $\text{X}$_n where each $\text{X}$_i is totally ordered satisfying f(x ∨ y) f(x ∧ y) ≥ f(x) f(y), where the lattice operations ∨ and ∧ refer to the usual ordering on $\text{X}$, is said to be multivariate totally positive of order 2 (MTP₂). A random vector Z = (Z₁, Z₂,…, Z_n) of n-real components is MTP₂ if its density is MTP₂. Classes of examples include independent random variables, absolute value multinormal whose covariance matrix Σ satisfies ?DΣ^?1D with nonnegative off-diagonal elements for some diagonal matrix D, characteristic roots of random Wishart matrices, multivariate logistic, gamma and F distributions, and others. Composition and marginal operations preserve the MTP₂ properties. The MTP₂ property facilitate the characterization of bounds for confidence sets, the calculation of coverage probabilities, securing estimates of multivariate ranking, in establishing a hierarchy of correlation inequalities, and in studying monotone Markov processes. Extensions on the theory of MTP₂ kernels are presented and amplified by a wide variety of applications.     

Hecke operators and an identity for the dedekind sums

If h, k ∈ Z, k > 0, the Dedekind sum is given by

$\text{s(h,k) =}\text{∑}\text{μ=1}\text{k}\text{μ}\text{k}\text{hμ}\text{k}$

, with

$\text{((x)) = x ? [x] ?}\text{1}\text{2}\text{, x?Z}$

,

$\text{=0 , x∈Z}$

. The Hecke operators T_n for the full modular group SL(2, Z) are applied to log η(τ) to derive the identities (n ∈ Z⁺)

$\text{∑ ∑ s(ah+bk,dk) = σ(n)s(h,k)}$

,

$\text{ad=n b(}\text{mod}\text{d)}$

$\text{d>0}$

where (h, k) = 1, k > 0 and σ(n) is the sum of the positive divisors of n. Petersson had earlier proved (1) under the additional assumption k ≡ 0, h ≡ 1 (mod n). Dedekind himself proved (1) when n is prime.     

Character formulas and spectra of compact nilmanifolds

The authors give a new method for calculating the spectrum and multiplicities of the irreducible unitary representations appearing in the quasi-regular representation U: N × L²(ΓβN) → L²(ΓβN) on a compact nilmanifold ΓβN. They proceed by decomposing the trace of U into traces of irreducible representations. The basic calculations in the paper deal with lattice subgroups (Λ = log Γ an additive lattice in the Lie algebra $\text{N}$), essentially using the Poisson summation formula. Let Ad′ be the contragredient adjoint action of N on $\text{N}$¹. If ?₀ ? $\text{N}$¹, the multiplicity of π(?₀) in U is zero unless the Ad′(N) orbit of ?₀ meets $\text{Λ}{}^{\mathrm{\perp }}\text{= {h ? N}{}^1\text{: <h, Λ> ?}\text{Z}\text{}}$. If ?₀ ? Λ^⊥, then the multiplicity is a sum over representatives of certain Ad′(Γ)-orbits in,

$\text{m(π(?}{}_0\text{),U) =}\text{∑}\text{Ad′(N)?}{}_0\text{∩Λ}{}^{\mathrm{\perp }}\text{Ad′(Γ)}\text{k(?)}$

.The constants $\text{k(?)}$ are given both algebraic and geometric interpretations that lead to simple and effective calculations. Similar formulas hold if Γ is not a lattice subgroup.     

Sur la structure galoisienne du groupe des unités d'un corps abélien réel de type (p, p)

Let p be a rational prime. We classify those $\text{Z}$[($\text{Z}$/p$\text{Z}$)²]-modules arising as submodules of the units (mod. torsion) of a real abelian field K with Galois group ($\text{Z}$/p$\text{Z}$)², up to isomorphism and up to genus. Explicit results are given when p is 2 or 3. We apply our classification to discuss the existence of a Minkowski unit in K for arbitrary p.