Upper bound for the alternation number of a torus knot

We give an upper bound for the alternation number of a torus knot which is of either 3-, 4-, or 5-braid or of other special types. Using the inequality relating the alternation number, signature, and Rasmussen s-invariant, discovered by Abe, we determine the alternation numbers of the torus knots T(3,l), , and T(4,5). Also, for any positive integer k we construct infinitely many 3-braid knots with alternation number k.     

Unbordered partial words

An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word u can be written as a concatenation of nonempty prefixes of a word v, then u can be written as a unique concatenation of nonempty unbordered prefixes of v. We study the properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any).     

Upper bound multigraphs for posets

The study of upper bound graphs of posets can be extended naturally to multigraphs. This paper characterizes such upper bound multigraphs, shows they determine the associated posets up to isomorphism, and extends results of D. Scott to characterize posets having chordal or interval upper bound multigraphs.Research partially supported by Office of Naval Research contract N00014-88-K-0163.     

Generalized periodicity and primitivity for words

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n ² is a lower bound and this is optimal in two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Count of primitive words

Abstract. The present paper concerns with the formula of the count of primitive words and ex-changeable primitive words.     

Testing primitivity on partial words

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program.     

Upper bound of weak-limitation for the Gross-Pitaevskii equation

This paper is concerned with the blow-up solutions of Gross-Pitaevskii equation. We obtain the upper bound of weak-limitation for the blow-up solutions by using the method of Cazenave (2003) [3] as well as the concentration compact principle.     

An upper bound for the number of matroids

An upper bound for the number of matroids is obtained. This upper bound complements the lower bound obtained by Piff and Welsh in [1].     

Upper bound theorems for homology manifolds

In this paper we prove the Upper Bound Conjecture (UBC) for some classes of (simplicial) homology manifolds: we show that the UBC holds for all odd-dimensional homology manifolds and for all 2k-dimensional homology manifolds Δ such that β _k (Δ)⩽Σ{β _i (Δ):i ≠k-2,k,k+2 and 1 ⩽i⩽2k-1}, where β _i (Δ) are reduced Betti numbers of Δ. (This condition is satisfied by 2k-dimensional homology manifolds with Euler characteristic χ≤2 whenk is even or χ≥2 whenk is odd, and for those having vanishing middle homology.) We prove an analog of the UBC for all other even-dimensional homology manifolds. Kuhnel conjectured that for every 2k-dimensional combinatorial manifold withn vertices, . We prove this conjecture for all 2k-dimensional homology manifolds withn vertices, wheren≥4k+3 orn≤3k+3. We also obtain upper bounds on the (weighted) sum of the Betti numbers of odd-dimensional homology manifolds.     

On the number of repetition-free words

A well-known problem is studied of the number of repetition-free words of the two types: the square-free words over a three-letter alphabet and the cube-free words over a two-letter alphabet.     

Unbordered factors and Lyndon words

A primitive word w is a Lyndon word if w is minimal among all its conjugates with respect to some lexicographic order. A word w is bordered if there is a nonempty word u such that w=uvu for some word v. A right extension of a word w of length n is a word wu where all factors longer than n are bordered. A right extension wu of w is called trivial if there exists a positive integer k such that w^k=uv for some word v.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word w which has a nontrivial right extension of length 2|w|-2.     

The number of binary cube-free words of length up to 47 and their numerical analysis

An analog of the work of Noonan and Zeilberger on square-free ternary words given for the case of cube-free binary words. As in their work, the Goulden-Jackso Cluster Method is used to derive a rigorous upper bound, as well as a non-rigorot estimate, for the limit of thenth roots of the terms. The Maple implementatin of the work is available from this paper's website www.math.temple. edu/`anne/cut free.html.     

Upper bound for transversals of tripartite hypergraphs

We prove 2 7/9v for 3-partite hypergraphs. (This is an improvement of the trivial bound 3v.)