Subsequence numbers and logarithmic concavity

Let S be a finite sequence of length r whose terms come from the finite alphabet a. The subsequence number of S (i = 0…r) is the number of distinct t-long subsequences of S. We prove (1) for r and a fixed, the S simultaneously attain their maximum possible values if and only if S is a repeated permutation of a (meaning no letters appears twice in S without all of the other letters of a intervening): (2) the numbers S…S……S, are logarithmically concave: and (3) over any central interval S…S……S…(iSr ? i). S, is least (through perhaps not uniquely). In addition, we show that for the generalized binomial coefficients c(i.j.n) defined by (1+x+…+ x^m?1)¹ = Σc(i.j.n)x¹, the sequence c(i ? 1.1.n), c(i?2.2n)… is strongly logarithmically concave, thus extending a result of S.M. Tanny and M. Zuker. Logarithmic concavity is treated in the context of triangular arrays of numbers.     

The method of asymptotic stabilization to a given trajectory based on a correction of the initial data

Let S be an operator in a Banach space H and S ⁱ (u) (i = 0, 1, ..., u ∈ H) be the evolutionary process specified by S. The following problem is considered: for a given point z ₀ and a given initial condition a ₀, find a correction l such that the trajectory {S ⁱ (a ₀ + l)} approaches }S ⁱ (z ₀)} for 0 < i ≤ n. This problem is reduced to projecting a ₀ on the manifold ?^?(z ₀, f ⁽ⁿ⁾) defined in a neighborhood of z ₀ and specified by a certain function f ⁽ⁿ⁾. In this paper, an iterative method is proposed for the construction of the desired correction u = a ₀ + l. The convergence of the method is substantiated, and its efficiency for the blow-up Chafee-Infante equation is verified. A constructive proof of the existence of a locally stable manifold ?^?(z ₀, f) in a neighborhood of a trajectory of hyperbolic type is one of the possible applications of the proposed method. For the points in ?^?(z ₀, f), the value of n can be chosen arbitrarily large.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

A symmetry relationship for a class of partitions

Let S(n, k, v) denote the number of vectors (a₀,…, a_n?1) with nonnegative integer components that satisfy a₀ + … + a_{n ? 1} = k and Σ_i=0^n?1ia_i ≡ v (mod n). Two proofs are given for the relation S(n, k, v) = S(k, n, v). The first proof is by algebraic enumeration while the second is by combinatorial construction.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

Generalized euler-type partition identities

Let A and S be subsets of the natural numbers. Let A′(n) be the number of partitions of n where each part appears exactly m times for some m?A. Let S(n) be the number of partitions of n into parts which are elements of S.     

Inclusion relations involving k-numerical ranges

Let W_k(A) denote the k-numerical range of an n × n matrix A. It is known that W_i(A) ? W_j(A) for 1 ? j? i? n. It this paper we derive more general inclusion relations of the form Σⁿ_iλ_iW_i(A) ? Σⁿ_iμ_iW_i(A), where λ_i, μ_i are real coefficients.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

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

On an additive representation function

Let A be an infinite subset of natural numbers, and X a positive real number. Let r(n) denotes the number of solution of the equation n=a₁+a₂ where a₁?a₂ and a₁, a₂∈A. Also let |A(X)| denotes the number of natural numbers which are less than or equal to X and belong to A. For those A which satisfy the condition that for all sufficiently large natural numbers n we have r(n)≠1, we improve the lower bound of |A(X)| given by Nicolas et. al. [NRS98]. The bound which we obtain is essentially best possible.     

Lower bound inequalities for norms of symmetrized tensor powers

Let V be a complex inner product space of positive dimension m with inner product 〈·,·〉, and let T_n(V) denote the set of all n-linear complex-valued functions defined on V×V×?×V (n-copies). By S_n(V) we mean the set of all symmetric members of T_n(V). We extend the inner product, 〈·,·〉, on V to T_n(V) in the usual way, and we define multiple tensor products A₁⊗A₂⊗?⊗A_n and symmetric products A₁·A₂?A_n, where q₁,q₂,…,q_n are positive integers and A_i∈T_qi(V) for each i, as expected. If A∈S_n(V), then A^k denotes the symmetric product A·A?A where there are k copies of A. We are concerned with producing the best lower bounds for ‖A^k‖², particularly when n=2. In this case we are able to show that ‖A^k‖² is a symmetric polynomial in the eigenvalues of a positive semi-definite Hermitian matrix, M_A, that is closely related to A. From this we are able to obtain many lower bounds for ‖A^k‖². In particular, we are able to show that if ω denotes 1/r where r is the rank of M_A, and , then

     

The p-Regular Partition Function Modulo p

Let b_?(n) denote the number of ?-regular partitions of n, where ? is a positive power of a prime p. We study in this paper the behavior of b_?(n) modulo powers of p. In particular, we prove that for every positive integer j, b_?(n) lies in each residue class modulo p^j for infinitely many values of n.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

The chromatic number of 5-valent circulants

A circulant C(n;S) with connection set S={a₁,a₂,…,a_m} is the graph with vertex set Z_n, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

On separable Lindenstrauss spaces

Isometric embeddings from l_∞ⁿin l_∞^{n + 1} can be described by a_i,n, i ? n, with $\text{∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{¦ a}{}_{\mathrm{i,n}}\text{¦ ? 1}$, such that e_i,n = e_{i,n + 1} + a_i,ne_{n + 1,n + 1}; i = 1,…, n; holds, where e_i,nand e_{i,n + 1} are the elements of the canonical unit vector bases of l_∞ⁿand l_∞^{n + 1}, respectively (negative signs may occur). We study the connections between a triangular substochastic matrix A, whose nth column consists of the elements a_i,n, i = 1,…, n, and the Banach space a_i,n, E_n ? E_{n + 1}, E_n ? l_∞ⁿ, where A determines the embeddings of the E_n. The class of these Banach spaces is the class of all separable Lindenstrauss spaces. Sufficient and necessary conditions are stated for a matrix A to represent c₀and c. Furthermore, we characterize the class of all extreme triangular substochastic matrices which represents C(K), where K is the Cantor set. We investigate how the special biface structure of the dual unit ball of X is reflected in the elements of a matrix A representing the separable Lindenstrauss space X. This is applicable to Gurarij spaces; we give a new proof for the maximality property of Gurarij spaces and show that they are isomorphic to A(S) where S is a Choquet simplex with dense extreme points.     

Divisibility Graph for Symmetric and Alternating Groups

Let X be a nonempty set of positive integers and X* = X?{1}. The divisibility graph D(X) has X* as the vertex set, and there is an edge connecting a and b with a, b ∈ X* whenever a divides b or b divides a. Let X = cs(G) be the set of conjugacy class sizes of a group G. In this case, we denote D(cs(G)) by D(G). In this paper, we will find the number of connected components of D(G) where G is the symmetric group S _n or is the alternating group A _n .     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.