Graphical properties related to minimal imperfection

Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let C_n^k denote the graph whose vertices can be enumerated as υ₁,…,υ_n in such a way that υ₁ and υ₁ are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to C_αω+1^ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ α and ω(G) ≡ ω.     

Pointwise properties of convergence in probability

If a sequence of random variables X_n converges to X in probability we know little about the pointwise behavior X_n(ω). In this note we show that if X_n converges to X quickly enough (for example, like n^?α for α > 0) then, for almost all ω, X_n(ω) converges to X(ω) outside a set of density zero.     

Counting subsets of the random partition and the ‘Brownian Bridge’ process

Let Ω_m be the set of partitions, ω, of a finite m-element set; induce a uniform probability distribution on Ω_m, and define X_ms(ω) as the number of s-element subsets in ω. We alow the existence of an integer-valued function n=n^(m)(t), t?[0, 1], and centering constants b_ms, 0?s? m, such that

$\text{Z}{}^{\mathrm{(m)}}\text{(t)=}\text{∑}\text{s=0}\text{n(m)(t)}\text{(X}{}_{\mathrm{ms}}\text{?b}{}_{\mathrm{ms}}\text{)}\text{√}\text{∑}\text{s=0}\text{m}\text{b}{}_{\mathrm{ms}}$

converges to the ‘Brownian Bridge’ process in terms of its finite-dimensional distributions.     

Asymptotic joint distribution of the largest roots of several multivariate F matrices I. Quasi-independent case

An asymptotic expansion of the joint distribution of k largest characteristic roots C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is given, where S'_is and S₀ are independent Wishart matrices with common covariance matrix Σ. The modified second-approximation procedure to the upper percentage points of the maximum of C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is also considered. The evaluation of the expansion is based on the idea for studentization due to Welch and James with the use of differential operators and of the perturbation procedure.     

The real interpolation method on couples of intersections

Suppose that (X ₀, X ₁) is a Banach couple, X ₀ ∩ X ₁ is dense in X ₀ and X ₁, (X₀,X₁)_θq (0 < θ < 1, 1 ≤ q < ∞) are the spaces of the real interpolation method, ψ ∈ (X ₀ ∩ X ₁), ψ ≠ 0, is a linear functional, N = Ker ψ, and N _i stands for N with the norm inherited from X _i (i = 0, 1). The following theorem is proved: the norms of the spaces (N₀,N₁)_θ,q and (X₀,X₁)_θ,q are equivalent on N if and only if θ ? (0, α) ∪ (β_∞, α₀ ∪ (β₀, α_∞) ∪ (β, 1), where α, β, α₀, β₀, α_∞, and β _∞ are the dilation indices of the function k(t)=K(t,ψ;X ₀ ^* ,X ₁ ^* ).     

Kähler structures on complex torus

Consider the complex torus T _C under the natural action of the compact real torus T. In this paper, we study T-invariant Kähler structures ω on T_C. For each ω, we consider the corresponding line bundleL on T _C. Namely, the Chern class ofL is [ω], and L is equipped with a connection ? whose curvature is ω. We construct a canonical T-invariant L ²-structure on the sections ofL,and let H _ω be the square-integrable holomorphic sections ofL.Then the Hilbert space H _ω is a unitary T-representation, and we study the multiplicity of the (l-dimensional) irreducible unitary T-representations in H_ω. We shall see that the multiplicity is controlled by the image of the moment map corresponding to the T-action preserving ω.     

Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.     

Remote points in large products

A point p ∈ βX\X is a remote point of X if p? cl_βXD for any nowhere dense D ? X. Van Douwen, and independently Chae and Smith, have shown that each non-pseudocompact space of countable π-weight has a remote point. Van Mill showed that many spaces of π-weight ω₁, such as ω×2^ω₁ also have remote points.We show that arbitrarily large products of spaces with countable π-weight which are not pseudocompact have remote points. In particular, ω×2^? for any infinite cardinal ?.     

Monochromatic Vs multicolored paths

Letl andk be positive integers, and letX={0,1,...,l ^k?1}. Is it true that for every coloring δ:X×X→{0,1,...} there either exist elementsx ₀<x ₁<...<x _l ofX with δ(x ₀,x ₁)=δ(x ₁,x ₂)=...=δ(x _l?1,x _l), or else there exist elementsy ₀<y ₁<...<y _k ofX with δ(y _i?1,y _i) ∈ δ(y _j?1,y _j) for all 1<-i<j≤k? We prove here that this is the case if eitherl≤2, ork≤4, orl≥(3k)^2k . The general question remains open.     

Uniform separation of points and measures and representation by sums of algebras

LetX andY _i, 1 ≦i ≦k, be compact metric spaces, and letρ _i:X →Y _i be continuous functions. The familyF={ρ _i} _i ^1/k is said to be ameasure separating family if there exists someλ > 0 such that for every measureμ inC(X)*, ‖μ ^o ρ _i ^?1 ‖ ≧λ ‖μ ‖ holds for some 1 ≦i ≦k.F is auniformly (point) separating family if the above holds for the purely atomic measures inC(X)*. It is known that fork ≦ 2 the two concepts are equivalent. In this note we present examples which show that fork ≧ 3 measure separation is a stronger property than uniform separation of points, and characterize those uniformly separating families which separate measures. These properties and problems are closely related to the following ones: letA ₁,A ₂, ...,A _k be closed subalgebras ofC(X); when isA ₁ +A ₂ + ... +A _k equal to or dense inC(X)?     

Countable contraction mappings in metric spaces: invariant sets and measure

We consider a complete metric space (X, d) and a countable number of contraction mappings on X, F = {F _i : i ∈ ?}. We show the existence of a smallest invariant set (with respect to inclusion) for F. If the maps F _i are of the form F _i (x) = r _i x + b _i on X = ? ^d , we prove a converse of the classic result on contraction mappings, more precisely, there exists a unique bounded invariant set if and only if r = sup _i r _i is strictly smaller than 1. Further, if ρ = {ρ _k } _k∈? is a probability sequence, we show that if there exists an invariant measure for the system (F, ρ), then its support must be precisely this smallest invariant set. If in addition there exists any bounded invariant set, this invariant measure is unique, even though there may be more than one invariant set.     

On three-designs of small order

For positive integers t?k?v and λ we define a t-design, denoted B_i[k,λ;v], to be a pair (X,B) where X is a set of points and B is a family, (B_i:i?I), of subsets of X, called blocks, which satisfy the following conditions: (i) |X|=v, the order of the design, (ii) |B_i|=k for each i?I, and (iii) every t-subset of X is contained in precisely λ blocks. The purpose of this paper is to investigate the existence of 3-designs with 3?k?v?32 and λ>0.Wilson has shown that there exists a constant N(t, k, v) such that designs B_t[k,λ;v] exist provided λ>N(t,k,v) and λ satisfies the trivial necessary conditions. We show that N(3,k,v)=0 for most of the cases under consideration and we give a numerical upper bound on N(3, k, v) for all 3?k?v?32. We give explicit constructions for all the designs needed.     

Distribution exacte du score local,cas markovien

Given a sequence $\text{X}\text{=(X}{}_{\mathrm{k}}\text{)}{}_{\mathrm{k?1}}$ of random variables taking values in {?v,…,0,…,+u}, let's define the local score of the sequence by H_n=max_1?i?j?n(∑_k=i^jX_k). The local score is used to analyze biological sequences pointing out regions of the sequences with interesting biological properties. In order to separate randomly events from really interesting segments, we establish here the distribution of the local score of H_n when the sequence $\text{X}$ is a Markov chain of order 1. To cite this article: S. Mercier, C. Hassenforder, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

The kernel of the neumann operator for a strictly diffractive analytic problem

We consider p a partial differential operator of order 2 and Rⁿ= ω⁺ ∪ ?ω ∪ ω^? a partition of Rⁿ , such that (p, ω⁺) admits a strictly diffractive point (in the sense of Friedlander and Melrose). We compute the trace and the trace of the normal derivative on ?ω of the solution u of the diffraction problem pu= 0 in ω⁺ u satisfying a mixed boundary condition on ?ω, ?ω analytic. That is done using the construction by Lebeau of a Gevrey 3 parametrix in the neighborhood of the strictly diffractive point.

This result generalizes, for a mixed boundary condition, the Gevrey 3 propogation result of Lebeau. We use this result to compute the leading term in the shadow region of the diffracted wave outside a strictly convex analytical obstacle with a mixed boundary condition and a given incoming wave.     

A Lindeberg-type theorem

Let (_kQ_ij)_k be a sequence of semi-Markov matrices arising from the nonhomogeneous J?X process of Markov renewal theory. A generalization of the sufficiency half of the Lindeberg central limit theorem is proved for sums S_n=∑ⁿ_i=1X_i suitably normed, where the X_i are the holding times of the J?X process. The approach used involves an adaption of the wellknown Trotter proof of the central limit theorem. Some familiar results are also obtained, by using this “convolution operator” approach.     

Familles de graphes expanseurs et paires de HeckeFamilies of expanding graphs and Hecke pairs

Let H be a subgroup of a group G. Suppose that (G,H) is a Hecke pair and that H is finitely generated by a finite symmetric set of size k. Then G/H can be seen as a graph (possibly with loops and multiple edges) whose connected components form a family (X_i)_i∈I of finite k-regular graphs. In this Note, we analyse when the size of these graphs is bounded or tends to infinity and we present criteria for (X_i)_i∈I to be a family of expanding graphs as well as some examples. To cite this article: M.B. Bekka et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 463–468.     

Quotient algebras of Stanley-Reisner rings and local cohomology

We study certain subcomplexes Δ′ of an arbitrary simplicial complex Δ such that H_mⁱ(k[Δ])-H_mⁱ(k[Δ′]) for any 0i<dim(k[Δ′]). Here, H_mⁱ(k[Δ]) is the ith local cohomology module of the Stanley-Reisner ring k[Δ] of Δ over a field k. Our technique is an elegant approach to one of the most generalized versions of the rank selection theorems of J. Munkres (1984, Michigan Math. J.31, 113–128, Theorem 6.4) and R. Stanley (1979, Trans. Amer. Math. Soc.249, 139–157, Theorem 4.3).     

Remarks on Projective Algebraic Fiber Spaces Over Curves

Let f:X → C be a fibration over curve C with general fiber F. Some numerical characteristics of h ⁱ ( _X ) in terms of h ⁱ ( _F ), the genus g(C) and the degree of direct image sheaves R ⁱ f _? (ω _X/C ) are given. If f is the derived fibration induced by m-canonical map, further numerical characterizations of m-plurigenus of F are given.     

A unique exchange property for bases

We define the concept of unique exchange on a sequence (X₁,…, X_m) of bases of a matroid M as an exchange of x ? X_i for y ? X_j such that y is the unique element of X_j which may be exchanged for x so that (X_i ? {x}) ∪ {y} and (X_j ? {y}) ∪ {x} are both bases. Two sequences X and Y are compatible if they are on the same multiset. Let UE(1) [UE(2)] denote the class of matroids such that every pair of compatible basis sequences X and Y are related by a sequence of unique exchanges [unique exchanges and permutations in the order of the bases]. We similarly define UE(3) by allowing unique subset exchanges. Then UE(1),UE(2), and UE(3) are hereditary classes (closed under minors) and are self-dual (closed under orthogonality). UE(1) equals the class of series-parallel networks, and UE(2) and UE(3) are contained in the class of binary matroids. We conjecture that UE(2) contains the class of unimodular matroids, and prove a related partial result for graphic matroids. We also study related classes of matroids satisfying transitive exchange, in order to gain information about excluded minors of UE(2) and UE(3). A number of unsolved problems are mentioned.     

The expected eigenvalue distribution of a large regular graph

Let K₁, K₂,... be a sequence of regular graphs with degree v?2 such that n(X_i)→∞ and ck(X_i)/n(X_i)→0 as i∞ for each k?3, where n(X_i) is the order of X_i, and c_k(X_i) is the number of k- cycles in X₁. We determine the limiting probability density f(x) for the eigenvalues of X>_i as i→∞. It turns out that

$\text{f(x)=}\text{v}\text{4(v?1)?v}{}^2\text{2π(v}{}^2\text{?x}{}^2\text{)}{}_0$

for ?x??2$\text{v-1}$, otherwise It is further shown that f(x) is the expected eigenvalue distribution for every large randomly chosen labeled regular graph with degree v.