Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

On the uniqueness of embedding a residual design

We prove that if a residual $\text{2-(k(k+λ?1)}\text{λ,k,λ)}$ design R has more than one embedding into a symmetric design then k ? λ(λ?1)². If equality holds then R has exactly two embeddings and the corresponding derived design is in both cases λ ? 1 identical copies of the design of points and lines of PG(3, λ ? 1). Using the main proposition from which these results follow we also prove that if a symmetric2-(v,k, λ) design has an axial non-central or central non-axial automorphism then k?λ(λ² ? 2λ + 2).     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

The inverse of a matrix polynomial

An explicit representation is obtained for P(z)^?1 when P(z) is a complex n×n matrix polynomial in z whose coefficient of the highest power of z is the identity matrix. The representation is a sum of terms involving negative powers of z?λ for each λ such that P(λ) is singular. The coefficients of these terms are generated by sequences u_k, v_k of 1×n and n×1 vectors, respectively, which satisfy u₁≠0, v₁≠0, ∑^k?1_h=0(1?h!)u_k?hP^(h)(λ)=0, ∑^k?1_h=0(1?h!)P^(h)(λ)v_k?h=0, and certain orthogonality relations. In more general cases, including that when P(z) is analytic at λ but not necessarily a polynomial, the terms in the representation involving negative powers of z?λ provide the principal part of the Laurent expansion for P(z)^?1 in a punctured neighborhood of z=λ.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

Sard's theorem for mappings in Hölder and Sobolev spaces

We prove various generalizations of classical Sard's theorem to mappings f:M ^m →N ⁿ between manifolds in Hölder and Sobolev classes. It turns out that if f ∈ C ^k,λ (M ^m ,N ⁿ ), then—for arbitrary k and λ—one can obtain estimates of the Hausdorff measure of the set of critical points in a typical level set f ^?1(y). The classical theorem of Sard holds true for f ∈ C ^k with sufficiently large k, i.e., k>max(m?n,0); our estimates contain Sard's theorem (and improvements due to Dubovitskii and Bates) as special cases. For Sobolev mappings between manifolds, we describe the structure of f ^?1(y).     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Degenerate orbits of adjoint representation of orthogonal and unitary groups regarded as algebraic submanifolds

We suggest a method for describing some types of degenerate orbits of orthogonal and unitary groups in the corresponding Lie algebras as level surfaces of a special collection of polynomial functions. This method allows one to describe orbits of the types SO(2n)/SO(2k)×SO(2) ^n?k , SO(2n+1)/SO(2k+1)×SO(2) ^n?k , and (S)U(n)/(S)(U(2k)×U(2) ^n?k ) in so(2n), so(2n+1), and (s)u(n), respectively. In addition, we show that the orbits of minimal dimensions of the groups under consideration can be described in the corresponding algebras as intersections of quadries. In particular, this approach is used for describing the orbit CP ^n?1?u(n).     

Elliptic equation with a singular potential in a domain with a conic point

This paper deals with the behavior of the nonnegative solutions of the problem $$- \Delta u = V(x)u, \left. u \right|\partial \Omega = \varphi (x)$$ in a conical domain Ω ? ? ⁿ , n ≥ 3, where 0 ≤ V (x) ∈ L₁(Ω), 0 ≤ ?(x) ∈ L₁(?Ω) and ?(x) is continuous on the boundary ?Ω. It is proved that there exists a constant C _*(n) = (n ? 2)²/4 such that if V ₀(x) = (c + λ ₁)|x|^?2, then, for 0 ≤ c ≤ C _*(n) and V(x) ≤ V ₀(x) in the domain Ω, this problem has a nonnegative solution for any nonnegative boundary function ?(x) ∈ L ₁(?Ω); for c > C _*(n) and V(x) ≥ V ₀(x) in Ω, this problem has no nonnegative solutions if ?(x) > 0.     

The number of large prime divisors of consecutive integers

Let ?(N) > 0 be a function of positive integers N and such that ?(N) → 0 and N^?(N) → ∞ as N → + ∞. Let Nν_N(n:…) be the number of positive integers n ≤ N for which the property stated in the dotted space holds. Finally, let g(n; N, ?, z) be the number of those prime divisors p of n which satisfy N^Z?(N) ? p ? N^?(N), 0 < z < 1 In the present note we show that for each k = 0, ±1, ±2,…, as N → ∞, limv_N(n : g(n; N, ?, z) ? g(n + 1; N, ?z) = k) exists and we determine its actual value. The case k = 0 induced the present investigation. Our solution for this value shows that the natural density of those integers n for which n and n + 1 have the same number of prime divisors in the range (1) exists and it is positive.     

Some combinatorial properties of hook lengths, contents, and parts of partitions

The main result of this paper is a generalization of a conjecture of Guoniu Han, originally inspired by an identity of Nekrasov and Okounkov. Our result states that if F is any symmetric function (say over ?) and if $$\Phi_n(F)=\frac{1}{n!}\sum_{\lambda\vdash n}f_\lambda^2F(h_u^2:u\in\lambda),$$ where h _u denotes the hook length of the square u of the partition λ of n and f _λ is the number of standard Young tableaux of shape λ, then Φ _n (F) is a polynomial function of n. A similar result is obtained when F(h _u ² :u∈λ) is replaced with a function that is symmetric separately in the contents c _u of λ and the shifted parts λ _i +n?i of λ.     

Further gossip problems

n people have distinct bits of information. They can communicate via k-party conference calls. How many such calls are needed to inform everyone of everyone else's information? Let f(n,k) be this minimum number. Then we give a simple proof that f(n,k)= [(n?k)(k?1)]+[nk] for 1?n?k², f(n,k)=2[(n?k)(k?1)] for n>k².In the 2-party case we consider the case in which certain of the calls may permit information flow in only one direction. We show that any 2n-4 call scheme that conveys everone's information to all must contain a 4-cycle, each of whose calls is “two way”, along with some other results. The method follows that of Bumby who first proved the 4-cycle conjecture.     

Ranges of certain functionals in classes of regular functions

LetP _κ,n (λ,β) be the class of functions \(g(z) = 1 + \sum\nolimits_{v = n}^\infty {c_\gamma z^v }\) , regular in ¦z¦<1 and satisfying the condition $$\int_0^{2\pi } {\left| {\operatorname{Re} \left[ {e^{i\lambda } g(z) - \beta \cos \lambda } \right]} \right|} /\left( {1 - \beta } \right)\cos \lambda \left| {d\theta \leqslant \kappa \pi ,} \right.z = re^{i\theta } ,$$ , 0 < r < 1 (κ?2,n?1, 0?Β<1, -π<λ<π/2;M _κ,n (λ,β,α),n?2, is the class of functions \(f(z) = z + \sum\nolimits_{v = n}^\infty {a_v z^v }\) , regular in¦z¦<1 and such thatF _α(z)∈P _κ,n?1(λ,β), where \(F_\alpha (z) = (1 - \alpha )\frac{{zf'(z)}}{{f(z)}} + \alpha (1 + \frac{{zf'(z)}}{{f'(z)}})\) (0?α?1). Onr considers the problem regarding the range of the system {g ^(v?1)(z_?)/(v?1)!}, ?=1,2,...,m,v=1,2,...,N _?, on the classP _κ,1(λ,β). On the classesP _κ,n (λ,β),M _κ,n (λ,β,α) one finds the ranges of C_v, v?n, a_m, n?m?2n-2, and ofg(?),F _?(?), 0<¦ξ¦<1, ξ is fixed.     

On the enumeration of skew Young tableaux

For fixed n and a fixed partition α of k<n we give an explicit formula for the number N(n;α) of standard skew Young tableaux with n squares and shape λ/α for some λ. From this formula the entire asymptotic expansion of N(n;α) as n→∞ can in principle be computed, generalizing recent work of McKay, Morse, and Wilf. We also give asymptotic formulas for the number f^λ/α of standard skew Young tableaux of shape λ/α for α fixed and λ “large.”     

Hamiltonicity, independence number, and pancyclicity

A graph on n vertices is called pancyclic if it contains a cycle of length ? for all 3≤?≤n. In 1972, Erd?s proved that if G is a Hamiltonian graph on n>4k⁴ vertices with independence number k, then G is pancyclic. He then suggested that n=Ω(k²) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n>ck^7/3 suffices.     

Chain sequences and symmetric generalized orthogonal polynomials

In this paper, we derive an explicit expression for the parameter sequences of a chain sequence in terms of the corresponding orthogonal polynomials and their associated polynomials. We use this to study the orthogonal polynomials K_n^(λ,M,k) associated with the probability measure dφ(λ,M,k;x), which is the Gegenbauer measure of parameter λ+1 with two additional mass points at ±k. When k=1 we obtain information on the polynomials K_n^(λ,M) which are the symmetric Koornwinder polynomials. Monotonicity properties of the zeros of K_n^(λ,M,k) in relation to M and k are also given.     

Some inverse results for Hill's equation

We consider Hill's equation y″+(λ−q)y=0 where q∈L¹[0,π]. We show that if l_n—the length of the n-th instability interval—is of order O(n^−(k+2)) then the real Fourier coefficients a_n^k,b_n^k of q^(k)—k-th derivative of q—are of order O(n⁻²), which implies that q^(k) is absolutely continuous almost everywhere for k=0,1,2,….     

On the summability factors of infinite series

The author has established that if [λ_n] is a convex sequence such that the series Σn ^-1λ_n is convergent and the sequence {K _n} satisfies the condition |K _n|=O[log(n+1)]^k(C, 1),k?0, whereK _n denotes the (R, logn, 1) mean of the sequence {n log (n+1)a _n}, then the series Σlog(n+1)^1-kλ_n a _n is summable |R, logn, 1|. The result obtained for the particular casek=0 generalises a previous result of the author [1].     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.