Enumeration of sequences of given specification according to rises,falls and maxima

Letn = (a₁.a₂ … a_N) denote a sequence of integers a_i={1.2.…n}. A rise is a part a_i.a_i+1 with a_i <a_i+1: a fall is a pair with a_ia_i+1: a level is a pair with a_i = a_i+1. A maximum is a triple a_i-1.a_ia_i+1 with a_i-1?a_i.a_i?a_i+1. If e_i is the number of a_j?n witha_j = i, then [e₁…e_n] is called the specification of n. In addition, a conventional rise is counted to the left of a₁ and a conventional fall to the right of a_N: ifa₁?a₂, then a₁ is counted as a conventional maximum, similarly if a_N-1 ? a_N thena_N is a conventional maximum. Simon Newcomb's problem is to find the number of sequences n with given specification and r rises; the refined problem of determining the number of sequences of given specification with r rises and s falls has also been solved recently. The present paper is concerned with the problem of finding the number of sequences of given specification with r rises, s falls. λ levels and λ maxima. A generating function for this enumerant is obtained as the quotient of two continuants. In certain special cases this result simplifies considerably.     

Weighted rational approximation in the complex plane

Given a triple (G, W, γ) of an open bounded set G in the complex plane, a weight function W(z) which is analytic and different from zero in G, and a number γ with 0 ≤ γ ≤ 1, we consider the problem of locally uniform rational approximation of any function ƒ(z), which is analytic in G, by weighted rational functions W^m_i+n_i(z)R_mi, n_i(z)_{i = 0}^∞, where R_mi, n_i(z) = P_mi(z)/Q_ni(z) with deg P_mi ≤ m_i and deg Q_ni ≤ n_i for all i ≥ 0 and where m_i + n_i → ∞ as i → ∞ such that lim m_i/[m_i + n_i] = γ. Our main result is a necessary and sufficient condition for such an approximation to be valid. Applications of the result to various classical weights are also included.     

Homology of certain algebras defined by graphs

Let K(G) for a finite graph G with vertices v₁,...,v_n denote the K-algebra with generators X₁,...,X_n and defining relations X_iX_j=X_jX_i if and only if v_i is not connected to v_j by an edge in G. We describe centralizers of monomials, show that the centralizer of a monomial is again a graph algebra, prove a unique factorization theorem for factorizations of monomials into commuting factors, compute the homology of K(G), and show that K(G) is the homology ring of a certain loop space. We also construct a K(π, 1) explicitly where π is the group with generators X₁,...,X_n and defining relations X_iX_j=X_jX_i if and only if v_i is not connected to v_j by an edge in G.     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

An approximate approach of global optimization for polynomial programming problems

Many methods for solving polynomial programming problems can only find locally optimal solutions. This paper proposes a method for finding the approximately globally optimal solutions of polynomial programs. Representing a bounded continuous variable x_i as the addition of a discrete variable d_i and a small variable ϵ_i, a polynomial term x_ix_i can be expanded as the sum of d_ix_j, d_jϵ_i; and ϵ_iϵ_j. A procedure is then developed to fully linearize d_ix_j and d_je_i, and to approximately linearize ϵ_iϵ_j with an error below a pre-specified tolerance. This linearization procedure can also be extended to higher order polynomial programs. Several polynomial programming examples in the literature are tested to demonstrate that the proposed method can systematically solve these examples to find the global optimum within a pre-specified error.     

An addition theorem for finite Abelian groups

If g₁, g₂, …, g_2n?1 is a sequence of 2n ? 1 elements in an Abelian group G of order n, it is known that there are n distinct indices i₁, i₂, …, i_n such that 0 = g_i1 + g_i2 + ? + g_in. In this paper a suitably general condition on the sequence is given which insures that every element g in G has a representation g = g_i1 + g_i2 + ? + g_in as the sum of n terms of the sequence.     

On a nonlinear p-adic dynamical system

We investigate the behavior of trajectories of a (3, 2)-rational p-adic dynamical system in the complex p-adic field ? _p , when there exists a unique fixed point x ₀. We study this p-adic dynamical system by dynamics of real radiuses of balls (with the center at the fixed point x ₀). We show that there exists a radius r depending on parameters of the rational function such that: when x ₀ is an attracting point then the trajectory of an inner point from the ball U _r (x ₀) goes to x ₀ and each sphere with a radius > r (with the center at x ₀) is invariant; When x ₀ is a repeller point then the trajectory of an inner point from a ball U _r (x ₀) goes forward to the sphere S _r (x ₀). Once the trajectory reaches the sphere, in the next step it either goes back to the interior of U _r (x ₀) or stays in S _r (x ₀) for some time and then goes back to the interior of the ball. As soon as the trajectory goes outside of U _r(x ₀) it will stay (for all the rest of time) in the sphere (outside of U _r(x ₀)) that it reached first.     

On the existence of super P-groups

A finite group (G, ·) is said to be sequenceable if its elements can be arranged in a sequence a₀ = e, a₁, a₂,…, a_n?1 in such a way that the partial products b₀ = a₀, b₁ = a₀a₁, b₂ = a₀a₁a₂,…, b_n?1 = a₀a₁a₂ ··· a_n?1 are all distinct (and consequently are the elements of G in a new order). It is said to be R-sequenceable if its elements can be ordered in such a way that the partial products b₀ = a₀, b₁ = a₀a₁, b₂ = a₀a₁a₂,…, b_n?2 = a₀a₁a₂ ··· a_n?2 are all different and so that b_n?1 = a₀a₁a₂ ··· a_n?1 = b₀ = e. (in the first case, the ordering a₀,a₁,…,a_n?1 of the elements is said to be a sequencing of G and, in the second case, an R-sequencing of G.) It is a super P-group if every element of one particular coset hG′ of the derived group can be expressed as the product of the n elements of G in such a way that the orderings of the elements in these products are sequencings of G with the exception that, in the case that h = e, the element e of G′ must be expressed as a product of the n elements of G which forms an R-sequencing of G. It is proved that every non-Abelian group of order pq such that p has 2 as a primitive root, where p and q are distinct odd primes with p < q, is a super P-group. Also provided is evidence for the conjectures that all Abelian groups and all dihedral groups of doubly even order (except those of orders 4 and 8) are super P-groups.     

Quasi-monotone mappings on θn-continua

A continuous function f from a continuum X onto a continuum Y is quasi-monotone if, for every subcontinuum M of Y with nonvoid interior, f^-1(M) has a finite number of components each of which is mapped onto M by f. A θ_n-continuum is one that no subcontinuum separates into more than n components. It is known that if f is quasi-monotone and X is a θ₁-continuum, then Y is a θ₁-continuum or a θ₂-continuum that is irreducible between two points. Examples are given to show that this cannot be generalized to a θ_n-continuum and n + 1 points for any n >1, but it is proved that if f is quasi-monotone and X is a θ_n-continuum, then Y is a θ_n-continuum or a θ_n+1-continuum that is the union of n + 2 continua H,S₁,S₂,…,S_n+1, whe for each i, S_i is the closure of a component of Y H, S_i is irreducible from some point P_i to H, and H is irreducible about its boundary. Some theorems and examples are given concerning the preservation of decomposition elements by a quasi-monotone map defined on a θ_n-continuum that admits a monotone, upper-semicontinuous decomposition onto a finite graph.     

Existence of Tchebycheff extensions

Given a Tchebycheff System {y_o ··· y_n} defined on an interval I, it is proved that there exists a function y_n+1, such that the system {y_o ··· y_n, y_n+1} is a Tchebycheff System on I. A function such as y_n+1 is called a Tchebycheff extension of the system {y_i}ⁿ_{(i = 0)}.     

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.     

The Erd?s-Ginzburg-Ziv theorem for dihedral groups

Let n≥23 be an integer and let D_2n be the dihedral group of order 2n. It is proved that, if g₁,g₂,…,g_3n is a sequence of 3n elements in D_2n, then there exist 2n distinct indices i₁,i₂,…,i_2n such that g_i1g_i2?g_i2n=1. This result is a sharpening of the famous Erd?s-Ginzburg-Ziv theorem for G=D_2n.     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.     

An explicit expression for the cost of a class of Huffman trees

Let T_n denote a binary tree with n terminal nodes V={υ₁,…,υ_n} and let l_i denote the path length from the root to υ_i. Consider a set of nonnegative numbers W={w₁,…,w_n} and for a permutation π of {1,…,n} to {1,…,n}, associate the weight w_i to the node υ_π(i). The cost of T_n is defined as C(T_n∣W)=Min_π∑ⁿ_i=1w_il_π(i).A Huffman tree H_n is a binary tree which minimizes C(T_n∣W) over all possible T_n. In this note, we give an explicit expression for C(H_n∣W) when W assumes the form: w_i=k for i=1,…,n?m; w_i=x for i=n?m+1,…,n. This simplifies and generalizes earlier results in the literature.     

Nonzero decomposable symmetrized tensors

Suppose k₁ ? ? ? k_t ? 1, m₁ ? ?? m_r ? 1, k₁+ ? +k_t = m₁+ ? +m_r = m. Let λ=(k₁,…,k_t) be a character of the symmetric group S_m. The restriction of λ to S_m1X…XS_mr contains the principal character as a component if and only if λ majorizes (m₁,…,m_r). This result is used to characterize the index set of the nonzero decomposable symmetrized tensors, corresponding to S_m and λ, which are induced from a basis of the underlying vector space.     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

On indecomposable subcones

Let K₁,K₂ be cones. We say that K₁ is a subcone of K₂ if ExtK₁?ExtK₂. Furthermore, if K₁≠K₂, K₁ is called a proper subcone; if dimK₁=dimK₂, K₁ is called a non-degenerate subcone. We first prove that every n-dimensional indecomposable cone, n?3, contains a non-degenerate indecomposable subcone which has no more than 2n-2 extremals. Then we construct for each n?3 an n-dimensional indecomposable cone with exactly 2n-2 extremals such that each of its proper non-degenerate subcones is decomposable.     

A note on tunnel number of composite knots

Let K be a knot in a sphere S³. We denote by t(K) the tunnel number of K. For two knots K₁ and K₂, we denote by K₁?K₂ the connected sum of K₁ and K₂. In this paper, we will prove that if one of K₁ and K₂ has high distance while the other has distance at least 3 then t(K₁?K₂)=t(K₁)+t(K₂)+1.     

Tension-flow polynomials on graphs

An orientation of a graph is acyclic (totally cyclic) if and only if it is a “positive orientation” of a nowhere-zero integral tension (flow). We unify the notions of tension and flow and introduce the so-called tension-flows so that every orientation of a graph is a positive orientation of a nowhere-zero integral tension-flow. Furthermore, we introduce an (integral) tension-flow polynomial, which generalizes the (integral) tension and (integral) flow polynomials. For every graph G, the tension-flow polynomial F_G(k₁,k₂) on G and the Tutte polynomial T_G(k₁,k₂) on G satisfy F_G(k₁,k₂)⩽T_G(k₁−1,k₂−1). We also characterize the graphs for which the inequality is sharp.     

Ramsey regions

Let (T₁,T₂,…,T_c) be a fixed c-tuple of sets of graphs (i.e. each T_i is a set of graphs). Let R(c,n,(T₁,T₂,…,T_c)) denote the set of all n-tuples, (a₁,a₂,…,a_n), such that every c-coloring of the edges of the complete multipartite graph, K_a1,a2,…,an, forces a monochromatic subgraph of color i from the set T_i (for at least one i). If N denotes the set of non-negative integers, then R(c,n,(T₁,T₂,…,T_c))⊆Nⁿ. We call such a subset of Nⁿ a “Ramsey region”. An application of Ramsey's Theorem shows that R(c,n,(T₁,T₂,…,T_c)) is non-empty for n?0. For a given c-tuple, (T₁,T₂,…,T_c), known results in Ramsey theory help identify values of n for which the associated Ramsey regions are non-empty and help establish specific points that are in such Ramsey regions. In this paper, we develop the basic theory and some of the underlying algebraic structure governing these regions.