An all-substrings common subsequence algorithm

Given two strings A and B of lengths n_a and n_b, n_a?n_b, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B^′ of B, the length of the longest string that is a subsequence of both A and B^′. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n_an_b) time and O(n_a+n_b) space. After this preparation, it is possible to build a matrix of size that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem.     

Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

The influence of large coalitions

This paper contains two results on influence in collective decision games. The first part deals with general perfect information coin-flipping games as defined in [3].Baton passing (see [8]), ann-player game from this class is shown to have the following property: IfS is a coalition of size at most \(\frac{n}{{3\log n}}\) , then the influence ofS on the game is only \(O\left( {\frac{{\left| S \right|}}{n}} \right)\) . This complements a result from [3] that for everyk there is a coalition of sizek with influence Ω(k/n). Thus the best possible bounds on influences of coalitions of size up to this threshold are known, and there need not be coalitions up to this size whose influence asymptotically exceeds their fraction of the population. This result may be expected to play a role in resolving the most outstanding problem in this area: Does everyn-player perfect information coin flipping game have a coalition ofo(n) players with influence 1?o(1)? (Recently Alon and Naor [1] gave a negative answer to this question.) In a recent paper Kahn, Kalai and Linial [7] showed that for everyn-variable boolean function of expectation bounded away from zero and one, there is a set of \(\frac{{n\omega (n)}}{{\log n}}\) variables whose influence is 1?o(1), wherew(n) is any function tending to infinity withn. They raised the analogous question where 1?o(1) is replaced by any positive constant and speculated that a constant influence may be always achievable by significantly smaller sets of variables. This problem is almost completely solved in the second part of this article where we establish the existence of boolean functions where only sets of at least \(\Omega \left( {\frac{n}{{\log ^2 n}}} \right)\) variables can have influence bounded away from zero.     

A subexponential algorithm for the coloured tree partition problem

Given a tree of n vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP) consists in partitioning the tree into p vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of complexity (with ) for the special case in which a vertex of each subtree is given.     

Some extremal problems arising from discrete control processes

We consider a simple abstract model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string ofn bits and is a “success” or “failure” depending on whether the string produced belongs to a prespecified setL. In an uninfluenced process each bit is chosen by a fair coin toss, and hence the probability of success is ¦L¦/2 ⁿ . A player called the controller, is introduced who has the ability to intervene in the process by specifying the value of some of the bits of the string. We answer the following questions for both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of ¦L¦what is the expected number of interventions needed to guarantee success? In particular our results imply that if ¦L¦/2 ⁿ =1/Ω(n) where Ω(n) tends to infinity withn (so the probability of success with no interventions is 0(1)) then withO(√n logΩ(n)) interventions the probability of success is 1?0(1). Our main results and the proof techniques are related to well-known results of Kruskal, Katona and Harper in extremal set theory.     

On orthostochastic, unistochastic and qustochastic matrices

We introduce qustochastic matrices as the bistochastic matrices arising from quaternionic unitary matrices by replacing each entry with the square of its norm. This is the quaternionic analogue of the unistochastic matrices studied by physicists. We also introduce quaternionic Hadamard matrices and quaternionic mutually unbiased bases (MUB). In particular we show that the number of MUB in an n-dimensional quaternionic Hilbert space is at most 2n+1. The bound is attained for n=2. We also determine all quaternionic Hadamard matrices of size n?4.     

A one-dimensional bin packing problem with shelf divisions

Given bins of size B, non-negative values d and Δ, and a list L of items, each item e∈L with size s_e and class c_e, we define a shelf as a subset of items packed inside a bin with total item sizes at most Δ such that all items in this shelf have the same class. Two subsequent shelves must be separated by a shelf division of size d. The size of a shelf is the total size of its items plus the size of the shelf division. The class constrained shelf bin packing problem (CCSBP) is to pack the items of L into the minimum number of bins, such that the items are divided into shelves and the total size of the shelves in a bin is at most B. We present hybrid algorithms based on the First Fit (Decreasing) and Best Fit (Decreasing) algorithms, and an APTAS for the problem CCSBP when the number of different classes is bounded by a constant C.     

Adaptive Itô-Taylor algorithm can optimally approximate the Itô integrals of singular functions

We deal with numerical approximation of stochastic Itô integrals of singular functions. We first consider the regular case of integrands belonging to the Hölder class with parameters r and ?. We show that in this case the classical Itô-Taylor algorithm has the optimal error Θ(n^−(r+?)). In the singular case, we consider a class of piecewise regular functions that have continuous derivatives, except for a finite number of unknown singular points. We show that any nonadaptive algorithm cannot efficiently handle such a problem, even in the case of a single singularity. The error of such algorithm is no less than n^{−min{1/2,r+?}}. Therefore, we must turn to adaptive algorithms. We construct the adaptive Itô-Taylor algorithm that, in the case of at most one singularity, has the optimal error O(n^−(r+?)). The best speed of convergence, known for regular functions, is thus preserved. For multiple singularities, we show that any adaptive algorithm has the error Ω(n^{−min{1/2,r+?}}), and this bound is sharp.     

Feedback numbers of Kautz digraphs

A subset of vertices (resp. arcs) of a graph G is called a feedback vertex (resp. arc) set of G if its removal results in an acyclic subgraph. Let f(d,n) (f_a(d,n)) denote the minimum cardinality over all feedback vertex (resp. arc) sets of the Kautz digraph K(d,n). This paper proves that for any integers d?2 and n?1

     

A centerless representation of the Virasoro algebra associated with the unitary circular ensemble

We consider the 2-dimensional Toda lattice tau functions τ_n(t,s;η,θ) deforming the probabilities τ_n(η,θ) that a randomly chosen matrix from the unitary group U(n), for the Haar measure, has no eigenvalues within an arc (η,θ) of the unit circle. We show that these tau functions satisfy a centerless Virasoro algebra of constraints, with a boundary part in the sense of Adler, Shiota and van Moerbeke. As an application, we obtain a new derivation of a differential equation due to Tracy and Widom, satisfied by these probabilities, linking it to the Painlevé VI equation.     

Thue-Morse at multiples of an integer

Let t=(tn)_n?0 be the classical Thue-Morse sequence defined by , where s₂ is the sum of the bits in the binary representation of n. It is well known that for any integer k?1 the frequency of the letter “1” in the subsequence t₀,tk,t2k,… is asymptotically 1/2. Here we prove that for any k there is an n?k+4 such that tkn=1. Moreover, we show that n can be chosen to have Hamming weight ?3. This is best in a twofold sense. First, there are infinitely many k such that tkn=1 implies that n has Hamming weight ?3. Second, we characterize all k where the minimal n equals k, k+1, k+2, k+3, or k+4. Finally, we present some results and conjectures for the generalized problem, where s₂ is replaced by sb for an arbitrary base b?2.     

A linear-time algorithm for edge-disjoint paths in planar graphs

In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n ^5/3(loglogn)^1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability.     

Convex integer maximization via Graver bases

We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where c is a convex function on R^d and w₁x,…,w_dx are linear forms on Rⁿ,

max{c(w₁x,…,w_dx):Ax=b,x∈Nⁿ}.     

Finite basis for analytic strong n-gaps

We identify the finite list of minimal analytic n-gaps which are not weakly countably separated, and we prove that every analytic n-gap which is not countably separated contains a gap from our finite list     

Classification of irreducible weight modules over higher rank Virasoro algebras

Let G be a rank n additive subgroup of C and Vir[G] the corresponding Virasoro algebra of rank n. In the present paper, irreducible weight modules with finite dimensional weight spaces over Vir[G] are completely determined. There are two different classes of them. One class consists of simple modules of intermediate series whose weight spaces are all 1-dimensional. The other is constructed by using intermediate series modules over a Virasoro subalgebra of rank n−1. The classification of such modules over the classical Virasoro algebra was obtained by O. Mathieu in 1992 using a completely different approach.     

Random sorting networks

A sorting network is a shortest path from 12?n to n?21 in the Cayley graph of Sn generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n→∞ the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Hölder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.     

Relativization makes contradictions harder for Resolution

We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res(d)$\mathrm{Res}(d)$, as well as their tree-like versions, Res^?(d)${\mathrm{Res}}^{?}(d)$. The contradictions we use are natural combinatorial principles: the Least number principle  , _LNPn${\mathrm{LNP}}_n$ and an ordered variant thereof, the Induction principle  , _IPn${\mathrm{IP}}_n$.     

Growing perfect cubes

An (n,a,b)-perfect double cube is a b×b×b sized n-ary periodic array containing all possible a×a×a sized n-ary array exactly once as subarray. A growing cube is an array whose c_j×c_j×c_j sized prefix is an (n_j,a,c_j)-perfect double cube for , where and n₁<n₂<?. We construct the smallest possible perfect double cube (a 256×256×256 sized 8-ary array) and growing cubes for any a.