On covering a product of sets with products of their subsets

Suppose that S₁,…,S_N are collections of subsets of X₁,…,X_N, respectively, such that n_i subsets belonging to S_i, and no fewer, cover X_i for all i. the main result of this paper is that to cover X₁ x…x X_N requires no fewer than σ^N_i=1 (n_i–1) + 1 and no more than Π^N_i=1n_i subsets of the form A₁ x…x A_N, where A_i∈S₁foralli. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.     

Proof of Gromov’s theorem on homogeneous nilpotent approximation for vector fields of class C 1

The article is devoted to the asymptotic properties of the vector fields $\tilde X_i^g $ , i = 1, …, N, θ _g -connected with C ¹-smooth basis vector fields {X _i } _i=1,…,N satisfying condition (+ deg). We prove a theorem of Gromov on the homogeneous nilpotent approximation for vector fields of classC ¹. Nontrivial examples are constructed of quasimetrics induced by vector fields {X _i } _{i=1, …, N} .     

Reconstruction from vertex-switching

Let X be a graph with vertices x₁ ,…, x_n. Let X_i be the graph obtained by removing all edges {x_i, x_j} of X and inserting all nonedges {x_i, x_k}. If n ? 0 (mod 4), then X can be uniquely reconstructed from the unlabeled graphs X₁.…, X_n. If n = 4 the result is false, while for n = 4m≥8 the result remains open. The proof uses linear algebra and does not explicitly describe the reconstructed graph X.     

On maximal antichains consisting of sets and their complements

Let 1 ? k₁ ? k₂ ? … ? k_n be integers and let S denote the set of all vectors x = (x₁, x₂, …, x_n) with integral coordinates satisfying 0 ? x_i ? k_i, i = 1, 2, …, n. The complement of x is (k₁ ? x₁, k₂ ? x₂, …, k_n ? x_n) and a subset X of S is an antichain provided that for any two distinct elements x, y of X, the inequalities x_i ? y_i, i = 1, 2, …, n, do not all hold. We determine an LYM inequality and the maximal cardinality of an antichain consisting of vectors and its complements. Also a generalization of the Erdös-Ko-Rado theorem is given.     

A result on hypothesis testing for a multivariate normal distribution when some observations are missing

Let U_i = (X_i, Y_i), i = 1, 2,…, n, be a random sample from a bivariate normal distribution with mean μ = (μ_x, μ_y) and covariance matrix

. Let X_i, i = n + 1,…, N represent additional independent observations on the X population. Consider the hypothesis testing problem H₀ : μ = 0 vs. H₁ : μ ≠ 0. We prove that Hotelling's T² test, which uses (X_i, Y_i), i = 1, 2,…, n (and discards X_i, i = n + 1,…, N) is an admissible test. In addition, and from a practical point of view, the proof will enable us to identify the region of the parameter space where the T²-test cannot be beaten. A similar result is also proved for the problem of testing μ_x ? μ_y = 0. A Bayes test and other competitors which are similar tests are discussed.     

The inertia of a Hermitian matrix having prescribed diagonal blocks

For i=1,…,m let H_i be an n_i×n_i Hermitian matrix with inertia In(H_i)= (π_i, ν_i, δ_i). We characterize in terms of the π_i, ν_i, δ_i the range of In(H) where H varies over all Hermitian matrices which have a block decomposition H= (X_ij)_{i, j=1,…, m} in which X_ij is n_i×n_j and X_ii=H_i.     

Permanence and Positive Periodic Solutions for Kolmogorov Competing Species Systems

We prove the existence of periodic solutions in a compact attractor of (R⁺)ⁿ for the Kolmogorov system x′_i = x_if_i(t, x₁, …, x_n), i = l, …, n in the competitive case. Extension to differential delay equations are con- sidered too. Applications are given to Lotka-Volterra systems with periodic coefficients.     

An explicit expression for the cost of a class of Huffman trees

Let T_n denote a binary tree with n terminal nodes V={υ₁,…,υ_n} and let l_i denote the path length from the root to υ_i. Consider a set of nonnegative numbers W={w₁,…,w_n} and for a permutation π of {1,…,n} to {1,…,n}, associate the weight w_i to the node υ_π(i). The cost of T_n is defined as C(T_n∣W)=Min_π∑ⁿ_i=1w_il_π(i).A Huffman tree H_n is a binary tree which minimizes C(T_n∣W) over all possible T_n. In this note, we give an explicit expression for C(H_n∣W) when W assumes the form: w_i=k for i=1,…,n?m; w_i=x for i=n?m+1,…,n. This simplifies and generalizes earlier results in the literature.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

On maximal antichains containing no set and its complement

Let 1?k₁?k₂?…?k_n be integers and let S denote the set of all vectors x = (x₁, …, x_n with integral coordinates satisfying 0?x_i?k_i, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of k_i elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities x_i?y_i, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k₁ + k₂ + …k_n. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k₁-x₁, k₂-x₂, …, k_n -x_n). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and$\text{|(}\text{1}\text{2}\text{K)X|}$ does not exceed the number of vectors in $\text{(}\text{1}\text{2}\text{K)S}$ with first coordinate different from k₁, then

$\text{∑}\text{i=0}\text{K}\text{i≠}\text{1}\text{2}\text{K}\text{|(i)X|}\text{|(i)S|}\text{+}\text{|(}\text{1}\text{2}\text{K)X|}\text{|(}\text{1}\text{2}\text{K-1)S|}\text{?1}$

.     

On Certain C-Test Words for Free Groups

Let F_m be a free group of a finite rank m ≥ 2 and let X_i, Y_j be elements in F_m. A non-empty word w(x₁,…,x_n) is called a C-test word in n letters for F_m if, whenever (X₁,…,X_n) = w(Y₁,…,Y_n) ≠ 1, the two n-typles (X₁,…,X_n) and (Y₁,…,Y_n) are conjugate in F_m. In this paper we construct, for each n ≥ 2, a C-test word v_n(x₁,…,x_n) with the additional property that v_n(X₁,…,X_n) = 1 if and only if the subgroup of F_m generated by X₁,…,X_n is cyclic. Making use of such words v_m(x₁,…,x_m) and v_m + 1(x₁,…,x_m + 1), we provide a positive solution to the following problem raised by Shpilrain: There exist two elements u₁, u₂ ∈ F_m such that every endomorphism ψ of F_m with non-cyclic image is completely determined by ψ(u₁), ψ(u₂).     

R-fuzzy computation

The present paper studies so-called R-fuzzy recursive program schemes which are finitely specified by systems of equations x_i = p_i, i = 1,…, n. Thereby, X = {x₁,…, x_n} is a finite set of variables and the p_i's are polynomials built up over X unioned wih a finite set F of function symbols and with coefficients in a given semiring R that determines the different kind of fuzziness by evaluating possible choices. Using power series on F-tree with variables of X the meaning of R-fuzzy recursive program schemes can formally be computed. The main result shows the equivalence of equational (fixed point) and operational semantics of such program schemes.     

Über Folgen,die BezÜglich Eines Mittels Rekurrent Sind

Let X be a convex subset of a finite-dimensional real vector space. A function M: X ^k → X is called a strict mean value, if M(x₁,…, x_k) lies in the convex hull of x₁,…, x_k), but does not coincide with one of its vertices. A sequence (x_n)_{n∈ ?} in X is called M-recursive if x_n+k = M(x_n, x_n+1,…, x_n+k?1) for all n. We prove that for a continuous strict mean value M every M-recursive sequence is convergent. We give a necessary and sufficient condition for a convergent sequence in X to be M-recursive for some continuous strict mean value M, and we characterize its limit by a functional equation. 39 B 72, 39 B 52, 40 A 05.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

Identifiability of the multinormal and other distributions under competing risks model

Let X₁, X₂ ,…, X_p be p random variables with joint distribution function F(x₁ ,…, x_p). Let Z = min(X₁, X₂ ,…, X_p) and I = i if Z = X_i. In this paper the problem of identifying the distribution function F(x₁ ,…, x_p), given the distribution Z or that of the identified minimum (Z, I), has been considered when F is a multivariate normal distribution. For the case p = 2, the problem is completely solved. If p = 3 and the distribution of (Z, I) is given, we get a partial solution allowing us to identify the independent case. These results seem to be highly nontrivial and depend upon Liouville's result that the (univariate) normal distribution function is a nonelementary function. Some other examples are given including the bivariate exponential distribution of Marshall and Olkin, Gumbel, and the absolutely continuous bivariate exponential extension of Block and Basu.     

Some comments on fuzzy variables

Nahmias introduced the concept of a fuzzy variable as a possible axiomatic framework from which a rigorous theory of fuzziness may be constructed. In this paper we attempt to shed more light on fuzzy variables in analogy with random variables. In particular, we study the problem: if X₁, X₂,…,X_n are mutually unrelated fuzzy variables with common membership function μ and α₁, α₂,…,α_n are real numbers satisfying α_i ? o for every i and Σ_i=1ⁿα_i=1, when does does Z = Σ_{i = 1}ⁿα_iX_i have the same membership function μ?     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

A note on reflexivity in Banach spaces

For any normed spaceX, the unit ball ofX is weak *-dense in the unit ball ofX ^**. This says that for any ε>0, for anyF in the unit ball ofX ^**, and for anyf ₁,…,f _n inX ^*, the system of inequalities |f _i(x)?F(f _i)|≤ε can be solved for somex in the unit ball ofX. The author shows that the requirement that ε be strictly positive can be dropped only ifX is reflexive.     

Sloane's box stacking problem

Recently, Sloane suggested the following problem: We are given n boxes, labeled 1,2,…,n. For i=1,…,n, box i weighs (m-1)i grams (where m?2 is a fixed integer) and box i can support a total weight of i grams. What is the number of different ways to build a single stack of boxes in which no box will be squashed by the weight of the boxes above it? Prior to this generalized problem, Sloane and Sellers solved the case m=2. More recently, Andrews and Sellers solved the case m?3. In this note we give new and simple proofs of the results of Sloane and Sellers and of Andrews and Sellers, using a known connection with m-ary partitions.     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.