Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 27–33
Characterizing posets for which their natural
transit functions coincide∗
Boštjan Brešar
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
Manoj Changat
Department of Futures Studies, University of Kerala, Trivandrum-695 034, India
Sandi Klavžar
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
and
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
Joseph Mathews
Chingamparampil, Vazhapally, Changanacherry, 686 103 Kerala, India
Antony Mathews
Department of Futures Studies, University of Kerala, Trivandrum-695 034, India
Prasanth G. Narasimha-Shenoi
Department of Mathematics, Government College, Chittur, Palakkad-678 104, India
Received 11 July 2008, accepted 19 December 2008, published online 4 March 2009
Abstract
The standard poset transit function of a poset P is a function TP that assigns to a pair of
comparable elements the interval between them, while TP (x, y) = {x, y} for a pair x, y of
incomparable elements. Posets in which the standard poset transit function coincides with
the shortest-path transit function of their cover-incomparability graph are characterized in
three ways, in particular with forbidden subposets.
Keywords: Transit function, ranked poset, underlying graph, geodesic interval, induced-path interval.
Math. Subj. Class.: 05C12, 05C62, 06A07
∗Work supported by the Ministry of Science of Slovenia and by the Ministry of Science and Technology of
India under the bilateral India-Slovenia grants BI-IN/06-07-002 and DST/INT/SLOV-P-03/05, respectively.
E-mail addresses: bostjan.bresar@uni-mb.si (Boštjan Brešar), mchangat@gmail.com (Manoj Changat),
sandi.klavzar@fmf.uni-lj.si (Sandi Klavžar), jose chingam@yahoo.co.in (Joseph Mathews),
sonykandans@yahoo.co.in (Antony Mathews), gnprasanth@gmail.com (Prasanth G. Narasimha-Shenoi)
Copyright c© 2009 DMFA
28 Ars Math. Contemp. 2 (2009) 27–33
1 Introduction
The notion of convexity has been extended from Euclidean spaces to several different math-
ematical structures. In the last several decades an abstract theory of convex structures was
developed. It is based on just two (or three in the infinite case) natural conditions, imposed
to a family of subsets of a given set. The theory is comprehensively surveyed in van de
Vel’s book [13], where the so-called interval convexity turns out as one of its universal
concepts.
As shown by Calder in [3], the pertinent properties of a mapping I : X×X → 2X that
yields a convexity on a set X are the symmetry law (I(x, y) = I(y, x) for all x, y ∈ X)
and the extensive law (x, y ∈ I(x, y)). These two laws constitute all axioms for the formal
interval convexity with I as the interval operator [13]. By adding also the idempotent law
(I(x, x) = {x} for all x ∈ X), one gets the concept of a transit function as defined by
Mulder [10]. His purpose was to generalize geodesic (and some other) intervals in graphs
and other discrete structures, including posets. Furthermore, for a set X on which a transit
function T is defined, the underlying graph GT was introduced as the graph with X as its
vertex set, where distinct u and v in X are adjacent whenever |T (u, v)| = 2.
In a poset P = (X,≤) by the notion of interval [x, y] one usually assumes that x
and y are two comparable elements, and [x, y] = {z : x ≤ z ≤ y}. This function can
be extended to all pairs of elements in a poset, by setting TP (x, y) = {x, y} if x and y
are incomparable, and TP (x, y) = [x, y] otherwise [7, 10, 13]. This yields an interval
convexity in the general sense as described above. Clearly TP is also a transit function on
P and is called the standard poset transit function.
The underlying graph GTP of the standard poset transit function TP was studied in [1]
under the name cover-incomparability graph of a poset P . (For other connections between
posets and graphs we refer to [12].) In GTP the most common transit function is given
by the geodesic intervals (formed by vertices on shortest paths between pairs in V (GTP )),
which is denoted IGP . The natural question appears, in which posets both transit functions
(interval convexities) TP and IGP coincide. In this note we characterize such posets in
two ways, once by listing forbidden subposets, and in the other case as certain maximal
ranked posets. Interestingly, in such posets also the induced-path transit function JGP in
the underlying graph coincides with the standard poset transit function of P , which is, in
fact, characteristic for these posets.
In the next section we fix terminology and state some simple observations. In Section 3
we prove the main theorem. In the conclusion we show how the theorem can be extended
from finite to chain-finite, countable posets.
2 Preliminaries
A transit function on a non-empty set V is a function T : V × V → 2V satisfying the
following axioms:
(t1) u ∈ T (u, v) for any u and v ∈ V .
(t2) T (u, v) = T (v, u) for all u and v ∈ V .
(t3) T (u, u) = {u} for all u ∈ V .
Prominent examples of transit functions on a connected graph G = (V,E) are the
geodesic transit function (studied extensively in [9]):
IG(u, v) = {w ∈ V | w lies on a shortest u, v-path in G} ,
B. Brešar et al.: Characterizing posets for which their natural transit functions coincide 29
the induced-path transit function [5, 8]:
JG(u, v) = {w ∈ V | w lies on an induced u, v-path in G} ,
and the all-paths transit function A, which is the coarsest path transit function on G [4, 6]:
AG(u, v) = {w ∈ V | w lies on some u, v-path in G} .
Recall [2, 11] that a ranked poset is a poset P = (V,≤) that is equipped with a rank
function ρ : V → Z satisfying:
• ρ is constant on all minimal elements of P (usually with value −1 or 0), and
• ρ preserves covering relations: if b covers a then ρ(b) = ρ(a) + 1.
A ranked poset P is said to be complete if for every i, every element of rank i covers
all the elements of rank i− 1.
Let P = (V,≤) be a poset. Then the poset Q = (V ′,≤′) is a subposet of P if V ′ ⊆ V
and if for any elements u and v of V ′, u ≤′ v if and only if u ≤ v.
Recall that the height of a poset P is the maximum size of a chain in P , and a poset is
called bipartite if its height is at most 2 [2].
Let P = (V,≤) be a poset, then the graphGP = (V,E) is called the cover-incompara-
bility graph of P if ab ∈ E whenever a covers b, or b covers a, or a and b are incomparable.
In other words, the edge set of GP is the union of the edge set of the cover graph of P and
the incomparability graph of P . Note that the cover-incomparability graph GP of a poset
P is just the underlying graph of the standard poset transit function. Hence GTP would be
an appropriate notation for the cover-incomparability graph (as stated in the introduction)
which we will shorten to GP in the sequel. We denote by IGP the geodesic transit function
in the cover-incomparability graph GP , and JGP the induced-path transit function in GP .
It can be easily verified that for any poset P , the graph GP is connected [1]. Let u, v be
a pair of incomparable elements of a poset P . If P has more than two elements, then it is
clear that there exists another element z in P which either covers or is incomparable with
one of u or v or both u and v. In all cases AGP (u, v) (where AGP stands for the all-paths
transit function in GP ) contains z, but TP (u, v) consists only of u and v alone. Therefore,
we have the following observation:
Remark 2.1. Let P = (V,≤) be a poset on at least three elements. Then TP = AGP if
and only if P is a chain.
3 The theorem
In this section we characterize the posets P = (V,≤) in which TP = IGP . First, if P
is bipartite (that is, the size of a longest chain is at most 2), then GP is a complete graph
which readily implies:
Remark 3.1. Let P = (V,≤) be a bipartite poset. Then TP = IGP = JGP .
In the following theorem we consider the non-trivial case, when the height of a poset is
greater than 2.
Theorem 3.2. Let P = (V,≤) be a poset of height at least 3. Then the following statements
are equivalent:
30 Ars Math. Contemp. 2 (2009) 27–33
(i) TP = IGP ;
(ii) TP = JGP ;
(iii) P has no subposet isomorphic to P1, P2, or P3, see Figure 1;
(iv) P is a complete ranked poset.
Figure 1: Forbidden subposets.
In the rest of this section we prove Theorem 3.2 and begin with the following implica-
tion.
(i)⇒ (iii). Let u, v, w, x be the elements of P that form a subposet isomorphic to P1, see
Figure 1. Let x = x0, x1, . . . , xk = w be a maximal x,w-chain in P . Note that k ≥ 1,
and that if k = 1 then w = x1. Note also that none of the elements xi, i < k, is below v
because otherwise x would be below v.
Let i, 1 ≤ i ≤ k, be the smallest index such that v ≤ xi. Such an index exists since
v ≤ w = xk. Then v and xi−1 are incomparable. Let v = v0, v1, . . . , vj = xi be a
maximal v, xi-chain in P . Note that j ≥ 1.
Suppose j ≥ 2. Then consider vj−2, vj−1, vj , xi−1. We claim that vj−2 is incom-
parable with xi−1. Indeed, if xi−1 ≤ vj−2 held, then xi would not be covering xi−1.
And if vj−2 ≤ xi−1 we would have v ≤ xi−1, which is not possible by the selection
of i. Analogous argument implies that vj−1 is incomparable with xi−1. Now observe that
dGP (vj−2, xi) = 2 hence xi−1 ∈ IGP (vj−2, xi). On the other hand, xi−1 /∈ TP (vj−2, xi),
a contradiction.
Suppose j = 1, that is, xi covers v. If i ≥ 2 then v ∈ IGP (xi−2, xi) but v /∈
TP (vi−2, xi). Let i = 1. Then x1 covers x. Let y be a vertex on a u, v-chain that is
covered by v. Then y ≤ x would imply u ≤ x. Moreover, x ≤ y would mean that x is
not covered by x1. It follows that y and x are incomparable and hence x ∈ IGP (y, x1) but
x /∈ TP (y, x1).
Thus we have proved that if P has a subposet P1 then TP 6= IGP . Analogous argument
also yields that a subposet P2 implies that TP 6= IGP .
Assume finally that u, v, w, x are the elements of P that form a subposet isomorphic
to P3, see Figure 1. Let u = u0, u1, . . . , uk = w be a u,w-chain that contains v. Then
k ≥ 2 and moreover, none of the elements ui is comparable to x. Then x ∈ IGP (u, u2) but
x /∈ TP (u, u2).
(ii)⇒ (iii). This implication follows by the same arguments as the implication (i)⇒ (iii)
because a path of length 2 is a shortest path if and only if it is induced.
(iii)⇒ (iv). Assume that P has no subposet isomorphic to P1, P2, or P3. Let C = u0 ≤
u1 ≤ · · · ≤ un be a longest chain in (P,≤). Then n ≥ 2.
B. Brešar et al.: Characterizing posets for which their natural transit functions coincide 31
Define S0 as the set consisting of the minimal elements of P. Further define Si, 1 ≤ i ≤
n, as the subset of V containing ui and the elements of P which are incomparable with ui
and that cover ui−1.
Claim 1. u0 ∈ S0.
This is clear because otherwise C would not be a longest chain.
Claim 2. Elements of Si, 0 ≤ i ≤ n, are pairwise incomparable.
This is clear for i = 0. Consider different elements vi andwi of Si, i ≥ 1. By the definition
of Si, both vi and wi cover ui−1. But then vi and wi are incomparable.
Claim 3. For i ≥ 1 any element of Si covers every element of Si−1.
Assume first i ≥ 2 and consider elements vi ∈ Si and wi−1 ∈ Si−1. Since vi ∈ Si,
it covers ui−1. By Claim 2, ui−1 and wi−1 are incomparable and hence wi−1 cannot be
below ui−2. If vi and wi−1 are incomparable, then vi, ui−1, ui−2, wi−1 form an induced
P2. Hence vi and wi−1 are comparable. Using Claim 2 again, wi−1 cannot be above vi
hence there must be a chain wi−1 < x ≤ · · · ≤ vi.
Suppose x 6= vi. Then x and ui−1 are incomparable. Indeed, ui−1 ≤ x would yield
ui−1 ≤ x ≤ vi, a contradiction with the fact that vi covers ui−1. On the other hand,
x ≤ ui−1 would give us that wi−1 ≤ x ≤ ui−1 contradicting Claim 2. So x and ui−1 are
incomparable, but then vi, x, wi−1, ui−1 induce P1. We conclude that x = vi and hence vi
covers wi−1. Note that the same argument also applies if vi = ui.
It remains to prove Claim 3 for i = 1. Let v1 ∈ S1 and w0 ∈ S0 be arbitrary elements.
Then v1 covers u0. By the above paragraph, u2 covers v1. If w0 and v1 are incomparable,
then u0, v1, u2, w0 induce P3 or P1. Since w0 is a minimal element, we can thus only have
w0 ≤ v1. Let x be the first element on a maximal w0, v1-chain. Then we can argue as
above that x = v1.
Claim 4.
⋃n
i=0 Si = V .
Let v be an arbitrary element of P . Consider a maximal chain v0 ≤ v1 ≤ · · · ≤ vm in
P that contains v. Clearly, m ≤ n. Hence v = vi for some 0 ≤ i ≤ m. We claim that
v ∈ Si and prove it by induction. The element v0 is minimal, hence v0 ∈ S0. Assume
now that vi−1 ∈ Si−1. Hence by Claim 3, ui covers vi−1. As vi also covers vi−1, it
follows that ui and vi are incomparable. If ui−1 and vi are incomparable then consider ui,
ui−1, ui−2, vi (or, if i = 1, consider ui−1, ui, ui+1, vi) to obtain P2 or P3 (or, P1 or P3).
So ui−1 and vi are comparable and it is only possible that ui−1 ≤ vi. Consider a chain
ui−1 ≤ x ≤ vi. Then x and vi−1 are incomparable. But then ui−1, x, vi, vi−1 induce P1.
Hence x = vi = v. Therefore v covers ui−1 and since in addition vi is incomparable to ui
we conclude that v = vi ∈ Si.
Claim 5. For 0 ≤ j ≤ i− 2 ≤ n− 2, no element of Si covers an element of Sj .
Let vi ∈ Si, wj ∈ Sj , j ≤ i − 2. Suppose vi covers wj . Let vj ≤ vj+1 ≤ · · · ≤ vi,
where vk ∈ Sk, be a vj , vi-chain. Then wj is incomparable with vj , . . . , vi−1. Hence
vi−2, vi−1, vi, wj induce a P1, a contradiction that proves Claim 5.
For v ∈ V , define ρ : V → Z by ρ(v) = i where v ∈ Si. Then ρ is a rank function on
P . Moreover, Claim 3 implies that this ranked poset is complete.
To complete the proof note that implications (iv) ⇒ (i) and (iv) ⇒ (ii) are straight-
forward.
32 Ars Math. Contemp. 2 (2009) 27–33
4 Extension to infinite posets
Let P = (V,≤) be an arbitrary poset. Then P is called chain-finite if every chain between
any comparable elements u and v is finite. We claim that Theorem 3.2 extends to countable,
chain-finite posets with the following modifications.
By a complete ranked poset we now mean a poset whose elements can be partitioned
into sets Si, i ∈ Z, such that every element of Si covers every element of Si−1 for all i and
that Sk 6= ∅ as soon as there are indices i and j such that i < k < j and Si 6= ∅, Sj 6= ∅.
Let P = (V,≤) be a countable, chain-finite poset. Then note that GP is a connected
(infinite) graph and hence IGP and JGP are well-defined.
With these additions Theorem 3.2 holds for such posets. The proof for (i)⇒ (iii) and
(ii)⇒ (iii), (iv)⇒ (i) and (iv)⇒ (ii) goes along the same lines as in the finite case. To
prove (iii)⇒ (iv) we can define the sets Si in a similar way. Notably, let C be an arbitrary
maximal chain of P and let its elements be . . . , u−2, u−1, u0, u1, u2, . . . (or u0, u1, u2, . . .
if P has minimal elements, and . . . , u−2, u−1, u0 if P has maximal elements). Then define
Si, i ∈ Z, as the subset of V containing ui and the elements of P which are incomparable
with ui and cover ui−1.
Now in the proof of (iii)⇒ (iv) most of the claims go through regardless of finiteness
of P . More precisely, Claim 1 is the same, or even not needed if P has no minimal and no
maximal elements (if P has only maximal elements then an analogous trivial claim has to
be used). Claims 2 and 5 have the same proofs as above, while Claim 3 is even easier in the
case when P has no minimal elements, since the last paragraph of its proof is not needed.
Hence, we only need to prove Claim 4 which is the only non-trivial part of the extension to
infinite posets.
Let x be an arbitrary element of a countable, chain-finite poset P . We need to show that
there exists an i such that x ∈ Si (from this one finds that
⋃
i Si = V ). The first step is to
show that x is incomparable with exactly one element from . . . , u−2, u−1, u0, u1, u2, . . ..
Suppose that x is incomparable with ui and uj , and let i < j. Then ui, uj , uj+1 and x
form a subposet isomorphic to P1 or P3, a contradiction. Next, suppose x is comparable
with all elements of the maximal chain C. We claim that then the set S = {ui ∈ C : ui ≤
x} is nonempty and bounded from above. Suppose this is not the case. Then assuming that
S is empty (resp. S not bounded from above) we quickly derive that for all ui ∈ C we
have x ≤ ui (resp. ui ≤ x), which is a contradiction with C being a maximal chain. Thus,
let uj be the largest element in C such that uj ≤ x, and note that uj cannot be a maximal
element in P because C is a maximal chain. Thus x ≤ uj+1 which again contradicts the
fact that C is maximal since x can be inserted between uj and uj+1, extending the chain
C. Hence x cannot be comparable to all elements of C either.
Thus x is incomparable with exactly one element of C, say ui. If ui is a minimal
element then i = 0 and x ∈ S0. Hence, let ui not be minimal, and we need to show that x
covers ui−1 (this will imply that x ∈ Si).
It is clear that ui−1 ≤ x ≤ ui+1. Let v be the first element on a chain from ui−1 to
x, and assume that v 6= x. Suppose that v is incomparable with ui. Then, since x is also
incomparable with ui we infer that ui−1, ui, v and x form a subposet, isomorphic to P2.
Since this is forbidden, the only possibility is that v and ui are comparable. If ui ≤ v, then
by transitivity ui ≤ x, but ui and v are incomparable. Also v ≤ ui is not possible, since
then one could extend the chain C between ui−1 and ui with v and the chain between v
and ui. Since C is a maximal chain this is a contradiction, hence v = x. Thus x covers
ui−1 and so x ∈ Si. Theorem 3.2 indeed extends to countable chain-finite posets.
B. Brešar et al.: Characterizing posets for which their natural transit functions coincide 33
References
[1] B. Brešar, M. Changat, S. Klavžar, M. Kovše, J. Mathews and A. Mathews, Cover-incompara-
bility graphs of posets, Order 25 (2008), 335–347.
[2] G. Brightwell and D. B. West, Partially ordered sets, in: K.H. Rosen (ed.), Handbook of Dis-
crete and Combinatorial Mathematics, CRC Press, Boca Raton, 2000, 717–752.
[3] J. R. Calder, Some elementary properties of interval convexities, J. London Math. Soc. 3 (1971),
422–428.
[4] M. Changat, S. Klavžar and H. M. Mulder, The all path transit function of a graph, Czech.
Math. J. 51 (2001), 439–448.
[5] M. Changat and J. Mathews, Induced path transit function, monotone and Peano axioms, Dis-
crete Math. 286 (2004), 185–194.
[6] M. Changat, H. M. Mulder and G. Sierksma, Convexities related to path properties on graphs,
Discrete Math. 290 (2005), 117–131.
[7] A. Mathews and J. Mathews, Transit functions on posets and lattices, in: M. Changat,
S. Klavžar, H. M. Mulder and A. Vijayakumar (eds.), Convexity in Discrete Structures, Lecture
Notes Ser. 5, Ramanujan Math. Soc., 2008, 105–116.
[8] M. A. Morgana and H. M. Mulder, The induced path convexity, betweenness and svelte graphs,
Discrete Math. 254 (2002), 349–370.
[9] H. M. Mulder, The Interval Function of a Graph, Mathematisch Centrum, Amsterdam, 1980.
[10] H. M. Mulder, Transit functions on graphs (and posets), in: M. Changat, S. Klavžar, H. M. Mul-
der, A. Vijayakumar (eds.), Convexity in Discrete Structures, Lecture Notes Ser. 5, Ramanujan
Math. Soc., 2008, 117–130.
[11] D. Stanton, D. White, Constructive Combinatorics, Springer, New York, 1986.
[12] W. Trotter, Graphs and partially ordered sets: recent results and new directions, Cong. Numer.
116 (1996), 253–278.
[13] M. van de Vel, Theory of Convex Structures, North-Holland, Amsterdam, 1993.