ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 73-82
Poly-antimatroid polyhedra
Yulia Kempner
Holon Institute of Technology, Israel
Vadim E. Levit
Ariel University, Israel
Received 31 October 2011, accepted 28 October 2012, published online 4 March 2013
Abstract
The notion of "antimatroid with repetition" was conceived by Bjorner, Lovasz and Shor in 1991 as an extension of the notion of antimatroid in the framework of non-simple languages. Further they were investigated by the name of "poly-antimatroids" (Nakamura, 2005, Kempner & Levit, 2007), where the set system approach was used. If the underlying set of a poly-antimatroid consists of n elements, then the poly-antimatroid may be represented as a subset of the integer lattice Zn. We concentrate on geometrical properties of two-dimensional (n = 2) poly-antimatroids - poly-antimatroid polygons, and prove that these polygons are parallelogram polyominoes. We also show that each two-dimensional poly-antimatroid is a poset poly-antimatroid, i.e., it is closed under intersection.
The convex dimension cdim(S) of a poly-antimatroid S is the minimum number of maximal chains needed to realize S. While the convex dimension of an n-dimensional poly-antimatroid may be arbitrarily large, we prove that the convex dimension of an n-dimensional poset poly-antimatroid is equal to n.
Keywords: Antimatroid, polyhedron, convex dimension, lattice animal, polyomino. Math. Subj. Class.: 05B35
1 Preliminaries
An antimatroid is an accessible set system closed under union [3]. An algorithmic characterization of antimatroids based on the language definition was introduced in [5]. Another algorithmic characterization of antimatroids that depicted them as set systems was developed in [14]. Dilworth (1940) was the first to study antimatroids, using another axiomatiza-tion based on lattice theory, and they have been frequently rediscovered in other contexts. The most updated survey on the subject may be found in [19].
E-mail addresses: yuliak@hit.ac.il (Yulia Kempner), levitv@ariel.ac.il (Vadim E. Levit)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
106
ArsMath. Contemp. 7 (2014) 74-121
Antimatroids can be viewed as a special case of either greedoids or semimodular lattices, and as a generalization of partial orders and distributive lattices. While classical examples of antimatroids connect them with posets, chordal graphs, convex geometries, etc., game theory gives a framework in which antimatroids are interpreted as permission structures for coalitions [1]. There are also rich connections between antimatroids and cluster analysis [16]. In mathematical psychology, antimatroids are used to describe feasible states of knowledge of a human learner [9].
A poly-antimatroid [21] is a generalization of the notion of the antimatroid to multisets. If the underlying set of a poly-antimatroid consists of n elements, then the n-dimensional poly-antimatroid may be represented as a subset of the integer lattice Zn.
In this paper we investigate the correspondence between poly-antimatroids and poly-ominoes. In the digital plane Z2, a polyomino [12] is a finite connected union of unit squares without cut points. If we replace each unit square of a polyomino by a vertex at its center, we obtain an equivalent object named a lattice animal [13]. Further, we use the name polyomino for the two equivalent objects.
A polyomino is called column-convex (row-convex) if all its columns (rows) are connected. In other words, each column/row has no holes. A convex polyomino is both row-convex and column-convex. The parallelogram polyominoes [6], sometimes known as staircase polygons [4, 13, 22], are a particular case of this family. In the staircase polygon each element may be reached from the source (lowest left) point by a path made only of north and east unit steps, and similarly this element may be reached from the target (highest right) point by a path made only of south and west unit steps. Hence staircase polygons are defined by a pair of monotone north-east paths that have common ending points.
We prove that a representation of a two-dimensional poly-antimatroid on the plane is a staircase polygon.
Let E be a finite set. A set system over E is a pair (E, F), where F is a family of sets over E, called feasible sets. We will use X U x for X U {x}, and X - x for X - {x}.
Definition 1.1. [18]A finite non-empty set system (E, F) is an antimatroid if
(A1) for each non-empty X e F, there exists x e X such that X - x e F
(A2) for all X,Y e F, and X £ Y, there exists x e X - Y such that Y U x e F.
Any set system satisfying (A1) is called accessible.
In addition, we use the following characterization of antimatroids.
Proposition 1.2. [18] For an accessible set system (E, F) the following statements are equivalent:
(i)	(E, F) is an antimatroid
(ii)	F is closed under union (X, Y ei^ X U Y e F)
An "antimatroid with repetition" was invented by Bjorner, Lovasz and Shor [2]. Further it was investigated by the name of "poly-antimatroid" as a generalization of the notion of the antimatroid for multisets. A multiset A over E is a function fA : E ^ N, where fA(e) is a number of repetitions of an element e in A. A poly-antimatroid is a finite nonempty multiset system (E, S) that satisfies the antimatroid properties (A1) and (A2). So antimatroids may be considered as a particular case of poly-antimatroids. Examples of an antimatroid ({x, y, z}, F) and a poly-antimatroid ({x, y}, S) are illustrated in Figure 1.
Y Kempner and V E. Levit: Poly-antimatroidpolyhedra
75
{x,y
{y,y}
0
0
(a)
(b)
Figure 1: (a) Antimatroid. (b) Poly-antimatroid.
Definition 1.3. A multiset system (E, S) satisfies the chain property if for all X,Y e F, and X c Y, there exists a chain X = X0 C Xi c ... C Xk = Y such that X, =
Xj_i U xi and X, e S for 0 < i < k.
It is easy to see that the chain property follows from (A2), but they are not equivalent. It is clear that each poly-antimatroid satisfies the chain property.
Antimatroids have already been investigated within the framework of lattice theory by Dilworth [7]. The feasible sets of an antimatroid ordered by inclusion form a lattice, with lattice operations: X V Y = X U Y, and X A Y is the maximal feasible subset of set X n Y called a basis. Since an antimatroid is closed under union, it has only one basis.
A finite lattice L is called join-distributive [3] if for any x e L the interval [x, y] is Boolean, where y is the join of all elements covering x. Such lattices have appeared under several different names, e.g. locally free lattices [18] and upper locally distributive lattices (ULD) [10, 20]. Distributive lattices are exactly those that are both upper and lower locally distributive.
Theorem 1.4. [3, 18] A finite lattice is join-distributive if and only if it is isomorphic to the lattice of feasible sets of some antimatroid.
It easy to see that feasible sets of a poly-antimatroid ordered by inclusion form a join-distributive lattice as well.
Consider a particular case of antimatroids called poset antimatroids [18]. A poset an-timatroid has as its feasible sets the lower sets of a poset (partially ordered set). Poset antimatroids can be characterized as the unique antimatroids, which are closed under intersection [18]. We extend this definition to poly-antimatroids.
Definition 1.5. A poly-antimatroid is called a poset poly-antimatroid if it is closed under intersection.
Evidently, feasible sets of a poset poly-antimatroid ordered by inclusion form a distributive lattice.
106
ArsMath. Contemp. 7 (2014) 76-121
2 Two-dimensional poly-antimatroids and polyominoes
In this section we consider a geometric characterization of two-dimensional poly-anti-matroids.
Let E = {x, y}. In this case each point A = (xA, yA) in the digital plane Z2 may be considered as a multiset A over E, where xA is a number of repetitions of an element x, and yA is a number of repetitions of an element y in multiset A. Thus a set of points in the digital plane Z2 that satisfies the properties of an antimatroid is a representation of a two-dimensional poly-antimatroid.
Definition 2.1. A set of points S in the digital plane Z2 is a poly-antimatroid polygon if
(A1) for every point (xA, yA) G S, such that (xA, yA) = (0,0), either (xA - 1, yA) G S or (xA, yA — 1) G S (A2) for all A £ B G S,
if xA > xB and yA > yB then either (xB + 1, yB) G S or (xB, yB + 1) G S if xa < xb and yA > yB then (xb , yB + 1) G S if xa > xb and yA < yB then (xb + 1, yB) G S
Notice that accessibility implies 0 G S.
For example, see a poly-antimatroid polygon in Figure 2.
A.
• • • • • • *B
• • • • • • • • •
0 1 2
Figure 2: A poly-antimatroid polygon.
We use the following notation [17]. If A
4-neighborhood N4(x, y) is the set of points
(x, y) is a point in a digital plane, the
N4(x, y) = {(x - 1, y), (x, y - 1), (x +1, y), (x, y + 1)} and 8-neighborhood N8(x, y) is the set of points
Ng(x,y) = {(x - 1, y), (x, y - 1), (x + 1,y), (x,y + 1), (x - 1,y - 1),
(x - 1, y + 1), (x + 1,y - 1), (x + 1,y + 1)}.
Let m be any of the numbers 4 or 8. A sequence A0, Ai,..., An is called an Nm-path if Aj G Nm(Ai-1) for each i = 1, 2, ...n. Any two points A, B G S are said to be Nm-connected in S if there exists an Nm-path A = A0, A1,..., An = B from A to B such that Aj G S for each i = 1,2, ...n. A digital set S is an Nm-connected set if any two points
y
1
x
Y Kempner and V E. Levit: Poly-antimatroidpolyhedra
77
P,Q from S are Nm-connected in S. An Nm-connected component of a set S is a maximal subset of S, which is Nm-connected.
An Nm-path A = A0, A^..., An = B from A to B is called a monotone increasing Nm-path if Aj C Ai+1 for all 0 < i < n, i.e.,
(xAi < XAi+1) A (yAi < yAi+1) or (xAi < xAi+1) A (yA. < Vaí+1 ).
The chain property and the fact that the family of feasible sets of a poly-antimatroid is closed under union mean that for each two points A, B: if B C A, then there is a monotone increasing N4-path from B to A, and if A is incomparable with B, then there is a monotone increasing N4-path from both A and B to A U B = (max(xA,xB), max(yA,yB)). In particular, for each A g S there is a monotone decreasing N4-path from A to 0. So, we can conclude that a poly-antimatroid polygon is an N4-connected component in the digital plane Z2.
Definition 2.2. A point set S C Z2 is defined to be orthogonally convex if, for every line L that is parallel to the x-axis (y = y*) or to the y-axis (x = x*), the intersection of S with L is empty, a point, or a single interval ([(x1, y*), (x2, y*)] = {(x1, y*), (x1 +
It follows immediately from the chain property that every poly-antimatroid polygon S is both connected and orthogonally convex.
In what follows we prove that poly-antimatroid polygons are closed not only under union, but under intersection as well.
Lemma 2.3. A poly-antimatroid polygon is closed under intersection, i.e., if two points A = (xA, yA) and B = (xB, yB) belong to a poly-antimatroid polygon S, then the point A n B = (min(xA, x^), min(yA, Vb)) G S.
Proof. The claim of the lemma is evident for two comparable points. Consider two incomparable points A and B, and assume without loss of generality that xA < xB and yA > yB. Then there is a monotone decreasing N4-path from A to 0, and so there is a point C = (xC, yB) G S on this path with xC < xA. Hence, the point A n B belongs to S, since it is located on the monotone increasing N4-path from C to B.	□
Thus, every poly-antimatroid polygon is a distributive lattice polyhedron [11], since
x, y G S ^ min(x, y), max(x, y) G S. Consider the following rectangles:
R = {(x, y) G Z2 : xmin < x < xmax A Vmin < y < Vmax} and |R > 1 Definition 2.4. The sequence of n rectangles C1, C2,..., Cn is called regular if
1, y*)>..., (x2, y*)}).
(a) = y^ =0
and for each 1 < i < n - 1 at least one of the inequality is strong
(c) xH1 < xi A y4^1 < n1 for each 1 < i < n - 1
,¿+1
,i+1
and for each 1 < i < n - 1 at least one of the inequality is strong
Lemma 2.3 implies that every poly-antimatroid polygon is a union of rectangles built on each pair of incomparable points. The following is even more explicit.
106
ArsMath. Contemp. 7 (2014) 78-121
Lemma 2.5. Every poly-antimatroid polygon is a regular sequence of rectangles.
Proof. Consider the set of rectangles built on pairs of incomparable points and leave only maximal rectangles, i.e., rectangles that are not covered completely by other rectangles. These rectangles forms a regular sequence. Indeed, the property (a) and (c) follows from the definition of a poly-antimatroid polygon (A1).
Suppose there are two maximal rectangles Rm and R2 with two incomparable minimal points (x^in, ylnin) and (xmin, y^iin). Then, since poly-antimatroid polygons are closed under union and under intersection, these rectangles are covered by two rectangles. The minimal and maximal points of the first rectangle are
(min(x1lnin, x^in), mintóin, ^iíj), (min^lx, xlx), min^ax , ymax)) • The minimal and maximal points of the second rectangle are
(max(xmin, xmin), max(ymin, ymin)), (max(xmax, Xmax), max(ymax, ymax))
respectively. There are the cases that these two rectangles are identical. See Figure 3. Thus the rectangles Rm and R2 are not maximal and so all minimal points are comparable. The same is true for maximal points as well.	□
Rm
Rm
Rm
Rm
y
y
0
x
x
Figure 3: Two examples for proof of Lemma 2.5.
The following theorem shows that a poly-antimatroid polygon is a parallelogram poly-omino.
Theorem 2.6. A set of points S in the digital plane Z2 is a poly-antimatroid polygon if and only if it is an orthogonally convex N4-connected set that is bounded by two monotone increasing N4-paths between (0,0) and the maximum point of the set (xmax, ymax).
To prove the "if" part of Theorem 2.6 it remains to give a definition of the boundary.
A point A in set S is called an interior point in S if N8(A) G S. A point in S which is not an interior point is called a boundary point. All boundary points of S constitute the boundary of S. We can see a poly-antimatroid polygon with its boundary in Figure 4.
Since poly-antimatroid polygons are closed under union and under intersection, there are six types of boundary points that we divide into two sets - lower and upper boundary:
Blower = {(x,y) G S : (x + 1,y) G S V (x,y - 1) G S V (x + 1,y - 1) G S}
Y Kempner and V E. Levit: Poly-antimatroidpolyhedra
79
B
10
B18 (xmax , ymax)
Bg
Bu
B 0 B i B 4	x
Figure 4: A boundary of a poly-antimatroid polygon.
= {(x,y) e S : (x - 1, y) eS V (x,y + 1) /S V (x - 1,y + 1) e S}
It is possible that Biower n Bupper = 0. For example, the point B10 in Figure 4 belongs to both the lower and upper boundaries.
From Lemma 2.5 it follows immediately that lower and upper boundaries are boundaries of regular sequence of rectangles and so a poly-antimatroid polygon is an orthogonally convex N4-connected set bounded by two monotone increasing N4-paths. The following lemma is the "only-if" part of Theorem 2.6.
Lemma 2.7. An orthogonally convex N4-connected set S that is bounded by two monotone increasing N4-paths between (0,0) and (xmax, ymax) is a poly-antimatroid polygon.
Proof. By Definition 2.1 we have to check the two properties (A1) and (A2):
(A1) Let A = (x, y) e S. If A is an interior point in S then (x — 1, y) e S and (x, y — 1) e S. If A is a boundary point, then the previous point on the boundary ((x, y — 1) or (x - 1 , y) ) belongs to S.
(A2) Let A ^ B e S. Consider two cases:
(i)	xa > xb and ya > yb. If B is an interior point in S then (xb + 1, yb) e S and (xb, yb + 1) e S. If B is a boundary point, then the next point on the boundary ((xb, yb + 1) or (xb + 1, yb)) belongs to S.
(ii)xa	< xb and ya > yb. We have to prove that (xb, yb +1) e S. Suppose the opposite. Then the point B is an upper boundary point. Since ya > yb there exists an upper boundary point (xa, y) with y > yb that contradicts the monotonicity of the boundary.	□
Corollary 2.8. Any poly-antimatroid polygon S may be represented as the union of its boundary:
S Blower V Bupper {X^ U Y : X e Blower, Y e Bupper }
y
3 Convex dimension
Definition 3.1. Convex dimension [18] cd«m(S) of any antimatroid S is the minimum number of maximal chains
0 = Xo C Xi C ... C Xk = Xmax with Xi = Xi-1 U xi
whose union gives the antimatroid S.
106
ArsMath. Contemp. 7 (2014) 80-121
The set of maximal chains sufficient to realize a poly-antimatroid is called a convex realizer.
The result of Corollary 2.8 shows that the convex dimension of a two-dimensional poly-antimatroid equals two. Note, that the convex dimension of an arbitrary three-dimensional poly-antimatroid may be arbitrarily large [8]. Let S be a set of points:
S = {(x,y,z) : (0 < x,y < N) A (0 < z < 1) A (z = 1 ^ x + y > N)}.
It is easy to check that S is a three-dimensional poly-antimatroid. Consider N +1 points (x, y, 1) with x + y = N. Since each of these points cannot be represented as a union of any points from S with smaller coordinates, the convex dimension of S is at least
N + 1.
In the sequel we prove that the convex dimension of an n-dimensional poset poly-antimatroids is at most n.
An endpoint of a feasible set X is an element e G X such that X — e is a feasible set too. A feasible set that has only one endpoint is called a path of the antimatroid. It is easy to see that a path is an union-irreducible element of the lattice and each feasible set is the union of its path subsets. The family of ideals in the set of paths partially ordered by set inclusion forms path poset antimatroid.
Theorem 3.2. [18] The convex dimension of antimatroid is equal to the width of its path poset.
It is easy to check that the theorem holds for poly-antimatroids as well. Denote by dim(S) the order dimension of the lattice of feasible multisets of a poly-antimatroid. The order (or the Dushnik-Miller) dimension of a poset is the smallest number of total orders the intersection of which gives the partial order.
Corollary 3.3. [18]
dim(S) < cdim(S)
Since any n-dimensional poly-antimatroid may be represented as a subset of the integer lattice Zn, its order dimension is at most n [23].
For poset poly-antimatroids their convex dimension should equal to order dimension, since feasible sets of a poset poly-antimatroid form a distributive lattice and order dimension of distributive lattice is equal to the width of its path poset (ideals of the union-irreducible elements)[23]. Eventually, we obtain the following.
Proposition 3.4. The convex dimension of the n-dimensional poset poly-antimatroids is at most n.
4 Conclusions
It turned out that a two-dimensional case of a poly-antimatroid known in this paper as a poly-antimatroid polygon is equivalent to special cases of polyominoes, lattice animals, and staircase polygons. It seems to be a challenging problem to generalize the path structure of poly-antimatroid polygons to upper dimensions.
Y Kempner and V E. Levit: Poly-antimatroidpolyhedra
81
References
[1]	E. Algaba, J. M. Bilbao, R. van den Brink and A. Jimenez-Losada, Cooperative Games on Antimatroids, Discrete Math. 282 (2004), 1-15.
[2]	A. Bjorner, L. Lovasz and P. R. Shor, Chip-firing games on graphs, European Journal of Combinatorics 12 (1991), 283-291.
[3]	A. Bjorner and G.M. Ziegler, Introduction to greedoids, in N. White (ed.), Matroid applications, Cambridge Univ. Press, Cambridge, UK, 1992.
[4]	M. Bousquet-Melou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996), 1-25.
[5]	E. A. Boyd and U. Faigle, An algorithmic characterization of antimatroids, Discrete Appl. Math. 28 (1990), 197-205.
[6]	M. Delest, J. P. Dubernard and I. Dutour, Parallelogram polyominoes and corners, J. Symb. Comp. 20 (1995), 503-515.
[7]	R. P. Dilworth, Lattices with unique irreducible decomposition, Ann. Math. 41 (1940), 771777.
[8]	D. Eppstein, Upright-Quad Drawing of st-planar learning spaces, J. Graph Algorithms Appl. 12 (2008), 51-72.
[9]	J.-Cl. Falmagne and J.-P. Doignon, Learning Spaces: Interdisciplinary Applied Mathematics, Springer-Verlag, Berlin, 2011.
[10]	S. Felsner and K. Knauer, ULD-Lattices and A-Bondes, Comb. Probab. Comput. 18, (2009), 707-724.
[11]	S. Felsner and K. Knauer, Distributive lattices, polyhedra, and generalized flow, Eur. J. Combin. 32 (2011), 45-59.
[12]	S. W. Golomb, Checker boards and polyominoes, Amer. Math. Monthly 61, no. 10 (1954), 675-682.
[13]	A. G. Guttmann (ed.), Polygons, Polyominoes and Polycubes (Lecture Notes in Physics, 775), Springer, 2009.
[14]	Y. Kempner and V. E. Levit, Correspondence between two antimatroid algorithmic characterizations, Electron. J. Comb. 10 (2003), R44.
[15]	Y. Kempner and V. E. Levit, A Geometric Characterization of Poly-antimatroids, Electron. Notes Discrete Math. 28 (2007), 357-364.
[16]	Y. Kempner and I. Muchnik, Clustering on antimatroids and convex geometries, WSEAS Transactions on Mathematics 2 (2003), 54-59.
[17]	R. Klette and A. Rosenfeld, Digital geometry: geometric methods for digital picture analysis, Morgan Kaufmann, San Francisco, 2004.
[18]	B. Korte, L. Lovasz and R. Schrader, Greedoids, Springer-Verlag, New York/Berlin, 1991.
[19]	B. Monjardet, The consequences of Dilworth's work on lattices with unique irreducible decompositions, in: K. P. Bogart, R. Freese, and J. P. S. Kung (eds.) The Dilworth theorems, Birkhauser Boston, Boston, MA, 1990, 192-199, an updated version: http://cams. ehess.fr/docannexe.php?id=1145
[20]	B. Monjardet, The presence of lattice theory in discrete problems of mathematical social sciences. Why, Math. Social Sci. 46 (2003), 103-144.
[21]	M. Nakamura, Characterization of polygreedoids and poly-antimatroids by greedy algorithms, Oper. Res. Lett. 33 (2005), 389-394.
106	ArsMath. Contemp. 7 (2014) 82-121
[22]	S.C. Nandy and B.B. Bhattacharya, On finding an empty staircase polygon of largest area (width) in a planar point-set, Comput. Geometry 26 (2003), 143-171.
[23]	W. T. Trotter, Combinatorics and Partially ordered sets. Dimension Theory, Johns Hopkins University Press, Baltimore, 1992.