Wallman compactification and matrices of zeroes and ones

Let M be an m by n matrix (where m and n are any finite or infinite cardinals) such that the entries of M are 0's or 1's and M contains the zero row $\text{0}$ and the rows of M are closed under coordinatewise multiplication. We prove that M can be extended to an m by n′ ? n matrix M′ such that the entries of M′ are 0's or 1's and M′ contains the zero row 0?′ and the extension preserves the zero products. Moreover, the newly introduced columns (if any) are pairwise distinct. Furthermore, if E′ is any set of rows of M′ with the property that for every finite subset of rows r′_i of E′ there exists j < n′ such that r′_ij = 1, then every subset of rows of E′ has the same property. We rephrase this by saying that if E′ has the finite intersection property then E′ has a nonempty intersection. We also show (this time by Zorn's lemma) that there exists an extension of M with all the abovementioned properties such that the extension preserves products sums, complements and the newly introduced columns (if any) are pairwise distinct in a stricter sense. In effect, our result shows that the classical Wallman compactification theorem can be formulated purely combinatorially requiring no introduction of any topology on n.     

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.     

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′}.     

A stochastic permutation-flowshop scheduling problem minimizing in distribution the schedule length

Consider n jobs (J₁,J₂,…,J_n) and m machines (M₁,M₂…,M_m). Upon completion of processing of J_i, 1 ? i ? n, on M_j 1 ? j ? m ? 1, it departs with probability p_i or moves to M_j+1 with the complementary probability, 1?p_i. A job completing service on M_m departs. The processing time of j_i on M_j possesses a distribution function F_j. It is proved that sequencing the jobs in a nondecreasing order of p_i minimizes in distribution the schedule length.     

On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

A Fisher type inequality

In this paper we study subsets of a finite set that intersect each other in at most one element. Each subset intersects most of the other subsets in exactly one element. The following theorem is one of our main conclusions. Let S₁,… S_m be m subsets of an n-set S with |S₁| ? 2 (l = 1, …,m) and |S_i ∩ S_j| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each S_i has non-empty intersection with at least m ? c of the remaining subsets. Then there is a least positive integer M(c) depending only on c such that either m ? n or m ? M(c).     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Canonical row-column-exchangeable arrays

Consider a standard row-column-exchangeable array X = (X_ij : i,j ≥ 1), i.e., X_ij = f(a, ξ_i, η_j, λ_ij) is a function of i.i.d. random variables. It is shown that there is a canonical version of X, X′, such that X′, and α′, ξ′₁, ξ′₂,…, η′₁, η′₂,…, are conditionally independent given ∩_{n ≥ 1}σ(X′_ij : max(i,j) ≥ n). This result is quite a bit simpler to prove than the analogous result for the original array X, which is due to Aldous.     

On discount residue classes

It is shown that, whenever m₁, m₂,…, m_n are natural numbers such that the pairwise greatest common divisors, d_ij=(m_i, m_j), i≠j are distinct and different from 1, then there exist integers a₁, a₂,…,a_n such that the solution sets of the congruences x≡_i (modm_i), i= 1,2,…,n are disjoint.     

Classes of matrices associated with the optimal assignment problem

Let E=[e_ij] be a matrix with integral elements, and let x be an indeterminate defined over the rational field Q. We investigate matrices of the form X=[x^e_ij] (i = 1,…, m; j = 1,…, n; m ⩽ n). We may multiply the lines (rows or columns) of the matrix X by suitable integral powers of x in various ways and thereby transform X into a matrix Y=[x^f_ij] such that the f_ij are nonnegative integers and each line of Y contains at least one element x⁰ = 1. We call Y a normalized form of X, and we denote by S(X) the class of all normalized forms associated with a given matrix X. The classes S(X) have a fascinating combinatorial structure, and the present paper is a natural outgrowth and extension of an earlier study. We introduce new concepts such as an elementary transformation called an interchange. We prove, for example, that two matrices in the same class are transformable into one another by interchanges. Our analysis of the class S(X) also yields new insights into the structure of the optimal assignments of the matrix E by way of the diagonal products of the matrix X.     

Bernstein type operators having 1 and x j as fixed points

For certain generalized Bernstein operators {L _n } we show that there exist no i, j ∈ {1, 2, 3,…}, i < j, such that the functions e _i (x) = x ⁱ and e _j (x) = x ^j are preserved by L _n for each n = 1, 2,… But there exist infinitely many e _i such that e ₀(x) = 1 and e _j (x) = x _j are its fixed points.     

Complementing and exactly covering sequences

The following is proved (in a slightly more general setting): Let α₁, …, α_m be positive real, γ₁, …, γ_m real, and suppose that the system [nα_i + γ_i], i = 1, …, m, n = 1, 2, …, contains every positive integer exactly once (= a complementing system). Then $\text{α}{}_{\mathrm{i}}\text{α}{}_{\mathrm{j}}$ is an integer for some i ≠ j in each of the following cases: (i) m = 3 and m = 4; (ii) m = 5 if all α_i but one are integers; (iii) m ? 5, two of the α_i are integers, at least one of them prime; (iv) m ? 5 and α_n ? 2ⁿ for n = 1, 2, …, m ? 4.For proving (iv), a method of reduction is developed which, given a complementing system of m sequences, leads under certain conditions to a derived complementing system of m ? 1 sequences.     

On separating systems whose elements are sets of at most k elements

A system A₁,…,A_m of subsets of X?{1,…,n} is called a separating system if for any two distinct elements of X there is a set A_i (1?i?m) that contains exactly one of the two elements. We investigate separating systems where each set A_i has at most k elements and we are looking for minimal separating systems, that means separating systems with the least number of subsets. We call this least number m(n,k). Katona has proved good bounds on m(n,k) but his proof is very complicated. We give a shorter and easier proof. In doing so we slightly improve the upper bound of Katona.     

A characterization of the multivariate normal distribution

Let X_j (j = 1,…,n) be i.i.d. random variables, and let Y′ = (Y₁,…,Y_m) and X′ = (X₁,…,X_n) be independently distributed, and A = (a_jk) be an n × n random coefficient matrix with a_jk = a_jk(Y) for j, k = 1,…,n. Consider the equation U = AX, Kingman and Graybill [Ann. Math. Statist.41 (1970)] have shown U ～ N(O,I) if and only if X ～ N(O,I). provided that certain conditions defined in terms of the a_jk are satisfied. The task of this paper is to delete the identical assumption on X₁,…,X_n and then generalize the results to the vector case. Furthermore, the condition of independence on the random components within each vector is relaxed, and also the question raised by the above authors is answered.     

Reversible-shop scheduling

Consider n jobs (J₁,…,J_n) and m machines (M₁,…,M_m). The route by which a job passes through the machines is either M₁ → M₂ → … → M_m or M_m → M_m−1 → … M₁, i.e. reversible-shop. It is proved that for three machines, the problem of minimizing the schedule length is NP-hard. Efficient algorithms are developed for the following special cases: three machines of which one or more are dominated; arbitrary number of machines where all operations have equal processing times; three machines, route-dependent reversible-shop where the second machine dominates the other two.     

Sequences of orthogonal vectors with a fixed norm

Let A = (a_ij) be an n × m matrix with a_ij ∈ K, a field of characteristic not 2, where Σ_i=1ⁿa_ij² = e, 1 ≤ j ≤ m, and Σ_i=1ⁿa_ija_ij′ = 0 for j ≠ j′. The question then is when is it possible to extend A, by adding columns, to obtain a matrix with orthogonal columns of the same norm. The question is answered for n ? 7 ≤ m ≤ n as well as for more general cases. Complete solutions are given for global and local fields, the answer depending on what congruence class modulo 4 n belongs to and how few squares are needed to sum to e.     

Heuristic procedures for the m-partial cover problem on a plane

The m-partial cover problem on a plane is defined as follows: given npoints located at cartesian coordinates (x_j, y_j) (j=1,…,n) each with an associated weight w_j, a critical distance R and an integer number m, determine the location of m centres so that the sum of the weights of those points lying within distance R of at least one centre is maximised. Five heuristic procedures to solve the m-partial cover problem are presented and computational experience reported. The use of the procedures for some related problems is discussed.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

Representing the GCD as linear combination in non-PID rings

We prove the following fact: If finitely many elements p ₁,p ₂,…,p _n of a unique factorization domain are given such that the greatest common divisor of each pair (p _i ,p _j ) can be expressed as a linear combination of p _i and p _j , then the greatest common divisor of all the p _i ’s can also be expressed as a linear combination of p ₁,…,p _n . We prove an analogous statement in general commutative rings.