Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Series

2009

Dartmouth Scholarship

Mathematics

Articles 1 - 5 of 5

Full-Text Articles in Physical Sciences and Mathematics

Counting 1324, 4231-Avoiding Permutations, Michael H. Albert, M. D. Atkinson, Vincent Vatter Nov 2009

Counting 1324, 4231-Avoiding Permutations, Michael H. Albert, M. D. Atkinson, Vincent Vatter

Dartmouth Scholarship

A complete structural description and enumeration is found for permutations that avoid both 1324 and 4231.

Go to article

Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter Jul 2009

Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter

Dartmouth Scholarship

The permutation π of length n, written in one-line notation as π (1)π (2)· · · π (n), is said to contain the permutation σ if π has a subsequence that is order isomorphic to σ, and each such subsequence is said to be an occurrence of σ in π or simply a σ pattern. For example, π = 491867532 contains σ = 51342 because of the subsequence π (2)π (3)π (5)π (6)π (9) = 91672. Permutation containment is easily seen to be a partial order on the set of all (finite) permutations, which we simply denote by ≤. If …

Go to article

Submodular Percolation, Graham R. Brightwell, Peter Winkler Jul 2009

Submodular Percolation, Graham R. Brightwell, Peter Winkler

Dartmouth Scholarship

Let $f:{\cal L}\to\mathbb{R}$ be a submodular function on a modular lattice ${\cal L}$; we show that there is a maximal chain ${\cal C}$ in ${\cal L}$ on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of ${\cal L}$, in a certain well-behaved partial order on sequences of reals. One consequence is that the maximum value of f on ${\cal C}$ is minimized over all such paths—i.e., if one can percolate from 0 to 1 on lattice points X with $f(X)\le b$, then one can do so along a …

Go to article

Perturbative Analysis Of The Method Of Particular Solutions For Improved Inclusion Of High-Lying Dirichlet Eigenvalues, A. H. Barnett May 2009

Perturbative Analysis Of The Method Of Particular Solutions For Improved Inclusion Of High-Lying Dirichlet Eigenvalues, A. H. Barnett

Dartmouth Scholarship

The Dirichlet eigenvalue or “drum” problem in a domain $\Omega\subset\mathbb{R}^2$ becomes numerically challenging at high eigenvalue (frequency) E. In this regime the method of particular solutions (MPS) gives spectral accuracy for many domain shapes. It requires a number of degrees of freedom scaling as $\sqrt{E}$, the number of wavelengths on the boundary, in contrast to direct discretization for which this scaling is E. Our main result is an inclusion bound on eigenvalues that is a factor $O(\sqrt{E})$ tighter than the classical bound of Moler–Payne and that is optimal in that it reflects the true slopes of curves appearing …

Go to article

The Number Of Permutations Realized By A Shift, Sergi Elizalde Jan 2009

The Number Of Permutations Realized By A Shift, Sergi Elizalde

Dartmouth Scholarship

A permutation $\pi$ is realized by the shift on N symbols if there is an infinite word on an N-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as $\pi$. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [J. M. Amigó, S. Elizalde, and M. B. Kennel, J. Combin. Theory Ser. A, 115 (2008), pp. 485–504] that the shortest forbidden patterns of the shift on N symbols have length $N+2$. In this paper we give …

Go to article