Finite linear spaces with two consecutive line degrees

Let L be a non-trivial finite linear space in which every line has n or n+1 points. We describe L completely subject to the following restrictions on n and on the number of points p: p≤n ²+n?1 and n≥3; n ²+n+2≤p≤n ²+2n?1 and n≥3; p=n ²+2n and n≥4; p=n ²+2n+2 and n≥3; p=n ²+2n+3 and n≥4.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

Author index for volume 39

The distribution γ(c, n) of de Bruijn sequences of order n and linear complexity c is investigated. Some new results are proved on the distribution of de Bruijn sequences of low complexity, i.e., their complexity is between 2^n?1 + n and 2^n?1 + 2^n?2. It is proved that for n ? 5 and 2^n?1 + n?c<2^n?1 + 2^n?2, γ(c, n) ≡ 0 (mod 4). It is shown that for n ? 11, γ(2^n?1 + n, n) > 0. It is also proved that γ(2^n?1 + 2^n?2, n) ? 4γ(2^n?2 ? 1, n ? 2) and we give a recursive method to generate de Bruijn sequences of complexity 2^n?1 + 2^n?2.     

On a problem of rota

Let S(n, k) denote Stirling numbers of the second kind; for each n, let K_n be such that S(n, K_n) ? S(n, k) for all k. Also, let P(n) denote the lattice of partitions of an n-element set. Say that a collection of partitions from P(n) is incomparable if no two are related by refinement. Rota has asked if for all n, the largest possible incomparable collection in P(n) contains S(n, K_n) partitions. In this paper, we construct for all n sufficiently large an incomparable collection in P(n) containing strictly more than S(n, K_n) partitions. We also estimate how large n must be for this construction to work.     

Primitive digraphs with smallest large exponent

A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies α_n?γ(D)?w_n, where α_n=⌊w_n/2⌋+2 and w_n=(n-1)²+1. It is shown that the minimum number of arcs in a primitive digraph D on n?5 vertices with exponent equal to α_n is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent α_n and n+2 arcs. These constructions extend to digraphs with some exponents between α_n and w_n. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent α_n and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2.     

Cartan models and cellular decompositions of symmetric Riemannian spaces

In this paper, by making use of the Cartan models, we will construct cellular decompositions of some symmetric Riemannian spaces such as Sp(n)/U(n), U(n)/O(n), U(2n)/Sp(n), O(2n)/U(n), SU(n)/SO(n), SU(2n)/Sp(n), SO(2n)/U(n).     

On some friends of the sociable numbers

Let s(n) denote the sum of the proper divisors of n. Set s ₀(n) = n, and for k > 0, put s _k (n) := s(s _k-1(n)) if s _k-1(n) > 0. Thus, perfect numbers are those n with s(n)?=?n and amicable numbers are those n with s(n) ?? n but s ₂(n)?=?n. We prove that for each fixed k ?? 1, the set of n which divide s _k (n) has density zero, and similarly for the set of n for which s _k (n) divides n. These results generalize the theorem of Erd?s that for each fixed k, the set of n for which s _k (n)?=?n has density zero.     

Inverse cyclotomic polynomials

Let Ψn(x) be the monic polynomial having precisely all non-primitive nth roots of unity as its simple zeros. One has Ψn(x)=(xn−1)/Φn(x), with Φn(x) the nth cyclotomic polynomial. The coefficients of Ψn(x) are integers that like the coefficients of Φn(x) tend to be surprisingly small in absolute value, e.g. for n<561 all coefficients of Ψn(x) are ?1 in absolute value. We establish various properties of the coefficients of Ψn(x), especially focusing on the easiest non-trivial case where n is composed of 3 distinct odd primes.     

Simplest cases of nth-degree stochastic dominance

Le p(n) be the fewest number of support points for probability distributions p and q for which p stochastically dominates q of degree n but not of any degrees less than n. Then ?(n) = n + 1 for n = 1,2,3, and ?(n) = 4 for all larger n.     

Improved book-embeddings of incomplete hypercubes

In this paper, we show that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻² vertices can be embedded in n−1 pages for all n≥4. For the case n≥4, this result improves Fang and Lai’s result that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹ vertices can be embedded in n−1 pages for all n≥2.Besides this, we show that the result can be further improved when n is large — e.g., any incomplete hypercube with at most 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷ (respectively, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷+2ⁿ⁻²³⁰) vertices can be embedded in n−1 pages for all n≥9 (respectively, n≥232).     

An inequality for 3-polytopes

We prove the inequality Σ_n≥7 (n−6) p_n≤v−12 for any 3-dimensional polytope with v vertices and p_n n-sided faces, such that Σ_n≥6 p_n≥3. The polytopes satisfying Σ_n≥7 (n−6) p_n=v−12 are described and an interpretation of our results is given in terms of density of n-sided faces in planar graphs.     

Minimal free resolutions of monomial curves in P3k

Minimal free resolutions for prime ideals with generic zero (tn3,tn3?n10tn11,tn3?n20tn2, tn31), n1<n2<n3 positive integers, (n1,n2,n3)=1, are determined.     

Triangulations of orientable surfaces by complete tripartite graphs

Orientable triangular embeddings of the complete tripartite graph K_n,n,n correspond to biembeddings of Latin squares. We show that if n is prime there are at least e^{nlnn-n(1+o(1))} nonisomorphic biembeddings of cyclic Latin squares of order n. If n=kp, where p is a large prime number, then the number of nonisomorphic biembeddings of cyclic Latin squares of order n is at least e^{plnp-p(1+lnk+o(1))}. Moreover, we prove that for every n there is a unique regular triangular embedding of K_n,n,n in an orientable surface.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

A note on a conjecture on permanents

Let Kn denote the set of all n × n nonnegative matrices whose entries have sum n, and let ϕ be a real function on K_n defined by ϕ (X) = Πⁿ_i=1Σⁿ_j=1x_ij + Πⁿ_j=1Σⁿ_i=1x_ij − per X for X = [x_ij] ϵ K_n. A matrix A ϵ K_n is called a ϕ -maximizing matrix on K_n if ϕ (A) ⩾ ϕ (X) for all X ϵ K_n. It is conjectured that J_n = [1/n]_{n × n} is the unique ϕ-maximizing matrix on K_n. In this note, the following are proved: (i) If A is a positive ϕ-maximizing matrix, then A = J_n. (ii) If A is a row stochastic ϕ-maximizing matrix, then A = J_n. (iii) Every row sum and every column sum of a ϕ-maximizing matrix lies between 1 − √2·n!/nⁿ and 1 + (n − 1)√2·n!/nⁿ. (iv) For any p.s.d. symmetric A ϵ K_n, ϕ (A) ⩽ 2 − n!/nⁿ with equality iff A = J_n. (v) ϕ attains a strict local maximum on K_n at J_n.     

On the symmetric hyperspace of the circle

By X(n), n?1, we denote the n-th symmetric hyperspace of a metric space X as the space of non-empty finite subsets of X with at most n elements endowed with the Hausdorff metric. In this paper we shall describe the n-th symmetric hyperspace S¹(n) as a compactification of an open cone over ΣDn−2, here Dn−2 is the higher-dimensional dunce hat introduced by Andersen, Marjanovi? and Schori (1993) [2] if n is even, and Dn−2 has the homotopy type of Sn−2 if n is odd (see Andersen et al. (1993) [2]). Then we can determine the homotopy type of S¹(n) and detect several topological properties of S¹(n).     

Congruence properties of Apéry numbers

Apéry introduced a recurrence relation for a proof of the irrationality of ζ(3). Let a_n (n ≥ 0) satisfy the relation n³a_n ? (34n³ ? 51n² + 27n ? 5)a_{n ? 1} + (n ? 1)³a_{n ? 2} = 0. Which values of a₀ and a₁ cause each a_n to be an integer? This question is answered and some congruence properties of the a_n are given.     

The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).     

The asymptotic number of (0,1)-matrices with zero permanent

It is shown that Z_n/n·2^{n2 - n + 1}→1, where Z_n is the number of n × n (0,1)-matrices with zero permanent.