Search

We introduce a framework for the study of formal contexts and their lattices induced by the additional structure of self-relations on top of the traditional incidence relation. The induced contexts use subsets as objects and attributes, hence the name power context and power concept. Six types of new incidence relations are introduced by taking into account all possible combinations of universal and existential quantifiers as well as the order of the quantifications in constructing the lifted power contexts. The structure of the power concept lattice is investigated through projection mappings from the baseline objects and attributes to those of the power context, respectively. We introduce the notions of extensional consistency and intensional consistency, corresponding to the topological notions of continuity in the analogous setting when concepts are viewed as closed sets. We establish Galois connections for these notions of consistency. We further introduce the notion of faithfulness for the first type of lifted incidence relation based on the fact that it can be equivalently characterized by a concept-faithful morphism. We also present conditions under which the power concept lattice serves as a factor lattice of the base concept lattice.

Known properties of ''canonical connections'' from database theory and of ''closed sets'' from statistics implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls.

Let e and n be positive integers and S={x1,…,xn} a set of n distinct positive integers. For x∈S, define GS(x)≔{d∈S|d

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and [email protected]?{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q"6. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a 'Pentagon' configuration with center e. Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.

Let B 3 ( K ) = { v : ∃ S ( 3 , K , v ) } . For K = { 4 } or { 4 , 6 } , B 3 ( K ) has been determined by Hanani. In this paper, we investigate the case of K = { 4 , 5 } . It is easy to see that if v ∈ B 3 ( { 4 , 5 } ) , then v ≡ 1 , 2 , 4 , 5 , 8 , 10 ( mod 12 ) . It is known that B 3 ( { 4 } ) = { v > 0 : v ≡ 2 , 4 ( mod 6 ) } ⊂ B 3 ( { 4 , 5 } ) by Hanani and that { v > 0 : v ≡ 5 ( mod 12 ) } ⊂ B 3 ( { 4 , 5 } ) by a previous paper of the author. We shall focus on the case of v ≡ 1 ( mod 12 ) . It is proved that B 3 ( { 4 , 5 } ) = { v > 0 : v ≡ 1 , 2 , 4 , 5 , 8 , 10 ( mod 12 ) and v ≠ 13 } .

A subset of a metric space is a k-distance set if there are exactly k non-zero distances occuring between points. We conjecture that a k-distance set in a d-dimensional Banach space (or Minkowski space), contains at most (k+1)^d points, with equality iff the unit ball is a parallelotope. We solve this conjecture in the affirmative for all 2-dimensional spaces and for spaces where the unit ball is a parallelotope. For general spaces we find various weaker upper bounds for k-distance sets., 7 pages, 2 figures

An ordered compact space is a compact topological space X, endowed with a partially ordered relation, whose graph is a closed set of X x X (cf. [4]). An important subclass of these spaces is that of Priestley spaces, characterized by the following property: for every x, y @e X with x @4 y there is an increasing clopen set A (i.e. A is closed and open and such that a @e A, a =< z implies that [email protected]) which separates x from y, i.e., x @e A and y @5 A. It is known (cf. [5, 6]) that there is a dual equivalence between the category Ld01 of distributive lattices with least and greatest element and the category P of Priestley spaces. In this paper we shall prove that a lattice L @e Ld01 is complete if and only if the associated Priestley space X verifies the condition: (E0) D @? X, D is increasing and open implies D^* is increasing clopen (where A^* denotes the least increasing set which includes A). This result generalizes a well-known characterization of complete Boolean algebras in terms of associated Stone spaces (see [2, Ch. III, Section 4, Lemma 1], for instance). We shall also prove that an ordered compact space that fulfils (E0) is necessarily a Priestley space.

Let H a = { vυ : υ ⩾ a + 1, υ ≡ 1 (mod a )}. It is well known that such sets are PBD-closed. Finite bases are found for these sets for a = 5, 6 and 7.

A matroidal family of graphs is a set M≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of M are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n⩾0, −2n, and is minimal with this property (with respect to the relation ⊆))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of M(n, r), s⩾r, we are able to give sufficient and necessary conditions for a subset P(n, r) of M(n, r) to yield a matroidal family of graphs when joined with the set I(n, s) of all graphs G∈M(n, s) which satisfy: If H∈P(n, r), then H⊆G. In particular, it is shown that M(n, r) is not a matroidal family of graphs for r⩾2. Furthermore, for n⩾0, 1−2n

Let L(G), V(G) and Ḡ be, respectively, the closed-set lattice, vertex set, edge set and complement of a graph G. Any lattice isomorphism Φ:L(G)⋍L(G′) induces a bijection Φ:V(G)→V(G′) such that for each x in V(G),Φ(x)=x′ iff Φ({x})={x′}. A graph G is strongly sensitive if for any graph G′ and any lattice isomorphism Φ:L(G)⋍L(G′), the bijection Φ induced by Φ is a graph isomorphism of G onto G′. G is minimally critical if L(G) ∥ L(G-e) for each e in E(G), and maximally critical if L(G) ∥ L(G+e) for any e in E(Ğ). In this paper, we prove that for any two nontrivial graphs G1 and G2, (1) G1 × G2 is maximally critical, and (2) G1 × G2 is strongly sensitive iff G1 × G2 is minimally critical. Necessary and sufficient conditions on G1 such that G1 × G2 is strongly sensitive are also obtained.

In this paper we study the direct product decompositions of closure operations and lattices of closed sets. We characterize the direct product decompositions of lattices of closed sets in terms of closure operations, and find those decompositions of lattices which correspond to the decompositions of closures. If a closure on a finite set is represented by its implication base (i.e. a binary relation on the powerset), we construct a polynomial algorithm to find its direct product decompositions. The main characterization theorem is also applied to define direct product decompositions of relational database schemes and to find out what properties of relational databases and schemes are preserved under the decompositions.

Let L ( T ) be the closed-set latice of a tree T . The lower length l ∗ (L(T)) of L ( T ) is defined as l ∗ (L(T))= min ≈{;|Γ|-1: Γ is a maximal chain in L(T) ≈}; Call a set S of vertices in T a sparse set if d ( x , y ) ⩾ 3 for any two distinct vertices x, y in S. The sparsity γ ( T ) of T is defined as γ ( T ) = max ≈{;| S |: S is a sparse set of T ≈}; We prove that, for any tree T of order n, l ∗ (L(T)) = n + 1 − γ(T) and deduce from this that l ∗ (L(T)) ⩾[n/2] + 1 . All trees T of order n such that l ∗ (L(T)) = [n/2] + 1 are characterized.

Restricted permutations are those constrained by having to avoid subsequences ordered in various prescribed ways. A closed set is a set of permutations all satisfying a given basis set of restrictions. A wreath product construction is introduced and it is shown that this construction gives rise to a number of useful techniques for deciding the finite basis question and solving the enumeration problem. Several applications of these techniques are given.

Denote by l ∗ (L) and l ∗ (L) respectively the upper length and lower length of a finite lattice L. The lattice L is said to be uniform if for each integer k with l ∗ (L) l ∗ (L) there exists in L a maximal chain of length k. It is shown that the closed-set lattice of a finite graph G is uniform if G is a tree. The result is not necessarily true if G is not a tree.

Let B3(K)={v:∃S(3,K,v)}. For K={4} or {4,6}, B3(K) has been determined by Hanani. In this paper, we investigate the case of K={4,5}. It is easy to see that if v∈B3({4,5}), then v≡1,2,4,5,8,10(mod12). It is known that B3({4})={v>0:v≡2,4(mod6)}⊂B3({4,5}) by Hanani and that {v>0:v≡5(mod12)}⊂B3({4,5}) by a previous paper of the author. We shall focus on the case of v≡1(mod12). It is proved that B3({4,5})={v>0:v≡1,2,4,5,8,10(mod12) and v≠13}.

Let Ω⊂{0,1}NΩ⊂{0,1}N be a nonempty closed set with N={0,1,2,…}N={0,1,2,…}. For N={N0