ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.26764 J. Algebra Comb. Discrete Appl. 3(1) • 7–11 Received: 2 March 2015 Accepted: 10 November 2015 Journal of Algebra Combinatorics Discrete Structures and Applications On the rank functions of H-matroids Research Article Yoshio Sano Abstract: The notion of H-matroids was introduced by U. Faigle and S. Fujishige in 2009 as a general model for matroids and the greedy algorithm. They gave a characterization of H-matroids by the greedy algorithm. In this note, we give a characterization of some H-matroids by rank functions. 2010 MSC: 05B35, 90C27 Keywords: Matroid, H-Matroid, Simplicial complex, Rank function 1. Introduction and main result The notion of matroids was introduced by H. Whitney [10] in 1935 as an abstraction of the notion of linear independence in a vector space. Many researchers have studied and extended the theory of matroids (cf. [2, 4, 5, 8, 9]). In 2009, U. Faigle and S. Fujishige [1] introduced the notion of H-matroids as a general model for matroids and the greedy algorithm. They gave a characterization of H-matroids by the greedy algorithm. In this note, we give a characterization of the rank functions of H-matroids that are simplicial complexes, for any family H. Our main result is as follows. Theorem 1.1. Let E be a finite set and let ρ : 2E → Z≥0 be a set function on E. Let H be a family of subsets of E with ∅,E ∈ H. Then, ρ is the rank function of an H-matroid (E,I) if and only if ρ is a normalized unit-increasing function satisfying the H-extension property. (E) (H-extension property) For X ∈ 2E and H ∈H with X ⊆ H, if ρ(X) = |X| < ρ(H), then there exists e ∈ H \X such that ρ(X ∪{e}) = ρ(X) + 1. Moreover, if ρ is a normalized unit-increasing set function on E satisfying the H-extension property and I := {X ∈ 2E | ρ(X) = |X|}, then (E,I) is an H-matroid with rank function ρ and I is a simplicial complex. This work was supported by JSPS KAKENHI Grant Number 15K20885. Yoshio Sano; Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba, Japan (email: sano@cs.tsukuba.ac.jp). 7 Y. Sano / J. Algebra Comb. Discrete Appl. 3(1) (2016) 7–11 This note is organized as follows. Section 2 gives some definitions and preliminaries on H-matroids. In Section 3, we give a proof of Theorem 1.1 and an example which shows H-matroids that are not simplicial complexes are not characterized only by their rank functions. 2. Preliminaries Let E be a nonempty finite set and let 2E denote the family of all subsets of E. For any family I of subsets of E, the extreme-point operator exI : I → 2E and the co-extreme-point operator ex∗I : I → 2 E associated with I are defined as follows: exI(I) := {e ∈ I | I \{e}∈I} (I ∈I), ex∗I(I) := {e ∈ E \ I | I ∪{e}∈I} (I ∈I). For any family I ⊆ 2E, we denote the set of maximal elements of I with respect to set inclusion by Max(I). Let I be a nonempty family of subsets of a finite set E. The family I is called constructible if it satisfies (C) exI(I) 6= ∅ for all I ∈I \{∅}. Note that (C) implies ∅ ∈ I. We call I ∈ I a base of I if ex∗I(I) = ∅. We denote by B(I) the family of bases of I, i.e., B(I) := {I ∈I | ex∗I(I) = ∅}. By definition, it holds that B(I) ⊇ Max(I). A constructible family I induces a (base) rank function ρ : 2E → Z≥0 via ρ(X) = maxB∈B(I)|X ∩B| = maxI∈I|X ∩ I| = maxI∈Max(I)|X ∩ I|. The following is easily verified by definitions. Lemma 2.1. The rank function ρ of a constructible family is normalized (i.e. ρ(∅) = 0) and satisfies the unit-increase property (UI) ρ(X) ≤ ρ(Y ) ≤ ρ(X) + |Y \X| for all X ⊆ Y ⊆ E. Remark that, by putting X = ∅, we obtain (UI)′ 0 ≤ ρ(Y ) ≤ |Y | for all Y ⊆ E. The restriction of I to a subset A ∈ 2E is the family I(A) := {I ∈ I | I ⊆ A}. Note that every restriction of a constructible family is constructible. A simplicial complex is a family I ⊆ 2E such that X ⊆ I ∈ I implies X ∈ I. We can easily check the following lemmas on simplicial complexes. Lemma 2.2. A family I ⊆ 2E is a simplicial complex if and only if exI(I) = I holds for any I ∈I. Proof. The lemma follows from the definitions of a simplicial complex and exI(·). Lemma 2.3. Let I ⊆ 2E be a simplicial complex and let X ∈ 2E. Then, (a) B(I) = Max(I). (b) For X ∈ 2E, X ∈I if and only if ρ(X) = |X|. (c) For H ∈ 2E, the family I(H) ⊆ 2H is a simplicial complex. 8 Y. Sano / J. Algebra Comb. Discrete Appl. 3(1) (2016) 7–11 Proof. (a): Suppose that there exists an element B ∈B(I) \ Max(I). Then, since B is not maximal in I, there exists I ∈I such that B ( I. For any e ∈ I \B, we have B ∪{e}∈ I since B ∪{e}⊆ I and I is a simplicial complex. Therefore e ∈ ex∗I(B). But this is a contradiction to B ∈B(I). (b): If X ∈ I, then ρ(X) = maxI∈I |X ∩ I| = |X|. Take X ∈ 2E with ρ(X) = |X|. Then there exists I ∈I such that |X ∩I| = ρ(X) = |X|. Therefore, X ⊆ I. Since I is a simplicial complex, we have X ∈I. (c): Take any X ∈ 2H and I ∈I(H) := {I ∈I | I ⊆ H} with X ⊆ I. Since I is a simplicial complex, X ∈I. Since X ⊆ H, we have X ∈I(H). We now recall the definitions of an H-independence system and an H-matroid, which were introduced by Faigle and Fujishige [1]. Let E be a finite set and let H be a family of subsets of E with ∅,E ∈H. A constructible family I ⊆ 2E is called an H-independence system if (I) for all H ∈H, there exists I ∈I(H) such that |I| = ρ(H). An H-matroid is a pair (E,I) of the set E and an H-independence system I satisfying the following property: (M) for all H ∈H, all the bases B of I(H) have the same cardinality |B| = ρ(H). 3. Proof of Theorem 1.1 First, we see an example which shows that H-matroids that are not simplicial complexes are not characterized by their rank functions. Example 3.1. Let E = {1,2,3} and H = {∅,E}. Let I1 = {∅,{2},{1,2},{2,3}}, I2 = {∅,{1},{3},{1,2},{2,3}}, I3 = {∅,{1},{2},{3},{1,2},{2,3}}. Then (E,I1), (E,I2), and (E,I3) are H-matroids with the same rank function ρ : 2E → Z≥0 such that ρ(∅) = 0, ρ({1}) = ρ({2}) = ρ({3}) = ρ({1,3}) = 1, and ρ({1,2}) = ρ({2,3}) = ρ({1,2,3}) = 2. Therefore, we cannot distinguish H-matroids in general by their rank functions. More generally, the following holds. Proposition 3.2. For any constructible families I and I′ with Max(I) = Max(I′), the rank function ρ′ associated with I′ coincides with the rank function ρ associated with I. Proof. For any X ∈ 2E, it holds that ρ(X) = maxI∈Max(I)|X ∩ I| = maxI∈Max(I′)|X ∩ I| = ρ′(X) since Max(I) = Max(I′). In the following, we give a proof of Theorem 1.1. Lemma 3.3. For any constructible family, there exists a simplicial complex such that their rank functions are the same. 9 Y. Sano / J. Algebra Comb. Discrete Appl. 3(1) (2016) 7–11 Proof. Let I ⊆ 2E be a constructible family. Define I′ := {X ∈ 2E | X ⊆ I for some I ∈ I}. Then it is clear that I′ is a simplicial complex. Obviously each Y ∈ Max(I) is maximal in I′, and I′ does not have new maximal members. Therefore Max(I) = Max(I′). Note that any simplicial complex is a constructible family. By Proposition 3.2, the rank functions of I and I′ are the same. Lemma 3.4. Let ρ : 2E → Z≥0 be the rank function of an H-matroid (E,I), where I is a simplicial complex. Then ρ satisfies the H-extension property. Proof. Take X ∈ 2E and H ∈ H with X ⊆ H, and suppose that ρ(X) = |X| < ρ(H). By Lemma 2.3 (c), I(H) is a simplicial complex since I is a simplicial complex. Note that B(I(H)) = Max(I(H)) by Lemma 2.3 (a). By Lemma 2.3 (b), X ∈ I. Therefore X ∈ I(H), and X is not a base of I(H) by (I) and (M) since ρ(X) < ρ(H). Thus there exists B ∈I such that X ( B ⊆ H and |B| = ρ(H). Take any element e ∈ B \X ⊆ H \X. Then X ∪{e} ∈ I since X ∪{e} ⊆ B ∈ I and I is a simplicial complex. Hence it follows that ρ(X ∪{e}) = |X ∪{e}| = |X|+ 1 = ρ(X) + 1. Lemma 3.5. Let ρ : 2E → Z≥0 be a normalized unit-increasing function satisfying the H-extension property for some family H⊆ 2E with ∅,E ∈H. Put Iρ := {X ∈ 2E | ρ(X) = |X|}. Then (E,Iρ) is an H-matroid and Iρ is a simplicial complex. Proof. First we show that Iρ is a simplicial complex. Take any I ∈ Iρ \ {∅} and any e ∈ I. Then we have ρ(I) = |I|. Since ρ is unit-increasing, we have ρ(I) ≤ ρ(I \ {e}) + 1 and thus ρ(I \ {e}) ≥ ρ(I) − 1 = |I|− 1 = |I \ {e}|. By (UI) and ρ(∅) = 0, we also have ρ(I \ {e}) ≤ 0 + |I \ {e}| and thus ρ(I \{e}) ≤ |I \{e}|. Therefore we have ρ(I \{e}) = |I \{e}| and thus I \{e}∈Iρ. By Lemma 2.2, Iρ is a simplicial complex. Hence it follows from definitions that Iρ satisfies (C) and (I). Now we show that Iρ satisfies (M). Take any H ∈ H. Suppose that there exist B1,B2 ∈ B(I (H) ρ ) such that |B1| 6= |B2|. Without loss of generality, we may assume that |B1| < |B2| ≤ ρ(H). Note that ρ(B1) = |B1| and ρ(B2) = |B2|. Then, by (E), there exists e ∈ H\B1 such that ρ(B1∪{e}) = ρ(B1)+1 = |B1|+ 1 = |B1 ∪{e}|. Thus we have B1 ∪{e}∈Iρ with B1 ∪{e}⊆ H. But this is a contradiction to the assumption that B1 is a base of I (H) ρ . Thus Iρ satisfies (M). Hence (E,Iρ) is an H-matroid. Proof of Theorem 1.1. It follows from Lemmas 2.1, 3.3, 3.4, and 3.5. Remark 3.6. Strict cg-matroids which were introduced by S. Fujishige, G. A. Koshevoy, and Y. Sano [3] in 2007 can be considered as H-matroids (E,I) where H is an abstract convex geometry and I ⊆H. The rank functions ρ : H→ Z≥0 of strict cg-matroids (E,H;I) are characterized in [6]. For more study on cg-matroids, see [7]. Remark 3.7. Faigle and Fujishige gave a characterization of the rank functions H-matroids when H is a closure space (see [1, Theorem 5.1]). Acknowledgment: The author is grateful to the anonymous referees for careful reading and valu- able comments. References [1] U. Faigle, S. Fujishige, A general model for matroids and the greedy algorithm, Math. Program. Ser. A 119(2) (2009) 353–369. 10 http://dx.doi.org/10.1007%2Fs10107-008-0213-1 http://dx.doi.org/10.1007%2Fs10107-008-0213-1 Y. Sano / J. Algebra Comb. Discrete Appl. 3(1) (2016) 7–11 [2] S. Fujishige, Submodular functions and optimization, Annals of Discrete Mathematics, Elsevier, Amsterdam, 2005. [3] S. Fujishige, G. A. Koshevoy, Y. Sano, Matroids on convex geometries (cg-matroids), Discrete Math. 307(15) (2007) 1936–1950. [4] B. Korte, L. Lovász, R. Schrader, Greedoids, Algorithms and combinatorics, Vol. 4, Springer-Verlag, Berlin, 1991. [5] J. Oxley, Matroid theory, Oxford University Press, Oxford, 1992. [6] Y. Sano, Rank functions of strict cg-matroids, Discrete Math. 38(20) (2008) 4734–4744. [7] Y. Sano, Matroids on convex geometries: subclasses, operations, and optimization, Publ. Res. Inst. Math. Sci. 47(3) (2011) 671–703. [8] A. Schrijver, Combinatorial optimization. Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003. [9] D. J. A. Welsh, Matroid theory, Academic Press, London, 1976. [10] H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57(3) (1935) 509–533. 11 http://dx.doi.org/10.1016/j.disc.2006.09.037 http://dx.doi.org/10.1016/j.disc.2006.09.037 http://dx.doi.org/10.1016/j.disc.2007.08.095 http://dx.doi.org/10.2977/PRIMS/48 http://dx.doi.org/10.2977/PRIMS/48 http://dx.doi.org/10.2307/2371182 Introduction and main result Preliminaries Proof of Theorem 1.1 References