Dependency relations

Abstract

In this paper, we introduce a notion of dependency between subsets of an arbitrary fixed non-empty set $\Omega$. To be more detailed, we introduce a preorder $\leftarrow$ on the power set $\mathcal {P}(\Omega )$ having the further property that $B \leftarrow A$ if and only if $\{b\} \leftarrow A$ for any $b \in B$. We shall argue that this relation generalizes well-studied notions of dependence occurring in such fields as linear algebra, topology, and combinatorics. Furthermore, we show that this relation is characterized by two set operators whose fixed points have interesting geometric and order-theoretic properties. After giving some some elementary results about such a dependency relation, we provide some specific examples taken from graph theory. An interesting property we will provide consists of the possibility to characterize partial orders on a finite lattice in terms of a suitable dependency relation. Finally, we introduce and analyze some specific classes of dependency relations, namely attractive and anti-attractive dependency relations.

1 Introduction

The search for axioms characterizing the so-called dependency relations is a typical topic of mathematical logic and related fields [2, 3]. Moreover, in a non-logical scope, the search for dependency axioms has been developed in different areas of mathematics [21, 23, 25, 27] and theoretical computer science [1], though in these works the corresponding axiomatizations have been formulated in non-equivalent ways.

The main purpose of the present paper consists of providing an axiomatization for dependency sufficiently general to frame within it a broad gamut of mathematical structures which are usually studied in contexts different from each other, such as graphs, digraphs, metric spaces, posets, topological spaces, vector spaces endowed with a bilinear form, group actions, information systems [24] and relational data tables [28].

Currently, there are several studies (for some examples see [4,5,6, 8, 10, 11, 22, 29, 30, 33]) in which the mutual interrelation between topological, combinatorial and order properties make sure that they could be framed in a broader theory of dependence.

The second set operator, denoted by $Ic_\leftarrow$, is a particular type of intensive operator having several interesting properties. The members of the fixed point family $INDP(\leftarrow )$ of $Ic_\leftarrow$ are exactly the subsets A of $\Omega$ such that $\{a\} \nleftarrow A{\setminus } \{a\}$ for any $a\in A$. Therefore, we can think of them as the natural candidates for the role of $\leftarrow$independent subsets of $\Omega$.

Independent sets have been broadly studied in matroid theory. In this setting, the family of dependent sets consists of non-independent subsets. In particular, taking the collection of all minimal dependent sets, we get the circuits through which a definition of matroid may be provided. This definition is cryptomorphic to that classically provided by means of the independent sets [32]. For many other cryptomorphic definitions of a matroid on a finite set $\Omega$, we refer the reader to [31]. In this context, let us also remind that independent sets may be also defined as certain subsets induced by closure operators satisfying an exchange property (for details see [31]).

At this point, we observe that in topology and in matroid theory, both closed and independent subsets do not arise from a specific binary relation on $\mathcal {P}(\Omega )$, but they are given as set systems satisfying specific axioms.

Now, given a pairing $\mathfrak {P}:=(U, F, \Lambda )$ on $\Omega$, for any $A\in \mathcal {P}(\Omega )$ we consider the equivalence relation $\equiv _A$ on U defined by $u\equiv _A u'$ if $F(u,a)=F(u',a)$ for any $a\in A$, and also the binary relation $\leftarrow _{\mathfrak {P}}$ on $\mathcal {P}(\Omega )$ given by $B \leftarrow _{\mathfrak {P}}A$ if the set partition induced by $\equiv _A$ is finer than the set partition induced by $\equiv _B$. Then it is immediate to verify that $\leftarrow _{\mathfrak {P}}$ is a dependency relation on $\mathcal {P}(\Omega )$. Therefore, by means of pairings, we can obtain many different examples of dependency relations.

We also recall here that, in theoretical computer science, when the set $\Omega$ is given as a specific finite set of attributes (or also properties), a pairing $\mathfrak {P}$ on $\Omega$ can be considered as a relational data table [28], on the attribute set $\Omega$. In such a context, the above described dependency relation $\leftarrow _{\mathfrak {P}}$ is known as attribute functional dependency, and it is a fundamental notion in database theory and related fields [28] (for a recent work on connections between algebra and functional dependency, see [17]).

2 Background and notation

In this paper we denote by $\Omega$ a fixed non-empty set and by $\mathcal {P}(\Omega )$ its power set. We also set $\mathcal {P}(\Omega )^2:=\mathcal {P}(\Omega )\times \mathcal {P}(\Omega )$. We denote by $\hat{n}$ the set $\{1,\dots ,n\}$ and by $\left( {\begin{array}{c}\Omega \\ k\end{array}}\right)$ the collection of all subsets of $\Omega$ with k elements. An element $\mathcal {F}\in \mathcal {P}(\mathcal {P}(\Omega ))$ is called a set system on $\Omega$ and an element $\mathcal {D}\in \mathcal {P}(\mathcal {P}(\Omega )^2)$ is called a binary relation on $\mathcal {P}(\Omega )$.

In what follows, if a binary relation on $\mathcal {P}(\Omega )$ is denoted by $\leftarrow$ (or with a similar symbol) we write $A \leftarrow B$ instead of $(A, B) \in \,\, \leftarrow$. On the other hand, if the binary relation on $\mathcal {P}(\Omega )$ is denoted by $\mathcal {D}$ (or with a similar capital letter), we write $(A,B)\in \mathcal {D}$.

If $\mathcal {B}, \mathcal {A}\in \mathcal {P}(\mathcal {P}(\Omega ))$ and $\leftarrow$ is a binary relation on $\mathcal {P}(\Omega )$, we write $\mathcal {B}\leftarrow ^{ext} \mathcal {A}$ if $B \leftarrow A$ for all $B\in \mathcal {B}, A\in \mathcal {A}$.

A set operator on $\Omega$ is a map $\sigma : \mathcal {P}(\Omega ) \rightarrow \mathcal {P}(\Omega )$ and we denote by $\mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$ the collection of all the set operators on $\Omega$.

We will consider the maps:

• $Fix: \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )} \rightarrow \mathcal {P}(\mathcal {P}(\Omega ))$, where $Fix(\sigma ):=\{A\in \mathcal {P}(\Omega ): \sigma (A)=A\}$;

• $Int : \mathcal {P}(\mathcal {P}(\Omega )) \rightarrow \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$, where $Int_{\mathcal {F}}(C):= \bigcap \{A\in \mathcal {F}: C \subseteq A\}$;

• $Dc: \mathcal {P}(\mathcal {P}(\Omega )^2 \rightarrow \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$, where $Dc_{\mathcal {D}}(C):=\bigcup \{B\in \mathcal {P}(\Omega ): (B, C) \in \mathcal {D}\}$;

• $Inc: \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )} \rightarrow \mathcal {P}(\mathcal {P}(\Omega )^2$, where $Inc(\sigma ):=\{(B,A)\in \mathcal {P}(\Omega )^2: B\subseteq \sigma (A)\}$;

for any $\sigma \in \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$, $\mathcal {F}\in \mathcal {P}(\mathcal {P}(\Omega ))$, $C\in \mathcal {P}(\Omega )$.

In the whole paper, whenever we consider basic notions and corresponding results concering partially ordered sets (briefly posets), we refer the reader to [19]. A partially ordered set (abbreviated poset) is a pair $P=(\Omega , \le )$, where $\Omega$ is a set and $\le$ is a binary, reflexive, antisymmetric and transitive relation on $\Omega$. If $P=(\Omega ,\le )$ is a partially ordered set and $x, y\in \Omega$, we also write $x < y$ if $x \le y$ and $x\ne y$. If x, y are two distinct elements of $\Omega$, we say that ycoversx, denoted by $x \lessdot y$ if $x \le y$ and there exists no element $z\in \Omega$ such that $x< z < y$. If $\mathbb {L}$ is a lattice with least element $\hat{0}_\mathbb {L}$ and $x \in \mathbb {L}$, we say that x is join-irreducible if $x \ne \hat{0}_{\mathbb {L}}$ and $x=y \vee z$ implies $x=y$ or $x=z$ for any $y,z \in \mathbb {L}$. We denote by $\mathcal {J}(\mathbb {L})$ the family of all join-irreducible elements of $\mathbb {L}$.

A set system $\mathcal {F}\in \mathcal {P}(\mathcal {P}(\Omega ))$ is called an abstract simplicial complex if $\mathcal {F}\ne \emptyset$ and it is closed under taking subsets, i.e. $X \in \mathcal {F}$ and $Y \subseteq X$ imply $Y \in \mathcal {F}$.

A set system $\mathcal {F}\in \mathcal {P}(\mathcal {P}(\Omega ))$ is called a topped intersection structure [19], or, equivalently, a convexity [6], on $\Omega$, if $\Omega \in \mathcal {F}$ and whenever $\{A_i: i\in I\}\subseteq \mathcal {F}$ also $\bigcap _{i\in I}A_i \in \mathcal {F}$. We denote by $CONV(\Omega )$ the set of all convexities on $\Omega$.

A set operator $\sigma \in \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$ is called a closure operator on $\Omega$ [19], or, equivalently, a convex hull on $\Omega$ [6] if:

• $A \subseteq \sigma (A)$;

• $A\subseteq B$ implies $\sigma (A)\subseteq \sigma (B)$;

• $\sigma (\sigma (A))=\sigma (A)$.

for any $A, B\in \mathcal {P}(\Omega )$. We denote by $CLOP(\Omega )$ the set of all closure operators on $\Omega$.

Theorem 2.1

[19] Let $\mathcal {F}\in CONV(\Omega )$ and $\sigma \in CLOP(\Omega )$. Then $Int_{\mathcal {F}}\in CLOP(\Omega )$, $Fix(\sigma )\in CONV(\Omega )$, $Fix(Int_{\mathcal {F}})=\mathcal {F}$ and $Int_{Fix(\sigma )}=\sigma$. Moreover, $(\mathcal {F}, \subseteq )$ is a complete lattice, usually called closure lattice induced by $\mathcal {F}$.

Theorem 2.1 asserts that the notions of convexity and closure operator on the same set $\Omega$ are mutually equivalent.

To conclude this section, we recall the basic notions of graph theory which we use in this work. We refer to [20] for any general notion concerning graph theory. Let $G=(V(G),E(G))$ be a finite simple (i.e. no loops and no multiple edges are allowed) undirected graph, with vertex set $V(G)=\{v_1,\dots ,v_n\}$ and edge set E(G). In this case, we also use the term n-graph. If $v, v'\in V(G)$, we will write $v \sim v'$ if $\{v,v'\}\in E(G)$ and $v \not \sim v'$ otherwise. The open neighborhood of the vertex v is the subset $N_G(v):=\{v'\in V(G): v\sim v'\}$. If v and w are two vertices of G, we call a sequence of vertices $v_0 \dots v_k$, where $v_0=v$ and $v_1=w$, a path between v and w. The number of edges of the path between v and w is called the length of the path. We denote by d(v, w) the distance between v and w, i.e. the length of any shortest path between v and w. A graph is said connected if there exists a path for any pair of vertices v and w. We denote by $C_n$ and $P_n$ respectively the n-cycle and the n-path on the vertex set $\{v_1,\dots ,v_n\}$. In what follows, all index sums of $C_n$ are implicitly taken mod(n).

3 Abstract dependency and related operators

In this section, we provide the notion of dependency relation with relative examples taken from various mathematical contexts and, next, we associate with any dependency relation $\leftarrow$ two set operators, namely $Dc_\leftarrow$ and $Ic_\leftarrow$, whose fixed point sets are respectively the closed and the independent subsets.

Definition 3.1

A dependency relation on $\mathcal {P}(\Omega )$ is a binary relation $\leftarrow$ on $\mathcal {P}(\Omega )$ such that

(D1):

$B \subseteq A \implies B \leftarrow A$;

(D2):

$C \leftarrow B, \,\, B\leftarrow A$$\implies$$C \leftarrow A$;

(D3):

$\{b\} \leftarrow A\,\,\, \forall b\in B \implies B \leftarrow A$.

If $B \leftarrow A$, we say that Bdepends on A. If $B \nleftarrow A$, we say that B that Bdoes not depend on A. We denote by $DREL(\Omega )$ the set of all dependency relations on $\mathcal {P}(\Omega )$. We say that B is $\leftarrow$trivial if $B \leftarrow \emptyset$ and not$\leftarrow$trivial otherwise. We say that $\leftarrow$ is pointwise non-trivial if any $b\in \Omega$ is not $\leftarrow$trivial. We denote by $DREL_{pnt}(\Omega )$ the set of all pointwise non-trivial dependency relations on $\mathcal {P}(\Omega )$. We use the notation $B\nleftarrow _{\forall } A$ whenever $\{b\} \nleftarrow A$ for all $b\in B$.

Remark 3.2

(i): If $\leftarrow$ is a dependency relation on $\mathcal {P}(\Omega )$, then the condition (D3) is equivalent to the following condition

$$\begin{aligned} \{b\} \leftarrow A\,\,\,\, \forall b\in B \iff B \leftarrow A \end{aligned}$$

(ii): Clearly, $DREL(\Omega )$ is a (proper) subset of $\mathcal {P}(\mathcal {P}(\Omega )^2)$.

We now provide several examples of dependency relations $\leftarrow$ taken from various mathematical contexts.

• Let $\tau$ be a topology on $\Omega$. Then $B\leftarrow A$ if $B\subseteq \overline{A}$, where $\overline{A}$ is the topological closure of A.

• Let $(\Omega , d)$ be a metric space, then we set $B\leftarrow A$ if whenever $u, u'\in \Omega$ and $d(u, a)=d(u',a)$ for any $a\in A$, then we also have $d(u,b)=d(u',b)$ for all $b\in B$.

• Let $(\Omega , d)$ be a metric space and $S_1(u):=\{x \in \Omega : \, d(u,x)=1\}$. Then, we set $B\leftarrow A$ if $S_1(u) \cap A = S_1(v') \cap A$ implies $S_1(v) \cap B = S_1(v') \cap B$, for $u,u'\in \Omega$

• Let $\Omega :=V(G)$ be the vertex subset of a graph G. We set $B\leftarrow A$ if $N_G(v) \cap A = N_G(v') \cap A$ implies $N_G(v) \cap B = N_G(v') \cap B$, for $v, v'\in V(G)$.

• Let U and $\Omega$ be two arbitrary sets and $R \subseteq U \times \Omega$ be any binary relation on $U \times \Omega$. If $A \in \mathcal {P}(\Omega )$ we set $A^\downarrow :=\{u \in U: \, (u,a) \in R \,\,\, \forall a \in A\}$. Moreover, if $X \in \mathcal {P}(U)$, we set $X^\uparrow :=\{b \in \Omega : \, (x,b) \in R \,\,\, \forall x \in X \}$. We set $B \leftarrow A$ if $B \subseteq (A^\downarrow )^\uparrow$.

• Let $\Omega :=M$ be a left-module over any unitary ring R. We set $B\leftarrow A$ if $B \subseteq \mathrm{Span}_R(A)$, where $\mathrm{Span}_R(A)$ denotes the linear span of A.

• Let V be a vector space over a field $\mathbb {K}$ and $\varphi : V \times V \rightarrow \mathbb {K}$ a $\mathbb {K}$-bilinear form on V. Let $\Omega =V$. If $A\subseteq V$, let $A^\perp$ be the orthogonal subspace of A with respect to $\varphi$, i.e. $A^\perp :=\{v \in V: \, \varphi (v,a)=0 \, \, \forall a \in A\}$. Then we consider the binary relation on $\mathcal {P}(V)$ given by $B\leftarrow A$ if $v+ A^\perp \subseteq v+B^\perp$ for any $v\in V$.

• Let G be a group acting on $\Omega$. If A is a subset of $\Omega$, the stabilizer of A is the subgroup of G defined by $\mathrm{Stab}_G(A)=\{g \in G: \, ga=a \, \, \forall a \in A\}$. Then, the binary relation defined by $B \leftarrow A$ if $g\mathrm{Stab}_G(A) \subseteq g\mathrm{Stab}_G(B)$ for all $g\in G$ is a dependency relation on $\mathcal {P}(\Omega )$. A particular case of such a dependency relation has been used in [8, 9] in order to investigate some properties of the group of the polynomial automorphisms of $\mathbb {C}^n$.

• As mentioned in the introductory section, another example of dependency relation arise from pairings. We will deal with it in detail in Sect. 6.

Remark 3.3

When $\Omega$ is a non finite set, for some proofs concerning the existence of minimal members of specific subset families it is necessary to assume the following further chain intersection condition (that in the finite case is superfluous):

(CIC):

if $\{C_i: i\in I\}$ is a chain in $(\mathcal {P}(\Omega ), \subseteq )$ and $C \leftarrow C_i$ for all $i \in I$, then $C\leftarrow \bigcap _{i\in I} C_i$.

If $\leftarrow$ is a dependency relation which also satisfies the axiom (CIC), we say that $\leftarrow$ a cic-dependency relation on $\Omega$. Clearly, if $\Omega$ is finite, any dependency relation on $\mathcal {P}(\Omega )$ is also a cic-dependency relation.

In the following result we establish an equivalent condition to the above condition (D3) for a binary relation which satisfies the properties (D1) and (D2).

Proposition 3.4

Let $\leftarrow$ be a binary relation on $\mathcal {P}(\Omega )$ which satisfies the properties (D1) and (D2). Then, $\leftarrow$ satisfies (D3) if and only if the following condition holds:

$(D3')$ :

$B_i \leftarrow A,\, \forall i\in I \implies \bigcup _{i\in I}B_i \leftarrow A$

Proof

Let $\leftarrow$ be a binary relation on $\mathcal {P}(\Omega )$ which satisfies (D1), (D2) and (D3). Assume that $B_i \leftarrow A$ for any $i\in I$. In view of (D3), it results that $\{b\} \leftarrow A$ for all $b\in B_i$ and $i\in I$. Therefore we get $\{b\} \leftarrow A$ for any $b\in \bigcup _{i\in I} B_i$.

Conversely, let $\leftarrow$ be satisfying (D1), (D2) and $(D3')$. Hence, if $b\in A$ for any $b\in B$, then $B=\bigcup _{b\in B}\{b\} \leftarrow A$ in view of $(D3')$. $\square$

3.1 The closure operator associated with a dependency relation

Let $\leftarrow$ be a fixed arbitrary dependency relation on $\mathcal {P}(\Omega )$. We can equivalently express the dependency relation $\leftarrow$ in terms of the corresponding set operator $Dc_\leftarrow$ in the following way.

Proposition 3.5

Let $A,B \in \mathcal {P}(\Omega )$. Then

$$\begin{aligned} B \leftarrow A \iff B \subseteq Dc_\leftarrow (A), \end{aligned}$$

(1)

so that we have

$$\begin{aligned} Dc_\leftarrow (A)=\{b \in \Omega : b\leftarrow A \}. \end{aligned}$$

(2)

Proof

Let $B \leftarrow A$, then $B \subseteq \bigcup \{C: \, C \leftarrow A \}=Dc_\leftarrow (A)$.

On the other hand, let $B \subseteq Dc_\leftarrow (A)=\bigcup \{C: \, C \leftarrow A \}$. Then, for any $b \in B$ there exists $C_b \in \mathcal {P}(\Omega )$ such that $b \in C_\{b\} \leftarrow A$. By both (D1) and (D2), it follows that $\{b\} \leftarrow A$ for any $b \in B$, so $B \leftarrow A$ by (D3). $\square$

We consider now the equivalence relation $\leftrightarrows$ on $\mathcal {P}(\Omega )$ defined by

$$\begin{aligned} A \leftrightarrows B :\iff A\leftarrow B\,\,\mathrm{and}\,\, B \leftarrow A \end{aligned}$$

(3)

We call the relation $\leftrightarrows$ the $\leftarrow$dependency equivalence on $\mathcal {P}(\Omega )$. If $A\leftrightarrows B$, we say that A and B are $\leftarrow$dependency equivalent, and we denote by $[A]_\leftrightarrows$ the equivalence class of A with respect to $\leftrightarrows$, which we call $\leftarrow$equivalence dependency class of A. We set $EDC(\leftarrow ):=\{[A]_\leftrightarrows : A\in \mathcal {P}(\Omega )\}$, that is the quotient set of $\mathcal {P}(\Omega )$ with respect to the dependency equivalence.

In this paper, we also deal with a weaker version of $\leftrightarrows$. In particular, we say that A and B are $\leftarrow$quasi equivalent, denoted by $A \leftrightarrows _q B$, if $A \leftarrow B$ or $B \leftarrow A$.

In the following result we establish two basic properties concerning the $\leftarrow$dependency equivalence.

Theorem 3.6

Let $A, B\in \mathcal {P}(\Omega )$. Then the following hold.

(i):

The set system $[A]_\leftrightarrows$ is union closed and the maximum element of $[A]_\leftrightarrows$ is $Dc_\leftarrow (A)$.

(ii):

$A \leftrightarrows B$ if and only if $Dc_\leftarrow (A)=Dc_\leftarrow (B)$.

Proof

(i): We first show that $[A]_\leftrightarrows$ is union closed. To this regard, let $\{B_i:i\in I\} \subseteq [A]_\leftrightarrows$. Then $B_i \leftarrow A$ for all $i\in I$, therefore, by $(D3')$ we have that $\bigcup _{i\in I} B_i \leftarrow A$. On the other hand, for any index $i\in I$ we have $A \leftarrow B_i \leftarrow \bigcup _{i\in I} B_i$, therefore, by (D2), it follows that $A \leftarrow \bigcup _{i\in I} B_i$. Hence $\bigcup _{i\in I} B_i \in [A]_\leftrightarrows$.

We now claim that $Dc_\leftarrow (A)$ is the maximum element of the set system $[A]_\leftrightarrows$. As $A\subseteq Dc_\leftarrow (A)$, then $A \leftarrow Dc_\leftarrow (A)$. On the other hand, it results that $\{b\} \leftarrow A$ if and only if $b\in Dc_\leftarrow (A)$. Thus, Property (D3) implies that $Dc_\leftarrow (A) \leftarrow A$ and, hence, $Dc_\leftarrow (A) \in [A]_\leftrightarrows$. At this point, take $B\in [A]_\leftrightarrows$. As $\{b\} \leftarrow B \leftarrow A$ for any $b\in B$, then we get $\{b\} \leftarrow A$ by (D2). This proves that $b\in Dc_\leftarrow (A)$ and, so, $B\subseteq Dc_\leftarrow (A)$.

(ii): If $A \leftrightarrows B$, then $[A]_\leftrightarrows =[B]_\leftrightarrows$, therefore $Dc_\leftarrow (A)=Dc_\leftarrow (B)$. Vice versa, if $Dc_\leftarrow (A)=Dc_\leftarrow (B)$, then $B\subseteq Dc_\leftarrow (B)=Dc_\leftarrow (A)$, therefore, by (1), we deduce that $B\leftarrow A$. Analogously, we also have $A\leftarrow B$. Hence $A \leftrightarrows B$. $\square$

In reference to the existence of minimal elements in any $\leftarrow$equivalence dependency class, this condition is always verified when $\leftarrow$ satisfies the chain intersection condition.

Proposition 3.7

Let $\leftarrow$ be a cic-dependency relation. Then $\min ([A]_\leftrightarrows ) \ne \emptyset$ for any $A \in \mathcal {P}(\Omega )$.

Proof

Let $A \in \mathcal {P}(\Omega )$ and $\{C_i: i \in I\}$ be a chain in $[A]_\leftrightarrows$. Clearly, we have $\bigcap \nolimits _{i \in I} C_i \leftarrow C_i \leftarrow A$. On the other hand, since $A \leftarrow C_i$ for any $i \in I$, it must necessarily be $A \leftarrow \bigcap \nolimits _{i \in I} C_i$. Hence, $A \leftrightarrows \bigcap \nolimits _{i \in I} C_i$. This proves that each chain has a lower bound and, by Zorn’s Lemma, there exists a minimal element in $[A]_\leftrightarrows$. $\square$

We now show that to give a dependency relation on $\mathcal {P}(\Omega )$ is equivalent to provide a closure operator on $\Omega$.

Theorem 3.8

Let $\leftarrow$ be a dependency relation on $\mathcal {P}(\Omega )$ and $\sigma \in CLOP(\Omega )$. Then $Dc_\leftarrow$ is a closure operator on $\Omega$, $Inc(\sigma )$ is a dependency relation on $\mathcal {P}(\Omega )$, and

$$\begin{aligned} Inc(Dc_\leftarrow )=\,\,\leftarrow \,\,\,\mathrm{and}\,\,\, Dc_{Inc(\sigma )}=\sigma \end{aligned}$$

(4)

Hence the map Dc induces a bijection $DREL(\Omega ) \rightarrow CLOP(\Omega )$, whose inverse $CLOP(\Omega ) \rightarrow DREL(\Omega )$ is the map induced by Inc.

Proof

Let $A, B\in \mathcal {P}(\Omega )$. Since $A\in [A]_\leftrightarrows$ and $Dc_\leftarrow (A)$ is the maximum element of $[A]_\leftrightarrows$, we have $A\subseteq Dc_\leftarrow (A)$. Let now $B\subseteq A$. For any $c\in Dc_\leftarrow (B)$ we have $\{c\} \leftarrow B \leftarrow A$, therefore $\{c\} \leftarrow A$ by (D2), that is $c\in Dc_\leftarrow (A)$. Hence $Dc_\leftarrow (B) \subseteq Dc_\leftarrow (A)$. As a direct consequence of the above two properties, we have that $Dc_\leftarrow (A) \subseteq Dc^2_\leftarrow (A)$. Vice versa, if $b\in Dc^2_\leftarrow (A)$, then $\{b\} \leftarrow Dc_\leftarrow (A) \leftarrow A$, so that, by (D2), $\{b\} \leftarrow A$, that is $b\in Dc_\leftarrow (A)$. Therefore $Dc^2_\leftarrow (A) \subseteq Dc_\leftarrow (A)$. This shows that $Dc^2_\leftarrow (A)=Dc_\leftarrow (A)$. Hence $Dc_\leftarrow$ is a closure operator on $\Omega$.

We set now $\leftarrow _\sigma \,:=Inc(\sigma )$. Then, by the definition of $Inc(\sigma )$ we have that $B\leftarrow _\sigma A$ if and only if $B\subseteq \sigma (A)$. Then, if $B\subseteq A$, we have $B\subseteq \sigma (B)\subseteq \sigma (A)$, therefore $B \leftarrow _\sigma A$. Moreover, if $C \leftarrow _\sigma B$ and $B\leftarrow _\sigma A$, then $C\subseteq \sigma (B)$ and $B\subseteq \sigma (A)$. Therefore $C \subseteq \sigma (B) \subseteq \sigma ^2(A)=\sigma (A)$, that is $C\leftarrow _\sigma A$. Finally, $B \leftarrow _\sigma A$ if and only if $b\in B \subseteq \sigma (A)$, that is equivalent to say that $\{b\} \leftarrow _\sigma A$ for all $b \in B$. Hence $\leftarrow _\sigma$ also satisfies (D3), and therefore it is a dependency relation on $\mathcal {P}(\Omega )$.

Let now $\tau := Dc_\leftarrow$ and $\leftarrow _\tau := Inc(\tau )$. Then, by (1), we have that

$$\begin{aligned} B\leftarrow _\tau A \iff B\subseteq \tau (A)=Dc_\leftarrow (A) \iff B \leftarrow A, \end{aligned}$$

and this shows that $Inc(Dc_\leftarrow )=\,\leftarrow$ .

Finally, we set again $\leftarrow _\sigma \,:=Inc(\sigma )$. Then

$$\begin{aligned} Dc_{\leftarrow _\sigma }(A):=\bigcup _{B\leftarrow _\sigma A}B =\bigcup _{B\subseteq \sigma (A)}B=\sigma (A), \end{aligned}$$

and this shows that $Dc_{Inc(\sigma )}=\sigma$. $\square$

Due to the relevance assumed by $Dc_\leftarrow$, we use the following terminology.

Definition 3.9

We call $Dc_\leftarrow (A)$ the $\leftarrow$dependency closure of A and we say that A is a $\leftarrow$closed subset, or simply that A is closed, if $A=Dc_\leftarrow (A)$. We denote by $CLOS(\leftarrow )$ the set of all $\leftarrow$closed subsets, so that we have $CLOS(\leftarrow )=Fix(Dc_\leftarrow )$. Moreover, if $A \in \mathcal {P}(\Omega )$, we also set $CLOS_\leftarrow (A):=\{A \cap B: \, B \in CLOS(\leftarrow ) \}$, so that, in particular, we have $CLOS(\leftarrow ):=CLOS_\leftarrow (\Omega )$.

As an immediate consequence of the fact that $Dc_\leftarrow$ is a closure operator, we have the following result.

Corollary 3.10

The following conditions hold:

(i):

$B \leftarrow A \iff Dc_\leftarrow (B) \subseteq Dc_\leftarrow (A) \iff Dc_\leftarrow (B)\leftarrow Dc_\leftarrow (A) \iff [B]_\leftrightarrows \leftarrow [A]_\leftrightarrows$;

(ii):

If $A,B \in CLOS(\leftarrow )$, then $B \leftarrow A$ if and only if $B \subseteq A$;

(iii):

$Dc_\leftarrow (A)$ is the smallest closed subset contaning A;

(iv):

$CLOS_\leftarrow (A)$ is a convexity on A whose closure operator is the restriction of $Dc_\leftarrow$ on A.

Remark 3.11

Since $CLOS(\leftarrow )$ is a convexity on $\Omega$ and $Dc_\leftarrow$ is its associated closed operator, by (i) of Corollary it follows that $(EDC(\leftarrow ), \leftarrow ^{ext})$ is a complete lattice, which is order isomorphic to the closure lattice $(CLOS(\leftarrow ), \subseteq )$.

3.2 The independence set operator associated with a dependency relation

For any $A\in \mathcal {P}(\Omega )$, we consider the subset of A so defined:

$$\begin{aligned} Ic_\leftarrow (A):=\{a\in A: \{a\} \leftarrow A{\setminus } \{a\}\} \end{aligned}$$

We now find the main properties satisfied by the set operator $Ic_\leftarrow \in \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$ and, moreover, we will prove that any set operator having the following properties (I1), (I2) and (I3) coincides with the set operator $Ic_\leftarrow$, for some dependency relation $\leftarrow$.

Theorem 3.12

The set operator $Ic_\leftarrow$ satisfies the following properties:

$\mathrm{{(I1)}}$ :

$Ic_\leftarrow (A) \subseteq A$;

$\mathrm{{(I2)}}$ :

if $A \subseteq B$ then $Ic_\leftarrow (A) \supseteq A\cap Ic_\leftarrow (B)$;

$\mathrm{{(I3)}}$ :

if $b\in \Omega {\setminus } ( A \cup Ic_\leftarrow (A\cup \{b\}))$ and $c\in Ic_\leftarrow (A\cup \{c\}){\setminus } A$, then $c\in Ic_\leftarrow (A\cup \{b,c\})$.

$\mathrm{{(I4)}}$ :

$Ic^2_\leftarrow (A) = Ic_\leftarrow (A)$.

Moreover, if $\sigma \in \mathcal {P}(\Omega )^{\mathcal {P}(\Omega )}$ satisfies the properties (I1), (I2) and (I3), there exists a dependency relation $\leftarrow$ on $\Omega$ such that $\sigma =Ic_\leftarrow$.

Proof

(I1) is obvious. Let now $A \subseteq B$ and $a \in A \cap Ic_\leftarrow (B)$. Thus, $a \in A$ and $\{a\} \leftarrow B {\setminus } \{a\}$. Assume by contradiction that $\{a\} \leftarrow A {\setminus } \{a\}$. By (D1), we have $A {\setminus } \{a\} \leftarrow B {\setminus } \{a\}$ and, by (D2), we would have $\{a\} \leftarrow B {\setminus } \{a\}$, contradicting our assumptions. Thus $a \in Ic_\leftarrow (A)$. This proves (I2).

Let us show (I3). To this regard, let $b\in \Omega {\setminus } ( A \cup Ic_\leftarrow (A\cup \{b\}))$ and $c\in Ic_\leftarrow (A\cup \{c\}){\setminus } A$. By our assumptions, we deduce that $\{c\} \nleftarrow A$ and $\{b\} \leftarrow A$. By (1), it follows that $c \notin Dc_\leftarrow (A)$ and $b \in Dc_\leftarrow (A)$. Since $Dc_\leftarrow \in CLOP(\Omega )$, we have $Dc_\leftarrow (A)=Dc_\leftarrow (A \cup \{b\})$, so $c \notin Dc_\leftarrow (A \cup \{b\})$. Again by (1), the last condition is equivalent to require that $\{c\} \nleftarrow A \cup \{b,c\}$, i.e. $c \in Ic_\leftarrow (A \cup \{b,c\})$. This shows (I3).

To prove (I4), we set $D:=Ic_\leftarrow (A)$. Then, by (I1), it is sufficient to show that $D \subseteq Ic_\leftarrow (D)$. Let us assume, by contradiction, that $a\in D$ and that $a\notin Ic_\leftarrow (D)$, i.e. $\{a\} \leftarrow D{\setminus } \{a\}$. Since $D{\setminus } \{a\} \subseteq A{\setminus } \{a\}$, we deduce that $\{a\} \leftarrow A{\setminus } \{a\}$, and this is in contrast with the hypothesis that $a\in Ic_\leftarrow (A)$. This proves (I4).

Let now $\sigma$ be a set operator satisfying (I1), (I2) and (I3). Let us consider the set operator $\varphi _\sigma : \mathcal {P}(\Omega ) \rightarrow \mathcal {P}(\Omega )$ defined as follows:

$$\begin{aligned} \varphi _\sigma (A):=A \cup A^*, \end{aligned}$$

(5)

where

$$\begin{aligned} A^*:=\{b \in \Omega : \, b \in \Omega {\setminus } (A \cup \sigma (A \cup \{b\}))\} \end{aligned}$$

We will prove that $\varphi _\sigma$ is a closure operator on $\Omega$, i.e. we want to prove that

• $A \subseteq \varphi _\sigma (A)$;

• $A \subseteq B \implies \varphi _\sigma (A) \subseteq \varphi _\sigma (B)$;

• $\varphi _\sigma ^2(A)=\varphi _\sigma (A)$

for any $A,B \in \mathcal {P}(\Omega )$. The inclusion $A \subseteq \varphi _\sigma (A)$ is immediate for any $A \in \mathcal {P}(\Omega )$. Let now $A \subseteq B$. It suffices to show that $A^* \subseteq \varphi _\sigma (B)$. Let $b \in A^*$. Assume that $b \in \Omega {\setminus } B$. Then, $A \cup \{b\} \subseteq B \cup \{b\}$, therefore, by (I2), we have that $\sigma (A \cup \{b\}) \supseteq \sigma (B \cup \{b\}) \cap (A \cup \{b\})$. But since $b \in \Omega {\setminus } \sigma (A \cup \{b\})$, it follows that $b \in \Omega {\setminus } ((A \cup \{b\}) \cap \sigma (B \cup \{b\}))$. Clearly, it implies that $b \in \Omega {\setminus } \sigma (B \cup \{b\})$ and this proves that $b \in \Omega {\setminus } (B \cup \sigma (B \cup \{b\}))=B^*$, i.e. $b \in \varphi _\sigma (B)$. On the other hand, if $b \in B$, it is obvious that $b \in \varphi _\sigma (B)$. This proves $\varphi _\sigma (A) \subseteq \varphi _\sigma (B)$ whenever $A \subseteq B$.

We now show that $\varphi _\sigma$ is idempotent. Clearly, $\varphi _\sigma (A) \subseteq \varphi _\sigma (\varphi _\sigma (A))$. Moreover, if $(\varphi _\sigma (A))^*=\emptyset$, then $\varphi _\sigma (\varphi _\sigma (A)) \subseteq \varphi _\sigma (A)$. Therefore, assume by contradiction that $(\varphi _\sigma (A))^*\ne \emptyset$ and let $b \in (\varphi _\sigma (A))^*$. Then, $b \in \Omega {\setminus } (\varphi _\sigma (A) \cup \sigma (\varphi _\sigma (A) \cup \{b\}))=\Omega {\setminus } ( (A \cup A^*) \cup \sigma (A \cup A^* \cup \{b\}))$. Let us prove that the condition $b \in \Omega {\setminus } A \cup A^*$ implies $b \in \sigma (A \cup A^* \cup \{b\})$.

Let us observe that since $b \in \Omega {\setminus } \varphi _\sigma (A)$, then $b \in \sigma (A \cup \{b\})$. Therefore, let us fix an integer m and assume that $b \in \sigma (A \cup B \cup \{b\})$ for any $B \subseteq A^*$ such that $|B|=m-1$. Let now $B \subseteq A^*$ such that $|B|=m$ and fix $c \in B$. We will prove that $c \in \Omega {\setminus } \sigma ((A \cup (B {\setminus } \{c\})) \cup \{c\})$ and that $b \in \sigma ((A \cup B {\setminus } \{c\}) \cup \{b\})$.

Let us note that $c \in \Omega {\setminus } \sigma ((A \cup (B {\setminus } \{c\})) \cup \{c\})$. As a matter of fact, we have that $c \in A^*$, so $c \in \Omega {\setminus } (A \cup \{c\})$. Furthermore, to say that $c \in B$ means that $A \cup \{c\} \subseteq A \cup B$ so, by (I2), $\sigma (A \cup \{c\}) \supseteq \sigma (A \cup B) \cap (A \cup \{c\})$. In other terms, $c \in \Omega {\setminus } \sigma (A \cup B)$, i.e. $c \in \Omega {\setminus } \sigma ((A \cup (B {\setminus } \{c\})) \cup \{c\})$. On the other hand, since $|B {\setminus } \{c\}|=m-1$, by the inductive hypothesis on $B {\setminus } \{c\} \subseteq A^*$, we have that $b \in \sigma ((A \cup B {\setminus } \{c\}) \cup \{b\})$. Hence, we can apply (I3) that, in this case, yields $c \in \sigma ((A \cup B {\setminus } \{c\}) \cup \{b,c\})=\sigma (A \cup B \cup \{b\})$, showing the claim for B. In particular, the claim holds for $B=A^*$. Then, $b \in \sigma (A \cup A^* \cup \{b\})$, contradicting our choice of b. Necessarily, it must be $(\varphi _\sigma (A))^*=\emptyset$. This proves that $\varphi _\sigma (\varphi _\sigma (A))=\varphi _\sigma (A)$.

By Theorem 3.8, there exists a dependency relation $\leftarrow$ on $\Omega$ such that $\varphi _\sigma =Dc_\leftarrow$. Let us prove that $\sigma =Ic_\leftarrow$. To this regard, let $a \in Ic_\leftarrow (A)$, then $\{a\} \leftarrow A {\setminus } \{a\}$ that, by (1), is equivalent to require that $a \notin Dc_\leftarrow (A {\setminus } \{a\})=(A {\setminus } \{a\}) \cup (A {\setminus } \{a\})^*$. Thus, $a \notin (A {\setminus } \{a\})^*$, i.e. $a \in (A {\setminus } \{a\}) \cup \sigma ((A {\setminus } \{a\}) \cup \{a\})$. In particular, it follows that $a \in \sigma (A)$.

On the other hand, let $a \in \sigma (A)$ and assume by contradiction that $\{a\} \leftarrow A {\setminus } \{a\}$. Then, $a \in Dc_\leftarrow (A {\setminus } \{a\})=\varphi _\sigma (A {\setminus } \{a\})=(A {\setminus } \{a\}) \cup (A {\setminus } \{a\})^*$ by (1). It must necessarily be $a \in (A {\setminus } \{a\})^*$, i.e. $a \in \Omega {\setminus } ((A \setminus \{a\}) \cup \sigma ((A {\setminus } \{a\}) \cup \{a\}))=\Omega {\setminus } ((A \setminus \{a\}) \cup \sigma (A))$. This entails $a \notin \sigma (A)$, contradicting our assumption. This proves that $\sigma =Ic_\leftarrow$ and concludes the proof. $\square$

In analogy with what we have done for the set operator $Dc_\leftarrow$, also for $Ic_\leftarrow$, we provide a suitable terminology.

Definition 3.13

We call $Ic_\leftarrow (A)$ the $\leftarrow$independency core of A. We say that A is an $\leftarrow$independent subset, or simply that A is independent, if $\{a\} \nleftarrow A{\setminus } \{a\}$ for all $a\in A$, in other terms, if $A=Ic_\leftarrow (A)$. We denote by $INDP(\leftarrow )$ the set of all $\leftarrow$independent subsets, that is $INDP(\leftarrow )=Fix(Ic_\leftarrow )$. Moreover, if $A \in \mathcal {P}(\Omega )$, we set $INDP_\leftarrow (A):=\{B \in INDP(\leftarrow ): \, B \subseteq A \}$. In particular, when $A=\Omega$, we have $INDP(\leftarrow ):=INDP_\leftarrow (\Omega )$.

We now two further basic properties of the set operator $Ic_\leftarrow$.

Proposition 3.14

We have that:

(i):

$Ic_\leftarrow (A)$ is a $\leftarrow$independent subset.

(ii):

$Ic_\leftarrow (Dc_\leftarrow (A)) \subseteq A$.

Proof

(i): It follows immediately by (I4).

(ii): Let $a \in Ic_\leftarrow (Dc_\leftarrow (A))$ and suppose by contradiction that $a \in Dc_\leftarrow (A) {\setminus } A$. This means that $A \subseteq Dc_\leftarrow (A) {\setminus } \{a\}$, so we have $\{a\} \leftarrow A \leftarrow Dc_\leftarrow (A) {\setminus } \{a\}$, i.e. $\{a\} \leftarrow Dc_\leftarrow (A) {\setminus } \{a\}$ by (D2), but this contradicts the fact that $a \in Ic_\leftarrow (Dc_\leftarrow (A))$. $\square$

In the next result we will prove that $INDP(\leftarrow )$ is an abstract simplicial complex on $\Omega$ and provide an alternative form to express it.

Theorem 3.15

$INDP(\leftarrow )$ is an abstract simplicial complex on $\Omega$ and we have that

$$\begin{aligned} INDP(\leftarrow )=\bigcup \{ \min ([A]_\leftrightarrows ): \, A \in \mathcal {P}(\Omega ) \} \end{aligned}$$

(6)

Proof

Clearly, $\emptyset \in INDP(\leftarrow )$. Let now $A \in INDP(\leftarrow )$ and $B \subseteq A$. Clearly, $Ic_\leftarrow (B) \subseteq B$. Let $b \in B$. Assume by contradiction that $\{b\} \leftarrow B {\setminus } \{b\}$. Moreover, since $B {\setminus } \{b\} \leftarrow A {\setminus } \{b\}$, by (D2) it follows that $\{b\} \leftarrow A {\setminus } \{b\}$, i.e. $b \notin Ic_\leftarrow (A)$. This is a contradiction. Hence $\{b\} \nleftarrow B {\setminus } \{b\}$, i.e. $Ic_\leftarrow (B)=B$. This shows that $INDP(\leftarrow )$ is an abstract simplicial complex.

Let $B \in \min ([A]_\leftrightarrows )$ for some $A \in \mathcal {P}(\Omega )$. Clearly, $Ic_\leftarrow (B) \subseteq B$. Let $b \in B$. Then $B {\setminus } \{b\} \leftarrow B$ but $B \nleftarrow B {\setminus } \{b\}$, i.e. there exists $b' \in B$ such that $\{b'\} \nleftarrow B {\setminus } \{b\}$. Now, since by (D1) we have $B {\setminus } \{b\} \leftarrow B {\setminus } \{b\}$ or, equivalently by (D3), $\{b''\} \leftarrow B {\setminus } \{b\}$ for any $b'' \in B {\setminus } \{b\}$. This forces that $b'=b$. Thus, $Ic_\leftarrow (B)=B$.

On the other hand, let let $B \in INDP(\leftarrow )$. Let us prove that $A \in \min ([A]_\leftrightarrows )$. For, assume by contradiction that $B \subsetneqq A$ such that $B \in \min ([A]_\leftrightarrows )$. Then $A \leftarrow B$ and $B \leftarrow A$. In particular, there exists $a \in A$ such that $B \subseteq A {\setminus } \{a\}$. Moreover, we have $A {\setminus } \{a\} \leftarrow B$ and $B \leftarrow A {\setminus } \{a\}$. Thus $A \leftrightarrows B \leftrightarrows A {\setminus } \{a\}$. Hence, $A {\setminus } \{a\} \leftarrow A$ and $A \leftarrow A {\setminus } \{a\}$. By (D3), this implies that $a' \leftarrow A {\setminus } \{a\}$ for any $a' \in A$ and, in particular, $\{a\} \leftarrow A {\setminus } \{a\}$. This contradicts the fact that $Ic_\leftarrow (A)=A$. $\square$

An immediate consequence of Theorem 3.15 is the following.

Corollary 3.16

$INDP_\leftarrow (A)$ is an abstract simplicial complex on A.

We call the elements of $\min ([A]_\leftrightarrows )$ the $\leftarrow$co-minimal independents of A.

4 Essential subsets and dependency bases

We now introduce the basic notion of dependency base for a subset of $\Omega$. This notion assumes a fundamental role within our dependency context because it generalizes to a more general abstract case the corresponding notion of minimal spanning subset for vector spaces. For recent studies and results on dependency bases induced by simple undirected graphs see [13].

Definition 4.1

Let $A, B\in \mathcal {P}(\Omega )$. We say that B is a $\leftarrow$dependency base of A, denoted by $B\leftarrow _{db} A$, if:

(B1):

$B\subseteq A$;

(B2):

$C \leftarrow A\implies C\leftarrow B$;

(B3):

B is minimal with respect to (B2). That is, for any $B'\subsetneqq B$, there exists $C'\in \mathcal {P}(\Omega )$ such that $C' \leftarrow A$ and $C' \nleftarrow B'$.

We set $BAS_\leftarrow (A):=\{B\in \mathcal {P}(A): B\leftarrow _{db} A\}$. When $\Omega$ is a finite set, we also consider the following subfamily $MBAS_\leftarrow (A):=\{B \in BAS_\leftarrow (A): \, |B| \le |C| \, \, \forall C \in BAS_\leftarrow (A)\}$ of $BAS_\leftarrow (A)$. In particular, we set $MBAS(\leftarrow )$ when $A=\Omega$. Moreover, we set $\rho _\leftarrow (A):=\min \{|B|: \, B \in BAS_\leftarrow (A)\}$.

Remark 4.2

The previous notion of $\leftarrow$dependency base generalizes to a purely mathematical abstract context the notion of reduct for information tables [24], or, equivalently, of key for relational databases [28].

In the next result, we relate the set systems $BAS_\leftarrow$ and $INDP_\leftarrow$ and we will give a basic property for the closed sets in terms of interrelation between $Ic_\leftarrow$ and $Dc_\leftarrow$.

Theorem 4.3

For any $A,B \in \mathcal {P}(\Omega )$, we have that:

• (i) $BAS_\leftarrow (A) \subseteq \max (INDP_\leftarrow (A))$ for any $A \in \mathcal {P}(\Omega )$.

• (ii) if $A \leftrightarrows B$ and $B \subseteq A$, then $BAS_\leftarrow (B) \subseteq BAS_\leftarrow (A)$;

• (iii) If $A \in CLOS(\leftarrow )$, then, $a\in A{\setminus } Ic_\leftarrow (A)$ if and only if there exists $B \in \mathcal {P}(\Omega )$ such that $a \notin B$ and $a \in Dc_\leftarrow (B) \subseteq A$.

Proof

(i): Let $B \in BAS_\leftarrow (A)$, then $B \subseteq A$. Let us note that $B \leftrightarrows A$. In fact, $B \subseteq A$ implies by (D1) that $B \leftarrow A$; on the other hand, $A \leftarrow A$ so, by (B2), we have that $A \leftarrow B$. This shows that $B \leftrightarrows A$. Now, let us show that $B \in \min ([A]_\leftrightarrows )$. To this regard, let $B' \subsetneqq B$ be such that $B' \min ([A]_\leftrightarrows )$. Let also $C \in \mathcal {P}(\Omega )$ be such that $C \leftarrow A$. But $A \leftarrow B'$ so, by (B2), we have that $C \leftarrow B'$. This means that $B'$ satisfies (B2), contradicting minimality of B. This shows that $B \in \min ([A]_\leftrightarrows )$. Finally, we prove that $B \in \max (INDP_\leftarrow (A))$. For, we observe that there is no $B'' \supsetneqq B$ such that $B'' \in INDP_\leftarrow (A)$, otherwise we would have $B'' \in \min ([A]_\leftrightarrows )$, that is impossible.

(ii): Let $C \in BAS_\leftarrow (B)$. Then $C \subseteq A$. Now, we will prove that C satisfies (B2) with respect to A. For, let $D \leftarrow A$. By (D2), it follows that $D \leftarrow B$, so, again by (D2), $D \leftarrow C$. This shows that C satisfies (B2) with respect to A. In particular, we have that $C \leftrightarrows A$. We now prove minimality. To this regard, let $C' \subsetneqq C$ be such that $C' \in BAS_\leftarrow (A)$. By using (D2), it is straightforward to see that $C' \in BAS_\leftarrow (B)$, and this contradicts the fact that $C \in BAS_\leftarrow (B)$. This entails that $C \leftarrow _{db} A$.

(iii): Let $A \in CLOS(\leftarrow )$ and $a \in A {\setminus } Ic_\leftarrow (A)$. Then, just consider $B \in BAS_\leftarrow (A)$ such that $a \notin B$. Nevertheless, we have $a \in Dc_\leftarrow (B)=Dc_\leftarrow (A)$.

Conversely, assume that $A \in CLOS(\leftarrow )$. Let moreover $a \in A$ and suppose that there exists $B \in \mathcal {P}(\Omega )$ such that $a \notin B$ and $a \in Dc_\leftarrow (B) \subseteq A$. Finally, assume by contradiction that $\{a\} \leftarrow A {\setminus } \{a\}$. By (1), this means that $a \notin Dc_\leftarrow (A {\setminus } \{a\})$. But, let us note that for any $C \subseteq A {\setminus } \{a\}$, we have that $Dc_\leftarrow (C) \subseteq Dc_\leftarrow (A {\setminus } \{a\})$ and, hence $a \notin Dc_\leftarrow (C)$. So, a subset B as in the hypothesis cannot exist, that is absurd. This proves that $a \in A {\setminus } Ic_\leftarrow (A)$. $\square$

In the next result, we relate the set operator $Ic_\leftarrow$ with the set system $BAS_\leftarrow$. In particular, we will see that $Ic_\leftarrow (A) \subseteq \bigcap BAS_\leftarrow (A)$ and, that equality holds for cic-dependency relations and, hence, also in the finite case.

Theorem 4.4

Let $A \in \mathcal {P}(\Omega )$. Then:

(i):

$Ic_\leftarrow (A) \subseteq \bigcap BAS_\leftarrow (A)$.

(ii):

If $\leftarrow$ is a cic-dependency relation, $Ic_\leftarrow (A)=\bigcap BAS_\leftarrow (A)$.

(iii):

If $\Omega$ is a finite set, then $Ic_\leftarrow (A) = \bigcap BAS_\leftarrow (A)$.

Proof

(i): Let $a \in Ic_\leftarrow (A)$ and assume, by contradiction, that there exists some $B\in BAS_\leftarrow (A)$ such that $a\notin B$, so that $B {\setminus } \{a\}=B$. Since $\{a\} \leftarrow A$, by (B2) we deduce that $\{a\} \leftarrow B=B {\setminus } \{a\} \subseteq A {\setminus } \{a\}$, therefore $\{a\} \leftarrow A{\setminus } \{a\}$. That is in contrast with the hypothesis that $a\in Ic_\leftarrow (A)$. This shows that $Ic_\leftarrow (A) \subseteq \bigcap BAS_\leftarrow (A)$.

(ii): On the other hand, let $a \in \bigcap BAS_\leftarrow (A)$ and let us assume, by contradiction, that $a\notin Ic_\leftarrow (A)$, so that $\{a\} \leftarrow A{\setminus } \{a\}$. Then $A{\setminus } \{a\}$ satisfies the property (B2). In fact, let $C\in \mathcal {P}(\Omega )$ such that $C \leftarrow A$, then $C \leftarrow (A{\setminus } \{a\}) \cup \{a\} \leftarrow A{\setminus } \{a\}$, so that $C \leftarrow A {\setminus } \{a\}$. Let us consider now the set system $\mathcal {F}$ of all subsets of $A{\setminus } \{a\}$ satisfying (B2). Then $\mathcal {F}$ is non-empty because $A{\setminus } \{a\} \in \mathcal {F}$. Let now $\{C_i: i \in I\} \subseteq \mathcal {F}$ be a chain and $C \leftarrow A$. By (B2), $C \leftarrow C_i$ for any $i \in I$. By condition (CIC), we have that $C \leftarrow \bigcap \nolimits _{i \in I} C_i$, i.e. $\bigcap \nolimits _{i \in I} C_i$ satisfies (B2). Zorn’s Lemma ensures the existence of a minimal element B in $\mathcal {F}$. Therefore, $a\notin B$ and $B\in BAS_\leftarrow (A)$, but this is in contrast with the hypothesis that $a \in \bigcap BAS_\leftarrow (A)$.

(iii): It is an immediate consequence of part (ii). $\square$

In the next theorem, we give two characterizations for a subset to be a $\leftarrow$-dependency base of A.

Theorem 4.5

Let $B \subseteq A$. Then the following conditions are equivalent:

(i):

$B \in BAS_\leftarrow (A)$.

(ii):

$Dc_\leftarrow (B)=Dc_\leftarrow (A)$ and $Dc_\leftarrow (B') \subsetneqq Dc_\leftarrow (A)$ for all $B' \subsetneqq B$.

(iii):

$Dc_\leftarrow (B)=Dc_\leftarrow (A)$ and $Ic_\leftarrow (B)=B$.

Proof

(i) $\implies$ (ii): The claim is immediate by the proof of (i) of Theorem 4.3.

(ii) $\implies$ (iii): Let us assume that $Dc_\leftarrow (B)=Dc_\leftarrow (A)$ and $Dc_\leftarrow (B') \subsetneqq Dc_\leftarrow (A)$ for all $B' \subsetneqq B$. We now prove that $Ic_\leftarrow (B)=B$. For, take $B'=B {\setminus } \{b\}$, for some $b \in B$. Assume by contradiction that $\{b\} \leftarrow B {\setminus } \{b\}$. By (1), it follows that $b \in Dc_\leftarrow (B')$, that is $Dc_\leftarrow (B')=Dc_\leftarrow (B)=Dc_\leftarrow (A)$, contradicting our hypothesis. Then, $\{b\} \nleftarrow B'$, that is $b \in Ic_\leftarrow (B)$. In view of the arbitrariness of b, we deduce that $Ic_\leftarrow (B)=B$.

(iii) $\implies$ (i): Let $B \subseteq A$ be such that $Dc_\leftarrow (B)=Dc_\leftarrow (A)$ and $Ic_\leftarrow (B)=B$. Clearly, (B1) is satisfied. We must prove that B satisfies (B2). To this regard, let $C \leftarrow A$. By (ii) of Theorem 3.6 and by (D2), it is immediate to see that $C \leftarrow B$. Finally, let us show (B3). Let $B' \subsetneqq B$ satisfying (B2). Clearly, there exists $b \in B$ such that $B' \subseteq B {\setminus } \{b\}$. Moreover, we have that $A \leftarrow B'$ and, in particular, by (D3), that $\{b\} \leftarrow B'$. This is absurd, since $Ic_\leftarrow (B)=B$, i.e. $\{b\} \nleftarrow B'$. This proves that B satisfies (B3), i.e. $B \in BAS_\leftarrow (A)$. $\square$

The condition that an element $a\in A$ satisfies the condition $\{a\} \leftarrow A {\setminus } \{a\}$ can be considered also relatively to a subset B of A in the following way.

Definition 4.6

Let $A, B \in \mathcal {P}(\Omega )$. We say that B is $\leftarrow A$-essential, or, equivalently, an $\leftarrow$essential subset of A, denoted by $B\leftarrow _{ess} A$, if:

(E1):

$B\subseteq A$;

(E2):

$B \nleftarrow A{\setminus } B$;

(E3):

B is minimal with respect to the property (E2), that is, $B'\subsetneqq B \implies B' \leftarrow A{\setminus } B'$.

We set $ESS_\leftarrow (A):=\{B\in \mathcal {P}(A): B\leftarrow _{ess} A\}$.

Remark 4.7

Let us notice that $Ic_\leftarrow (A)$ coincides with the subset of all $\leftarrow$essential elements of A.

For specific computations of essential subset families relative to dependency relations induced by graphs see [13].

In the next result, we provide two characterizations for a subset to be a $\leftarrow A$-essential subset.

Theorem 4.8

Let $B \subseteq A$. Then the following conditions are equivalent:

(i):

$B \in ESS_\leftarrow (A)$.

(ii):

$Dc_\leftarrow (A{\setminus } B)\subsetneqq Dc_\leftarrow (A)$ and $Dc_\leftarrow (A{\setminus } B')=Dc_\leftarrow (A)$ for all $B'\subsetneqq B$.

(iii):

$A {\setminus } B$ covers A in the lattice $(CLOS_\leftarrow (A),\subseteq )$.

Proof

(i) $\implies$ (ii): Clearly, for any $B \subseteq A$, we have that $A {\setminus } B \subseteq A$, whence $Dc_\leftarrow (A {\setminus } B) \subseteq Dc_\leftarrow (A)$. On the other hand, let $B \in ESS_\leftarrow (A)$. Property (E2) ensures that $B \nleftarrow A {\setminus } B$ and, in view of (1), we conclude that $B \not \subseteq Dc_\leftarrow (A {\setminus } B)$. Nevertheless, as $B \subseteq Dc_\leftarrow (A)$, it must necessarily be $Dc_\leftarrow (A {\setminus } B) \subsetneqq Dc_\leftarrow (A)$.

Finally, by (E3), we have that if $B' \subsetneqq B$, then $B' \leftarrow A {\setminus } B'$. Therefore, by (1), it follows that $B' \subseteq Dc_\leftarrow (A {\setminus } B')$, so $A {\setminus } B' \cup B'=A \subseteq Dc_\leftarrow (A {\setminus } B')$. This means that $Dc_\leftarrow (A)=Dc_\leftarrow (A {\setminus } B')$ and this shows the claim.

(ii) $\implies$ (i): Let $B \in \mathcal {P}(\Omega )$ be such that $Dc_\leftarrow (A{\setminus } B)\subsetneqq Dc_\leftarrow (A)$ and $Dc_\leftarrow (A{\setminus } B')=Dc_\leftarrow (A)$ for all $B'\subsetneqq B$. Clearly, (E1) is verified. Now, let us prove (E2). To this regard, assume by contradiction that $B \leftarrow A {\setminus } B$. Then, by (1), it follows that $B \subseteq Dc_\leftarrow (A {\setminus } B)$, that means that $Dc_\leftarrow (A)=Dc_\leftarrow (A {\setminus } B)$, contradicting our assumption. Hence, $B \nleftarrow A {\setminus } B$. Finally, let $B' \subsetneqq B$ be such that $B' \nleftarrow A {\setminus } B'$. Then $B' \not \subseteq Dc_\leftarrow (A {\setminus } B')$, so $Dc_\leftarrow (A) \ne Dc_\leftarrow (A {\setminus } B')$, again contradicting our assumption. This proves (E3) and, in particular, that $B \leftarrow _{ess} A$.

(ii) $\implies$ (iii): Let $B \subseteq A$ such that $Dc_\leftarrow (A{\setminus } B)\subsetneqq Dc_\leftarrow (A)$ and $Dc_\leftarrow (A{\setminus } B')=Dc_\leftarrow (A)$ for all $B'\subsetneqq B$. Let us show that $A {\setminus } B=Dc_\leftarrow (A {\setminus } B) \cap A$. Clearly, $A {\setminus } B \subseteq Dc_\leftarrow (A {\setminus } B) \cap A$. Vice versa, let $a \in Dc_\leftarrow (A {\setminus } B) \cap A$ and assume that $a \notin A {\setminus } B$. Hence $a \in B$.

Set now $B':=B {\setminus } A$. It is straightforward to show that $Dc_\leftarrow (A {\setminus } B)=Dc_\leftarrow (A {\setminus } B')$. Nevertheless, we would have $Dc_\leftarrow (A {\setminus } B)=Dc_\leftarrow (A {\setminus } B')=Dc_\leftarrow (A)$, contradicting our assumption. This means that $A {\setminus } B=Dc_\leftarrow (A {\setminus } B) \cap A$, i.e. $A {\setminus } B \in CLOS_\leftarrow (A)$. We must show that $A {\setminus } B$ covers A in the lattice $CLOS_\leftarrow (A)$. To this regard, suppose by contradiction it were false. Then, there exists $A {\setminus } B \subsetneqq C \subsetneqq A$ such that C covers A in the lattice $CLOS_\leftarrow (A)$. But, this ensures that $C=A {\setminus } B'$ for some non-empty $B' \subsetneqq B$. Let us prove that $Dc_\leftarrow (C) \subsetneqq Dc_\leftarrow (A)$. Assume by contradiction that equality holds, that is $Dc_\leftarrow (C)=Dc_\leftarrow (A)$. Since $C=A \cap M$ for some $M \in CLOS(\leftarrow )$, we would have $Dc_\leftarrow (C)=Dc_\leftarrow (A) \subseteq M$, i.e. $A \subseteq M$. But, this implies that $A \cap M=C \supseteq A$ and this is impossible. So, $Dc_\leftarrow (C) \subsetneqq Dc_\leftarrow (A)$. However, the existence of such a subset C contradicts our hypothesis on B. This proves that $A {\setminus } B$ covers A in the lattice $CLOS_\leftarrow (A)$.

(iii) $\implies$ (ii): Let B be a non-empty subset of A such that $A \setminus B$ covers A in the lattice $CLOS_\leftarrow (A)$. Assume by contradiction that $Dc_\leftarrow (A {\setminus } B)=Dc_\leftarrow (A)$. Since $A {\setminus } B=A \cap C$ for some $C \in CLOS(\leftarrow )$, we have that

$$\begin{aligned} Dc_\leftarrow (A \cap C)=Dc_\leftarrow (A {\setminus } B)=Dc_\leftarrow (A) \subseteq Dc_\leftarrow (A) \cap Dc_\leftarrow (C)=Dc_\leftarrow (A) \cap C, \end{aligned}$$

i.e. $Dc_\leftarrow (A) \subseteq C$. In other terms, we showed that $A=A \cap Dc_\leftarrow (A) \subseteq A \cap C=A {\setminus } B$ or, equivalently $A=A {\setminus } B$, that is a contradiction. Hence $Dc_\leftarrow (A {\setminus } B) \subsetneqq Dc_\leftarrow (A)$. Furthermore, let $B' \subsetneqq B$ and assume by contradiction that $Dc_\leftarrow (A {\setminus } B') \subsetneqq Dc_\leftarrow (A)$. Then, $A {\setminus } B \subsetneqq A {\setminus } B' \subseteq Dc_\leftarrow (A {\setminus } B') \cap A$. In particular, we also have that $Dc_\leftarrow (A {\setminus } B') \cap A \subsetneqq A$, otherwise $A \subseteq Dc_\leftarrow (A {\setminus } B')$, i.e. $Dc_\leftarrow (A)=Dc_\leftarrow (A {\setminus } B')$, contradicting our assumption. In this way, we showed that $A {\setminus } B$ does not cover A in the lattice $CLOS_\leftarrow (A)$, that is absurd. This proves the claim. $\square$

5 Some basic classifications of dependency relations

In this section, we establish some basic classifications for dependency relations and provide some results concerning equivalent formulations of such classifications. Next, in graph context we provide examples of dependency relations which fall in the classifications described in this section.

Theorem 5.1

Let $\leftarrow$ be a dependency relation on $\mathcal {P}(\Omega )$. Then the following conditions are equivalent:

(i):

for any $A\in \mathcal {P}(\Omega )$ and any $b,c\in \Omega$ we have that

$$\begin{aligned} \{b,c\} \nleftarrow _{\forall } A \,\, \mathrm{and}\,\, A \cup \{b\} \leftrightarrows _q A \cup \{c\} \implies A \cup \{b\} \leftrightarrows A \cup \{c\} \end{aligned}$$

(ii):

for any $A\in \mathcal {P}(\Omega )$, $b\in \Omega$, $a\in A$, we have that

$$\begin{aligned} \{b\} \nleftarrow A\,\,\,\mathrm{and}\,\,\, \{a\} \leftarrow A{\setminus } \{a\} \implies \{a\} \leftarrow (A{\setminus } \{a\}) \cup \{b\} \end{aligned}$$

Proof

$(i) \implies (ii)$: Let $\leftarrow$ satisfying (i) and let $A \in \mathcal {P}(\Omega )$, $a \in A$ and $b \in \Omega$ be such that $\{b\} \nleftarrow A$ and $\{a\} \leftarrow A {\setminus } \{a\}$. Assume by contradiction that $\{a\} \leftarrow (A {\setminus } \{a\}) \cup \{b\}$. Clearly, $a \ne b$, otherwise we would have $\{a\} \leftarrow (A {\setminus } \{a\}) \cup \{b\}$, contradicting by our assumption. Notice now that $\{b\} \nleftarrow A {\setminus } \{a\}$ otherwise $\{b\} \leftarrow A {\setminus } \{a\} \leftarrow A$ would imply $\{b\} \leftarrow A$ by (D2), that is a contradiction. Set $B:=A {\setminus } \{a\}$. It may be easily shown using our assumptions and the properties of the dependency relations that $\{a,b\} \nleftarrow _\forall B$ and that $B \cup \{a\}=A \leftarrow B \cup \{b\}$. Moreover, it follows that $A \leftrightarrows B \cup \{b\}=(A {\setminus } \{a\}) \cup \{b\}$, whence $\{b\} \leftarrow A$, contradicting our hypothesis. Therefore $\leftarrow$ satisfies (ii).

$(ii) \implies (i)$: Assume that $\leftarrow$ satisfies (ii). Let us consider $A \in \mathcal {P}(\Omega )$ and $b,c \in \Omega$ such that $\{b,c\} \nleftarrow _\forall A$ and $A \cup \{b\} \leftrightarrows _q A \cup \{c\}$. Let us assume, in particular, that $A \cup \{b\} \leftarrow A \cup \{c\}$ (the other case is similar). Let us assume by contradiction that $A \cup \{b\} \not \leftrightarrows A \cup \{c\}$, i.e. $A \cup \{c\} \nleftarrow A \cup \{b\}$.

Set $B:=A \cup \{b\}$. The last condition implies that $\{c\} \nleftarrow B$. Moreover, by our assumptions, we have $\{b\} \nleftarrow (A \cup \{b\}) {\setminus } \{b\}$. Since $\leftarrow$ satisfies (ii), we deduce that $\{b\} \nleftarrow (B {\setminus } \{b\}) \cup \{c\}=A \cup \{c\}$, i.e. $\{b\} \nleftarrow A \cup \{c\}$, that is a contradiction. Thus $A \cup \{b\} \leftrightarrows A \cup \{c\}$, i.e. $\leftarrow$ satisfies (i). $\square$

We call a dependency relation $\leftarrow$ an attractive dependency relation if it satisfies (i) or (ii) of Theorem 5.1. We denote by $DREL_{a}(\Omega )$ the set of all attractive dependency relations on $\mathcal {P}(\Omega )$.

In the finite case, we can establish the following equivalences for the condition obtained negating the thesis of (i) of Theorem 5.1.

Theorem 5.2

Let $\Omega$ be a finite set and let $\leftarrow$ be a dependency relation on $\mathcal {P}(\Omega )$ . Then the following conditions are equivalent:

• (i) For any $A\in \mathcal {P}(\Omega )$ and any $b \ne c\in \Omega$ we have that

  $$\begin{aligned} \{b,c\} \nleftarrow _{\forall } A \,\, \mathrm{and}\,\, A \cup \{b\} \leftrightarrows _q A \cup \{c\} \implies A \cup \{b\} \not \leftrightarrows A \cup \{c\} \end{aligned}$$

• (ii) $|\min ([A]_\leftrightarrows )|=1$ for any $A \in \mathcal {P}(\Omega )$;

• (iii) $\min ([A]_\leftrightarrows )=\{Ic_\leftarrow (Dc_\leftarrow (A))\}$ for any $A \in \mathcal {P}(\Omega )$;

• (iv) $Dc_\leftarrow (Ic_\leftarrow (A))=Dc_\leftarrow (A)$ for any $A \in \mathcal {P}(\Omega )$.

Proof

(i) $\implies$ (ii): Assume by contradiction that $|\min ([A]_\leftrightarrows )| \ge 2$ for some $A \in \mathcal {P}(\Omega )$; let $B,B'$ two distinct subsets in $\min ([A]_{\leftrightarrows })$ and $b \in B$. Clearly, $B {\setminus } \{b\} \not \leftrightarrows A$. Let us take $B'' \subseteq B'$ minimal with respect to the property that $B {\setminus } \{b\} \cup B'' \leftrightarrows A$. It is obvious that $B'' \ne \emptyset$. So, let $c \in B''$. Then $(B {\setminus } \{b\}) \cup (B'' {\setminus } \{c\}) \not \leftrightarrows A$. In particular, it follows that both the relations $\{b\} \nleftarrow (B {\setminus } \{b\}) \cup (B'' {\setminus } \{c\})$ and $\{c\} \nleftarrow (B {\setminus } \{b\}) \cup (B'' {\setminus } \{c\})$ hold. Set $C:=(B {\setminus } \{b\}) \cup (B'' {\setminus } \{c\})$. This means that $\{b,c\} \nleftarrow _\forall C$. Furthermore, it is straightforward to verify that $C \cup \{b\} \leftrightarrows C \cup \{c\}$. By the fact that $\leftarrow \, \in DREL_{aa}(\Omega )$, we conclude that $b=c$, i.e. $B \subseteq B'$. In a similar way, we prove that $B' \subseteq B$, so $B=B'$, that is a contradiction. This shows that $|\min ([A]_\leftrightarrows )|=|BAS_\leftarrow (Dc_\leftarrow (A))|=1$ for any $A \in \mathcal {P}(\Omega )$.

(ii) $\implies$ (iii): Assume that $|\min ([A]_\leftrightarrows )|=1$ for any $A \in \mathcal {P}(\Omega )$. Just observe that $BAS_\leftarrow (B)=BAS_\leftarrow (Dc_\leftarrow (A))$ for any $B \in [A]_\leftrightarrows$. Hence, by (iii) of Theorem 4.4, we conclude that $Ic_\leftarrow (Dc_\leftarrow (A))=Ic_\leftarrow (B)$ for any $B \in [A]_\leftrightarrows$ and, in particular, that $Ic_\leftarrow (Dc_\leftarrow (A)) \in \min ([Dc_\leftarrow (A)]_\leftrightarrows )$. So, the thesis has been proved.

(iii) $\implies$ (iv): Assume that $\min ([A]_\leftrightarrows )=\{Ic_\leftarrow (Dc_\leftarrow (A))\}$ for any $A \in \mathcal {P}(\Omega )$. By (iii) of Theorem 4.4, we have that $BAS_\leftarrow (A)=\{Ic_\leftarrow (A)\}$, therefore by (ii) of Theorem 3.6, it follows that $Dc_\leftarrow (Ic_\leftarrow (A))=Dc_\leftarrow (A)$. This shows the claim.

(iv) $\implies$ (i): Suppose that $Dc_\leftarrow (A)=Dc_\leftarrow (Ic_\leftarrow (A))$ for any $A \in \mathcal {P}(\Omega )$ and let us consider $b \ne c$ such that $\{b,c\} \nleftarrow _\forall A$ and assume that $\{b\} \leftarrow A \cup \{c\}$. Let us prove that $\{c\} \nleftarrow A \cup \{b\}$. For, assume by contradiction that $\{c\} \leftarrow A \cup \{b\}$. In particular, by Definition of $Ic_\leftarrow$, we deduce that $\{b,c\} \cap Ic_\leftarrow (A \cup \{b,c\})=\emptyset$. This proves that $Ic_\leftarrow (A \cup \{b,c\}) \subseteq A$. Now, we show that

$$\begin{aligned} Ic_\leftarrow (A \cup \{b,c\}) \subseteq Ic_\leftarrow (A). \end{aligned}$$

(7)

In fact, let $a \in Ic_\leftarrow (A \cup \{b,c\})$. Then, $\{a\} \leftarrow A {\setminus } \{a\} \cup \{b,c\}$. In particular, it must necessarily be $\{a\} \leftarrow A {\setminus } \{a\}$ otherwise, by (D2), we would have $\{a\} \leftarrow A {\setminus } \{a\} \leftarrow A {\setminus } \{a\} \cup \{b,c\}$, i.e. $A \leftarrow A {\setminus } \{a\} \cup \{b,c\}$, that is a contradiction. This shows (7). Thus, by our assumption and by (7), it follows that $Dc_\leftarrow (A \cup \{b,c\})=Dc_\leftarrow (Ic_\leftarrow (A \cup \{b,c\})) \subseteq Dc_\leftarrow (Ic_\leftarrow (A))=Dc_\leftarrow (A) \subseteq Dc_\leftarrow (A \cup \{b,c\})$, i.e. $Dc_\leftarrow (A)=Dc_\leftarrow (A \cup \{b,c\})$ or, equivalently, $\{b,c\} \subseteq Dc_\leftarrow (A)$. This means that $\{b,c\} \leftarrow A$, that is a contradiction. This shows that $\leftarrow$ satisfies (i). $\square$

We say that $\leftarrow$ is an anti-attractive dependency relation if $\leftarrow$ satisfies the condition (i) of Theorem 5.2. We denote by $DREL_{aa}(\Omega )$ the set of all anti-attractive dependency relations on $\mathcal {P}(\Omega )$.

When $\Omega$ is finite and the dependency relation is also pointwise non-trivial, we can provide a further equivalence with the property of local anti-attractiveness. In order to establish this equivalence, we set

$$\begin{aligned} A \looparrowleft B :\iff ( (A\subseteq B) \, \mathrm{and} \, (b\in B \,\,\, \mathrm{and}\,\,\, \{b\} \nleftarrow B \implies b \in A )), \end{aligned}$$

for any $A,B \in \mathcal {P}(\Omega )$.

We have then the following result.

Theorem 5.3

Let $\Omega$ be a finite set and $\leftarrow$ be a pointwise non-trivial relation on $\mathcal {P}(\Omega )$. Then the following conditions are equivalent:

(i):

$\leftarrow$ is anti-attractive;

(ii):

for any $A, B \in \mathcal {P}(\Omega )$ such that $A \looparrowleft B$, we have that $a \in A \,\,\,\mathrm{and}\,\,\, \{a\} \leftarrow A {\setminus } \{a\} \implies \{a\} \leftarrow B {\setminus } \{a\}$.

Proof

$(i) \implies (ii)$: Let $\leftarrow \, \in DREL_{aa}(\Omega ) \cap DREL_{pnt}(\Omega )$. For, let us assume that $A \looparrowleft B$, that is clearly equivalent to require that $Ic_\leftarrow (B) \subseteq A \subseteq B$. Let $b \in Ic_\leftarrow (B)$. Then $\{b\} \nleftarrow B {\setminus } \{b\}$ so, a fortiori, $\{b\} \nleftarrow A {\setminus } \{b\}$. This means that $b \in Ic_\leftarrow (A)$ and, in particular, $Ic_\leftarrow (B) \subseteq Ic_\leftarrow (A)$. By (iv) of Theorem 5.2, we have

$$\begin{aligned} Dc_\leftarrow (Ic_\leftarrow (B))=Dc_\leftarrow (B) \subseteq Dc_\leftarrow (Ic_\leftarrow (A))=Dc_\leftarrow (A) \subseteq Dc_\leftarrow (B), \end{aligned}$$

that is $Dc_\leftarrow (A)=Dc_\leftarrow (B)$. Moreover, by (iii) of Theorem 5.2 and by (iii) of Theorem 4.4, it follows that $\min ([A]_\leftrightarrows )=\{Ic_\leftarrow (A)\}$ and, in particular, $Ic_\leftarrow (A)=Ic_\leftarrow (B)$. By the definition of $Ic_\leftarrow$, we conclude that $\leftarrow$ satisfies (ii).

$(ii) \implies (i)$: Assume that $\leftarrow$ satisfies (ii). We must prove that $\leftarrow \, \in DREL_{aa}(\Omega )$. For, let $b \ne c$ be such that $\{b,c\} \nleftarrow _\forall A$ and assume that $\{b\} \leftarrow A \cup \{c\}$ (the other case is similar). To say that $\{b,c\} \nleftarrow _\forall A$ means that $b \in Ic_\leftarrow (A \cup \{b\})$ and $c \in Ic_\leftarrow (A \cup \{c\})$.

Assume now by contradiction that $\{c\} \leftarrow A \cup \{b\}$. By our assumptions, it easily follows that $Dc_\leftarrow (A \cup \{b\})=Dc_\leftarrow (A \cup \{c\})=Dc_\leftarrow (A \cup \{b,c\})$, i.e. $\{b,c\} \cap Ic_\leftarrow (A \cup \{b,c\})=\emptyset$. This entails $Ic_\leftarrow (A \cup \{b,c\}) \subseteq A$.

Thus, $A \cup \{b\} \looparrowleft A \cup \{b,c\}$. By our assumptions on $\leftarrow$, it must necessarily be $Ic_\leftarrow (A \cup \{b\}) \subseteq Ic_\leftarrow (A \cup \{b,c\})$. But this means that $b \in Ic_\leftarrow (A \cup \{b\}) \subseteq Ic_\leftarrow (A \cup \{b,c\}) \subseteq A$, that leads to a contradiction, namely $\{b\} \leftarrow A$. Then $\leftarrow \, \in DREL_{aa}(\Omega )$ and this concludes the proof. $\square$

6 Dependency relations induced by pairings

We now introduce a structure on $\Omega$ with which we are able to provide a dependency relation on $\mathcal {P}(\Omega )$. Next, we show that when $\Omega$ is a finite set, by means of such a structure we can obtain any possible dependency relation on $\mathcal {P}(\Omega )$.

Definition 6.1

We call a triple $\mathfrak {P}=\langle U, F, \Lambda \rangle$, where U, $\Lambda$ are non-empty sets and F is a map $U \times \Omega \rightarrow \Lambda$, a pairing on $\Omega$. We denote by $PAIR(\Omega )$ the set of all pairings on $\Omega$.

In a purely combinatorial context, in the finite case we can identify the pairing $\mathfrak {P}$ with the rectangular table whose rows and columns are labeled respectively by the elements $u\in U$ and $a\in \Omega$ and whose entries are the values F(u, a).

For any $A\in \mathcal {P}(\Omega )$, we denote by $\equiv _A$ be the equivalence relation on U defined by

$$\begin{aligned} u \equiv _A u' :\iff F(u, a)=F(u', a), \end{aligned}$$

(8)

for any $a \in A$, for all $u, u'\in U$. In view of the interpretation of $\equiv _A$ given in graph context (see [13]), we say that $\equiv _A$ is the A-symmetry relation on U. We can consider $\equiv _A$ as a type of local symmetry relation induced by the pairing structure (for more detailed studies on this relation see [18]). If $u\in U$, let $[u]_A$ the equivalence class of u with respect to $\equiv _A$, that we call A-symmetry class of u, and let $\pi _{\mathfrak {P}}(A):=\{[u]_A: u \in U\}$ be the set partition on U induced by $\equiv _A$, that we call A-symmetry partition of U. Based on (8), we will define a dependency relation arising from the pairing context. If $A, B\in \mathcal {P}(\Omega )$, we can consider the situation in which the local symmetry induced by A can be transmitted in the local symmetry induced by B. We set therefore

$$\begin{aligned} B \leftarrow _{\mathfrak {P}}A :\iff (\forall u, u' \in U, \,\, u\equiv _A u' \implies u\equiv _B u') \end{aligned}$$

(9)

Then it is immediate to verify that $\leftarrow _{\mathfrak {P}}$ is a dependency relation on $\mathcal {P}(\Omega )$.

Let us note that the right part of (9) is equivalent to the condition $\pi _{\mathfrak {P}}(A) \preceq \pi _{\mathfrak {P}}(B)$, where $\preceq$ is the usual refining partial order between set partitions of U. In what follows, we write $\pi _{\mathfrak {P}}(A) \prec \pi _{\mathfrak {P}}(B)$ when $\pi _{\mathfrak {P}}(A) \preceq \pi _{\mathfrak {P}}(B)$ and $\pi _{\mathfrak {P}}(A) \ne \pi _{\mathfrak {P}}(B)$.

Definition 6.2

By referring to the pairing $\mathfrak {P}$, we use the following terminology.

• We call $\leftarrow _{\mathfrak {P}}$ the $\mathfrak {P}$-dependency relation on $\Omega$, or simply the $\mathfrak {P}$-dependency on $\Omega$ and, if $B \leftarrow _{\mathfrak {P}}A$, we say that B is $\mathfrak {P}$-dependent on A;

• We denote by $\leftrightarrows _{\mathfrak {P}}$ the corresponding equivalence relation associated with $\leftarrow _{\mathfrak {P}}$ and given in (3) and we call $\leftrightarrows _{\mathfrak {P}}$ the $\mathfrak {P}$-dependency equivalence on $\mathcal {P}(\Omega )$;

• if $A \leftrightarrows _{\mathfrak {P}} B$, we say that A and B are $\mathfrak {P}$-dependency equivalent and we denote by $[A]_{\mathfrak {P}}$ the equivalence class with respect to $\leftrightarrows _{\mathfrak {P}}$, that we call $\mathfrak {P}$-equivalence dependency class of A.

Remark 6.3

When we deal with pairings, we will use $\mathfrak {P}$ instead of $\leftarrow _{\mathfrak {P}}$. For example, we will write $Dc_{\mathfrak {P}}$ instead of $Dc_{\leftarrow _{\mathfrak {P}}}$, $CLOS_{\mathfrak {P}}(A)$ instead of $CLOS_{\leftarrow _{\mathfrak {P}}}(A)$, $CLOS(\mathfrak {P})$ instead of $CLOS(\leftarrow _{\mathfrak {P}})$ and, similarly, for the other set operators and set systems introduced in the previous sections. Moreover, we use the terminology $\mathfrak {P}$ instead of $\leftarrow$. For example, $Dc_{\mathfrak {P}}$ will be called the $\mathfrak {P}$-dependency closure and so on.

Remark 6.4

Let us note that $A \leftrightarrows _{\mathfrak {P}} B$ if and only if $\pi _{\mathfrak {P}}(A)=\pi _{\mathfrak {P}}(B)$.

In the next result we show that in the finite case any dependency relation on $\mathcal {P}(\Omega )$ is a $\mathfrak {P}$-dependency relation, for some pairing $\mathfrak {P}\in PAIR(\Omega )$.

Theorem 6.5

Let $\Omega$ be a finite set and let $\leftarrow$ be a dependency relation on $\mathcal {P}(\Omega )$. Then there exists a pairing $\mathfrak {P}\in PAIR(\Omega )$ such that $\leftarrow _{\mathfrak {P}}$ coincides with $\leftarrow$.

Proof

Let $\mathcal {H}:=CLOS(\leftarrow )$. Since $\mathcal {H}$ is a convexity, it is also a lattice with respect the set theoretical inclusion whose top element is $\Omega$ (see [19]). On the other hand, in Theorem 4.1 of [18] it has been proved that for any finite convexity there exists a pairing on the same ground set whose closed subset family coincides with the given convexity. Therefore, in our case there exists a pairing $\mathfrak {P}\in PAIR(\Omega )$ such that $\mathcal {H}=CLOS(\mathfrak {P})$. This entails that $Dc_{\mathfrak {P}}=Dc_\leftarrow$ and so, by (1), we deduce that the dependency relations $\leftarrow$ and $\leftarrow _{\mathfrak {P}}$ coincide. $\square$

We set

$$\begin{aligned} \Gamma _{\mathfrak {P}}(A,B):=\{u\in U: [u]_A \subseteq [u]_B\}, \end{aligned}$$

(10)

for any $A,B\in \mathcal {P}(\Omega )$.

Moreover, when U is a finite set, we can also consider the map $\gamma _{\mathfrak {P}}: \mathcal {P}(\Omega ) \times \mathcal {P}(\Omega ) \rightarrow [0,1]$ defined by

$$\begin{aligned} \gamma _{\mathfrak {P}}(A,B):=\frac{|\Gamma _{\mathfrak {P}}(A,B)|}{|U|} \end{aligned}$$

Then we have that

$$\begin{aligned}&B \leftarrow _{\mathfrak {P}}A \iff \pi _{\mathfrak {P}}(A) \preceq \pi _{\mathfrak {P}}(B) \nonumber \\&\qquad \iff \Gamma _{\mathfrak {P}}(A,B)=U \iff \mathrm{(when}\,\, U \,\,\mathrm{is\,\, finite)}\,\, \gamma _{\mathfrak {P}}(A,B)=1 \end{aligned}$$

In the next result, we show that the dependency relation induced by pairings generalizes the partial order relations on finite lattices.

Theorem 6.6

Let $\mathbb {L}=(L, \le _{\mathbb {L}})$ be a finite lattice. Then there exist a finite set $\Omega$, a pairing $\mathfrak {P}\in PAIR(\Omega )$ and a bijective map $\eta : L \rightarrow CLOS(\mathfrak {P})$ such that

$$\begin{aligned} y \le _{\mathbb {L}} x \iff \gamma _{\mathfrak {P}}(\eta (x), \eta (y))=1 \end{aligned}$$

(11)

for any $x, y\in L$.

Proof

Let $\mathbb {L}=(L, \le _{\mathbb {L}})$ be a finite lattice. In view of a classical result of order theory [19], any finite lattice can be represented as a convexity $\mathfrak {S}_\mathbb {L}$ on $\Omega _\mathbb {L}:=\mathcal {J}(\mathbb {L})$, whose closure operator $\phi : \mathcal {P}(\Omega ) \rightarrow \mathcal {P}(\Omega )$ assumes the form

$$\begin{aligned} \phi (A):=\Big \{x \in \Omega : \, x \le \bigvee A\Big \} \end{aligned}$$

and such that $\mathbb {L}$ is order isomorphic to $(\mathfrak {S}_\mathbb {L}, \subseteq )$. Let us denote by $\eta$ such an isomorphism. Now, by means of the same construction exhibited in the proof of Theorem 6.5, we can find a pairing $\mathfrak {P}\in PAIR(\Omega _\mathbb {L})$ such that $\mathfrak {S}_\mathbb {L}=CLOS(\mathfrak {P})$. Then, since $\eta$ is an order isomorphism, by part (iii) of Corollary 3.10 we have that

$$\begin{aligned} y \le _\mathbb {L}x \iff \eta (y) \subseteq \eta (x) \iff \eta (y) \leftarrow _{\mathfrak {P}}\eta (x), \end{aligned}$$

for any $x, y\in L$. The thesis follows then by (). $\square$

Corollary 6.7

In the same hypotheses and notations of Theorem 6.6, the lattice $\mathbb {L}$ is order isomorphic to the lattice $(EDC(\leftarrow _{\mathfrak {P}}), \leftarrow _{\mathfrak {P}}^{ext})$.

Proof

It is a consequence of Remark 3.11, () and (11)

In view of Theorem 6.6, we observe that the function $\gamma _{\mathfrak {P}}$ allows us to refine the partial order $\le _{\mathbb {L}}$, since it provides a numerical information also between two non-comparable nodes of the lattice $\mathbb {L}$. In fact, for any two elements $x,y \in \mathbb {L}$, we have that $x \le _\mathbb {L}y$ if and only if $\gamma _{\mathfrak {P}}(\eta _{\mathfrak {P}}(x),\eta _{\mathfrak {P}}(y))=1$ but, however, we can always compute the value $\gamma _{\mathfrak {P}}(\eta _{\mathfrak {P}}(x),\eta _{\mathfrak {P}}(y))$ even if x and y are non-comparable each other. To this regard, let us note that the complete knowledge of the table of all possible values $\gamma _{\mathfrak {P}}(A,B)=1$, for $A, B\in \mathcal {P}(\Omega )$, provides a more detailed information with respect to the partial order $\le _\mathbb {L}$. To this regard, we recall that several recent results concerning the determination of such tables and relates averages, for pairings induced by graphs, digraphs and some types of discrete dynamical systems have been obtained in [12, 15, 26].

7 Dependency relations induced by graphs

In this final section we investigate two types of dependency relations induced by simple undirected graphs. In the first case we induce the dependency relation on the vertex set of a connected n-graph by means of the distance between vertices. In the second case we use adjacency. We provide classification results for paths, cycles and complete multipartite graphs.

7.1 Distance pairing from connected n-graphs

Let G be a connected n-graph. Then, we can associate with it the pairing $\mathfrak {P}[G,d]:=(V(G),d,\mathbb {N})$, where d denotes the usual distance between two vertices of G. We call $\mathfrak {P}[G,d]$ the distance pairing of G. In what follows, when we denote the quantity $\rho _\leftarrow (A)$ given in Definition 4.1, we will omit the symbol $\leftarrow$.

Remark 7.1

It is immediate to see that $\pi _{\mathfrak {P}}(\emptyset )=V(G)$ and $\pi _{\mathfrak {P}}(V(G))=v_1|\dots |v_n$.

In the next result, we firstly provide a general form for $CLOS(\mathfrak {P}[C_n,d])$ and, next, we prove a type of replaceability and a type of decomposability for the dependency relation associated with $\mathfrak {P}[C_n,d]$. Finally, we show that $\mathfrak {P}[C_n,d]$ is an attractive pairing and compute both $BAS(\mathfrak {P}[C_n,d])$ and $\rho (\mathfrak {P}[C_n,d])$.

Theorem 7.2

Let $n \ge 3$ and $\mathfrak {P}:=\mathfrak {P}[C_n,d]$. Then

(i):

we have that:

$$\begin{aligned} CLOS(\mathfrak {P})=\left\{ \begin{array}{ll} \{\emptyset \} \cup \{ v_i, \,\, i=1,\dots ,n \} \cup V(G) &{} \mathrm{if} \,\, n=2k+1\\ \{\emptyset \} \cup \left\{ \{v_i,v_{i+\frac{n}{2}} \}, \, \, i=1,\dots ,\frac{n}{2} \right\} \cup V(G) &{} \mathrm{if} \,\, n=2k\\ \end{array} \right. \end{aligned}$$

(ii):

for any $A \in \mathcal {P}(\Omega )$ and any $\{b\} \leftarrow _{\mathfrak {P}}A$ there exists $a \in A$ such that for any $\{x\} \leftarrow _{\mathfrak {P}}A$ it follows that $\{x\} \leftarrow _{\mathfrak {P}}\{b\} \cup (A {\setminus } \{a\})$;

(iii):

$\mathfrak {P}[C_n,d]$ is attractive;

(iv):

for any pair $(A,b) \in CLOS(\mathfrak {P}) \times \Omega$ it results that

$$\begin{aligned} \{c\} \leftarrow A \cup \{b\} \iff \exists \,a\in A:\, \{c\} \leftarrow \{a, b\}. \end{aligned}$$

(12)

(v):

we have that

$$\begin{aligned} BAS(\mathfrak {P}[C_n,d])=\left\{ \begin{array}{ll} \left( {\begin{array}{c}V(C_n)\\ 2\end{array}}\right) &{} \mathrm{if} \,\, n=2k+1\\ \left( {\begin{array}{c}V(C_n)\\ 2\end{array}}\right) \big \backslash \left\{ \{v_i,v_{i+\frac{n}{2}} \}, \, \, i=1,\dots ,\frac{n}{2} \right\} &{} \mathrm{if} \,\, n=2k\\ \end{array} \right. \end{aligned}$$

In particular, $\rho (\mathfrak {P}[C_n,d])=2$.

Proof

(i): Let us compute $\pi _{\mathfrak {P}}(A)$ when A runs over $\mathcal {P}(V(C_n))$. Clearly, if $A=\emptyset$, we have $\pi _{\mathfrak {P}}(A)=v_1\dots v_n$. If $A=v_i$ for some $i=1,\dots ,n$, we have that $v_i$ constitutes a single block since it is the only vertex whose distance from $v_i$ is 0. This shows that $\pi _{\mathfrak {P}}(A) \ne \pi _{\mathfrak {P}}(\emptyset )$, so $Dc_{\mathfrak {P}}(\emptyset )=\emptyset$. Furthermore, when n is odd, each symmetry block distinct from that of $v_i$ contains exactly two vertices, while, when n is even, the symmetry block of $v_{i+\frac{n}{2}}$ contains only $v_{i+\frac{n}{2}}$, that is the only vertex whose distance from $v_i$ is $i+\frac{n}{2}$, whereas the other blocks contain two elements. Clearly $\pi _{\mathfrak {P}}(\{v_i\})=\pi _{\mathfrak {P}}(\{v_{i+\frac{n}{2}}\})$.

Now, let $A=\{v_i\} \ne \{v_j\}=A'$. Assume that $A \leftrightarrows _{\mathfrak {P}} A'$. Then, for any two vertices $v_k,v_{k'} \in V(C_n)$ we must have $d(v_k,v_i)=d(v_{k'},v_i)$ if and only if $d(v_k,v_j)=d(v_{k'},v_j)$. In particular, $d(v_i,v_j)=d(v_k,v_i)+d(v_k,v_j)=d(v_{k'},v_i)+d(v_{k'},v_j)$. This means that the line joining $v_i$ and $v_j$ divides the regular polygon $C_n$ in two symmetric parts, but this happens if and only if n is even and $j=i+\frac{n}{2}$. This shows that $\pi _{\mathfrak {P}}(v_i)=\pi _{\mathfrak {P}}(\{v_j\})$ if and only if n is even and $j=i+\frac{n}{2}$.

Let us consider $A=\{v_i,v_j\}$. Then, when n is odd, there are no two vertices symmetric to both $v_i$ and $v_j$, so $\pi _{\mathfrak {P}}(A)=\pi _{\mathfrak {P}}(V(C_n))=v_1|\dots |v_n$; on the contrary, when n is even, this happens if only if $A=\{v_i,v_{i+\frac{n}{2}}\}$. This shows that $Dc_{\mathfrak {P}}(\{v_i\})=\{v_i\}$, for $i=1,\dots ,n$, when n is odd and that $Dc_{\mathfrak {P}}(v_i)=\{v_i,v_{i+\frac{n}{2}}\}$, for $i=1,\dots ,\frac{n}{2}$, when n is even. Finally, since any other vertex subset A having cardinality greater than 2 contains two vertices whose distance is not $\frac{n}{2}$, then $A \leftrightarrows _{\mathfrak {P}} V(C_n)$.

(ii): By (1), the condition for any $A \in \mathcal {P}(\Omega )$ and any $\{b\} \leftarrow _{\mathfrak {P}}A$ there exists $a \in A$ such that for any $\{x\} \leftarrow _{\mathfrak {P}}A$ it follows that $\{x\} \leftarrow _{\mathfrak {P}}\{b\} \cup (A {\setminus } \{a\})$ is equivalent to say that $\bigcup _{a\in A}(\{b\} \cup Dc_{\mathfrak {P}}(A {\setminus } \{a\}))=Dc_{\mathfrak {P}}(A)$. Hence, we will prove $\bigcup _{a\in A}(\{b\} \cup Dc_{\mathfrak {P}}(A {\setminus } \{a\}))=Dc_{\mathfrak {P}}(A)$. To this regard, let us observe that it is immediate to prove that $\bigcup _{a\in A}(\{b\} \cup Dc_{\mathfrak {P}}(A {\setminus } \{a\})) \subseteq Dc_{\mathfrak {P}}(A)$ whenever $\{b\} \leftarrow _{\mathfrak {P}}A$. On the other hand, If $A=\emptyset$, the reverse inclusion is obvious. Moreover, the claim is obvious if $Dc_{\mathfrak {P}}(A)=A$, since $b \in A$. W now prove the reverse inclusion in the other non-trivial cases. Let now $n \ge 3$ be an odd integer. If $A=\{a\}$, then we can only take $a=b$. Let us consider a vertex subset $A \subseteq V(C_n)$ such that $|A| \ge 2$ and fix $\{b\} \leftarrow _{\mathfrak {P}}A$ such that $b \notin A$. Since $|(A {\setminus } \{a\}) \cup \{b\}| = |A|$, we conclude that $Dc_{\mathfrak {P}}(A)=Dc_{\mathfrak {P}}((A {\setminus } \{a\}) \cup \{b\})=V(C_n)$ and the thesis follows.

On the contrary, let $n \ge 4$ be an even integer and $\{b\} \leftarrow _{\mathfrak {P}}A$ such that $b \notin A$. If $A=\{v_i\}$ and $b=v_{i+\frac{n}{2}}$, the claim follows by the fact that $Dc_{\mathfrak {P}}(v_i)=Dc_{\mathfrak {P}}(v_{i+\frac{n}{2}})$. Finally, if $A \leftrightarrows _{\mathfrak {P}} V(C_n)$, there always exists a vertex $a \in A$ whose distance from b is different from $i+\frac{n}{2}$, thus just replace with another vertex in A, say $a'$. In this way, we have that $Dc_{\mathfrak {P}}(A {\setminus } \{a\}' \cup \{b\})=V(C_n)$. This proves that $Dc_{\mathfrak {P}}(A) \subseteq \bigcup _{a\in A}(\{b\} \cup Dc_{\mathfrak {P}}(A {\setminus } \{a\}))$ and claim follows.

(iii): In view of Theorem 5.1, we must show that for any $A\in \mathcal {P}(\Omega )$ and any $b,c\in \Omega$ we have that

$$\begin{aligned} \{b,c\} \nleftarrow _{\forall } A \,\, \mathrm{and}\,\, A \cup \{b\} \leftrightarrows _q A \cup \{c\} \implies A \cup \{b\} \leftrightarrows A \cup \{c\} \end{aligned}$$

To this aim, let $A \in \mathcal {P}(V(C_n))$ and $b,c \in V(C_n) {\setminus } Dc_{\mathfrak {P}}(A)$ such that $b \in Dc_{\mathfrak {P}}(A \cup \{c\})$ (the case $c \in Dc_{\mathfrak {P}}(A \cup \{b\})$ is similar). We have to show that $c \in Dc_{\mathfrak {P}}(A \cup \{b\})$, so that $A \cup \{b\} \leftrightarrows _{\mathfrak {P}} A \cup \{c\}$. To this regard, we study the odd and the even case separatedly.

Let $n \ge 3$ be an odd integer. In view of part (i), we have only to investigate the cases $A=\emptyset$ and $A=v_i$, for $i=1,\dots ,n$. Let $A=\emptyset$, then to say that $b \in Dc_{\mathfrak {P}}(c)$ means that $b=c$ by part (i), hence $c \in Dc_{\mathfrak {P}}(A \cup \{b\})$. Moreover, let now $A=\{v_i\}$ for some $i \in \hat{n}$. Then $Dc_{\mathfrak {P}}(A)=A$, thus, for any $b,c \in V(C_n) {\setminus } A$, we have $|A \cup \{b\}|=|A \cup \{c\}|=2$, so $Dc_{\mathfrak {P}}(A \cup \{b\})=Dc_{\mathfrak {P}}(A \cup \{c\})=V(C_n)$. This proves the claim when n is odd.

On the other hand, let $n \ge 4$ be an even integer. In view of part (i), we have only to investigate the cases $A=\emptyset$, $A=\{v_i\}$, for $i=1,\dots ,n$, and $A=\{v_i,v_{i+\frac{n}{2}}\}$. If $A=\emptyset$, then let $c:=v_i$. The condition $b \in Dc_{\mathfrak {P}}(A \cup \{c\})$ implies that $b=v_i$ or $b=v_{i+\frac{n}{2}}$. In both cases, it follows immediately by part (i), that $c \in Dc_{\mathfrak {P}}(A \cup \{b\})$. Let now $A=\{v_i\}$ for some $i \in \hat{n}$. Then, to take $b,c \in V(C_n) {\setminus } Dc_{\mathfrak {P}}(A)$ means that $\{b,c\} \cap \{v_i,v_{i+\frac{n}{2}}\}=\emptyset$. Hence $Dc_{\mathfrak {P}}(A \cup \{b\})=Dc_{\mathfrak {P}}(A \cup \{c\})=V(C_n)$, i.e. $c \in Dc_{\mathfrak {P}}(A \cup \{b\})$ whenever $b \in Dc_{\mathfrak {P}}(A \cup \{c\})$. The case $A=\{v_i,v_{i+\frac{n}{2}}\}$ is similar. This shows that $\mathfrak {P}$ is attractive.

(iv): Let $n \ge 3$ be an odd integer. In view of part (i), we have that $CLOS(\mathfrak {P})=\{\emptyset , \{v_1\},\dots ,\{v_n\},V(C_n)\}$. Clearly, if if $A=\emptyset$ or $A=V(C_n)$, then (A, b) satisfies (12) for any $b \in V(C_n)$. On the other hand, let $A=v_i$ for some $i=1,\dots ,n$. The pair $(v_i,v_i)$ obviously satisfies (12). Moreover, if $b=v_j$ for $j \ne i$, then $Dc_{\mathfrak {P}}(A \cup \{b\})=V(C_n)=\bigcup \nolimits _{a \in A} Dc_{\mathfrak {P}}(\{a,b\})$, that is clearly equivalent to (12).

Assume now that $n \ge 4$ is an even integer. In view of part (i), we have that $CLOS(\mathfrak {P})=\{\emptyset , \{v_i,v_{i+\frac{n}{2}}\},V(C_n)\}$, where $i=1,\dots ,\frac{n}{2}$. The claim is obvious when $A=\emptyset$ or $A=V(C_n)$. Hence, assume $A=\{v_i,v_{i+\frac{n}{2}}\}$ and let $b:=v_i$. Then $Dc_{\mathfrak {P}}(A \cup \{v_i\})=Dc_{\mathfrak {P}}(A)=Dc_{\mathfrak {P}}(\{v_i\}) \cup Dc_{\mathfrak {P}}(A)$, so the pair (A, b) satisfies (12). The case $b=v_{i+\frac{n}{2}}$ may be investigated similarly to $b=v_i$. Finally, let $c:=v_j$, where $j \ne i,i+\frac{n}{2}$. Hence, by part (i), $Dc_{\mathfrak {P}}(A \cup \{c\})=V(C_n)=Dc_{\mathfrak {P}}(\{v_i,v_j\}) \cup Dc_{\mathfrak {P}}(\{v_{i+\frac{n}{2}},v_j\})$, i.e. (12) holds.

(v): It is an immediate consequence of the definition of $BAS(\mathfrak {P}[C_n,d])$ and of part (i).

$\square$

In the next result, we express the general form of $CLOS(\mathfrak {P}[P_n,d])$ and compute $BAS(\mathfrak {P}[P_n,d])$.

Theorem 7.3

Let $n \ge 3$ and set $\mathfrak {P}:=\mathfrak {P}[P_n,d]$. Then:

(i):

we have that

$$\begin{aligned} CLOS(\mathfrak {P}[P_n,d])=\{\emptyset \} \cup \{ v_i, \,\, i=2,\dots ,n-1 \} \cup V(P_n); \end{aligned}$$

(ii):

we have that

$$\begin{aligned} BAS(\mathfrak {P}[P_n,d])=\{ \{v_1\},\{v_n\}\} \cup \left\{ A \in \left( {\begin{array}{c}V(P_n)\\ 2\end{array}}\right) : \, \{v_1,v_n\} \cap A=\emptyset \right\} . \end{aligned}$$

In particular, $\rho (\mathfrak {P}[P_n,d])=1$. On the other hand, if G is a connected n-graph such that $\rho (\mathfrak {P}[G,d])=1$, then $G=P_n$.

Proof

(i): Let us compute $\pi _{\mathfrak {P}}(A)$ when A runs over $\mathcal {P}(V(P_n))$. Clearly, $\pi _{\mathfrak {P}}(\emptyset )=v_1\dots v_n$. On the other hand, if $A=v_i$ for some $i=1,\dots ,n$, we have that $v_i$ constitutes a single block since it is the only vertex whose distance from $v_i$ is 0. This shows that $\pi _{\mathfrak {P}}(A) \ne \pi _{\mathfrak {P}}(\emptyset )$, so $Dc_{\mathfrak {P}}(\emptyset )=\emptyset$. Let us also observe that when $A=\{v_1\}$ or $A=\{v_n\}$ there are no two vertices having equal distance from A, so $\pi _{\mathfrak {P}}(\{v_1\})=\pi _{\mathfrak {P}}(\{v_n\})=v_1|\dots |v_n$, i.e. $\{v_1\} \leftrightarrows _{\mathfrak {P}} \{v_n\} \leftrightarrows _{\mathfrak {P}} V(P_n)$. Contrariwise, if $A=v_i$, for some $i=2,\dots ,n-1$, just observe that $v_{i-1} \equiv _A v_{i+1}$ but, if $B:=\{v_j\}$, where $j \in \{2,\dots ,n-1\} {\setminus } \{i\}$, then $d(v_{i-1},v_j) \ne d(v_{i+1},v_j)$, therefore $v_{i-1} \not \equiv _B v_{i+1}$. This proves that $\pi _{\mathfrak {P}}(\{v_i\}) \ne \pi _{\mathfrak {P}}(\{v_j\})$ for any $i,j=2,\dots ,n-1$ and, also, that $v_1|\dots |v_n \prec \pi _{\mathfrak {P}}(v_i)$. Finally, let us show that for any 2-subset A, we have $A \leftrightarrows _{\mathfrak {P}} V(P_n)$. It suffices to show the claim for a 2-subset $A \in \mathcal {P}(V(P_n))$ such that $A \cap \{v_1,v_n\}=\emptyset$. To this regard, let $A=\{v_i,v_j\}$ and $v_k \equiv _A v_{k'}$. Then $d(v_i,v_k)=d(v_i,v_{k'})=l$ and $d(v_j,v_k)=d(v_j,v_{k'})=s$. Thus $\{v_k,v_{k'}\}=N^l_{P_n}(v_i) \cap N^s_{P_n}(v_j)$, where $N^q_{P_n}(v):=\{v' \in V(P_n): \, d(v,v')=q\}$. The only occurring case is that $v_{i-l}=v_{j-s}$ and $v_{i+l}=v_{j+s}$, from which $i=j$, that is impossible. This means that $\pi _{\mathfrak {P}}(A)=v_1|\dots |v_n$, so $Dc_{\mathfrak {P}}(v_i)=\{v_i\}$ when $i=2,\dots ,n-1$ and, moreover, $Dc_{\mathfrak {P}}(A)=V(G)$ in the other cases.

(ii): The claim on $BAS(\mathfrak {P}[P_n,d])$ and on $\rho (\mathfrak {P}[P_n,d])$, follows immediately by part (i).

On the other hand, let G be a connected n-graph such that $\rho (\mathfrak {P}[G,d])=1$. This means that there exists $A \in MBAS(\mathfrak {P}[G,d])$ such that $|A|=1$. So, let $A=\{v\}$. In particular, $\pi _{\mathfrak {P}}(A)=\pi _{\mathfrak {P}}(V(G))=v_1|\dots |v_n$, thus the map $w \in V(G) \mapsto d(v,w) \in \{0,\dots ,n-1\}$ is bijective. The only graph having this property is exactly $P_n$ and v is one of its extreme points. $\square$

7.2 Adjacency pairing

Let G be a n-graph. We consider now the pairing $\mathfrak {P}[G]:=(V(G),F,\{0,1\}) \in PAIR(V(G))$, where $F: V(G) \times V(G) \rightarrow \{0,1\}$ is defined by

$$\begin{aligned} F(u,v):=\left\{ \begin{array}{ll} 1 &{} \mathrm{if} \,\, u \sim v\\ 0 &{} \mathrm{otherwise}\\ \end{array} \right. \end{aligned}$$

We call $\mathfrak {P}[G]$ the adjacency pairing of G and we usually write G instead of $\mathfrak {P}[G]$. Let $A \subseteq V(G)$ a vertex subset. It is easy to prove that the A-symmetry relation $\equiv _A$ can be translated as follows:

$$\begin{aligned} v \equiv _A v' : \Longleftrightarrow N_G(v) \cap A = N_G(v') \cap A \end{aligned}$$

(13)

We now prove some basic property of A-symmetry for graphs.

Proposition 7.4

Let $v,v'\in G$ and $A\subseteq V(G)$. Then:

• (i) $v\equiv _A v'$ if and only if for all $z \in A$ it results that $v \sim z$ if and only if $v'\sim z$.

• (ii) If $v\sim v'$ then or $\{v,v'\} \cap A = \emptyset$.

• (iii) If $v \equiv _A v'$ and $\{v,v'\} \cap A \ne \emptyset$, then $v \not \sim v'$.

Proof

Straightforward. $\square$

Definition 7.5

A n-graph $G=(V(G),E(G))$ is said complete multipartite if there exist s non-empty subsets $B_1,\dots ,B_s$ of V(G) such that

(i):

$|B_i|=r_i$;

(ii):

$B_i \cap B_j=\emptyset$ if $i \ne j$;

(iii):

$\bigcup \nolimits _{i=1}^s B_i=V(G)$;

(iv):

$E(G)=\{\{x,y\}: \, x \in B_i, \, y \in B_j, \, i \ne j\}$.

We denote a complete multipartite graph by $K_{r_1,\dots ,r_s}$ or $(B_1|\cdots |B_s)$.

In the next result, we are able to express $CLOS(K_{r_1,\cdots ,r_s})$ and to prove that complete multipartite graphs are attractive pairings.

Theorem 7.6

Let $G:=K_{r_1,\dots ,r_s}=(B_1|\dots |B_s)$, with $r_i \ge 2$ for any $i=1,\dots ,s$. Then:

(i):

$A \in CLOS(G)$ if and only if $A=V(G)$ or $A=\bigcup \nolimits _{q=1}^t B_{i_q}$, where $0 \le t \le s-2$;

(ii):

G is attractive.

Proof

(i): We need to compute the A-symmetry partition of $K_{r_1,\dots ,r_s}$. For, let $A \subseteq V(G)$, then we set

$$\begin{aligned} Q_G(A):=\{B_i: \, A \cap B_i \ne \emptyset \}. \end{aligned}$$

We denote by r the quantity $|Q_G(A)|$. We claim that

$$\begin{aligned} \pi _G(A)=B_{i_1}|\cdots |B_{i_r}|Q_G(A)^c \end{aligned}$$

(14)

For, just observe that two vertices $u,u'$ belonging to the same subset $B_i$ are not adjacent to the vertices of the same subset but they are adjacent to the other vertices. In particular, we deduce that $u \equiv _A u'$ if and only if $u,u' \in B_i$ for some $i=1,\dots ,s$ or $u,u' \in Q_G(A)^c$. Therefore, we have $\pi _G(A)=B_{i_1}|\dots |B_{i_r}|Q_G(A)^c$ and this proves (14). Let us also observe that if $r=n-1$, then $\pi _G(A)=B_1|\dots |B_s=\pi _G(V(G))$. It is now straightforward to deduce that $A \in CLOS(G)$ if and only if $A=V(G)$ or $A=\bigcup \nolimits _{q=1}^t B_{i_q}$, where $0 \le t \le s-2$.

(ii): Let $A \in \mathcal {P}(V(G))$ and $b,c \in V(G)$ such that $\{b,c\} \nleftarrow _\forall A$ and $\{c\} \leftarrow A \cup \{b\}$ (the case $\{b\} \leftarrow A \cup \{c\}$ is similar). This means that $b,c \in Q_G(A)^c$ and, in particular, that they belong to the same subset $B_l \in Q_G(A)^c$. Thus

$$\begin{aligned} Dc_G(A \cup \{b\})=Q_G(A) \cup B_l=Dc_G(A \cup \{c\}), \end{aligned}$$

so $b \in Dc_G(A \cup \{c\})$, as claimed. $\square$

In the next result, we give the A-symmetry partition for the complete graph $K_n$, provide an explicit expression for $CLOS(K_n)$ and finally prove that $K_n$ is attractive.

Proposition 7.7

Let $n\ge 2$ and let $A=\{w_1,\dots ,w_k\}$ be a generic subset of $V(K_n)=\{v_1,\dots , v_n\}$. Then we have that:

(i):

$\pi _{K_n}(A)=w_1|w_2|\dots |w_k|A^c$;

(ii):

$CLOS(K_n)=\{ K\subseteq V(K_n): |K|\le n-2\}\cup \{V(K_n)\}$;

(iii):

$K_n$ is attractive.

Proof

(i): Let $v,\,v'\in V(K_n)$, with $v\ne v'$. In view of (iii) of Proposition 7.4, as $v \sim v'$, we deduce that the condition $v \equiv _A v'$ implies $v,\,v' \in A^c$. On the other hand, if $v,\, v' \in A^c$, then $\forall z \in A$, $F(z,v)=F(z,v')=1$, namely $v \equiv _A v'$.

(ii): Let $\mathcal {H}:=\{ B\subseteq V(K_n): |B|\le n-2\}\cup \{V(K_n)\}$ and $B \in \mathcal {H}$. We must prove that $B=Dc_{K_n}(B)$. By definition of $Dc_{K_n}(B)$ we have that $B \subseteq Dc_{K_n}(B)$, therefore it remains to show that $Dc_{K_n}(B) \subseteq B$.

If $B = V(K_n)$, then obviously $B = Dc_{K_n}(B)$. We can assume therefore $B \ne V(K_n)$. Let now $v \in V(K_n){\setminus } B$. Since $|B| \le n-2$, there exists a vertex let $z \in V(K_n){\setminus } B$ such that $v \ne z$. Since $0 = F(v,v) \ne F(v,z) = 1$ and $v \equiv _B z$, by (2) we have that $v \notin Dc_{K_n}(B)$. It follows that $V(K_n){\setminus } B \subseteq V(K_n){\setminus } Dc_{K_n}(B)$, and thus $Dc_{K_n}(B) \subseteq B$. Hence if $B\in \mathcal {H}$ then $B=Dc_{K_n}(B)$.

We assume now that $B\subseteq V(K_n)$ and $B=Dc_{K_n}(B)$. We must prove that $B=V(K_n)$ or $|B|\le n-2$. Let $B \ne V(K_n)$ and suppose by absurd that $|B|=n-1$. Then $B^c$ is a singleton and therefore we have that $\pi _{K_n}(B)=v_1|\cdots |v_n=\pi _{K_n}(V(K_n))$, in view of part (i). Thus $B\leftrightarrows _{K_n} V(K_n)$, and this implies $B=Dc_{K_n}(B)=V(K_n)$ by virtue of (ii) of Proposition 3.6, which gives a contradiction because $B\ne V(K_n)$. This shows that $|B|\le n-2$, i.e. $B\in \mathcal {H}$.

(iii): Let $A \in \mathcal {P}(V(K_n))$ and $b,c \in V(K_n)$ such that $\{b,c\} \nleftarrow _\forall A$ and $\{c\} \leftarrow A \cup \{b\}$ (the case $\{b\} \leftarrow A \cup \{c\}$ is similar). Then, in view of part (ii), it must necessarily be $|A| \le n-2$, so $Dc_{K_n}(A)=A$. We distinguish two cases: if $|A| < n-2$, then again by part (ii), we have $Dc_{K_n}(A \cup \{b\})=A \cup \{b\}$, so $b=c$ and the claim is true; on the contrary, if $|A|=n-2$, then $|A \cup \{b\}|=|A \cup \{c\}|=n-1$ and $Dc_{K_n}(A \cup \{b\})=Dc_{K_n}(A \cup \{c\})=V(K_n)$, so by (ii) of Proposition 3.6, $A \cup \{b\} \leftrightarrows _{\mathfrak {P}} A \cup \{c\}$ and the claim has been proved. $\square$