Search

Abstract: We prove that the Lipschitz constant of the Lipschitz stability result for the inverse conductivity problem proved in [G. Alessandrini, S. Vessella, Lipschitz stability for the inverse conductivity problem, Adv. in Appl. Math. 35 (2005) 207–241], behaves exponentially with respect to the number N of regions considered. [Copyright &y& Elsevier]

Abstract In this paper, we study the distribution of consecutive patterns in the set of 123-avoiding permutations and the set of 132-avoiding permutations, that is, in S n (123) and S n (132). We first study the distribution of consecutive pattern γ -matches in S n (123) and S n (132) for each length 3 consecutive pattern γ. Then we extend our methods to study the joint distributions of multiple consecutive patterns. Some more general cases are discussed in this paper as well. [ABSTRACT FROM AUTHOR]

In this paper, we provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs in two different ways: (1) We represent spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper-Hafnians (orders and signs are not considered); (2) We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam (2004) [1] and Pfaffian matrix tree theorem by Masbaum and Vaintrob (2002) [15]. • We provide generating functions and counting formulas for spanning trees and spanning forests in hypergraphs through Berezin-Grassmann integrals on Zeon algebra and hyper- Hafnians when orders and signs are not considered. • We establish a Hyper-Pfaffian-Cactus Spanning Forest Theorem through Berezin-Grassmann integrals on Grassmann algebra (orders and signs are considered), which generalizes the Hyper-Pfaffian-Cactus Theorem by Abdesselam [Advances in Applied Mathematics (2004) Vol. 33: 51-70] and Pfaffian matrix tree theorem by Masbaum and Vaintrob [Internat. Math. Res. Notices (2002) Vol. 27: 1397-1426]. [ABSTRACT FROM AUTHOR]

In the paper 'A probabilistic analysis of a discrete-time evolution in recombination' [4] the evolution of the recombination transformation Ξ = ∑ δ ρ δ ⨂ J ∈ δ μ J was described by a Markov chain (Y n) on a set of partitions, which converges to the finest partition. Our main results were the description of the geometric decay rate to the limit and the quasi-stationary behavior of the Markov chain when conditioned on the event that the chain does not hit the limit. All these results continue to be true, but the Markov chain (Y n) that was claimed to satisfy Ξ n = E (⨂ J ∈ Y n μ J) required to be modified. This is done in this Corrigendum. [ABSTRACT FROM AUTHOR]

Abstract Throughout the last decade, we have seen much progress towards characterising and computing the minimum hybridisation number for a set P of rooted phylogenetic trees. Roughly speaking, this minimum quantifies the number of hybridisation events needed to explain a set of phylogenetic trees by simultaneously embedding them into a phylogenetic network. From a mathematical viewpoint, the notion of agreement forests is the underpinning concept for almost all results that are related to calculating the minimum hybridisation number for when | P | = 2. However, despite various attempts, characterising this number in terms of agreement forests for | P | > 2 remains elusive. In this paper, we characterise the minimum hybridisation number for when P is of arbitrary size and consists of not necessarily binary trees. Building on our previous work on cherry-picking sequences, we first establish a new characterisation to compute the minimum hybridisation number in the space of tree-child networks. Subsequently, we show how this characterisation extends to the space of all rooted phylogenetic networks. Moreover, we establish a particular hardness result that gives new insight into some of the limitations of agreement forests. [ABSTRACT FROM AUTHOR]

Abstract: The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one. We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with , let . Let , let be the number of factors in the prime factorization of n. We give an algorithm to decide whether there exists n, with , and a finite maximal code C which is also factorizing such that . We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in satisfy a property defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set can be embedded in a set satisfying . Furthermore, we prove that, conversely, for each set satisfying , under additional hypotheses, there exists a factorizing code C such that and, as a consequence, is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each , we have , with . In addition, we prove that there exist sets which satisfy and which are not codes. [Copyright &y& Elsevier]

Abstract: The main aim of this paper is the adaptation of the results of the papers [Y.A. Bahturin, S.K. Sehgal, M.V. Zaicev, Group gradings on associative algebras, J. Algebra 241 (2) (2001) 677–698; Y.A. Bahturin, S.K. Sehgal, M.V. Zaicev, Finite-dimensional graded simple algebras, preprint, and M.V. Zaĭtsev, S.K. Segal, Finite gradings of simple Artinian rings, Vestnik Moskov. Univ. Ser. I Mat. Mekh., vol. 3, 2001, pp. 21–24, 77 (in Russian); translation in Moscow Univ. Math. Bull. 56 (3) (2001) 21–24] about the structure of graded simple rings from the gradings by groups to the gradings by cancellative semigroups. [Copyright &y& Elsevier]

Abstract: In this paper, we generalize the inductive techniques used in a previous paper [D. Warren, Optimal packing behavior of some 2-block patterns, Ann. Combin. 8 (2) (2004) 355–367] to prove a general result by which we may calculate the packing density of a 2-block pattern given the packing behavior of a smaller pattern having the same ratio of block sizes. We apply this result to compute the packing densities of patterns having layer sequences of the form in the case that and . Necessary unimodality and maximality results are proven as we need them. [Copyright &y& Elsevier]

One way to characterize configurations of points up to congruence is by considering the distribution of all mutual distances between points. This paper deals with the question if point configurations are uniquely determined by this distribution. After giving some counterexamples, we prove that this is the case for the vast majority of configurations.In the second part of the paper, the distribution of areas of sub-triangles is used for characterizing point configurations. Again it turns out that most configurations are reconstructible from the distribution of areas, though there are counterexamples. [Copyright &y& Elsevier]

The paper provides a description of the large deviation behavior for the Euclidean norm of projections of ℓ p n -balls to high-dimensional random subspaces. More precisely, for each integer n ≥ 1 , let k n ∈ { 1 , … , n − 1 } , E ( n ) be a uniform random k n -dimensional subspace of R n and X ( n ) be a random point that is uniformly distributed in the ℓ p n -ball of R n for some p ∈ [ 1 , ∞ ] . Then the Euclidean norms ‖ P E ( n ) X ( n ) ‖ 2 of the orthogonal projections are shown to satisfy a large deviation principle as the space dimension n tends to infinity. Its speed and rate function are identified, making thereby visible how they depend on p and the growth of the sequence of subspace dimensions k n . As a key tool we prove a probabilistic representation of ‖ P E ( n ) X ( n ) ‖ 2 which allows us to separate the influence of the parameter p and the subspace dimension k n . [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze O''Hara''s partition bijection. We present three type of results. First, we show that O''Hara''s bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O''Hara''s bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O''Hara''s bijection can be computed in polynomial time, i.e. much more efficiently than by O''Hara''s construction. [Copyright &y& Elsevier]

Abstract: Determining the location of the maximum of Stirling numbers is a well-developed area. In this paper we give the same results for the so-called r-Stirling numbers which are natural generalizations of Stirling numbers. [Copyright &y& Elsevier]

Abstract: A standard matrix representation A of a matroid M represents M relative to a fixed basis B. Deleting rows and columns of A correspond to contracting elements of B and deleting elements of . If M is 3-connected, it is often desirable to perform such an element removal from M while maintaining 3-connectivity. This paper proves that this is always possible provided M has no 4-element fans. We also show that, subject to a mild essential restriction, this element removal can be done so as to retain a copy of a specified 3-connected minor of M. [Copyright &y& Elsevier]

Abstract: In this paper we prove that two quantities relating to the length of permutations defined on trees are independent of the structures of trees. We also find that these results are closely related to the results obtained by Graham and Pollak [R.L. Graham, H.O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971) 2495–2519] and by Bapat, Kirkland, and Neumann [R. Bapat, S.J. Kirkland, M. Neumann, On distance matrices and Laplacians, Linear Algebra Appl. 401 (2005) 193–209]. [Copyright &y& Elsevier]

Abstract: In an earlier paper [D. Richards, Q. Zheng, Determinant formulas for multidimensional hypergeometric period matrices, Adv. in Appl. Math. 29 (2002) 137–151] on the determinants of certain period matrices, we formulated a conjecture about the determinant of a certain hypergeometric matrix. In this article, we establish this conjecture by constructing a system of linear equations in which that determinant is one of the variables. As a consequence, we obtain the value of an integral which generalizes the well-known multidimensional beta integral of A. Selberg [A. Selberg, Bemerkninger om et multipelt integral, Norsk. Mat. Tidsskr. 26 (1944) 71–78] and some hypergeometric determinant formulas of A. Varchenko [A. Varchenko, The Euler beta-function, the Vandermonde determinant, the Legendre equation, and critical values of linear functions on a configuration of hyperplanes. I, Izv. Akad. Nauk SSSR Ser. Mat. 53 (1989) 1206–1235, English translation, Math. USSR-Izv. 35 (1990) 543–571; A. Varchenko, The Euler beta-function, the Vandermonde determinant, the Legendre equation, and critical values of linear functions on a configuration of hyperplanes. II, Izv. Akad. Nauk SSSR Ser. Mat. 54 (1990) 146–158, English translation, Math. USSR-Izv. 36 (1991) 155–167]. [Copyright &y& Elsevier]

Abstract: The purpose of this paper is to compute the Möbius function of filters in the partition lattice formed by restricting to partitions by type. The Möbius function is determined in terms of the descent set statistics on permutations and the Möbius function of filters in the lattice of integer compositions. When the underlying integer partition is a knapsack partition, the Möbius function on integer compositions is determined by a topological argument. In this proof the permutahedron makes a cameo appearance. [Copyright &y& Elsevier]

Abstract: The gap function of an infinite word over the binary alphabet gives the distances between consecutive 1''s in this word. In this paper we study infinite binary words whose gap function is injective or “almost injective.” A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is increasing is obtained. [Copyright &y& Elsevier]

Abstract: In electrical impedance tomography, one tries to recover the conductivity inside a body from boundary measurements of current and voltage. In many practically important situations, the object has known background conductivity but it is contaminated by inhomogeneities. The factorization method of Andreas Kirsch provides a tool for locating such inclusions. It has been shown that the inhomogeneities can be characterized by the factorization technique if the conductivity coefficient jumps to a higher or lower value on the boundaries of the inclusions. In this paper, we extend the results to the case of weaker inclusions: If the inhomogeneities inside the body are more (or less) conductive than the known background, if the conductivity coefficient and its lowest normal derivatives are continuous over the inclusion boundaries, and if the mth normal derivative of the conductivity jumps on the inclusion boundaries, then the factorization method provides an explicit characterization of the inclusions. [Copyright &y& Elsevier]

Abstract: In this paper, we prove a new identity for the product of two partial theta functions. An immediate corollary is Warnaar''s generalization of the Jacobi triple product identity. [Copyright &y& Elsevier]

Abstract: In this paper we describe completely the involutions of the first kind of the algebra of upper triangular matrices. Every such involution can be extended uniquely to an involution on the full matrix algebra. We describe the equivalence classes of involutions on the upper triangular matrices. There are two distinct classes for when n is even and a single class in the odd case. Furthermore we consider the algebra of the upper triangular matrices over an infinite field F of characteristic different from 2. For every involution ∗, we describe the ∗-polynomial identities for this algebra. We exhibit bases of the corresponding ideals of identities with involution, and compute the Hilbert (or Poincaré) series and the codimension sequences of the respective relatively free algebras. Then we consider the ∗-polynomial identities for the algebra over a field of characteristic zero. We describe a finite generating set of the ideal of ∗-identities for this algebra. These generators are quite a few, and their degrees are relatively large. It seems to us that the problem of describing the ∗-identities for the algebra of the upper triangular matrices may be much more complicated than in the case of ordinary polynomial identities. [Copyright &y& Elsevier]

Abstract: We give here a new proof of the non-degeneracy of the fundamental bilinear form for -m-Quasi-Invariants and for m-Quasi-Invariants of classical Weyl groups. We also indicate how our approach can be extended to other Coxeter groups. This bilinear form plays a crucial role in the original proof [P. Etingof, V. Ginzburg, On m-quasi-invariants of a Coxeter group, arXiv: math.QA/0106175 v1, June 2001] that m-Quasi-Invariants are a free module over the invariants as well as in all subsequent proofs [Y. Berest, P. Etingof, V. Ginsburg, Cherednik algebras and differential operators on quasi-invariants, math.QA/0111005; A. Garsia, N. Wallach, Some new applications of orbit harmonics, Sém. Lothar. Combin. 50 (2005), Article B50j]. However, in previous literature this non-degeneracy was stated and used without proof with reference to some deep results of Opdam [E.M. Opdam, Some applications of shift operators, Invent. Math. 98 (1989) 1–18] on shift-differential operators. This result hinges on the validity of a deceptively simple identity on Dunkl operators which, at least in the case, begs for an elementary painless proof. An elementary but by all means not painless proof of this identity can be found in a paper of Dunkl and Hanlon [C. Dunkl, P. Hanlon, Integrals of polynomials associated with tableaux and the Garsia–Haiman conjecture, Math. Z. 228 (1998) 537–567. 71]. Our proof here is not elementary but hopefully it should be painless and informative. [Copyright &y& Elsevier]

Abstract: Charles L. Dodgson, who lectured on mathematics at Christ Church in Oxford University, constructed ciphers that were state of the art in his time. In poems and letters he demonstrated a great talent for creating acrostics and anagrams. In this paper I describe the ciphers closely and argue that their creation was intertwined with his word game inventions. [Copyright &y& Elsevier]

The present authors introduced recently (see [Adv. in Appl. Math. 32 (2004) 576]) the notion of shifted asymmetry index series denoted , for an arbitrary species of structures, F, and a series of weights, ξ. This series generalizes the classical asymmetry index series, , of G. Labelle [Discrete Math. 99 (1992) 141] to take into account the substitution of species with non-zero constant term [Combinatoire Énumérative, Lecture Notes in Math., vol. 1234, Springer-Verlag, 1986, pp. 126–159]. In [Adv. in Appl. Math. 32 (2004) 576], we can find explicit formulas for the shifted asymmetry index series of usual species (sets, cycles, permutation, trees, …). The goal of this paper is to complement [Adv. in Appl. Math. 32 (2004) 576] by computing closed formulas for the series and , of the species of oriented sets and ALT of even permutation of their elements. Oriented sets are, by definition, totally ordered sets modulo an even permutation of their elements. Such structures were used, for example, by Pólya and Read [Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, Springer-Verlag, 1987] in the context of combinatorial chemistry problems (vertex-sets of oriented simplices). [Copyright &y& Elsevier]

Using Lie theory, Stefano Capparelli conjectured an interesting Rogers–Ramanujan type partition identity in his 1988 Rutgers PhD thesis. The first proof was given by George Andrews, using combinatorial methods. Later, Capparelli was able to provide a Lie theoretic proof.Most combinatorial Rogers–Ramanujan type identities (e.g., the Göllnitz–Gordon identities, Gordon''s combinatorial generalization of the Rogers–Ramanujan identities, etc.) have an analytic counterpart. The main purpose of this paper is to provide two new series representations for the infinite product associated with Capparelli''s conjecture. Some additional related identities, including new infinite families are also presented. [Copyright &y& Elsevier]

The grafting of finite planar reduced rooted trees is a system of m-ary operations, m⩾2, on the set PRT of those trees.We consider power series with rational coefficients in a single variable x where the set of monomials is {1}∪PRT, 1 is the empty tree and x denotes the tree with a single node. Grafting induces a string (·m)m⩾2 of m-ary multiplications on this power series algebra Q{{x}}∞.We show that for any natural number k⩾2 there is a unique power series expk(x) ∈Q{{x}}∞ such that and expk(0)=exp′k(0)=1, where exp′k(x) is the formal derivative of expk(x) with respect to x. We suggest to call it the k-ary non-associative exponential series.It follows that Also it is shown that there is a unique generic exponential exp(q,x) where the coefficients are in the field Q(q) of rational functions in a single variable q over Q such that The limit limq→∞exp(q,x) exists and is equal to the classical-looking series For any tree t∈PRT the coefficient of exp(q,x) relative to t is of the form [t]/[n-1]! where n=deg(t), [n-1]! is the q-factorial of n-1 and [t] is a polynomial in q for which a closed formula is derived.As the topic of this paper is in the meeting point of combinatorics of trees and non-associative algebra, one can expect further interesting cross-relations. [Copyright &y& Elsevier]

One of the central problems in matroid theory is Rota''s conjecture that, for all prime powers q, the class of GF(q)-representable matroids has a finite set of excluded minors. This conjecture has been settled for q⩽4 but remains open otherwise. Further progress towards this conjecture has been hindered by the fact that, for all q>5, there are 3-connected GF(q)-representable matroids having arbitrarily many inequivalent GF(q)-representations. This fact refutes a 1988 conjecture of Kahn that 3-connectivity would be strong enough to ensure an absolute bound on the number of such inequivalent representations. This paper introduces fork-connectivity, a new type of self-dual 4-connectivity, which we conjecture is strong enough to guarantee the existence of such a bound but weak enough to allow for an analogue of Seymour''s Splitter Theorem. We prove that every fork-connected matroid can be reduced to a vertically 4-connected matroid by a sequence of operations that generalize Δ–Y and Y–Δ exchanges. It follows from this that the analogue of Kahn''s Conjecture holds for fork-connected matroids if and only if it holds for vertically 4-connected matroids. The class of fork-connected matroids includes the class of 3-connected forked matroids. By taking direct sums and 2-sums of matroids in the latter class, we get the class M of forked matroids, which is closed under duality and minors. The class M is a natural subclass of the class of matroids of branch-width at most 3 and includes the matroids of path-width at most 3. We give a constructive characterization of the members of M and prove that M has finitely many excluded minors. [Copyright &y& Elsevier]

If Z is the group of integers, A a finite alphabet and AZ the set of all functions c :Z→A, the equivalence between pre-injectivity and surjectivity of a local function holds for irreducible shifts of finite type of AZ (see [Pure Math. Appl. 11 (2000) 471–484]). In [Theoret. Comput. Sci. 299 (2003) 477–493] we give a definition of strong irreducibility that, together with the finite type condition, allows us to prove the above equivalence for strongly irreducible shifts of finite type in AΓ, if Γ is an amenable group. In this paper, we define semi-strong irreducibility for a shift. This property allows us to prove the implication “pre-injective ⇒ surjective” for a local function on a semi-strongly irreducible shift of finite type of AΓ, if Γ has nonexponential growth. As a by-product, we prove that the entropy of a proper subshift of a semi-strongly irreducible shift X is strictly smaller than the entropy of X. [Copyright &y& Elsevier]

An infinite sequence of graphs {Gn}n⩾0 is called recursive if the Tutte polynomials T(Gn;x,y) satisfy a linear recurrence relation whose coefficients are polynomials in x and y. In this paper we introduce a general method based on transfer matrices for proving that a family is recursive that covers all examples known to us. As an application we show that, for fixed s, the sequence of complete bipartite graphs {Ks,n} is recursive and satisfies a linear recurrence whose degree is the number of partitions of the integer s. [Copyright &y& Elsevier]

We consider the problem of enumerating the permutations containing exactly k occurrences of a pattern of length 3. This enumeration has received a lot of interest recently, and there are a lot of known results. This paper presents an alternative approach to the problem, which yields a proof for a formula which so far only was conjectured (by Noonan and Zeilberger). This approach is based on bijections from permutations to certain lattice paths with “jumps,” which were first considered by Krattenthaler. [Copyright &y& Elsevier]

In this paper, we show that any convex geometry (dual antimatroid) gives rise to a lace map and deduce some recent variants of the inclusion-exclusion principle from Zeilberger''s abstract lace expansion. [Copyright &y& Elsevier]