![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
We give a new proof of the theorem of Boesch–Tindell and Farzad–Mahdian–Mahmoodian–Saberi–Sadri that a directed graph extends to a strongly connected digraph on the same vertex set if and only if it has no complete directed cut. Our proof bounds the number of edges needed for such an extension; we give examples to demonstrate sharpness. We apply the characterization to a problem on non-transitive dice.
1 Introduction
Characterization theorems in graph theory are important because they often guarantee short certificates for both a “yes” and “no” answer to the question of whether a graph satisfies a particular property. Many such theorems state that obvious necessary conditions are also sufficient. In this note we give a new proof of such a result about directed graphs (Theorem 1, originally due to Farzad, Mahdian, Mahmoodian, Saberi, and Sadri Citation[1] based on a similar theorem of Boesch and Tindell Citation[2]) and we apply it to a problem on non-transitive dice from Schaefer Citation[3]. Our proof applies to a less general family than the original but yields a previously unknown numerical bound.
A strict digraph is a directed graph in which each unordered pair of vertices is the set of endpoints of at most one edge; that is, a strict digraph is an orientation of a simple graph. A digraph is strongly connected, or strong, if it contains a (directed) path from to
for every ordered pair of vertices. A digraph
extends to a digraph
if
and
. We ask when a (strict) digraph extends to a strongly connected strict digraph. Note that it does so if and only if it extends to a strongly connected tournament, where a tournament is an orientation of a complete graph.
For a set , let
. When
, the cut
is the set
, where we write
for an edge oriented from
to
. A cut
is a dicut if there is no “back edge” of the form
with
and
. It is a complete dicut if it contains all
edges of the form
with
and
.
Obviously, a digraph that extends to a strongly connected strict digraph contains no complete dicut. This obvious necessary condition is also sufficient. That fact is a special case of a theorem by Farzad et al. Citation[1, Theorem B(iii)].
Theorem 1
Strong Connectability A strict digraph of order at least extends to a strong strict digraph if and only if it contains no complete dicut.
We call such a digraph strongly connectable. We prove sufficiency in Section 2 from a new, stronger result, Theorem 2, in which we give an upper bound on how many edges need to be added.
A consequence of Theorem 1 is that the problem of deciding strong connectability belongs to the class NP co-NP. A certificate for strong connectability is a strongly connected extension, and a certificate for not being strongly connectable is a complete dicut. Both are easy to confirm. The latter is obvious. For the former, there exists an extension to a strong tournament, which contains a spanning cycle by Moon Citation[4, Section 4].
In Section 3 we apply Theorem 1 to a problem on “non-transitive dice” discussed in Schaefer Citation[3]. A set of dice is non-transitive if there is a cycle such that each die beats the next in cyclic order, and it is balanced if there exists a value such that for any two dice, one beats the other with probability exactly
. Schaefer asked which digraphs are realizable by balanced non-transitive dice; he showed that those digraphs are precisely the ones that are strongly connectable. (That result led to our investigation of strong connectability.) Thus Theorem 1 provides a criterion for a digraph to be realizable by balanced non-transitive dice, where a set of dice realizes a digraph if the vertices can be assigned to dice in the set so that when
is an edge, the die representing
beats the die representing
.
The theorem of Farzad et al. is based on a theorem of Boesch and Tindell Citation[2]. Consider a partially oriented multigraph , that is, a graph that may have multiple edges (but not loops) and in which a subset of edges has been oriented. Assume the underlying graph
, which is obtained from
by treating all edges as undirected, is connected. A weak dipath in
is a subgraph
of
whose underlying graph
is a path in
such that every oriented edge in
follows the same direction as
; that is, there are no “back edges”, although
may contain undirected edges.
We call strong if for every ordered pair
of vertices, there is a weak dipath in
from
to
. An
-cut is a set of the form
for some nonempty
; we call
the originating set. An
-dicut is an
-cut that contains every edge of
having exactly one endpoint in its originating set. That is, for an
-dicut where
is the originating set,
has no undirected edge
or back edge
with
and
. In particular, when
and
is the subdigraph of
consisting of all oriented edges, the
-dicuts are precisely the complete dicuts of
as defined before Theorem 1.
Boesch and Tindell characterized when can be oriented (by directing the undirected edges) to be strongly connected. Their result generalizes Robbins’ Theorem Citation[5], which solved the special case where all edges are unoriented. Farzad et al. Citation[1, Theorem B(i, iii)] observed an important corollary: another necessary and sufficient condition is that the underlying graph
be 2-edge-connected and there be no
-dicut. (Farzad et al. Citation[1] attribute this to Boesch and Tindell Citation[2], but it was not stated as such in Citation[2].) This result is more general than Theorem 1, which considers only the special case where
is the complete graph
, with our strict digraph being their subgraph of oriented edges in
. It is not clear whether our proof bounding the number of edges of
that must be oriented generalizes to their setting.
A different analogue of our problem has also been studied previously. Eswaran and Tarjan Citation[6] studied strong connectability for general digraphs, which allow antiparallel pairs of edges. This makes a huge difference. Without strictness, every digraph extends to a strong digraph, simply by introducing every ordered pair of distinct vertices as an edge. Thus, their tasks are to find the minimum number of edges to add and an algorithm to produce a smallest strong extension. This can be viewed as another special case of the Boesch–Tindell model, in which is
with all edges doubled and
has no parallel directed edges.
Frank Citation[7] and Frank and Jordán Citation[8,9] generalized the questions to extensions that have connectivity or edge-connectivity at least , again allowing antiparallel edge pairs and again seeking the smallest such extension and an algorithm.
The problems for strict digraphs are very different, beginning with the fact that not every strict digraph is strongly connectable. We also do not find an exact minimum number or smallest set of edges. The complexity of determining the minimum size of an extension set remains open, and it seems hard to generalize Theorem 1 to characterize digraphs extendable to a strict -connected digraph.
2 Strongly connectable digraphs
A strong component of a digraph is a maximal strongly connected subgraph. The strong components of
yield an acyclic digraph
by contracting each strong component to a vertex and eliminating duplicate edges and loops. A strong component is a source or sink component of
according as it is a source or sink vertex in
(it may be both). Given distinct strong components
and
, we say that
is a successor of
if there is a path from
to
in
, and then also
is a predecessor of
. For
, let
denote the strong component of
containing
. The underlying graph of a digraph
, as with a partially oriented multigraph, is the graph
obtained by treating its edges as unordered pairs. We say that
is weakly connected when
is connected. The weak components of a digraph
are the subdigraphs induced by the vertex sets of components of
.
We prove Theorem 1 by obtaining an upper bound on the number of edges needed. We will strengthen the upper bound for disconnected graphs in Lemma 4 and Proposition 5.
Theorem 2
Upper Bound Let be a strict digraph having at least three vertices and
strong components. If
has no complete dicut, then
extends to a strongly connected strict digraph by adding at most
edges, with equality if and only if
is disconnected and each weak component of
is strong.
Proof
Suppose that is disconnected and every weak component of
is strong. If
, then choose one vertex from each component and add a cycle of
edges through them to obtain a strongly connected extension. If
, then since
has at least three vertices, one weak component has at least two vertices, and we can add edges to and from distinct vertices in that component to obtain a strong extension. Since every weak component must receive an added entering edge, equality holds in this case.
Henceforth we may assume that not every weak component is strong, so has a strong component that is a sink component but not a source component.
Case 1: is weakly connected. To prove the upper bound
, we use induction on
. For
there is nothing to prove (no edge need be added). Consider
.
Let be the set of all vertices in source components of
. Since
is a dicut, there is a pair
with
and
such that
. Add edge
to
, forming a new strict digraph
. If
is a successor to
in
, then
has a strong component containing
and
, so
has at most
strong components. Otherwise,
implies that
has some source component as a predecessor; let
be a vertex in that component, and let
. Since no edge connects two source components,
is a strict digraph. It has at most
strong components, since
,
, and
all lie in a single strong component of
. It now suffices by the induction hypothesis to show that
and in the second case also
has no complete dicut.
Let be a complete dicut in
. As
has no complete dicut, the added edge
must satisfy
and
. Thus
and
. In
no edges enter the source component
, so in
only one edge enters
. Since
, this implies
. That makes
a source vertex in
, so only the edge
enters it in
. Thus
. This implies that
is a source vertex in
and therefore in
, which contradicts
. We conclude that
has no complete dicut.
In the case where is not a successor to
, the source component
in
remains a source component in
. Also, the strong component of
that contains both
and
from
is a successor of
in
. Thus
is formed from
by adding
in the way that
was formed from
by adding
. Since
satisfies the same hypotheses required of
, the same argument now implies that
also has no complete dicut.
Case 2: is not weakly connected. Let
with
be the weak components of
. In each
choose a source component
and a sink component
such that
if
is strong and otherwise
is a successor of
. Treating subscripts modulo
, for
add an edge
such that
and
.
The resulting digraph is weakly connected. It is obviously strict when
, and when
the edges
and
do not have the same pair of endpoints because at least one weak component is not strong. For the same reason, the
added edges are too few to complete a complete dicut unless
and
has exactly three vertices, but then
is a (directed) cycle. Thus, the connected case applies to
.
Let be the number of strong components of
. Since all
and all
lie in one strong component in
, and there are at least
such sets since
only when
is strong, we have
. By Case 1,
can be made strongly connected by adding at most
edges, so the number of edges needed to make
strongly connected is at most
.□
This proof appears to require that, in the situation of Boesch–Tindell and Farzad et al., the graph underlying the partially oriented graph is the complete graph
. Therefore, we do not expect a similar bound in the generality of those papers.
Remark 3
Since every source component needs an entering edge and every sink component needs an exiting edge, at least added edges are needed for a strongly connected extension, where
and
are the numbers of source and sink components.
Example 1
The upper bound is sharp for weakly connected strict digraphs. Consider the digraph obtained from a transitive tournament with
vertices by deleting the unique spanning path. There are
strong components and no complete dicut, and extending to a strong strict digraph requires adding the
missing edges. When
, this example has two source components and two sink components, so the lower bound in Remark 3 can be arbitrarily bad when
is weakly connected.
Example 2
The upper bound is also sharp for digraphs with more than one weak component when the components are not all strong. Let
be the digraph formed from the complete bipartite graph
with bipartition
, where
and
, by directing each edge from
to
and adding an isolated vertex. A strong extension must add edges entering each vertex in
and edges leaving each vertex in
, but no edge can do both. Thus, the needed number of added edges is at least
, which equals
. Here again the bound of Remark 3 is weak.
In spite of Example 2, the upper bound can be reduced in the disconnected case by using additional information, such as the number of weak components that are not strong, the number of strong components that are neither sources nor sinks, or the number of source and sink components in each weak component. We omit the details of the first two; the next result concerns the last.
Lemma 4
Disconnected Upper Bound Let be a strict digraph that is not weakly connected. Let
be its weak components, and let
and
be the number of source and sink components, respectively, in
. The minimum number of edges that must be added to make
strongly connected is at most
Proof
We add edges from sink components of to source components of
, viewing subscripts modulo
. We add at least one edge leaving each sink component and one edge entering each source component. This is easy to do using
edges. The resulting digraph is obviously strongly connected and, when
, strict. When
, the same observation as in Case 2 of Theorem 2 allows it to be strict.□
The exact value of this upper bound depends on the cyclic order chosen for the components of . We do not know a procedure to minimize the sum. The lower bound from Remark 3 is
; it equals the upper bound from Lemma 4 when the comparison of
and
goes the same way for each
. Hence both bounds are sharp.
Recall that the weak components of correspond to the components of
.
Proposition 5
Disconnected Upper Bound A strict digraph that is not weakly connected can be strongly connected by adding at most
edges, where
has
source components,
sink components, and
weak components. The bound equals
, where
strong components are source or sink components and
weak components are not strong components.
Proof
This follows from Lemma 4, since (again taking subscripts modulo
), giving an upper bound of
. The sum is
. The sum
exceeds
by the number
of weak components that are strongly connected; hence
.□
Proposition 5 strengthens the upper bound in Theorem 2 when is not weakly connected. By definition, always
, so the upper bound of
is reduced by at least
for each weak component that is not strong.
Example 3
Toward understanding the problem of obtaining strong extensions by adding the fewest edges, it is interesting to consider digraphs obtained from bipartite graphs. Let be a strict digraph obtained from a bipartite graph with bipartition
by orienting all edges from
to
. We forbid the underlying graph to be complete bipartite, because the orientation would yield a complete dicut. Let
and
.
As in Remark 3, a strongly connected extension of must always add at least
edges; this is the trivial lower bound. By symmetry, suppose
. We claim that achieving this lower bound requires adding edges not in
that match
into
. To see this, note that
added edges must enter
and
added edges must exit
. To do this using only
edges, each of the
added edges leaving
must be one of the
edges entering
. These
edges form a matching of
into
.
If the digraph on vertices induced by the vertices covered by this matching is strongly connected, then adding an edge from the matched vertices of
to each of its
remaining vertices completes the desired strongly connected extension.
At the other extreme, when has
edges, only the one edge missing from
can connect a sink to a source, and the upper bound
cannot be improved.
The common generalization of the two extremes improves the lower bound to , where
is the maximum size of a matching from
into
using edges not in the original bipartite graph.
A digraph is
-connected if it has more than
vertices and any deletion of fewer than
vertices from
leaves a strong digraph. For a generalization analogous to those studied for non-strict digraphs, we say that a strict digraph
is
-connectable if it extends to a
-connected strict digraph. An obvious necessary condition for
-connectability is that every dicut
lacks at least
edges. It is not clear whether this condition is sufficient; our proofs for
do not extend, because when
the maximal
-connected subgraphs of a graph need not be pairwise disjoint.
3 Non-transitive dice
In a set of ordinary dice, all dice are the same and the probability that one die rolls a higher number than another is, if we exclude ties (e.g., by ignoring them and rolling again), exactly . Martin Gardner publicized the idea, due to Bradley Efron, of dice where not only is the probability other than
, but there can be three dice such that each beats one of the others with probability greater than
(see Gardner Citation[10–12]). Such dice are non-transitive: generalizing to
dice, there exist
that can be arranged cyclically so that each has probability greater than
of rolling higher than its successor.
Quimby found a set of four non-transitive 6-sided dice whose 24 sides are the distinct numbers from 1 to 24 [Citation13] (see Savage [Citation14] for other sets of non-transitive dice). Schaefer and Schweig [Citation15] carried the idea further; they studied -sided generalized dice in which each die has
different numbers on it and the numbers on all dice are distinct. We may regard each die as a set of
distinct integers and define a set of dice
as a set of pairwise disjoint such sets. As they observed, one can always choose the dice to partition the set
.)
We say that die beats
and write
if, among all pairs of numbers in
, the first number is larger than the second more than half the time. A set of dice is transitive if the relation
is transitive. Although it may be contrary to intuition, a randomly chosen set of (more than two) dice need not be transitive. Schaefer and Schweig [Citation15] showed that it is easy to make an intransitive set of three or four
-sided dice when
.
The relation can be represented by a digraph
with one vertex for each die and an edge from
to
if
beats
. The relation
is antisymmetric, meaning that
and
imply
, so the digraph
is strict. If
is any subgraph of
, we say that
realizes
; that means every edge of
corresponds to a pair of dice in
in which one beats the other as indicated by the direction of the edge. (
need not be an induced subgraph.)
Let be the probability that
beats
; that is,
is the proportion of pairs in
in which the first number is the larger. (Because no two numbers on dice are equal,
.) Schaefer and Schweig [Citation15] call a set of dice balanced if all unordered pairs
are the same. They found that for
it is possible to form non-transitive dice that are balanced. Schaefer Citation[3] then showed that for a tournament
of order
, there is a balanced set of
non-transitive dice that realizes
if and only if
is strongly connected. He observed the corollary that non-transitive dice realizing a strict digraph
can be chosen balanced if and only if
is strongly connectable. Thus Theorem 1 gives a criterion for the existence of balanced dice realizing a given relation (transitive or not).
Corollary 6
An antisymmetric relation is realizable by a set of balanced dice if and only if its digraph has no complete dicut.
References
- FarzadB.MahdianM.MahmoodianE.S.SaberiA.SadriB., Forced orientation of graphs Bull. Iranian Math. Soc. 32 1 2006 79–89
- BoeschFrankTindellRalph, Robbins’s theorem for mixed multigraphs Amer. Math. Monthly 87 9 1980 716–719
- Alex Schaefer, Balanced non-transitive dice, II. Tournaments, College Math J.,arXiv:1706.089086 (in press).
- MoonJohn W., Topics on Tournaments1968HoltRinehart and Winston, New York
- RobbinsH.E., A theorem on graphs, with an application to a problem of traffic control Amer. Math. Monthly 46 5 1939 281–283
- EswaranKapali P.TarjanRobert E., Augmentation problems SIAM J. Comput. 5 4 1976 653–665
- FrankAndrás, Augmenting graphs to meet edge-connectivity requirements SIAM J. Discrete Math. 5 1 1992 25–53
- FrankAndrásJordánTibor, Minimal edge-coverings of pairs of sets J. Combin. Theory Ser. B 65 1 1995 73–110
- FrankAndrásJordánTibor, Directed vertex-connectivity augmentation Connectivity augmentation of networks: structures and algorithms, (Budapest, 1994)Math. Program. 84B 3 1999 537–553
- GardnerMartin, The paradox of the nontransitive dice and the elusive principle of indifference Sci. Am. 223 12 1970 110–114
- GardnerMartin, On the paradoxical situations that arise from nontransitive relations Sci. Am. 231 10 1974 120–125
- GardnerMartin, Nontransitive dice and other paradoxes The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems2001Norton, New York286–296Ch. 22
- Shirley Quimby, The Pallbearers Review (1971). (Cited in [12].).
- Savage JrRichard P., The paradox of nontransitive dice Amer. Math. Monthly 101 5 1994 429–436
- SchaeferAlexSchweigJay, Balanced non-transitive dice College Math. J. 48 1 2017 10–16