Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks

We consider the subclass of linear programs that formulate Markov Decision Processes (mdps). We show that the Simplex algorithm with the Gass-Saaty shadow-vertex pivoting rule is strongly polynomial for a subclass of mdps, called controlled random walks (CRWs); the running time is O(|S|³?|U|²), where |S| denotes the number of states and |U| denotes the number of actions per state. This result improves the running time of Zadorojniy et al. (Mathematics of Operations Research 34(4):992?C1007, 2009) algorithm by a factor of |S|. In particular, the number of iterations needed by the Simplex algorithm for CRWs is linear in the number of states and does not depend on the discount factor.     

A substitution theorem for graceful trees and its applications

A graceful labeling of a graph G=(V,E) assigns |V| distinct integers from the set {0,…,|E|} to the vertices of G so that the absolute values of their differences on the |E| edges of G constitute the set {1,…,|E|}. A graph is graceful if it admits a graceful labeling. The forty-year old Graceful Tree Conjecture, due to Ringel and Kotzig, states that every tree is graceful.We prove a Substitution Theorem for graceful trees, which enables the construction of a larger graceful tree through combining smaller and not necessarily identical graceful trees. We present applications of the Substitution Theorem, which generalize earlier constructions combining smaller trees.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

Persistence of Anderson localization in Schrödinger operators with decaying random potentials

We show persistence of both Anderson and dynamical localization in Schrödinger operators with non-positive (attractive) random decaying potential. We consider an Anderson-type Schrödinger operator with a non-positive ergodic random potential, and multiply the random potential by a decaying envelope function. If the envelope function decays slower than |x|^-2 at infinity, we prove that the operator has infinitely many eigenvalues below zero. For envelopes decaying as |x|^-α at infinity, we determine the number of bound states below a given energy E<0, asymptotically as α↓0. To show that bound states located at the bottom of the spectrum are related to the phenomenon of Anderson localization in the corresponding ergodic model, we prove: (a) these states are exponentially localized with a localization length that is uniform in the decay exponent α; (b) dynamical localization holds uniformly in α.     

On some properties of base-matroids

Let M=(E,F) be a rank-n matroid on a set E and B one of its bases. A closed set θ⊆E is saturated with respect to B, or B-saturated, when |θ∩B|=r(θ), where r(θ) is the rank of θ.The collection of subsets I of E such that |I∩θ|?r(θ), for every closed B-saturated set θ, turns out to be the family of independent sets of a new matroid on E, called base-matroid and denoted by M_B. In this paper we prove some properties of M_B, in particular that it satisfies the base-axiom of a matroid.Moreover, we determine a characterization of the matroids M which are isomorphic to M_B for every base B of M.Finally, we prove that the poset of the closed B-saturated sets ordered by inclusion is isomorphic to the Boolean lattice B_n.     

Writing representations over minimal fields

The chief aim of this paper is to describe a procedure which, given a d-dimensional absolutely irreducible matrix representation of a finite group over a finite field E, produces an equivalent representation such that all matrix entries lie in a subfield F of E which is as small as possible. The algorithm relies on a matrix version of Hilbert's Theorem 90, and is probabilistic with expected running time O(|E:F|d³) when |F| is bounded. Using similar methods we then describe an algorithm which takes as input a prime number and a power-conjugate presentation for a finite soluble group, and as output produces a full set of absolutely irreducible representations of the group over fields whose characteristic is the specified prime, each representation being written over its minimal field.     

On the interval completion of chordal graphs

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.     

Directed Graph Pattern Matching and Topological Embedding

Pattern matching in directed graphs is a natural extension of pattern matching in trees and has many applications to different areas. In this paper, we study several pattern matching problems in ordered labeled directed graphs. For the rooted directed graph pattern matching problem, we present an efficient algorithm which, given a pattern graphPand a target graphT, runs in time and spaceO(|E_P| |V_T| + |E_T|). It is faster than the best known method by a factor ofmin{|E_T|, |E_P| |V_T|}. This algorithm can also solve the directed graph pattern matching problem without increasing time or space complexity. Our solution to this problem outperforms the best existing method by Katzenelson, Pinter and Schenfeld by a factor ofmin{|V_P| |E_T|, |V_P| |E_P| |V_T|}. We also present an algorithm for the directed graph topological embedding problem which runs in timeO(|V_P| |E_T| + |E_P|) and spaceO(|V_P| |V_T| + |E_P| + |E_T|). To our knowledge, this algorithm is the first one for this problem.     

On the Best Exponent in Markov Inequality

Let E be a compact set preserving the Markov inequality and m(E) be its best exponent i.e., m(E) is the infimum of all possible exponents in this inequality on E. It is known that $\alpha (E) \le \frac1{m(E)}$ where α(E) is the best exponent in Hölder continuity property of the (pluri)complex Green function (with pole at infinity) of E. We show that if E???? ^N (or ? ^N ) with N?≥?2 then the Markov inequality need not be fulfilled with m(E). We also construct a set E????² such that the Markov inequality holds at the tip of exponential cusps composing E but for the whole set E we have m(E)?=?∞. Moreover, we prove that sup m(E)?=?∞ where the supremum is taken over all compact sets E???? preserving the Markov inequality. Finally, we prove that if E is a Markov set in ? then its image F(E) under a holomorphic mapping F is a Markov set too. More precisely, we prove that $m(F(E))\leq m(E)\cdot \Big(1+ \max\limits_{ \partial E\cap\{F'(t)=0\}}\textrm{ord}_t F'\Big)$ .     

Computing the endomorphism ring of an ordinary elliptic curve over a finite field

We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field Fq. Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of , while our bound for the second algorithm depends primarily on log|DE|, where DE is the discriminant of the order isomorphic to End(E). As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed.     

Weakly tight functions, their Jordan type decomposition and total variation in effect algebras

In the present paper, we have studied envelopes of a function m defined on a subfamily E (containing 0 and 1) of an effect algebra L. The notion of a weakly tight function is introduced and its relation to tight functions is investigated; examples and counterexamples are constructed for illustration. A Jordan type decomposition theorem for a locally bounded real-valued weakly tight function m defined on E is established. The notions of total variation |m| on the subfamily E and m-atoms on a sub-effect algebra E (along with a few examples of m-atoms for null-additive as well as non null-additive functions) are introduced and studied. Finally, it is proved for a real-valued additive function m on a sub-effect algebra E that, m is non-atomic if and only if its total variation |m| is non-atomic.     

Competitively Tight Graphs

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ _E (G) of the graph G via θ _E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ _E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ _E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ _E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ _E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.     

Codes projectifs a deux ou trois poids associfs aux hyperquadriques d'une geometrie finie

The notion of closure structures of finite rank is introduced and several closure structures familiar from algebra and logic are shown to be of finite rank. The following theorem is established: Let k be any natural number and $\text{C}$ any closure structure of rank k + 2. If B is a finite base (generating set) of $\text{C}$and D is an irredundant (independent) base of $\text{C}$ such that |B| + k < |D|, then there is an irredundant base E of $\text{C}$ such that |B| < |E| < |B| + k.     

Decomposing graphs into paths of fixed length

Barát and Thomassen have conjectured that, for any fixed tree T, there exists a natural number k _T such that the following holds: If G is a k _T -edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition. The conjecture is trivial when T has one or two edges. Before submission of this paper, the conjecture had been verified only for two other trees: the paths of length 3 and 4, respectively. In this paper we verify the conjecture for each path whose length is a power of 2.     

Testing membership in matroid polyhedra

Given a matroid M on E and a nonnegative real vector x=(x_j:j∈E), a fundamental problem is to determine whether x is in the convex hull P of (incidence vectors of) independent sets of M. An algorithm is described for solving this problem for which the amount of computation is bounded by a polynomial in |E|, independently of x, allowing as steps tests of independence in M and additions, subtractions, and comparisons of numbers. In case x ∈ P, the algorithm finds an explicit representation for x which has additional nice properties; in case x ? P it finds a most-violated inequality of the system defining P. The same technique is applied to the problem of finding a maximum component-sum vector in the intersection of two matroid polyhedra and a box.     

Interpretation of the Evolution of the Homogeneous Markov System (or,equivalently, of the Embedded Markov Chain) as the Deformation of a Viscoelastic Medium. The 3-D Case

Every attainable structure of a continuous time homogeneous Markov chain (HMC) with n states, or of a closed Markov system with an embedded HMC with n states, or more generally of a Markov system driven by an HMC, is considered as a point-particle of ? ⁿ . Then, the motion of the attainable structure corresponds to the motion of the respective point-particle in ? ⁿ . Under the assumption that “the motion of every particle at every time point is due to the interaction with its surroundings”, ? ⁿ (and equivalently the set of the accosiated attainable structures of the homogeneous Markov system (HMS), or alternatively of the underlying embedded HMC) becomes a continuum. Thus, the evolution of the set of the attainable structures corresponds to the motion of the continuum. In this paper it is shown that the evolution of a three-dimensional HMS (n = 3) or simply of an HMC, can be interpreted through the evolution of a two-dimensional isotropic viscoelastic medium.     

2-Universally complete Riesz spaces and inverse-closed Riesz spaces

In this paper we show mainly two results about uniformly closed Riesz subspaces of ?^X containing the constant functions. First, for such a Riesz subspace E, we solve the problem of determining the properties that a real continuous functiondefined on a proper open interval of ?should have in order that the conditions “E is closed under composition with ” and “E is closed under inversion in X” become equivalent. The second result, reformulated in the more general frame of the Archimedean Riesz spaces with weak order unit e, establishes that E (e-uniformly complete and e-semisimple) is closed under inversion in C(Spec E) if and only if E is 2-universally e-complete.     

A chain theorem for internally 4-connected binary matroids

Let M be a matroid. When M is 3-connected, Tutte's Wheels-and-Whirls Theorem proves that M has a 3-connected proper minor N with |E(M)−E(N)|=1 unless M is a wheel or a whirl. This paper establishes a corresponding result for internally 4-connected binary matroids. In particular, we prove that if M is such a matroid, then M has an internally 4-connected proper minor N with |E(M)−E(N)|?3 unless M or its dual is the cycle matroid of a planar or Möbius quartic ladder, or a 16-element variant of such a planar ladder.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.