An optimum testing algorithm for some symmetric coherent systems

A symmetric coherent system (or k-out-of-n system) is a system composed of n components CO₁, CO₂ …, CO_n, each component existing in either a working or failing state. Such a system is in a working state if and only if k or more of its components are working, where 1 ? k ? n. It is assumed that the components can only be tested individually, and every test gives perfect information as to whether the tested component is working or failing. Let P_i, be the a priori probability that the component CO_i is working and C_i, be the cost of testing component CO_i. An optimal (minimum total expected cost) testing algorithm is an algorithm to determine the condition of a given symmetric coherent system by testing some of its components individually. In general, such an algorithm is a sequential process, that is, the next component to be tested is a function of the outcomes of the tests already applied. Every (optimal) testing algorithm corresponds to a (optimal) feasible testing policy which is basically a binary rooted tree with some component assigned to each node. In this paper an algorithm is presented for constructing an optimal feasible testing policy for symmetric coherent systems, where $\text{C}{}_{\mathrm{i}}\text{P}{}_{\mathrm{i}}\text{≠}\text{C}{}_{\mathrm{j}}\text{P}{}_{\mathrm{j}}$ and $\text{C}{}_{\mathrm{i}}\text{(1 ? P}{}_{\mathrm{i}}\text{)}\text{≠}\text{C}{}_{\mathrm{j}}\text{(1 ? P}{}_{\mathrm{j}}\text{)}$ whenever i ≠ j. This algorithm can be implemented as an optimal testing algorithm with polynomial complexity. Moreover, it is proven that any optimal testing algorithm corresponds to some feasible testing policy which can be generated by this algorithm.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [2].     

An extremal problem for sets with applications to graph theory

Let X₁, …, X_n be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let A_ij and B_ij be subsets of X_i that satisfy |A_ij| ? r_i and |B_ij| ? s_i for 1 ? i ? n, 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{ij}}\text{) = ?}$ for 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{il}}\text{) ≠ ?}$ for 1 ? j < l ? h. We prove that $\text{h?}\text{Π}\text{i=1}\text{n}\text{r}{}_{\mathrm{i}}\text{+s}{}_{\mathrm{i}}\text{r}{}_{\mathrm{i}}$. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).     

An optimal algorithm for finding all the jumps of a monotone step-function

The idea of binary search is generalized as follows. Given ?: {0, 1,…, N} → {0,…, K} such that $\text{?(0) = 0}$, $\text{?(N) = K}$, and $\text{?(i) ? ?(j)}$ for i < j, all the “jumps” of f, i.e., all is such that $\text{?(i) > ?(i ? 1)}$ together with the difference $\text{?(i) ? ?(i ? 1)}$ are recognized within f-evaluations. This is proved to be the exact bound in the non-trivial case when K ? N. An optimal strategy is as follows: The first query will be at i = 2^m, where $\text{m = [}\text{log}{}_2\text{(}\text{N}\text{K}\text{)]}$. An adversary will then respond either $\text{?(i) = 0}$ or $\text{?(i) - 1}$ as explained in the paper.     

Solution of a system of functional-differential equations arising from an optimization problem

In connection with an optimization problem, all functions ?: Iⁿ → $\text{R}$ with continuous nonzero partial derivatives and satisfying

$\text{??}\text{?x,}{}_{\mathrm{i}}\text{??}\text{?x}{}_{\mathrm{j}}$

for all x_i, x_j ≠ I, i, j = 1,2,…, n (n > 2) are determined (I is an interval of positive real numbers).     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

A noncommutative version of the matrix inversion formula

The cofactor expression (? 1)^i+j$\text{det}\text{(I ? B)}{}_{\mathrm{<mtext>j</mtext><mtext>?</mtext><mtext>i</mtext><mtext>?</mtext>}}\text{det}\text{(I ? B)}$ for the (i, j)-entry in the inverse of a matrix (I ? B) is proved to be equal to the corresponding entry of the series Σ_m≥0B^m, by using purely combinatorial methods: circuit monoid techniques and monomial rearrangements. Moreover, the identity is shown to hold in a non-commutative formal power series algebra.     

Bound on integrals: Elimination of the dual and reduction of the number of equality constraints

Let L_j (j = 1, …, n + 1) be real linear functions on the convex set $\text{F}$ of probability distributions. We consider the problem of maximization of L_n+1(F) under the constraint F ? $\text{F}$ and the equality constraints L₁(F) = z₁ (i = 1, …, n). Incorporating some of the equality constraints into the basic set $\text{F}$, the problem is equivalent to a problem with less equality constraints. We also show how the dual problems can be eliminated from the statement of the main theorems and we give a new illuminating proof of the existence of particular solutions.The linearity of the functions L_j(j = 1, …, n + 1) can be dropped in several results.     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

Limit of the spectra of the interior Neumann problems when a solid domain shrinks to a plane one

Let (Δ + λ) u = 0 in $\text{D}$c$\text{R}$^d, $\text{?u}\text{?N}\text{=0}$ on ?$\text{D}$. How do the eigenvalues λ_j behave when $\text{D}$ shrinks to a domain Δ ? R^{d ? 1} ? The answer depends not only on Δ but on the way $\text{D}$ shrinks to Δ. The limit of λ_j is found. Examples are given.     

A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

Properties of (0, 1)-matrices without certain configurations

We generalize results of Ryser on (0, 1)-matrices without triangles, 3 × 3 submatrices with row and column sums 2. The extremal case of matrices without triangles was previously studied by the author. Let the row intersection of row i and row j (i ≠ j) of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do not 0 otherwise. For matrices satisfying some conditions on forbidden configurations and column sums ? 2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. The extremal matrices with m rows and $\text{(}\text{m}\text{2}\text{)}$ distinct columns have a unique SDR of pairs of rows with 1's. A triangle bordered with a column of 0's and its (0, 1)-complement are also considered as forbidden configurations. Similar results are obtained and the extremal matrices are closely related to the extremal matrices without triangles.     

Singular perturbation problems for systems of partial differential equations of elliptic type

Elliptic boundary value problems for systems of nonlinear partial differential equations of the form $\text{F}{}_{\mathrm{i}}\text{(x, u}{}_1\text{, u}{}_2\text{,…, u}{}_{\mathrm{N}}\text{,}\text{?u}{}_{\mathrm{i}}\text{?x}{}_{\mathrm{j}}\text{, ?}{}^{\mathrm{p}}{}_{\mathrm{i}}\text{?}{}^2\text{u}{}_{\mathrm{i}}\text{?x}{}_{\mathrm{j}}\text{?x}{}_{\mathrm{k}}\text{) = ?}{}_{\mathrm{i}}\text{(x), x ? R}{}^{\mathrm{n}}$, i = 1(1)N, j, k = 1(1)n, p_i ? 0, ? being a small parameter, with Dirichlet boundary conditions are considered. It is supposed that a formal approximation Z is given which satisfies the boundary conditions and the differential equations upto the order χ(?) = o(1) in some norm. Then, using the theory of differential inequalities, it is shown that under certain conditions the difference between the exact solution u of the boundary value problem and the formal approximation Z, taken in the sense of a suitable norm, can be made small.     

The use of the tetrachoric series for evaluating multivariate normal probabilities

The tetrachoric series is a technique for evaluating multivariate normal probabilities frequently cited in the statistical literature. In this paper we have examined the convergence properties of the tetrachoric series and have established the following. For orthant probabilities, the tetrachoric series converges if $\text{|;?}{}_{\mathrm{ij}}\text{|; <}\text{1}\text{(k ? 1)}$, 1 ≤ i < j ≤ k, where ?_ij are the correlation coefficients of a k-variate normal distribution. The tetrachoric series for orthant probabilities diverges whenever k is even and $\text{?}{}_{\mathrm{ij}}\text{>}\text{1}\text{(k ? 1)}$ or k is odd and $\text{?}{}_{\mathrm{ij}}\text{>}\text{1}\text{(k ? 2)}$, 1 ≤ i < j ≤ k. Other specific results concerning the convergence or divergence of this series are also given. The principal point is that the assertion that the tetrachoric series converges for all k ≥ 2 and all ?_ij such that the correlation matrix is positive definite is false.     

Representation and index theory for C1-algebras generated by commuting isometries

We discuss here representation and Fredholm theory for C¹-algebras generated by commuting isometries. More particularly, for n commuting isometries {V_j: 1 ? j ? n} on separable Hilbert space we give a representation resembling the well-known representation for a single isometry. Our representation permits an analysis of the C¹-algebras $\text{Ol}$=$\text{Ol}$(V_j:1?j?n) generated by the {V_j}. The commutator ideal in $\text{Ol}$ is identified precisely and, under certain additional hypotheses, the Fredholm operators in $\text{Ol}$ are also precisely determined. Finally, we obtain formulas in terms of topological data for the index of Fredholm operators in some interesting algebras of the type $\text{Ol}$(V_j:1?j?n).     

A conjecture of recski in combinatorial set theory

A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ S_i = n and |S_i ∩ S_i| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(n^p+1logn).     

On positional games

Let {A_i} be a family of sets and let S = ∩_iA_i. By a positional game we shall mean a game played by two players on {A_i}. The players alternately pick elements of S and that player wins who fist has all the elements of one of the A_i. This paper deals with almost disjoint hypergraphs only, i.e., |A_i∪A_j| ? 1 if i ≠ j. Let $\text{M}{}^1\text{(n)}$ be the smallest integer for which there is an almost disjoint n-uniform hypergraph $\text{|T| = M}{}^1\text{(n)}$, so that the first player has a winning strategy. It is shown that $\text{lim}{}_{\mathrm{n}}\text{[M}{}^1\text{(n)]}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 4}$, which was conjectured by Erdös. The same method is applied to prove a conjecture of Hales and Jewett on r-dimensional tick-tack-toe if r is large enough. Finally we prove that for an arbitrary almost disjoint n-uniform hypergraph the second player has such a strategy that the first player unable to win in his mth move if m < (2 ? ?)ⁿ.     

A characterization of planar cubic graphs

If S is a collection of circuits in a graph G, the circuits in S are said to be consistently orientable if G can be oriented so that they are all directed circuits. If S is a set of three or more consistently orientable circuits such that no edge of G belongs to more than two circuits of S, then S is called a ring if there exists a cyclic ordering C₀, C₁,…, C_{n ? 1}, C₀ of the n circuits in S such that $\text{EC}{}_{\mathrm{i}}\text{? EC}{}_{\mathrm{j}}\text{≠ ?}$ if and only if j = i or j ≡ i ? 1 (mod n) or j ≡ i + 1 (mod n). We characterise planar cubic graphs in terms of the non-existence of a ring with certain specified properties.     

Graphical t-wise balanced designs

A pair (X, $\text{B}$) will be a t-wise balanced design (tBD) of type t?(v, K, λ) if $\text{B}\text{= (B}{}_{\mathrm{i}}\text{: i ? I)}$ is a family of subsets of X, called blocks, such that: (i) $\text{|X| = v ?}\text{N}$, where $\text{N}$ is the set of positive integers; (ii) $\text{1?t?|B}{}_{\mathrm{i}}\text{|?K?}\text{N}$, for every i ? I; and (iii) if T ? X, |T| = t, then there are λ ? $\text{N}$ indices i ? I where T ? B_i. Throughout this paper we make three restrictions on our tBD's: (1) there are no repeated blocks, i.e. $\text{B}$ will be a set of subsets of X; (2) t ? K or there are no blocks of size t; and (3) $\text{P}{}_{\mathrm{k}}\text{(X)?}\text{B}$ or $\text{B}$ does not contain all k-subsets of X for any t<k?v. Note then that X ? $\text{B}$. Also, if we give the parameters of a specific tBD, then we will choose a minimal K.We focus on the $\text{t?((}\text{p}\text{2}\text{), K, λ)}$ designs with the symmetric group S_p as automorphism group, i.e. X will be the set of $\text{v = (}\text{p}\text{2}\text{)}$ labelled edges of the undirected complete graph K_p and if B ? $\text{B}$ then all subgraphs of K_p isomorphic to B are also in $\text{B}$. Call such tBD's ‘graphical tBD's’. We determine all graphical tBD's with λ = 1 or 2 which will include one with parameters 4?(15,{5,7},1).