| 1. |
- Eriksen, Niklas, et al.
(författare)
-
Estimating the expected reversal distance after a fixed number of reversals
- 2004
-
Ingår i: Advances in Applied Mathematics. - San Diego, USA : Elsevier. - 0196-8858 .- 1090-2074. ; 32:3, s. 439-453
-
Tidskriftsartikel (refereegranskat)abstract
- We address the problem of computing the expected reversal distance of a genome with n genes obtained by applying t random reversals to the identity. A good approximation is the expected transposition distance of a product of t random transpositions in S-n. Computing the latter turns out to be equivalent to computing the coefficients of the length function (i.e., the class function returning the number of parts in an integer partition) when written as a linear combination of the irreducible characters of Sn. Using symmetric functions theory, we compute these coefficients, thus obtaining a formula for the expected transposition distance. We also briefly sketch how to compute the variance.
|
|
| 2. |
- Andrén, Daniel, 1973-, et al.
(författare)
-
On the complexity of matrix reduction over finite fields
- 2007
-
Ingår i: Advances in Applied Mathematics. - : Academic Press. - 0196-8858 .- 1090-2074. ; 39:4, s. 428-452
-
Tidskriftsartikel (refereegranskat)abstract
- We study matrix elimination over finite fields, and present an algorithm which is asymptotically faster than the traditional Gauss--Jordan elimination. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices.Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from $\mathrm{GL}_{n}(\mathbb{F}_{q})$, with $n$ an $q$ smallFinally we consider an extension of the problems studied for finite fields to finite semifields. We give a conjecture on the behaviour of a natural analogue of $\mathrm{GL}_{n}$ for semifields and prove this for a certain class of semifields.
|
|
| 3. |
- Ayyer, Arvind, et al.
(författare)
-
An inhomogeneous multispecies TASEP on a ring
- 2014
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 57, s. 21-43
-
Tidskriftsartikel (refereegranskat)abstract
- We reinterpret and generalize conjectures of Lam and Williams as statements about the stationary distribution of a multispecies exclusion process on the ring. The central objects in our study are the multiline queues of Ferrari and Martin. We make some progress on some of the conjectures in different directions. First, we prove Lam and Williams' conjectures in two special cases by generalizing the rates of the Ferrari-Martin transitions. Secondly, we define a new process on multiline queues, which have a certain minimality property. This gives another proof for one of the special cases; namely arbitrary jump rates for three species.
|
|
| 4. |
- Ayyer, A., et al.
(författare)
-
Bumping sequences and multispecies juggling
- 2018
-
Ingår i: Advances in Applied Mathematics. - : Academic Press. - 0196-8858 .- 1090-2074. ; 98, s. 100-126
-
Tidskriftsartikel (refereegranskat)abstract
- Building on previous work by four of us (ABCN), we consider further generalizations of Warrington's juggling Markov chains. We first introduce “multispecies” juggling, which consist in having balls of different weights: when a ball is thrown it can possibly bump into a lighter ball that is then sent to a higher position, where it can in turn bump an even lighter ball, etc. We both study the case where the number of balls of each species is conserved and the case where the juggler sends back a ball of the species of its choice. In this latter case, we actually discuss three models: add-drop, annihilation and overwriting. The first two are generalisations of models presented in (ABCN) while the third one is new and its Markov chain has the ultra fast convergence property. We finally consider the case of several jugglers exchanging balls. In all models, we give explicit product formulas for the stationary probability and closed form expressions for the normalisation factor if known.
|
|
| 5. |
- Backelin, Jörgen, et al.
(författare)
-
Wilf-equivalence for singleton classes
- 2007
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 38:2, s. 133-148
-
Tidskriftsartikel (refereegranskat)abstract
- Write p(1)p(2)(...)pm for the permutation matrix (delta p(i) j)(m x m). Let S-n(M) be the set of n x n permutation matrices which do not contain the m x m permutation matrix M as a submatrix. In [R. Simion, F.W. Schmidt, Restricted permutations, European J. Combin. 6 (1985) 383-406] Simion and Schmidt show bijectively that vertical bar S-n (123)vertical bar = vertical bar S-n (213)vertical bar. In the present work, we give a bi jection from S-n (12...tp(t+1)... p(m)) to S-n (t...21 p(t+1)...p(m)). This result was established for t = 2 in [J. West, Permutations with forbidden subsequences and stack-sortable permutations, PhD thesis, MIT, Cambridge, MA, 1990] and for t = 3 in [E. Babson, J. West, The permutations 123p(4)... p(t) and 321 p(4)...p(t) are Wilf-equivalent, Graphs Combin. 16 (2001) 373-3801. Moreover, if we think of n x n permutation matrices as transversals of the n by n square diagram, then we generalise this result to transversals of Young diagrams.
|
|
| 6. |
- Björnberg, Jakob, 1983, et al.
(författare)
-
Heisenberg models and Schur-Weyl duality
- 2023
-
Ingår i: Advances in Applied Mathematics. - 0196-8858 .- 1090-2074. ; 151
-
Tidskriftsartikel (refereegranskat)abstract
- We present a detailed analysis of certain quantum spin systems with inhomogeneous (non-random) mean-field interactions. Examples include, but are not limited to, the interchange-and spin singlet projection interactions on complete bipartite graphs. Using two instances of the representation theoretic framework of Schur-Weyl duality, we can explicitly compute the free energy and other thermodynamic limits in the models we consider. This allows us to describe the phase transition, the ground-state phase diagram, and the expected structure of extremal states. & COPY; 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).
|
|
| 7. |
- Björner, Anders
(författare)
-
A cell complex in number theory
- 2011
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 46:1-4, s. 71-85
-
Tidskriftsartikel (refereegranskat)abstract
- Let Delta(n) be the simplicial complex of squarefree positive integers less than or equal to n ordered by divisibility. It is known that the asymptotic rate of growth of its Euler characteristic (the Mertens function) is closely related to deep properties of the prime number system. In this paper we study the asymptotic behavior of the individual Betti numbers beta(k)(Delta(n)) and of their sum. We show that Delta(n) has the homotopy type of a wedge of spheres, and that as n -> infinity S beta(k)(Delta(n)) = 2n/pi(2) + O(n(theta)), for all theta > 17/54, Furthermore, for fixed k, beta k(Delta(n)) similar to n/2logn (log log n)(k)/k!. As a number-theoretic byproduct we obtain inequalities partial derivative(k)(sigma(odd)(k+1)(n)) infinity S beta k((Delta) over tilde (n)) = n/3 + O(n(theta)), for all theta > 22/27.
|
|
| 8. |
- Boman, J, et al.
(författare)
-
Symmetries of quantum graphs and the inverse scattering problem
- 2005
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 1090-2074 .- 0196-8858. ; 35:1, s. 58-70
-
Tidskriftsartikel (refereegranskat)abstract
- The Schrodinger equation on a graph together with a set of self-adjoint boundary conditions at the vertices determine a quantum graph. If the graph has one or more infinite edges one can associate a scattering matrix to the quantum graph. It is proved that if such a graph has internal symmetries then the boundary conditions, and hence the self-adjoint operator describing the quantum system, in general cannot be reconstructed from the scattering matrix. In addition it is shown that if the Schrodinger operator possesses internal symmetry then there exists a different quantum graph associated with the same scattering matrix.
|
|
| 9. |
- Braun, Benjamin, et al.
(författare)
-
Detecting the integer decomposition property and Ehrhart unimodality in reflexive simplices
- 2018
-
Ingår i: Advances in Applied Mathematics. - : Academic Press. - 0196-8858 .- 1090-2074. ; 100, s. 122-142
-
Tidskriftsartikel (refereegranskat)abstract
- A long-standing open conjecture in combinatorics asserts that a Gorenstein lattice polytope with the integer decomposition property (IDP) has a unimodal (Ehrhart) h*-polynomial. This conjecture can be viewed as a strengthening of a previously disproved conjecture which stated that any Gorenstein lattice polytope has a unimodal h*-polynomial. The first counterexamples to unimodality for Gorenstein lattice polytopes were given in even dimensions greater than five by Mustata and Payne, and this was extended to all dimensions greater than five by Payne. While there exist numerous examples in support of the conjecture that IDP reflexives are h*-unimodal, its validity has not yet been considered for families of reflexive lattice simplices that closely generalize Payne's counterexamples. The main purpose of this work is to prove that the former conjecture does indeed hold for a natural generalization of Payne's examples. The second purpose of this work is to extend this investigation to a broader class of lattice simplices, for which we present new results and open problems.
|
|
| 10. |
- Canfield, E. Rodney, et al.
(författare)
-
The Mahonian probability distribution on words is asymptotically normal
- 2011
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 46:1-4, s. 109-124
-
Tidskriftsartikel (refereegranskat)abstract
- The Mahonian statistic is the number of inversions in a permutation of a multiset with a(i) elements of type i, 1 <= i <= m. The counting function for this statistic is the q analog of the multinomial coefficient (a(1) +...+4 a(m) a(1)...a(m)), and the probability generating function is the normalization of the latter. We give two proofs that the distribution is asymptotically normal. The first is computer-assisted, based on the method of moments. The Maple package Mahoni anStat, available from the webpage of this article, can be used by the reader to perform experiments and calculations. Our second proof uses characteristic functions. We then take up the study of a local limit theorem to accompany our central limit theorem. Here our result is less general, and we must be content with a conjecture about further work. Our local limit theorem permits us to conclude that the coefficients of the q-multinomial are log-concave, provided one stays near the center (where the largest coefficients reside).
|
|
