Packing densities of layered patterns.

Format:

Book

Thesis/Dissertation

Author/Creator:

Price, Alkes Long.

Contributor:

University of Pennsylvania.

Language:

English

Subjects (All):

Mathematics.

0405.

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

Local Subjects:

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

0405.

Physical Description:

134 pages

Contained In:

Dissertation Abstracts International 58-03B.

System Details:

Mode of access: World Wide Web.

text file

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.

Source: Dissertation Abstracts International, Volume: 58-03, Section: B, page: 1324.

Local Notes:

School code: 0175.

ISBN:

9780591362756

Access Restriction:

Restricted for use by site license.