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).     

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).     

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.     

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.     

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.     

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.     

The diminishing segment process

Let Ξ₀=[−1,1], and define the segments Ξ_n recursively in the following manner: for every n=0,1,…, let Ξ_n+1=Ξ_n∩[a_n+1−1,a_n+1+1], where the point a_n+1 is chosen randomly on the segment Ξ_n with uniform distribution. For the radius ρ_n of Ξ_n, we prove that n(ρ_n−1/2) converges in distribution to an exponential law, and we show that the centre of the limiting unit interval has arcsine distribution.     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

Weak convergence with random indices

Suppose {X_nn?-0} are random variables such that for normalizing constants a_n>0, b_n, n?0 we have Y_n(·)=(X[_{n, ·}]-b_n/a_n ? Y(·) in D(0.∞) . Then a_n and b_n must in specific ways and the process Y possesses a scaling property. If {N_n} are positive integer valued random variables we discuss when Y_Nn → Y and Y'_n=(X[_Nn]-b_n)/a_n ? Y'. Results given subsume random index limit theorems for convergence to Brownian motion, stable processes and extremal processes.     

Limiting distributions of functionals of Markov chains

Let \s{X_n, n ? 0\s} and \s{Y_n, n ? 0\s} be two stochastic processes such that Y_n depends on X_n in a stationary manner, i.e. P(Y_n ? A\vbX_n) does not depend on n. Sufficient conditions are derived for Y_n to have a limiting distribution. If X_n is a Markov chain with stationary transition probabilities and Y_n = f(X_n,..., X_n+k) then Y_n depends on X_n is a stationary way. Two situations are considered: (i) \s{X_n, n ? 0\s} has a limiting distribution (ii) \s{X_n, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times.     

Computing Lyapunov constants for random recurrences with smooth coefficients

In recent years, there has been much interest in the growth and decay rates (Lyapunov constants) of solutions to random recurrences such as the random Fibonacci sequence x_n+1=±x_n±x_n−1. Many of these problems involve nonsmooth dynamics (nondifferentiable invariant measures), making computations hard. Here, however, we consider recurrences with smooth random coefficients and smooth invariant measures. By computing discretised invariant measures and applying Richardson extrapolation, we can compute Lyapunov constants to 10 digits of accuracy. In particular, solutions to the recurrence x_n+1=x_n+c_n+1x_n−1, where the {c_n} are independent standard normal variables, increase exponentially (almost surely) at the asymptotic rate (1.0574735537…)ⁿ. Solutions to the related recurrences x_n+1=c_n+1x_n+x_n−1 and x_n+1=c_n+1x_n+d_n+1x_n−1 (where the {d_n} are also independent standard normal variables) increase (decrease) at the rates (1.1149200917…)ⁿ and (0.9949018837…)ⁿ, respectively.     

A trichotomy for a class of equivalence relations

Let Xn, n ∈ N be a sequence of non-empty sets, ψn : Xn2 → IR+. We consider the relation E = E((Xn, ψn)n∈N) on ∏n∈N Xn by (x, y) ∈ E((Xn, ψn)n∈N) <=>Σn∈Nψn(x(n), y(n)) < +∞. If E is an equiv- alence relation and all ψn, n ∈ N, are Borel, we show a trichotomy that either IRN/e1≤B E, E1≤B E, or E≤B E0. We also prove that, for a rather general case, E((Xn, ψn)n∈N) is an equivalence relation iff it is an ep-like equivalence relation.     

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.     

Bases for some reciprocity algebras II

We construct bases for the stable branching algebras for the symmetric pairs (GL_n,O_n), (O_n+m,O_n×O_m) and (Sp_2n,GL_n).     

Support convergence in the single ring theorem

We study the eigenvalues of non-normal square matrices of the form A _n ?=?U _n T _n V _n with U _n , V _n independent Haar distributed on the unitary group and T _n real diagonal. We show that when the empirical measure of the eigenvalues of T _n converges, and T _n satisfies some technical conditions, all these eigenvalues lie in a single ring.     

The asymptotic stability of difference equations

In this paper, the linear delay difference equation x_n+1 −x_n = −a_nx_n−k, where a_n ≥ 0 (n ≥ 0) any nonnegative coefficient sequence, is considered and its stability properties are investigated. The obtained result is extended to the nonlinear difference equation x_n+1 − x_n = f_n(x_n−k).     

Sequences of Diophantine approximations

We sharpen a technique of Gelfond to show that, in a sense, the only possible gap-free sequences of “good” Diophantine approximations to a fixed α ∈ C are trivial ones. For example, suppose that a > 1 and that (δ_n)_n=1^∞ and (σ_n)_n=1^∞ are two positive, strictly increasing unbounded sequences satisfying δ_n+1 ≤ aδ_n and σ_n+1 ≤ aσ_n. If there is a sequence of nonzero polynomials P_n ∈ Z[x] with deg P_n ≤ δ_n, deg P_n + log height P_n ≤ σ_n, and ∣P_n(α)∣ ≤ e^{?(2a+1)δ_nσ_n}, then each P_n(α) = 0.     

Improved error estimates for the perturbed Galerkin method applied to a class of generalized eigenvalue problems

We consider the generalized eigenvalue problem x-Kx = μBx in a complex Banach space E. Here, K and B are bounded linear operators, B is compact, and 1 is not in the spectrum of K. If {E_n: n = 1, 2,…} is a sequence of closed subspaces of E and P_n: E → E_n is a linear projection which maps E onto E_n, then we consider the sequence of approximate eigenvalue problems {x_n - P_nKx_n = μP_nBx_n in E_n: n = 1, 2,…}. Assuming that ∥K-P_nK∥ → 0 and t|B-P_nB∥ → 0 as n → ∞, we prove the convergence of sequences of eigenvalues and eigenelements of the approximate eigenvalue problem to eigenvalues and eigenelements of the original eigenvalue problem, and establish upper bounds for the errors. These error bounds are sharper than those given by Vainikko in Ref. 2 for the more general problem x = μTx in E, T linear and compact, and the sequence of approximate problems {x_n = μT_nx_n in E_n: n = 1, 2,…}, and do not involve the operator S_n = T_n-P_nT ∥;E_n.     

The algebra of one-sided inverses of a polynomial algebra

We study in detail the algebra S_n in the title which is an algebra obtained from a polynomial algebra P_n in n variables by adding commuting, left (but not two-sided) inverses of the canonical generators of P_n. The algebra S_n is non-commutative and neither left nor right Noetherian but the set of its ideals satisfies the a.c.c., and the ideals commute. It is proved that the classical Krull dimension of S_n is 2n; but the weak and the global dimensions of S_n are n. The prime and maximal spectra of S_n are found, and the simple S_n-modules are classified. It is proved that the algebra S_n is central, prime, and catenary. The set I_n of idempotent ideals of S_n is found explicitly. The set I_n is a finite distributive lattice and the number of elements in the set I_n is equal to the Dedekind number d_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.