=Paper=
{{Paper
|id=None
|storemode=property
|title=The Lattice of all Betweenness Relations: Structure and Properties
|pdfUrl=https://ceur-ws.org/Vol-972/paper27.pdf
|volume=Vol-972
|dblpUrl=https://dblp.org/rec/conf/cla/BeaudouKN12
}}
==The Lattice of all Betweenness Relations: Structure and Properties==
https://ceur-ws.org/Vol-972/paper27.pdf
The latti e of all betweenness relations :
Stru ture and properties
Laurent Beaudou, Mamadou Moustapha Kanté, and Lhouari Nourine
Clermont Université, Université Blaise Pas al, LIMOS, CNRS, Fran e
laurent.beaudouuniv-bp lermont.fr, {mamadou.kante,nourine}isima.fr
Abstra t. We onsider impli ation bases with premises of size exa tly
2, whi h are also known as betweenness relations. Our motivations is
that several problems in graph theory an be modelled using betweenness
relations, e.g. hull number, maximal liques. In this paper we hara terize
the latti e of all betweenness relations by giving its poset of irredu ible
elements. Moreover, we show that this latti e is a meet-sublatti e of the
latti e of all losure systems.
1 Introdu tion
A onvexity spa e on a ground set X is a subset of 2X that is losed under
interse tion. Convexity spa es were studied in [13℄ and are sometimes alled
Closure systems. The members of a onvexity spa e are alled onvex sets. Sin e
the paper [13℄, onvexity spa es are studied by several authors who des ribe
several of their properties (see the joint paper [8℄ of Edelman and Jamison for a
list of publi ations during the eighties), in parti ular the set of onvexity spa es
forms a latti e.
In this paper we deal with betweenness relations whi h are spe ial ases of
onvexity spa es. The notion of betweenness relation has appeared in the early
twentieth entury when mathemati ians fo used on fundamental geometry [4℄.
A betweenness relation B on a nite set X is a set of triples (x, y, z) ∈ X 3 .
The most intuitive betweenness relations are those oming from metri spa es
(a point y is between x and z if they satisfy the triangular equality). A onvex
set of a betweenness relation B is a subset Y of X su h that for all (x, y, z) ∈ B ,
if {x, z} ⊆ Y , then y ∈ Y . It is well-known that the set of onvex sets of
a betweenness relation is a onvexity spa e. Betweenness relations have been
thoroughly studied by Menger and his students [16℄. Other betweenness relations
have arisen in resear h elds as probability theory with the work of Rei henba h
[18℄. Betweenness relations have been also studied in graphs in order to generalize
geometri al theorems [1,2,9℄ (see the survey [17℄ for a non exhaustive list of
betweenness relations on graphs).
We are interested in des ribing the set of all betweenness relations on a
ground set X . We prove that the set of all onvexity spa es on X derived from
betweenness relations on X forms a latti e and is in fa t a meet-sublatti e of the
latti e of all onvexity spa es on X (we give an example showing that it is not
c 2012 by the paper authors. CLA 2012, pp. 317–325. Copying permitted only for
private and academic purposes. Volume published and copyrighted by its editors.
Local Proceedings in ISBN 978–84–695–5252–0,
Universidad de Málaga (Dept. Matemática Aplicada), Spain.
318 Laurent Beaudou, Mamadou Moustapha Kanté and Lhouari Nourine
a sub-latti e). We also des ribe the set of meet and join-irredu ible elements of
the latti e. We on lude by showing that the set of onvexity spa es obtained
from lique betweenness relations on graphs is a sublatti e of the latti e of all
onvexity spa es of betweenness relations.
This paper is motivated by understanding links between several parameters
that are onsidered in dierent areas su h as FCA, database, logi and graph
theory.
Summary. Notations and de nitions are given in Se tion 2. The des ription of
the latti e of onvexity spa es of betweenness relations is given in Se tion 3. The
onvexity spa es of lique betweenness relations is des ribed in Se tion 4. Some
questions arising from algorithmi aspe ts are given in Se tion 5.
2 Preliminaries
Let X be nite set. A partially ordered set on X (or poset ) is a re exive, anti-
symmetri and transitive binary relation denoted by P := (X, ≤). For x, y ∈ X ,
we say that y overs x, denoted by x ≺ y , if for any z ∈ X with x ≤ z ≤ y we
have x = z or y = z . A latti e L := (X, ≤) is a partially ordered set with the
following properties:
1. for all x, y ∈ X there exists a unique z , denoted by x ∨ y , su h that for all
t ∈ X , t ≥ x and t ≥ y implies z ≤ t. (Upper bound property.)
2. for all x, y ∈ X there exists a unique z , denoted by x ∧ y , su h that for all
t ∈ X , t ≤ x and t ≤ y implies z ≥ t. (Lower bound property.)
Let L = (X, ≤) be a latti e. An element x ∈ X is alled join-irredu ible
(resp. meet-irredu ible ) if x = y ∨ z (resp. x = y ∧ z ) implies x = y or x = z .
A join-irredu ible (resp. meet-irredu ible) element overs (resp. is overed by)
exa tly one element. We denote by JL and ML the set of all join-irredu ible and
meet-irredu ible elements of L respe tively.
The poset of irredu ible elements of a latti e L = (X, ≤) is a representation
of L by a bipartite poset Bip(L) = (JL , ML , ≤). The on ept latti e of Bip(L)
is isomorphi to L (for more details see the books of Davey and Priestley [3℄,
and Ganter and Wille [10℄).
An impli ation on X is an ordered pair (A, B) of subsets of X , denoted by
A → B . The set A is alled the premise and the set B the on lusion of the
impli ation A → B . Let Σ be a set of impli ations on X . A subset Y ⊆ X is
Σ - losed if for ea h impli ation A → B in Σ , A ⊆ Y implies B ⊆ Y . The losure
of a set S by Σ , denoted by S Σ , is the smallest Σ - losed set ontaining S .
Let S be a subset of X . Algorithm 1 omputes the losure of S by a between-
ness relation Σ . It is known as forward haining pro edure or hase pro edure
[11℄.
The set of Σ - losed subsets of X , denoted by FΣ , is a losure system on X
(i.e losed under set-interse tion), and when ordered under in lusion is a latti e.
The lattice of all betweenness relations: Structure and properties 319
Algorithm 1: Set Closure(S, Σ )
Data S⊆X
: A set Σ and a betweenness
Result : The S
losure
Σ
begin Σ
Let S := S ;
while ∃xy → z ∈ Σ s.t. {x, y} ⊆ S and z ∈/ S do
Σ Σ
S Σ = S Σ ∪ {z};
end
Conversely, given a losure system F on X , a family Σ of impli ations on X
is alled an impli ational basis for F if F = FΣ . A subset K ∈ X is alled a key
if K Σ = X and K is minimal under in lusion with this property. The name key
omes from database theory [15℄.
De nition 1. An impli ation set Σ on X is alled a betweenness relation if for
all A → B ∈ Σ , |A| = 2.
Two betweenness relations Σ1 and Σ2 are said to be equivalent, denoted by
Σ1 ≡ Σ2 , if FΣ1 = FΣ2 . We de ne the losure of a betweenness relation Σ by
Σ c = {ab → c | a, b, c ∈ X and Σ ≡ Σ ∪ {ab → c}}. Note that Σ c is the
unique maximal betweenness relation equivalent to Σ . In ea h equivalen e lass
we distinguish two types of betweenness relations:
Canoni al A anoni al betweenness is the maximum in its equivalen e lass.
Optimal A betweenness Σ is optimal if for any betweenness relation Σ ′ equiv-
alent to Σ , we have |Σ| ≤ |Σ ′ |.
A graph G is a pair (V (G), E(G)), where V (G) is the set of verti es and
E(G) is the set of edges. We onsider simple graphs (for further de nitions see
the book [6℄). Examples of betweenness relations arising from graph theory are
ΣG = {xy → z | z lies in a shortest path from x to y} and ΣG = {xy → V (G) |
xy ∈ E(G)}. Several other notions of onvexity spa es are de ned on graphs (see
[17℄). Figure 1 gives an example of a graph and its onvex sets for the shortest
path betweenness.
3 The Latti e of all Betweenness Relations
Let X be a nite set and Σ a betweenness relation on X . Given two sets A and
C in 2X su h that A ⊆ C , we de ne the set interval [A, C] as the family of all
sets B in 2X su h that A ⊆ B ⊆ C .
Demetrovi s et al. [5℄ gave a hara terization of onvex sets of an impli ation
basis. Proposition 1 is restri ted to betweenness relations.
320 Laurent Beaudou, Mamadou Moustapha Kanté and Lhouari Nourine
{a,b,c,d}
{a,c} {a,d} {b,c} {b,d}
c
{a} {c} {d} {b}
a b
d {}
(a) A graph G (b) Convex sets of G for
shortest path betweenness
Fig. 1. A graph and its onvex sets for the shortest path betweenness relation
Proposition 1. [5℄ Let Σ be a betweenness relation on a set X . Then,
[
FΣ = 2X \ [{a, b}, X \ {c}].
ab→c∈Σ
We denote by FX := {FΣ | Σ is a betweenness relation on X} the family of
all betweenness relations on X .
Theorem 1. FX is a losure system and therefore a latti e when stru tured
under in lusion.
Proof. We have to prove that this stru ture is losed under the interse tion and
it ontains a unique maximal element.
Let F1 , F2 ∈ FX , then there exist Σ1 and Σ2 indu ing these families of onvex
sets on X . Let F = F1 ∩ F2 and Σ be the betweenness de ned by ab → c ∈ Σ if
ab → c ∈ Σ1 or ab → c ∈ Σ2 . Then we laim that F = FΣ .
Let C be a set in F . It is onvex for Σ1 and for Σ2 . Therefore, for any a, b in
C , every c su h that ab → c ∈ Σ1 or ab → c ∈ Σ2 is in C . From this, we derive
that for any a, b in C , every c su h that ab → c ∈ Σ is in C , so that C is onvex
for Σ .
Re ipro ally, let C be a onvex set for Σ . We will show that it is onvex for Σ1
and Σ2 . Let a, b, c be elements of X su h that a and b are in C and ab → c ∈ Σ1 .
Then ab → c ∈ Σ and sin e C is onvex for Σ , b is in C . Therefore, C is in F1 .
Similarly it is in F2 so that it is in F .
Sin e Σ = Σ1 ∪ Σ2 , we on lude that Σ is a betweenness relation and there-
fore the set FX is losed under interse tion.
The family 2X is in FX . It arises when Σ is the empty betweenness relation.
Proposition 2. Given two families F1 and F2 in FX and their anoni al be-
tweenness relations Σ1 and Σ2 . Then
The lattice of all betweenness relations: Structure and properties 321
F1 ∧ F2 = FΣ1 ∪Σ2 .
F1 ∨ F2 = FΣ1 ∩Σ2 .
Proof. See the proof of Theorem 1 for the rst point. Noww, note that Σ1 and
Σ2 are anoni al betweenness relations. Suppose that F1 ∨ F2 is not FΣ1 ∩Σ2 . By
Proposition 1, we have F1 ∨ F2 ⊆ FΣ1 ∩Σ2 .
Now all Σ∨ the anoni al betweenness relation related to F1 ∨ F2 . If ab →
c ∈ Σ∨ for some a, b and c in X , then we know that ab → c ∈ Σi be ause
Fi ⊆ F1 ∨ F2 for i = 1, 2 (in the anoni al form, we have every ab → c su h
that the orresponding interval has no interse tion with F ). Therefore, every
ab → c ∈ Σ∨ is true for Σ , and FΣ1 ∩Σ2 = F1 ∨ F2 .
Corollary 1. FX is a meet-sublatti e of the latti e of all losure systems on X .
Proof. Let F1 and F2 be two families in FX . Sin e F1 ∩ F2 is the losure system
of a betweenness relation then the meet is preserved and thus FX is a a meet-
sublatti e of the latti e of all losure systems on X .
Remark 1. Noti e that FX is not a sublatti e of the latti e of all losure systems
on X . It su es to onsider the example where X = {1, 2, 3, 4}. Take the o-
atoms F1 = 2X \ [{1, 2}, {1, 2, 3}] de ned by the betweenness relation restri ted
to 12 → 4 and F2 = 2X \ [{2, 3}, {1, 2, 3}] de ned by the betweenness relation
restri ted to 23 → 4. Then F1 ∪ F2 = 2X \ {{1, 2, 3}} and is a losure system,
while F1 ∨ F2 is the top element, 2X .
In the following, we give a hara terization of the poset of irredu ible elements
of FX .
Proposition 3. The poset of irredu ible elements of FX is the bipartite poset
Bip(FX ) = (JFX , MFX , ⊆) where
JFX := {F⊥ ∪ {S} | S ∈ 2X \ F⊥ } where F⊥ = {∅, X} ∪ {{x} | x ∈ X}
MFX := {2X \ [ab, X \ {c}] | a, b, c ∈ X}.
Proof. We prove this proposition point by point.
Consider the maximal S betweenness relation Σ = {ab → c | a, b, c ∈ X}.
Then F⊥ = FΣ = 2X \ ab→c∈Σ [{a, b}, X \ {c}] (see Proposition 1). Thus
F⊥ = {∅, X} ∪ {{x} | x ∈ X}.
For meet-irredu ible elements, we will rst onsider o-atoms. Let Σ be a
betweenness relation su h that FΣ is a o-atom. Sin e Σ is non-empty, then
there exists a set whi h is not onvex. Thus Σ must ontain an impli ation
ab → c, with a, b, c ∈ X , whi h orresponds to the maximal losure system in
FX and dierent from 2X . Namely, we remove from 2X the onvex sets of the
interval [{a, b}, X \ {c}].
Now suppose there exists another meet-irredu ible element F whi h is not a
o-atom. Call Σ1 a betweenness relation su h that F is FΣ1 . Also, all F ′ the
322 Laurent Beaudou, Mamadou Moustapha Kanté and Lhouari Nourine
only su essor of FΣ1 and Σ2 a betweenness su h that F ′ is FΣ2 . By Proposi-
tion 1, we know that from F ′ to F , we remove at least an interval of the form
[{a, b}, X \ {c}]. Thus, the o-atom asso iated to the impli ation ab → c is not
above F ′ but it is above F , so that F has at least two su essors. We on lude
that all meet-irredu ible elements are o-atoms of FX .
For join-irredu ible elements, we will rst hara terize atoms of FX . Pi k
any subset S of X whi h is not empty, a singleton or the whole of X . De ne
the betweenness relation ΣS su h that ab → c ∈ ΣS for every a, b, c in X ex ept
those where a and b are in S and c is not in S . Then FΣS is F⊥ ∪ {S}. Now
suppose there exists a join-irredu ible F ∈ FX that is not an atom. F ontains
at least one set S whi h is not in the unique losure system F ′ ∈ FX that
it overs. But there is an atom whi h ontains exa tly F ” = F⊥ ∪ {S}, with
F ” ⊆ F and F ” 6⊆ F ′ . Thus F overs at least two elements, and thus F is not a
join-irredu ible element.
FX n n−3 n
Corollary 2. ontains 2 (n − 2)2 meet-irredu ible and 2 − (n + 2)
join-irredu ible elements.
Proof. Every o-atom is of the form 2X \ [{a, b}, X \ {c}] and is above every atom
formed by F⊥ and any set not in the forbidden interval. This makes 2n − (n +
2) − 2n−3 atoms below it.
An atom of the form F⊥ ∪ S where S is a set on X of size 2 to n − 1, is below
every o-atom that does not forbid S . This number equals n2 (n − 2)2n−3 −
2 (n − |S|)].
[ |S|
Figure 2 shows the irredu ible poset for X = {1, 2, 3, 4} where every atom is
represented by the set S added to F⊥ and every o-atom is represented by the
removed impli ation xy → z .
12 → 3 12 → 4 13 → 2 13 → 4 14 → 2 14 → 3 23 → 1 23 → 4 24 → 1 24 → 3 34 → 1 34 → 2
{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4}
Fig. 2. Irredu ible poset for n = 4
The lattice of all betweenness relations: Structure and properties 323
4 Clique Betweenness Relations
In this se tion we deal with a spe ial betweenness relation de ned through a
graph in a spe i way. Many other betweenness relations on graphs an be
de ned in the same way, e.g. independent sets, set overs.
Given a graph G, we de ne the betweenness relation
ΣG := {ab → c | c ∈ X, ab ∈
/ E(G)}.
The onvex sets of ΣG are exa tly the liques of G. Noti e that for any graph
G, there is a orresponding betweenness relation ΣG . In the following, we har-
a terize the latti e of all ΣG where G is a graph with vertex-set X . We denote
by FKX = {FΣG | G is a graph on X}.
Proposition 4. (FK
X , ⊆) is a latti e.
Proof. The bottom (resp. top) element of FX orresponds to FΣG where G is a
stable (resp. lique) on X .
Moreover, FK X is losed under interse tion (the liques of the interse tion of
two graphs are exa tly the ones in the interse tion of both families of liques).
Therefore, (FKX , ⊆) is a latti e.
Sin e ΣG is a betweenness relation, then FK
X ⊂ FX for any graph G de ned
on X .
FK F
Proposition 5. The latti e ( X , ⊆) is a sublatti e of ( X , ⊆).
Proof. It is easy to see that it is a meet-sublatti e, the meet of two families is
the interse tion of both families in both stru tures.
In order to prove that it is a join-sublatti e of (FX , ⊆), onsider two graphs
G1 and G2 and their lique families F1 and F2 . Call G the graph union of G1 and
G2 and F the family of its liques. The related betweenness relation is obtained
by taking the interse tion of betweenness relations related to G1 and G2 (non-
edges in G are exa tly non-edges in G1 and in G2 ). Therefore it is the join of F1
and F2 in (FX , ⊆).
FK n
Corollary 3. The latti e ( X , ⊂) is a boolean latti e with atoms.
2
Proof. For ea h graph G, its orresponding anoni al betweenness relation is the
set ΣG
c
:= {ab → X | ab ∈ / E(G)}. Note that any super-set of ΣG c
orresponds to
a betweenness relation of a partial graph of G, by deleting edges ab from G whi h
orresponds to adding ab → X in ΣG c
. Sin e any atom of (FKX , ⊂) orresponds to
a betweenness relation whi h ontains exa tly an impli ation ab → X , we have
exa tly n2 atoms.
324 Laurent Beaudou, Mamadou Moustapha Kanté and Lhouari Nourine
5 Algorithmi Aspe ts of Betweenness Relations
In this se tion, we re all some optimization problems related to betweenness
relations.
Minimum Key (MK)
Input: Σ a betweenness relation on X and k an integer.
Question: Is there a set K ⊆ X su h that |K| ≤ k and K Σ = X ?
These problems have been studied in the several domains and spe ially in
database theory, and they have been proved NP- omplete [5,14,15℄ for general
impli ation bases. The problem MK has been proved NP- omplete for parti ular
ases of betweenness relations (see for instan e [7℄ for the shortest path between-
ness relation on graphs). It is known as the hull number of a betweenness relation.
Therefore, we have the following.
Proposition 6. MK is NP- omplete.
Re ently, Kanté and Nourine [12℄ have shown that M K is polynomial for
shortest path betweenness relations of hordal and distan e hereditary graphs
by using database te hniques. Can we use the latti e stru ture of FX to get new
polynomial time algorithms for the MK problem in new graph lasses?
Now we onsider the problem whi h omputes an optimal over of a between-
ness relation. This problem is to nd an optimal betweenness relation whi h is
equivalent to a given betweenness relation. Several works have been done in the
general ase known as Horn minimization [11℄.
Optimal Cover (OC)
Input: Σ a betweenness relation on X and k an integer.
Question: Is there a betweenness relation Σ ′ equivalent to Σ su h that |Σ ′ | ≤ k ?
The size of an optimal over is known as the hydra number [19℄. The ompu-
tational omplexity of the hydra number is open for betweenness relations, but
is NP- omplete for the general ase [11,15℄. We hope that the latti e stru ture
of FX ould help to address this question.
6 Con lusion
In this paper, we hara terize the ontext of the latti e of all betweenness re-
lations on a nite set, whi h is a meet-sublatti e of the latti e of all losure
systems on the same set. We are onvin ed that the stru ture of latti e an help
to understand some problems of graph theory su h as hull number and hydra
number. In the future we will investigate the link of these parameters and the
stru ture of the latti e.
The lattice of all betweenness relations: Structure and properties 325
Referen es
1. Xiaomin Chen and Va²ek Chvátal. Problems related to a de Bruijn-Erd®s theorem.
Dis rete Applied Mathemati s, 156(11):21012108, 2008.
2. Va²ek Chvátal. Antimatroids, betweenness, onvexity. In Cook, W.J., Lováz, L.,
Vygen, J. (eds.) Resear h Trends in Combinatorial Optimization, pages 5764,
2019.
3. B. A. Davey and A. Priestley. Introdu tion to Latti es and Order. Cambridge
University Press, 2002.
4. G. de Beauregard Robinson. The foundations of geometry. Mathemati al exposi-
tions. University of Toronto Press, 1952.
5. János Demetrovi s, Leonid Libkin, and Ilya B. Mu hnik. Fun tional dependen ies
in relational databases: A latti e point of view. Dis rete Applied Mathemati s,
40(2):155185, 1992.
6. Reinhardt Diestel. Graph Theory. Springer-Verlag, 3rd edition, 2005.
7. Mitre Costa Dourado, John G. Gimbel, Jan Krato hvíl, Fábio Protti, and
Jayme Luiz Szwar ter. On the omputation of the hull number of a graph. Dis-
rete Mathemati s, 309(18):56685674, 2009.
8. P.H. Edelman and R.E. Jamison. The theory of onvex geometries. In R. Rustin,
editor, Geometriae Dedi ata, vol 19, Ni3, pages 247270. springer, 1985.
9. Martin Farber and Robert E. Jamison. Convexity in graphs and hypergraphs.
SIAM Journal on Algebrai and Dis rete Methods, 7:433444, 1986.
10. B. Ganter and R. Wille. Formal on ept analysis: Mathemati al foundations.
Springer (Berlin and New York), 1999.
11. Peter L. Hammer and Alexander Kogan. Optimal ompression of propositional
horn knowledge bases: Complexity and approximation. Artif. Intell., 64(1):131
145, 1993.
12. M.M. Kanté and L. Nourine. Polynomial time algorithms for omputing a minimum
hull set in distan e-hereditary and hordal graphs. Submitted, 2012.
13. D.C. Kay and E.W. Womble. Axiomati onvexity theory and relationships be-
tween the Carathéodory, Helly, and Radon numbers. Pa i Journal of Mathe-
mati s, 38:471485, 1971.
14. Claudio L. Lu hesi and Sylvia L. Osborn. Candidate keys for relations. Journal
of Computer and System S ien es, 17(2):270 279, 1978.
15. David Maier. Minimum overs in relational database model. J. ACM, 27(4):664
674, 1980.
16. Karl Menger. Untersu hungen über allgemeine metrik. Mathematis he Annalen,
100:75163, 1928. 10.1007/BF01448840.
17. Igna io M. Pelayo. On onvexity in graphs. Te hni-
al report, Universitat Politè ni a de Catalunya, http://www-
ma3.up .es/users/pelayo/resear h/De nitions.pdf, 2004.
18. H. Rei henba h and M. Rei henba h. The Dire tion of Time. California Library
Reprint Series. University of California Press, 1956.
19. Despina Stasi, Robert H. Sloan, and György Turán. Hydra formulas and dire ted
hypergraphs: A preliminary report. In ISAIM, 2012.