On sorting by 3-bounded transpositions

Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better.We show that to sort any permutation via correcting hops and skips, ⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H_n of those permutations of S_n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G_n⊆S_n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.     

The number of reachable pairs in a digraph

For a digraph G, let R(G) (respectively, R^(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range S_n of R(G) and the range of R^(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to S_n. These determine the set S_n for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)^0.57+2, for arbitrary k.     

On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

For a given permutation matrix P, let fP(n) be the maximum number of 1-entries in an n×n(0,1)-matrix avoiding P and let SP(n) be the set of all n×n permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that cP:=limn→∞fP(n)/n is finite, while the Stanley-Wilf conjecture asserts that is finite.In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture.We focus on the values of the Stanley-Wilf limit (sP) and the Füredi-Hajnal limit (cP). We improve the reduction and obtain which decreases the general upper bound on sP from sP?constconstO(klog(k)) to sP?constO(klog(k)) for any k×k permutation matrix P. In the opposite direction, we show .For a lower bound, we present for each k a k×k permutation matrix satisfying cP=Ω(k²).     

Asymptotic bounds for permutations containing many different patterns

We say that a permutation σ∈Sn contains a permutation π∈Sk as a pattern if some subsequence of σ has the same order relations among its entries as π. We improve on results of Wilf, Coleman, and Eriksson et al. that bound the asymptotic behavior of pat(n), the maximum number of distinct patterns of any length contained in a single permutation of length n. We prove that by estimating the amount of redundancy due to patterns that are contained multiple times in a given permutation. We also consider the question of k-superpatterns, which are permutations that contain all patterns of a given length k. We give a simple construction that shows that Lk, the length of the shortest k-superpattern, is at most . This may lend evidence to a conjecture of Eriksson et al. that .     

Reconstruction of permutations distorted by reversal errors

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group Sym_n generated by reversals. It is shown that for any n?3 an arbitrary permutation π is uniquely reconstructible from four distinct permutations at reversal distance at most one from π where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability p₃→1 and from two permutations with a probability as n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least erroneous patterns are required in order to reconstruct an arbitrary permutation.     

The Riemannian product structures of spacelike hypersurfaces with constant k-th mean curvature in the de Sitter spaces

In this paper, we investigate complete spacelike hypersurfaces in the de Sitter space with constant k-th mean curvature and two distinct principal curvatures one of which is simple. We obtain some characterizations of the Riemannian product H¹(c₁)×Sn−1(c₂) or Hn−1(c₁)×S¹(c₂) in the de Sitter space .     

Construction of a certain circular unit and its applications

For an abelian number field k, let CS(k) be the group of circular units of k defined by Sinnott, and CW(k) be that suggested by Washington. In this paper, we construct an element in CW(k) for a real subfield k of conductor . We will see that the order of in the factor group CW(k)/CS(k) can be very large. As an application, we derive some information about the class number of k for special cases.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

The existence and upper bound for two types of restricted connectivity

In this paper, we study two types of restricted connectivity: κ_k(G) is the cardinality of a minimum vertex cut S such that every component of G−S has at least k vertices; is the cardinality of a minimum vertex cut S such that there are at least two components in G−S of order at least k. In this paper, we give some sufficient conditions for the existence and upper bound of κ_k(G) and/or , and study some properties of these two parameters.     

Generalized Latin squares and their defining sets

A generalized Latin square of type (n,k) is an n×n array of symbols 1,2,…,k such that each of these symbols occurs at most once in each row and each column. Let d(n,k) denote the cardinality of the minimal set S of given entries of an n×n array such that there exists a unique extension of S to a generalized Latin square of type (n,k). In this paper we discuss the properties of d(n,k) for k=2n-1 and k=2n-2. We give an alternate proof of the identity d(n,2n-1)=n²-n, which holds for even n, and we establish the new result . We also show that the latter bound is tight for n divisible by 10.     

Zero-divisor semigroups and refinements of a star graph

Let G be a refinement of a star graph with center c. Let be the subgraph of G induced on the vertex set V(G)?{c or end vertices adjacent to c}. In this paper, we completely determine the structure of commutative zero-divisor semigroups S whose zero-divisor graph G=Γ(S) and S satisfy one of the following properties: (1) has at least two connected components, (2) is a cycle graph C_n of length n≥5, (3) is a path graph P_n with n≥6, (4) S is nilpotent and Γ(S) is a finite or an infinite star graph. For any finite or infinite cardinal number n≥2, we prove that for any nilpotent semigroup S with zero element 0, S⁴=0 if Γ(S) is a star graph K_1,n. We prove that there is exactly one nilpotent semigroup S such that S³≠0 and Γ(S)≅K_1,n. For several classes of finite graphs G which are refinements of a star graph, we also obtain formulas to count the number of non-isomorphic corresponding semigroups.     

Discrete approximations to real-valued leaf sequencing problems in radiation therapy

For a given m×n nonnegative real matrix A, a segmentation with 1-norm relative error e is a set of pairs (α,S)={(α₁,S₁),(α₂,S₂),…,(α_k,S_k)}, where each α_i is a positive number and S_i is an m×n binary matrix, and , where |A|₁ is the 1-norm of a vector which consists of all the entries of the matrix A. In certain radiation therapy applications, given A and positive scalars γ,δ, we consider the optimization problem of finding a segmentation (α,S) that minimizes subject to certain constraints on S_i. This problem poses a major challenge in preparing a clinically acceptable treatment plan for Intensity Modulated Radiation Therapy (IMRT) and is known to be NP-hard. Known discrete IMRT algorithms use alternative objectives for this problem and an L-level entrywise approximation (i.e. each entry in A is approximated by the closest entry in a set of L equally-spaced integers), and produce a segmentation that satisfies . In this paper we present two algorithms that focus on the original non-discretized intensity matrix and consider measures of delivery quality and complexity (∑α_i+γk) as well as approximation error e. The first algorithm uses a set partitioning approach to approximate A by a matrix that leads to segmentations with smaller k for a given e. The second algorithm uses a constrained least square approach to post-process a segmentation of to replace with real-valued α_i in order to reduce k and e.