Packing densities of layered patterns / Alkes L. Price.

Format:

Book

Manuscript

Microformat

Thesis/Dissertation

Author/Creator:

Price, Alkes L.

Contributor:

University of Pennsylvania.

Language:

English

Subjects (All):

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

Local Subjects:

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

Physical Description:

vii, 134 pages : illustrations ; 29 cm

Production:

1997.

Summary:

By a pattern we mean a fixed permutation $\tau\ \in\ S\sb{m}$. An occurrence of a pattern $\tau$ in a permutation $\sigma\ \in\ S\sb{n}$ is a subsequence $\sigma(i\sb1),\..., \sigma(i\sb{m})$ such that $\sigma(i\sb{j}) <\ \sigma(i\sb{k})\ \Leftrightarrow\ \tau(j) <\ \tau(k).$ A theorem of Galvin, originally conjectured by Wilf, states that, for every $\tau\ \in\ S\sb{m},$ the maximum number of occurrences of $\tau$ in an n-permutation is asymptotically proportional to $n\choose m$; the asymptotic proportionality constant is then called the packing density of $\tau$. As defined by Stromquist, a pattern is layered if its list of entries can be partitioned into layers whose entries are ascending between layers and descending within layers (e.g., 321465). We characterize the packing density of a general layered pattern as the maximum of a polynomial over a compact region. We determine bounds for the packing density, determine explicit packing densities for certain classes of layered patterns, and use the above characterization of the packing density to approximate the packing densities of various layered patterns whose packing densities are not known explicitly.

Notes:

Thesis (Ph.D. in Mathematics) -- University of Pennsylvania, 1997.

Includes bibliographical references and index.

Local Notes:

University Microfilms order no.: 97-27276.

OCLC:

187470475