ۥ-!@ L-GhF)oMMMMM[45@u54iMah
Packing Layered Posets Into Posets
draft, 7/18/93
Walter Stromquist
This essay is really about packing numbers of permutations, but the part that has been written so far is about packing posets. This work was inspired by Herb Wilf's questions about packing densities of permutations.
Definitions: Layered and LOT posets and lower sets.
A poset is a nonempty, finite set with a partial ordering denoted as usual by SYMBOL 179 \f "Symbol", SYMBOL 163 \f "Symbol", SYMBOL 62 \f "Symbol", SYMBOL 60 \f "Symbol". We will use the terms "above" and "below" to refer to the relationship between elements in the poset ordering.
A poset P is layered if it can be partitioned into disjoint subsets P1,...,Pn such that xSYMBOL 62 \f "Symbol"y in P iff x SYMBOL 206 \f "Symbol"Pi and y SYMBOL 206 \f "Symbol"Pj with iSYMBOL 62 \f "Symbol"j. That is, elements in each layer are above all elements in lower layers, but distinct elements in the same layer are incomparable.
A poset is layered on top (LOT) if it can be partitioned into two disjoint subsets P1 and P2, with P2 nonempty, such if x is in P2, we have x>y iff y is in P1. Note that if this is the case, then P2 must consist precisely of the maximal elements of P. Thus, the LOT condition means that every maximal element of P is above every non-maximal element. Every layered poset is also LOT.
EMBED MSDraw \* mergeformat EMBED MSDraw \* mergeformat
Typical layered poset: Full comparability between layers, none within a layer.
Typical layered-on-top (LOT) poset: Every maximal element is above every other element.
If x is a maximal element of P, we denote by L(x) the set {y in P | y < x}. We call this the lower set corresponding to x. Note that a poset is LOT iff all maximal elements have the same lower set, and that in this case the lower set is just the set of non-maximal elements.
Packing numbers and packing functions. When posets are "optimal."
Let P and Q be posets. Then the packing number of P in Q, denoted p(P,Q), is defined to be the number of distinct subsets of Q (with ordering inherited from Q) that are isomorphic to P. Viewed as a function of Q, we call p(P,Q) a simple packing function, or the simple packing function corresponding to P, and P is called its pattern. More generally, a packing function is any non-negative linear combination of simple packing functions:
EMBED Equation
where m is a non-negative integer, P1,...,Pm are posets, and a1, ..., am are non-negative real numbers. The ai's are called the coefficients of this packing function, and the Pi's are called the patterns.
In this paper we will be looking for posets Q that maximize a given packing function, given the size of Q. We say that Q is optimal for f if f(Q) >= f(Q') for any poset Q' satisfying |Q'|=|Q|. If |Q|=n, we also say that Q is optimal for f of size n.
We are mainly concerned with simple packing functions. It turns out that our main results are true for general packing functions, and that proving them in that form makes the induction steps easier.
Packing functions with LOT patterns are optimized by LOT posets.
Theorem 1. Let n SYMBOL 179 \f "Symbol"1, let P be a LOT poset, and let f be the simple packing function defined by f(Q)=p(P,Q). Then there is a LOT poset Q which is optimal for f of size n.
Proof. We need some specialized notation. If P and Q are posets with x, y in Q, then we write p(P,Q,x) for the number of subsets of Q that contain x and are isomorphic to P, and we write p(P,Q,not y) for the number of subsets of Q that are isomorphic to P but do not contain y. We combine these notations freely and extend them to general packing functions in the obvious way.
Now let f(Q)=p(P,Q) as in the statement of the theorem. Let us choose a specific poset Q which is optimal for f of size n. Specifically, we choose Q so that among all of the posets that are optimal for f of size n, Q has the largest possible group of maximal elements with identical lower sets. We will suppose that Q is not LOT, and argue to a contradiction.
If Q is not LOT, then we can choose maximal elements x and y of Q with L(x) SYMBOL 185 \f "Symbol" L(y). We choose x and y so that exactly one of them is in that large group of maximal elements with identical lower sets. We will construct another poset Q' with the same underlying set as Q, but which contradicts the choice of Q.
Without loss of generality, assume that
f(Q, x, not y) >= f(Q, y, not x). [1]
If equality holds in [1], then we can also insist that x is the one which is in the large group with identical lower sets.
Now we construct Q' as follows: If u and v in Q are both different from y, then v>u in Q' iff v>u in Q. If u is different from y, then y>u in Q' iff x>u in Q. Thus, we have altered the relationships involving y in order to make L(y) agree with L(x) in Q', and left the relationships not including y alone.
Now:
f(Q') = f(Q', not y) + f(Q', y, not x) + f(Q', x, y).
Let's work on each of these terms separately. For the first term, clearly
f(Q', not y) = f(Q, not y),
since for subsets not including y, the posets Q and Q' are identical. Furthermore, from the construction of Q', we have
f(Q', y, not x) = f(Q, x, not y) >= f(Q, y, not x).
(The first equality comes from counting subsets isomorphic to P: for each such subset of Q' that contains y but not x, we can put x in place of y, and get an isomorphic subset of Q.)
Finally, we derive
f (Q', x, y) >= f(Q, x, y)
from the layered character of P, as follows: Suppose A is a subset of Q' that is isomorphic to P and contains x and y. Then the elements of P corresponding to x and y are both maximal elements of P. All other maximal elements of P must be mapped to
Q' - {x,y} - L(x) - L(y), and all non-maximal elements of P must be mapped to L(x) SYMBOL 199 \f "Symbol" L(y).
But that means that the entire image of P---that is, all of A---is in the part of Q' whose ordering is unchanged from Q. So, A is still isomorphic to P when A is viewed as a subset of Q.
We conclude that
f(Q') = f(Q', not y) + f(Q', y, not x) + f(Q', x, y)
SYMBOL 179 \f "Symbol" f(Q, not y) + f(Q, y, not x) + f(Q, x, y) = f(Q). [2]
Furthermore, if we have a strict inequality in [1], then we have a strict inequality in [2] as well. But that contradicts the optimality of Q. On the other hand, if we have equality in [1] and [2], then Q' and Q are both optimal, but in this case Q' has a larger group of maximal elements with identical lower sets (since y has been brought into the group).
This completes the proof of Theorem 1. //
(Note that the above construction might convert non-maximal elements of Q into maximal elements of Q'. This does not affect the proof.)
Theorem 2 is the same as theorem 1, but for general packing functions.
Theorem 2. Let P1, ..., Pm all be LOT posets, and consider the packing function
f(Q) = a1 p(P1,Q) +... + am p(Pm,Q).
Let n SYMBOL 179 \f "Symbol"1. Then there is a LOT poset Q which is optimal for f of size n.
Proof: The proof is identical to the proof of Theorem 1. //
(Note that theorem 2 does not follow directly from the statement of theorem 1.)
Packing functions with layered patterns are optimized by layered posets.
Theorems 3 and 4 are the same as theorems 1 and 2, but with "layered" in place of "LOT". We will give the proof of Theorem 3. The proof of theorem 4 is an obvious extension of the same proof.
Theorem 3. Let n SYMBOL 179 \f "Symbol"1, let P be a layered poset, and let f be the simple packing function defined by f(Q)=p(P,Q). Then there is a layered poset Q which is optimal for f of size n.
Theorem 4. Let P1, ..., Pm all be layered posets, and consider the packing function
f(Q) = a1 p(P1,Q) +... + am p(Pm,Q).
Let n SYMBOL 179 \f "Symbol"1. Then there is a layered poset Q which is optimal for f of size n.
Proof of Theorem 3: Induct on the size n.
Let Q be optimal for f of size n. From theorem 1, Q must be layered on top. Thus Q consists of some maximal elements which are above all non-maximal elements, and a set Q0 of non-maximal elements. If Q0 is empty, then Q is actually layered and we are done; so we may assume that Q0 is non-empty; and in fact Q0 is a poset of size smaller than n.
If we alter the ordering of Q0 in such a way that it remains a poset, then Q also remains a poset.
Let u1, u2,... be the maximal elements of P, and let x1, x2,... be the maximal elements of Q. Then u1, u2, ... are all interchangeable, and x1, x2,... are, too.
For each value of iSYMBOL 179 \f "Symbol"0, consider the number of subsets of Q which are isomorphic to P and which contain exactly i maximal elements of Q. In each of the isomorphisms, exactly i of the maximal elements of P correspond to the maximal elements of Q---it doesn't matter which maximal elements in either case---and the rest of P corresponds to elements of Q0.
Thus, the number of such packings is
(number of maximal elements of Q)-choose-(i), times
the number of packings of (P with i of its maximal elements removed) in Q0.
It follows that p(P,Q) is just the sum of these terms for i >= 0.
But this sum is just a (general) packing function with Q0 as its argument. (Actually, one of the terms in the sum is a constant independent of Q0, but that doesn't matter.) All of the subsets of P involved in the packing function are layered. If the ordering on Q is such as to maximize p(P,Q), it must be that the ordering on Q0 is such as to maximize this packing function. By the induction assumption, Q0 must be layered. So, Q itself is layered. This completes the proof of Theorem 3. //
Example, and the connection to permutations.
Let Q be a sequence of n distinct numbers q1,...,qn. We might as well suppose that Q is a permutation of 1..n. A "132 pattern" in Q is a triple (i,j,k) with i < j < k but qi--''O/??of:;^
8 Z&MrEdMicrosoft DrawZ&MrEd|Helv???&MrEdxnx
&MrEd--&MrEd&MrEd6:&MrEd|&MrEdp|l&MrEd0`d|,&MrEd $|&MrEdDx|@&MrEdlh&MrEd>nr:&MrEd8fj4&MrEd%&MrEd%&MrEd%H&MrEd%&MrEd%&MrEd%&MrEd%H&MrEd%$&MrEd%N&MrEd%$&MrEd%&MrEd%J&MrEd%r&MrEd%V&MrEd%J&MrEd%P&MrEd%x&MrEd:jn6&MrEd%R&MrEd%XV&MrEd%R&MrEd%P&MrEd%VV&MrEd%P--''$N L>($:@.
) .1&MathType@@\Times New Roman-!f@!Q@!a@!p@
!P@ !Q@!a@!p@6!P@6!Q Times New Roman+-!m!m@4Times New Roman-!(@!)@Y!(@< !,@
!)@!(@!,@V!)@Symbol-!=@y!+@
!+ Times New Roman-!1!1@GMT Extra-!L"System-:pW(|T O .1 `
&MathType@-F*1 -21x-888Times New Roman+-!2!3+!3p!0!464
Symbol-!-:!0Times New Roman+-!. !."System-:.$ .1@`&MathType-P
P.
.\Times New RomanHe-!f!n!n !P@Times New Roman+-!(!)P!max
!(!,`!)!.Symbol-!=!=+Symbol-!pq
!p
Times New RomanHe-!132"System-:. H .1&MathType\Times New Roman-!f!n!kI!n3 !f
!k
!kR!n!k@Times New Roman-!(!)-!max
!(!)Symbol-!=!<x!+b!-Fences--!F!H!Gk!Ik!Kk!JE!L_E!NE!M@!O_@!Q@!PvTimes New Roman-!2"System-F~:#r@230343630+&#(#F3:
~(D .1&MathType-vU -P-P33@Times New Roman+-!a@HSymbol-!=@_!-@!MTimes New Roman+-!1i!2@G!3@h!1@T
!366:Fences--!d:!i@ Times New Roman+-!."System-:g), O .1@&MathType -FV* -2-84848Times New Roman-!b0Symbol-!=`!-!jTimes New Roman-!2H!3!3!464r!."System-z:g7D .1@&MathType-
@Times New Roman-!(@!)@
!;@Times New Roman-!x@!x@!x Times New Roman-!3!2M Times New Roman-!1i !3@Symbol-!+@!+@t!="System-:3`6 .1@&MathType Times New Romans -!a GSymbol-! )Times New Romans -!. !2531"System-:
. .1 `&MathType- 4Times New Roman-!4t!1!1~ !42357 Times New Romanw -!3!4Times New Roman-!a!a!aTimes New Romanw -!(e!)!(B!)!.`Symbol-!-{!-$!"System-??tMSDraw U jZ&MrEdMicrosoft DrawZ&MrEd|Helv???&MrEdHxXxH@
&&MrEd@--D&MrEd&MrEd
&
&MrEd|&MrEdp|l&MrEd0`d|,&MrEd $|&HX&MrEdP PTL&MrEd @PTD&MrEd PT&MrEd PT&MrEdP PTL
&
&MrEd%"&MrEd%&MrEd%&MrEd%"&MrEd%&MrEd%&MrEd%H"&MrEd%H&MrEd%&MrEd%N&MrEd%&MrEd%(&`@&MrEd%h2(&MrEd%(8(&MrEd%(8
&
& @&MrEd%(2&MrEd%8&MrEd%8
&
&p:&MrEd%,&MrEd%2&MrEd%h2
&
&MrEd%(8&MrEd%(b2&MrEd%h8&MrEd%b8&MrEd%"8&MrEd%n>--''O/??Y,,
METAFILEPICTUR Uf* jZ&MrEdMicrosoft DrawZ&MrEd|Helv???&MrEdHxXxH@
&&MrEd@--D&MrEd&MrEd
&
&MrEd|&MrEdp|l&MrEd0`d|,&MrEd $|&HX&MrEdP PTL&MrEd @PTD&MrEd PT&MrEd PT&MrEdP PTL
&
&MrEd%"&MrEd%&MrEd%&MrEd%"&MrEd%&MrEd%&MrEd%H"&MrEd%H&MrEd%&MrEd%N&MrEd%&MrEd%(&`@&MrEd%h2(&MrEd%(8(&MrEd%(8
&
& @&MrEd%(2&MrEd%8&MrEd%8
&
&p:&MrEd%,&MrEd%2&MrEd%h2
&
&MrEd%(8&MrEd%(b2&MrEd%h8&MrEd%b8&MrEd%"8&MrEd%n>--''O/??4MSDraw;^
Z&MrEdMicrosoft DrawZ&MrEd|Helv???&MrEdxnx
&MrEd--&MrEd&MrEd6:&MrEd|&MrEdp|l&MrEd0`d|,&MrEd $|&MrEdDx|@&MrEdlh&MrEd>nr:&MrEd8fj4&MrEd%&MrEd%&MrEd%H&MrEd%&MrEd%&MrEd%&MrEd%H&MrEd%$&MrEd%N&MrEd%$&MrEd%&MrEd%J&MrEd%r&MrEd%V&MrEd%J&MrEd%P&MrEd%x&MrEd:jn6&MrEd%R&MrEd%XV&MrEd%R&MrEd%P&MrEd%VV&MrEd%P--''$N L>($r&MrEd'R
METAFILEPICT;h;^
8 Z&MrEdMicrosoft DrawZ&MrEd|Helv???&MrEdxnx
&MrEd--&MrEd&MrEd6:&MrEd|&MrEdp|l&MrEd0`d|,&MrEd $|&MrEdDx|@&MrEdlh&MrEd>nr:&MrEd8fj4&MrEd%&MrEd%&MrEd%H&MrEd%&MrEd%&MrEd%&MrEd%H&MrEd%$&MrEd%N&MrEd%$&MrEd%&MrEd%J&MrEd%r&MrEd%V&MrEd%J&MrEd%P&MrEd%x&MrEd:jn6&MrEd%R&MrEd%XV&MrEd%R&MrEd%P&MrEd%VV&MrEd%P--''$N L>($ Equation
f(Q)=a1
p(P1
,Q)+L+am
p(Pm
,Q)C
METAFILEPICT@@. ) .1&MathType@@\Times New Roman-!f@!Q@!a@!p@
!P@ !Q@!a@!p@6!P@6!Q Times New Roman+-!m!m@4Times New Roman-!(@!)@Y!(@< !,@
!)@!(@!,@V!)@Symbol-!=@y!+@
!+ Times New Roman-!1!1@GMT Extra-!L"System-v Equation`
2
3
-30.464.
METAFILEPICTppW( O .1 `
&MathType@-F*1 -21x-888Times New Roman+-!2!3+!3p!0!464
Symbol-!-:!0Times New Roman+-!. !."System-V Equation
f(n)=maxpab=nP(132,p).
METAFILEPICTQ.$ .1@`&MathType-P
P.
.\Times New RomanHe-!f!n!n !P@Times New Roman+-!(!)P!max
!(!,`!)!.Symbol-!=!=+Symbol-!pq
!p
Times New RomanHe-!132"System- Equation
f(n)=maxk<nf(k)+kn-k2()[]TIES
METAFILEPICT) H .1&MathType\Times New Roman-!f!n!kI!n3 !f
!k
!kR!n!k@Times New Roman-!(!)-!max
!(!)Symbol-!=!<x!+b!-Fences--!F!H!Gk!Ik!Kk!JE!L_E!NE!M@!O_@!Q@!PvTimes New Roman-!2"System-F~:#r@230343630+&#(#F3V Equation
a=12
3
-1().366P
METAFILEPICT
~( .1&MathType-vU -P-P33@Times New Roman+-!a@HSymbol-!=@_!-@!MTimes New Roman+-!1i!2@G!3@h!1@T
!366:Fences--!d:!i@ Times New Roman+-!."System-v Equation`
b=2
3
-3.464
METAFILEPICTgg) O .1@&MathType -FV* -2-84848Times New Roman-!b0Symbol-!=`!-!jTimes New Roman-!2H!3!3!464r!."System- Equation
(x3
+x2
+x)=13;
METAFILEPICTgHg7 .1@&MathType-
@Times New Roman-!(@!)@
!;@Times New Roman-!x@!x@!x Times New Roman-!3!2M Times New Roman-!1i !3@Symbol-!+@!+@t!="System-V Equation@
a.2531
METAFILEPICT33`6 .1@&MathType Times New Romans -!a GSymbol-! )Times New Romans -!. !2531"System- Equation
4a(1-a)3
(1-a4
).42357FvPvv,NCED
METAFILEPICT
t
. .1 `&MathType- 4Times New Roman-!4t!1!1~ !42357 Times New Romanw -!3!4Times New Roman-!a!a!aTimes New Romanw -!(e!)!(B!)!.`Symbol-!-{!-$!"System-??
PAGE9
il 74730.2425@compuserve.com
PAGE9
PAGE9
PAGE9
23IJLMcdfg|}OPQWXcdez{|u 01df]*+HIJK+08I\fwy ] c e i k
5
6
@
G
I
`
i
-./0:;WXY_ǽX
D(Q
DG
D@yH_`qrs{|
'-./0FGOPik 67KM01LMcdTV*6<=>FG
Z
- ; [ \ r s { ~ !!!!!!!A!B!X!Y!a!h!}!B"C"b"c"""""##$$+$,$w%x%&&'&&&''''((i((((((G)H)J)K)M)N)**]***+ +6+7+e+f+|+}+++++5,6,L,M,Q-R-h-i-*.+.A.B.[.\.r.s.....////0/4/<F<G<R<S<i<j<p<w<<<l==s???????????@@@
@@@@@@AACCDD%D&D'DNDODeDfDhDFFG
ĺdu
DHhs
Do
DصD hjMOQ ] _ 24
ƶzuozz!h!!!R0I.1%.-(7'1%.-
1%.-
1%.-
1%.-!!p!\!J!!!J!*ce"$MO68oqwy "9
C&(TV*,~
IK !f!h!!!""Z#\##${%%%!J!!,!!!t!!!!DQ%%%*&,&o&q&e(g(i((())**++++#,%,,,--E.G.l0n0&1q111111111111122s4lWDT d
Sk1%.-pSk1%.-!!!D!\!,!,!t!!J!!-222 22222222222!2#2%2(2*2,2.20222426282;2=2?2P4lWDT d
4lWDT d
4lWDT d
Sk1%.-?2A2D2F2H2J2L2N2P2R2T2W2Y2[2]2_2a2c2e2g23˺P@;6!t!pSk1%.-4lWDT d
4lWDT d
Sk1%.-4lWDT d
334(4*4,4X4Z444[5]55666666666666666666666ʹ~:lcDT d
1%.-
1%.-!!D!J!!!!!6666666666677777
7
7777777777"7$7&7(7*7,7.7072747ŴŴŴy:lcDT d
1%.-:lcDT d
$476787S7U7W7Y7[7]7_7a7c7e7g7i7k7m7o7q7Ŵh:lcDT d
,
1%.-
1%.-:lcDT d
q7s7u7w7{7}7777777788889@9B999$:&:<:>:::::C;E;;;;;n<p<<<+=Ŵ}wqkf!!h! !!D!,!
1%.-lDT d
1%.-:lcDT d
(+=h=j=l===I>K>T?q?s???@ @"@@@@AAARATAuAwAAABBCC+E-EEEFFBGDGFGYGwGGGGGGGG)+-/9;=!!!!! !!!J!A D D {F=!+28?{FioS
_
*6"<abcdefg%2?23647q7+=hijklmnopq5Times New Roman $%&')+-/045679;= D D D xF=!+28>xFio,~
EFHFxF!!_
*6"<=abcdefgs%2?23647q7+==hijklmnopq5Times New Roman Symbol&ArialWingdings)@J`q ,CCZ"")3)))))0*G***++,,,,D-[---112222213H3i3y3{34494P44455556366667/7F777'8>88889 9"9-9=9?99:):@:::::S>c>e>n>~>>>>>BBBBxF99999999:::9999999999999999999:99:99999999999:::9999:::99!2v22HFfFhFiFnFoFpFrFtFvFxF,4-/05679;G"h
ׅB
ׅ
ׅ? iC:\WORDDOTS\BASIC.DOTPacking PosetsJuly 1993 versionWalter StromquistWalter Stromquist