On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

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.     

Spanning subgraphs of k-connected digraphs

It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most $\text{2m + 6(k ?1)(n ? 1))}\text{(5k ? 3)}$ edges. When k = 2 the bound is improved to $\text{(3m + 8(n ? 1))}\text{10}$, which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices.     

On weighted lattice paths

A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set $\text{{(n, m) ¦ f(n ? 1) ? m ? f(n), n = 1, 2, …}}$ will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant $\text{x(}\text{k}\text{2}\text{)}$.     

On the number of combinations without unit separation

Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if $\text{n ? 2(k ? 1), f(n,k)=}\text{∑}\text{i=0}\text{κ}\text{(}\text{n?k+I?2i}\text{k?2i}\text{)}$ (where $\text{κ = [}\text{k}\text{2}\text{]}$). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then $\text{(n,k)=(}\text{n?k}\text{k}\text{)+(}\text{n?k?1}\text{k?1}\text{)}$.     

On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

Finding the maximum,merging, and sorting in a parallel computation model

A model for synchronized parallel computation is described in which all p processors have access to a common memory. This model is used to solve the problems of finding the maximum, merging, and sorting by p processors. The main results are: 1. Finding the maximum of n elements (1 < p ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log log}\text{p)}$; (optimal for $\text{p ≤}\text{n}\text{log log}\text{n}$). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log}\text{n)}$ for p ≤ n (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$), $\text{O(}\text{log}\text{m}\text{log}\text{p}\text{n}\text{)}$ for $\text{p ≥ n(= O(k)}\text{if}\text{p = m}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{n, k > 1)}$. 3. Sorting n elements within a depth of $\text{O(}\text{n}\text{p}\text{log}\text{n}\text{+}\text{log}\text{n}\text{log}\text{p)}$ for p ≤ n, (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$). $\text{O(}\text{log}{}^2\text{n}\text{log}\text{p}\text{n}\text{) +}\text{log}\text{n)}$ for $\text{p ≥ n (= O(k}\text{log}\text{n)}\text{if}\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{, k > 1)}$. The depth of O(klogn) for $\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ processors was also achieved by Hirschberg (Comm. ACM21, No. 8 1978, 657–661) and Preparata IEEE Trans ComputersC-27 (July 1978), 669–673). Our algorithm is substantially simpler. All the elementary operations including allocation of processors to their jobs are taken into account in deriving the depth complexity and not only comparisons.     

Nonnegative factorization of completely positive matrices

Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with $\text{m?}\text{1}\text{2}\text{k(k+1)?N}$, where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is $\text{(k+1)}{}^2\text{4}$ (k odd),$\text{k(k+2)}\text{4}$ (k even).     

The visually distinct configurations of k sets

Two sets of sets, C₀ and C₁, are said to be visually equivalent if there is a 1-1 mapping m from C₀ onto C₁ such that for every S, T?C₀, S ∩ T=0 if and only if m(S)∩ m(T)=0 and S?T if and only if m(S)?m(T). We find estimates for V(k), the number of equivalence classes of this relation on sets of k sets, for finite and infinite k. Our main results are that for finite k, $\text{1}\text{2}\text{k}{}^2\text{-k log k <log V (k)<ak}{}^2\text{+βk+log k}$, where α and β are approximately 0.7255 and 2.5323 respectively, and there is a set N of cardinality $\text{1}\text{2}\text{(k}{}^2\text{+k)}$ such that there are V(k) visually distinct sets of k subsets of N.     

Families of intersecting finite vector spaces

The following theorem is proved. It is a generalization of the problem for finite vector spaces analogous to a theorem of Kleitman for finite sets.Let V be an n-dimensional vector space over a finite field F of q elements. Suppose we have two collections, one consisting of k- and the other of m-dimensional subspaces of V with the property that the intersection of each member of one with each member of the other has dimension no less than r.Then if n ? k + m + 2 or n ? k + m + 1 and q ? 3, there are either no more than $\text{[}\text{n?r}\text{k?r}\text{]}{}_{\mathrm{q}}$ members in the first family or fewer than $\text{[}\text{n?r}\text{m?r}\text{]}{}_{\mathrm{q}}$ members in the second.The method used leads to a similar result for sets, provided that n ? r + (r + 1)(k ? r)(m ? r + 1) with k ? m.     

On the maximum number of permutations with given maximal or minimal distance

Let us denote by R(k, ? λ)[R(k, ? λ)] the maximal number $\text{M}$ such that there exist $\text{M}$ different permutations of the set {1,…, k} such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ? λ) ? kR(k ? 1, ? λ ? 1), R(k, ? λ) ? R(k, ? λ ? 1) ? k!, R(k, ? λ) ? kR(k ? 1, ? λ ? 1). We show: R(k, ? k ? 2) = 2, R(k, ? 1) = (k ? 1)!, R(p^m, ? 2) = (p^m ? 2)!, R(p^m + 1, ? 3) = (p^m ? 2)!, $\text{R(k, ? k ? 3) =}\text{k!}\text{2}$, R(k, ? 0) = k, R(p^m, ? 1) = p^m(p^m ? 1), R(p^m + 1, ? 2) = (p^m + 1)p^m(p^m ? 1). The exact value of R(k, ? λ) is determined whenever k ? k₀(k ? λ); we conjecture that R(k, ? λ) = (k ? λ)! for k ? k₀(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ? λ) ? R(k, ? λ)| is attained for $\text{λ = (}\text{k}\text{2}\text{) + O(}\text{k}\text{log}\text{k}\text{)}$.     

On the length of optimal TSP circuits in sets of bounded diameter

Let V be a set of n points in R^k. Let d(V) denote the diameter of V, and l(V) denote the length of the shortest circuit which passes through all the points of V. (Such a circuit is an “optimal TSP circuit”.) l^k(n) are the extremal values of l(V) defined by l^k(n)=max{l(V)|V∈V_n^k}, where V_n^k={V|V?R^k,|V|=n, d(V)=1}. A set V∈V_n^k is “longest” if l(V)=l^k(n). In this paper, first some geometrical properties of longest sets in R² are studied which are used to obtain l²(n) for small n′s, and then asymptotic bounds on l^k(n) are derived. Let δ(V) denote the minimal distance between a pair of points in V, and let: δ^k(n)=max{δ(V)|V∈V_n^k}. It is easily observed that $\text{δ}{}^{\mathrm{k}}\text{(n)=O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{)}$. Hence, $\text{c}{}_{\mathrm{k}}\text{=}\text{lim sup}{}_{\mathrm{n\to \infty }}\text{δ}{}^{\mathrm{k}}\text{(n)n}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$ exists. It is shown that for all $\text{n, c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{≤δ}{}^{\mathrm{k}}\text{(n)}$, and hence, for all $\text{n, l}{}^{\mathrm{k}}\text{(n)≥ c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>1?1</mtext><mtext>k</mtext>}}$. For k=2, this implies that $\text{l}{}^2\text{(n)≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which generalizes an observation of Fejes-Toth that $\text{lim}{}_{\mathrm{n\to \infty }}\text{l}{}^2\text{(n)n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}$. It is also shown that $\text{l}{}^{\mathrm{k}}\text{(n) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]nδ}{}^{\mathrm{k}}\text{(n) + o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{+ o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{)}$. The above upper bound is used to improve related results on longest sets in k-dimensional unit cubes obtained by Few (Mathematika2 (1955), 141–144) for almost all k′s. For k=2, Few's technique is used to show that $\text{l}{}^2\text{(n)≤(}\text{πn}\text{2}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ O(1)}$.     

Spaces of matrices of equal rank

Let M_m,n(F) denote the space of all mXn matrices over the algebraically closed field F. A subspace of M_m,n(F), all of whose nonzero elements have rank k, is said to be essentially decomposable if there exist nonsingular mXn matrices U and V respectively such that for any element A, UAV has the form

$\text{UAV=}\text{A}{}_1\text{A}{}_2\text{A}{}_3\text{0}$

where A₁ is iX(k–i) for some i?k. Theorem: If $\text{K}$ is a space of rank k matrices, then either $\text{K}$ is essentially decomposable or dim $\text{K}$?k+1. An example shows that the above bound on non-essentially-decomposable spaces of rank k matrices is sharp whenever n?2k–1.     

A problem of Zarankiewicz

Zarankiewicz, in problem P 101, Colloq. Math., 2 (1951), p. 301, and others have posed the following problem: Determine the least positive integer k_α,β(m, n) so that if a 0,1-matrix of size m by n contains k_α,β(m, n) ones then it must have an α by β submatrix consisting entirely of ones. This paper improves upon previously known upper bounds for k_α,β(m, n) by proving that $\text{k}{}_{\mathrm{\alpha \beta }}\text{(m,n)?}\text{1+((β?1)}\text{(}\text{p}\text{α?1}\text{))(}\text{m}\text{α}\text{)}\text{+}\text{((p+1)(α?1)}\text{α}\text{)n}$ for each integer p greater than or equal to α ? 1. Each of these inequalities is better than the others for a specific range of values of n. Equality is shown to hold infinitely often for each value of p. Finally some applications of this result are made to arrangements of lines in the projective plane.     

Best quadrature formulas at equally spaced nodes

It has been known for some time that the trapezoidal rule $\text{T}{}_{\mathrm{n}}\text{f =}\text{1}\text{2}\text{f(0) + f(1) + … + f(n ? 1) +}\text{1}\text{2}\text{f(n)}$ is the best quadrature formula in the sense of Sard for the space W^1,p, all functions such that f′ ?L^p. In other words, the norm of the error functional Ef = ∝₀ⁿf(x) dx ? ∑_{k = 0}ⁿλ_kf(k) in W^1,p is uniquely minimized by the trapezoidal sum. This paper deals with quadrature formulas of the form ∑_{k = 0}ⁿ ∑_l?Jc_klf^(l)(k) where J is some subset of {0, 1,…, m ? 1}. For certain index sets J we identify the best quadrature formula for the space W^m,p, all functions such that f^(m)?L^p. As a result, we show that the Euler-Maclaurin quadrature formula

$\text{T}{}_{\mathrm{n}}\text{f +}\text{∑}\text{o<2v≤m}\text{B}{}_{\mathrm{2v}}\text{(2v)!}\text{(f (2v?1)(0) ? f (2v?1) (n))}$

is the best quadrature formula of the above form with J = {0, 1, 3,…, ?m ? 1} for the space W^m,p, providing m is an odd integer.     

On a problem of C. C. Chen and D. E. Daykin

Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that $\text{α(k, p, h) ≤ h + 1 + (k ? 1){(p ? h ? 1) × (h}{}^{\mathrm{p}}\text{+ 1)}}{}^{\mathrm{<mtext>1</mtext><mtext>h</mtext>}}$ and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if

$\text{(}\text{n}\text{3}\text{)>(}\text{p}\text{3}\text{)}\text{Σ}\text{i=1}\text{t}\text{(}\text{e}{}_{\mathrm{i}}\text{2}\text{)}$

where e_i is the number of edges of color i, 1 ≤ i ≤ t.     

Probabilities of dominant candidates based on first-place votes

Suppose each of an odd number n of voters has a strict preference order on the three ‘candidates’ in {1,2,3} and votes for his most preferred candidate on a plurality ballot. Assume that a voter who votes for i is equally likely to have ijk and ikj as his preference order when {i,j,k} = {1,2,3}.Fix an integer m between $\text{1}\text{2}$(n + 1) and n inclusive. Then, given that n_i of the n voters vote for i, let f_m(n₁,n₂,n₃) be the probability that one of the three candidates is preferred by m or more voters to each of the other two.This paper examines the behavior of f_m over the lattice points in L_n, the set of triples of non-negative integers that sum to n. It identifies the regions in L_n where f_m is 1 and where f_m is 0, then shows that f_m(a,b + 1, c)>f_m(a + 1,b,c) whenever a + b + c + 1 = n, a≤c≤b, a<c<m and c≤n ? m. These results are used to partially identify the points in L_n where f_m is minimized subject to f_m>0. It is shown that at least two of the n_i are equal at minimizing points.     

On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.