Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

Inclusion-exclusion inequalities

Ifμ is a positive measure, andA ₂, ...,A _n are measurable sets, the sequencesS ₀, ...,S _n andP _[0], ...,P _[n] are related by the inclusion-exclusion equalities. Inequalities among theS _i are based on the obviousP _[k]≧0. Letting =the average average measure of the intersection ofk of the setsA _i , it is shown that (−1) ^k Δ ^k M _i ≧0 fori+k≦n. The casek=1 yields Fréchet’s inequalities, andk=2 yields Gumbel’s and K. L. Chung’s inequalities. Generalizations are given involvingk-th order divided differences. Using convexity arguments, it is shown that forS ₀=1, whenS ₁≧N−1, and for 1≦k<N≦n andv=0, 1, .... Asymptotic results asn → ∞ are obtained. In particular it is shown that for fixedN, for all sequencesM ₀, ...,M _n of sufficiently large length if and only if for 0<t<1.     

A characteristic property of spheres

Summary We prove: Let S be a closed n-dimensional surface in an(n+1)-space of constant curvature (n ≥ 2); k₁ ≥ ... ≥ k_n denote its principle curvatures. Let φ(ξ₁, ..., ξ_n) be such that . Then if φ(k₁, ..., k_n)=const on S and S is subject to some additional general conditions (those(II ₀) or(II) n^o 1), S is a sphere. To Enrico Bompiani on his scientific Jubilee     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

The existence of non-degenerate functions on a compact differentiablem-manifoldM

Summary Let M be a compact differentiable m-manifold of class C^m in E_n, n=2m+1. Let x=(x₁, ..., x_n) represent a point in E_n. The union of the direction c on the direction sphere S_n−1 in E_n such that the scalar product c · x defines a non-degenerate fonction on M is an open subset of S_n−1 whose complement θ has a Lebesgue measure zero on S_n−1. When M is non-compact θ can be everywhere dense on S_n−1, but still has Lebesgue measure zero. To Giovanni Sansone on his 70^th birth day.     

Packing nearly-disjoint sets

De Bruijn and Erdős proved that ifA ₁, ...,A _k are distinct subsets of a set of cardinalityn, and |A _i ∩A _j |≦1 for 1≦i<j ≦k, andk>n, then some two ofA ₁, ...,A _k have empty intersection. We prove a strengthening, that at leastk /n ofA ₁, ...,A _k are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary. Partially supported by N. S. F. grant No. MCS—8103440     

On the weak non-defectivity of veronese embeddings of projective spaces

Fix integers n, x, k such that n≥3, k>0, x≥4, (n, x)≠(3, 4) and k(n+1)<( _n ^n+x ). Here we prove that the order x Veronese embedding ofP ⁿ is not weakly (k−1)-defective, i.e. for a general S⊃P ⁿ such that #(S) = k+1 the projective space | I _2S (x)| of all degree t hypersurfaces ofP ⁿ singular at each point of S has dimension ( _n ^/n+x )−1− k(n+1) (proved by Alexander and Hirschowitz) and a general F∈| I _2S (x)| has an ordinary double point at each P∈ S and Sing (F)=S. The author was partially supported by MIUR and GNSAGA of INdAM (Italy).     

Extreme value limit laws in the nonidentically distributed case

LetX ₁, ...,X _n be independent random variables, letF _i be the distribution function ofX _i (1≦i≦n) and letX _1n ≦... ≦X _nn be the corresponding order statistics. We consider the statisticsX _kn, wherek=k(n),k/n → 1 andn−k → ∞. Under some additional restrictions concerning the behaviour of the sequences {a _n>0,b _n,k(n),F _n} we characterize the class of all distribution functionsH such that Prob{(X _kn −b _n )/a _n <x)}→H. Dedicated to the Memory of N. V. Smirnov (1900–1966)     

The Grothendieck ring of varieties and piecewise isomorphisms

Let K ₀(Var _k ) be the Grothendieck ring of algebraic varieties over a field k. Let X, Y be two algebraic varieties over k which are piecewise isomorphic (i.e. X and Y admit finite partitions X ₁, ..., X _n , Y ₁, ..., Y _n into locally closed subvarieties such that X _i is isomorphic to Y _i for all i ≤ n), then [X] = [Y] in K ₀(Var _k ). Larsen and Lunts ask whether the converse is true. For characteristic zero and algebraically closed field k, we answer positively this question when dim X ≤ 1 or X is a smooth connected projective surface or if X contains only finitely many rational curves.     

Large-deviation probability and the local dimension of sets

Let X ₁ , X ₂ , ..., X_n be n independent identically distributed real random variables and S_n = Σ _n=1 ⁿ X_i. We obtain precise asymptotics forP (S_n ∈ nA) for rather arbitrary Borel sets A₁ in terms of the density of the dominating points in A. Our result extends classical theorems in the field of large deviations for independent samples. We also obtain asymptotics forP (S_n ∈ γ_nA), with γ_n/n → ∞. Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part I.     

Almost sure central limit theorems for random functions

Let {Xn,-∞< n <∞} be a sequence of independent identically distributed random variables with EX1 = 0, EX12 = 1 and let Sn =∑k=1∞Xk, and Tn = Tn(X1,…,Xn) be a random function such that Tn = ASn Rn, where supn E|Rn| <∞and Rn = o(n~(1/2)) a.s., or Rn = O(n1/2-2γ) a.s., 0 <γ< 1/8. In this paper, we prove the almost sure central limit theorem (ASCLT) and the function-typed almost sure central limit theorem (FASCLT) for the random function Tn. As a consequence, it can be shown that ASCLT and FASCLT also hold for U-statistics, Von-Mises statistics, linear processes, moving average processes, error variance estimates in linear models, power sums, product-limit estimators of a continuous distribution, product-limit estimators of a quantile function, etc.     

Cyclic homology and the Macdonald conjectures

Summary LetA+(k) denote the ring [t]/t ^k+1 and letG be a reductive complex Lie algebra with exponentsm ₁, ...,m n. This paper concerns the Lie algebra cohomology ofGA ₊(k) considered as a bigraded algebra (here one of the gradings is homological degree and the other, which we callweight, is inherited from the obvious grading ofGA ₊(k)). We conjecture that this Lie algebra cohomology is an exterior algebra withk+1 generators of homological degree 2m _s +1 fors=1,2, ...,n. Of thesek+1 generators of degree 2m _s +1, one has weight 0 and the others have weights (k+1)m _s +t fort=1,2, ...,k.It is shown that this conjecture about the Lie algebra cohomology of A ₊(k) implies the Macdonald root system conjectures. Next we consider the case thatG is a classical Lie algebra with root systemA _n ,B _n ,C _n , orD _n. It is shown that our conjecture holds in the limit onn asn approaches infinity which amounts to the computation of the cyclic and dihedral cohomologies ofA+(k). Lastly we discuss the relevance of this limiting case to the case of finiten in this situation.Partially supported by NSF grant number MCS-8401718 and a Bantrell Fellowship     

Maximum of a conformal,invariant in the problem of nonoverlapping domains

The paper is devoted to the well-known circle of problems on the maximum of the products of powers of conformal radii of nonoverlapping domains. Let a₁, ..., a_n be distinct points of and let D₁, ..., D_n be a system of simply connected domains in, pairwise disjoint and such that a_kD_k, k=1, ..., n. By R(D_ka_k) we denote the conformal radius of the domain D_k relative to the point a_k. One considers the problem on the maximum of the product in the family of all indicated systems of domains, under the condition that a₁, ..., a_n runs over all systems of distinct points in (n4) and one finds the geometric characteristic of the extremal configurations of this problem in terms of the associated quadratic differential.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 112, pp. 172–183, 1981.     

The superstar packing problem

Hell and Kirkpatrick proved that in an undirected graph, a maximum size packing by a set of non-singleton stars can be found in polynomial time if this star-set is of the form {S ₁, S ₂, ..., S _k } for some k∈ℤ₊ (S _i is the star with i leaves), and it is NP-hard otherwise. This may raise the question whether it is possible to enlarge a set of stars not of the form {S ₁, S ₂, ..., S _k } by other non-star graphs to get a polynomially solvable graph packing problem. This paper shows such families of depth 2 trees. We show two approaches to this problem, a polynomial alternating forest algorithm, which implies a Berge-Tutte type min-max theorem, and a reduction to the degree constrained subgraph problem of Lovász. Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No. 504438.     

Long and short paths in uniform random recursive dags

In a uniform random recursive k-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S _n is the shortest path distance from node n to the root, then we determine the constant σ such that S _n /log n→σ in probability as n→∞. We also show that max _1≤i≤n S _i /log n→σ in probability.     

Generalized derivations with Engel condition on multilinear polynomials

Let R be a prime ring with extended centroid C, δ a nonzero generalized derivation of R, f(x ₁, ..., x _n ) a nonzero multilinear polynomial over C, I a nonzero right ideal of R and k ≥ a fixed integer. If [δ(f(r ₁, ..., r _n )), f(r ₁, ..., r _n )] _k = 0, for all r ₁, ..., r _n ∈ I, then either δ(x) = ax, with (a-γ)I = 0 and a suitable γ ∈ C or there exists an idempotent element e ∈ soc(RC) such that IC = eRC and one of the following holds (1) if char(R) = 0 then f(x ₁, ..., x _n ) is central valued in eRCe (2) if char(R) = p > 0 then is central valued in eRCe, for a suitable s ≥ 0, unless when char(R) = 2 and eRCe satisfies the standard identity s ₄ (3) δ(x) = ax−xb, where (a+b+α)e = 0, for α ∈ C, and f(x ₁, ..., x _n )² is central valued in eRCe.     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

Convergence of double Fourier series

Summary Let a2π-periodic function f(x, y) be continuous in some neighbourhood of the point (x, y) except possibly along finitely many lines l ₁ , l ₂ , ..., l_k terminating at (x, y). The problem of convergence of the Fourier series of f(x, y) at the point (x, y) is examined in some detail. It is established that under certain restrictions on the variation of f(x, y), and also on the lines l ₁ , l ₂ , ..., l_k, the fourier series converges to a value bounded above by the limit superior, and below by the limit inferior of f(x+u, y+v), u, v →0, this value depending on the manner in which the series is summed. The preparation of this paper was financed, in part, by a Canadian Mathematical Congress Summer Research Grant (1968). Entrata in Redazione il 3 febbraio 1969.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.