# A Visibility Roadmap Sampling Approach for a Multi-Robot Visibility-Based
Pursuit-Evasion Problem

Trevor Olsen, Anne M. Tumlin, Nicholas M. Stiffler and Jason M. O’Kane T.
Olsen, A. M. Tumlin, N. M. Stiffler, and J. M. O’Kane are with the Department
of Computer Science and Engineering, University of South Carolina, Columbia,
SC 29208, USA. {tvolsen<EMAIL_ADDRESS>{stifflen<EMAIL_ADDRESS>This material is based upon work supported by the National Science Foundation
under Grant Nos. 1659514 and 1849291.

###### Abstract

Given a two-dimensional polygonal space, the multi-robot visibility-based
pursuit-evasion problem tasks several pursuer robots with the goal of
establishing visibility with an arbitrarily fast evader. The best known
complete algorithm for this problem takes time doubly exponential in the
number of robots. However, sampling-based techniques have shown promise in
generating feasible solutions in these scenarios. One of the primary drawbacks
to employing existing sampling-based methods is that existing algorithms have
long execution times and high failure rates for complex environments. This
paper addresses that limitation by proposing a new algorithm that takes an
environment as its input and returns a joint motion strategy which ensures
that the evader is captured by one of the pursuers. Starting with a single
pursuer, we sequentially construct Sample-Generated Pursuit-Evasion Graphs to
create such a joint motion strategy. This sequential graph structure ensures
that our algorithm will always terminate with a solution, regardless of the
complexity of the environment. We describe an implementation of this algorithm
and present quantitative results that show significant improvement in
comparison to the existing algorithm.

##  I Introduction

Autonomous reconnaissance tasks, in which robots strive to observe salient
features of objects or agents within their environments, remain one of the
most active threads of research within the robotics community. Such tasks have
wide-ranging application domains such as environmental monitoring [5, 6, 15,
39, 40], surveillance [1, 2, 4, 7], and search-and-rescue [13, 33, 24]. Many
of these tasks can be framed as two-player games played amongst opposing
teams: evaders (who wish to evade capture) and pursuers (who seek to capture
them). This paper is concerned with a specific form of this two-player game,
wherein a team of pursuers must locate an evader (or group of evaders) in a
polygonal environment.

Specifically, we address one such problem where a group of pursuers, each
equipped with an omni-directional sensor that extends to the polygonal
boundary, must form a motion plan to locate an arbitrarily fast evader in a
polygonal environment. Figure 1 illustrates this scenario. The literature has
a number of results for this problem in the single-pursuer case, including
algorithms with strong guarantees such as completeness [11] and path length
optimality [37]. However, the case in which multiple pursuers cooperate is not
nearly as well understood. A complete algorithm is known, but it runs in time
doubly-exponential in the number of pursuers [34].

Figure 1: An example multi-pursuer solution strategy generated by the proposed
algorithm. The filled circle represent the initial location of the pursuer,
while the hollow circles represent its final location.

One approach to overcome the computational challenge posed by this multiple-
pursuer pursuit-evasion planning task [35], showed the feasibility of
sampling-based techniques to generate joint motion strategies. Nevertheless,
that approach has several important limitations.

  1. (i)

The existing algorithm lacks insight into how the sampling should be
performed, and treats the sampling distribution as a “black box.”

  2. (ii)

The existing algorithm requires a predetermined number of pursuers as input;
it cannot adapt the number of pursuers to the complexity of the environment.

  3. (iii)

The solutions generated by this approach are of poor quality, in the sense
that there nearly always are motions by one or more of the pursuers that do
not actively contribute to the search.

After a review of related work (Section II), precise statement of the problem
(Section III), and a summary of important concepts from prior work on this
problem (Section IV), this paper makes three new contributions that address
the limitations of the existing algorithm.

  1. (i)

We introduce a new sampling strategy, tailored to the visibility-based nature
of the problem (Section V-A).

  2. (ii)

We describe a method that eliminates the need for the number of pursuers to be
provided as input, instead iteratively increasing the size of the team
(Section V-B).

  3. (iii)

We present a post-processing algorithm that improves solution quality (Section
V-C).

Finally, Section VI presents quantitative evaluations of these new
improvements and Section VII previews future work.

##  II Related work

This research blends ideas from two vibrant threads of prior robotics
research: visibility-based pursuit-evasion and sampling-based motion planning
in high dimensional spaces.

In regard to pursuit-evasion, this work is most closely aligned with the
problem first introduced by Suzuki and Yamashita [38], in which an evader
operating in a geometric environment seeks to locate an unpredictable evader
capable of moving arbitrarily quickly. This work was later expanded by Guibas,
Latombe, LaValle, Lin, and Motwani [11] who provide a complete algorithm for
the single pursuer scenario in simply-connected environments for a pursuer
with an omnidirectional field-of-view. Park, Lee, and Chwa [25] identified
necessary and sufficient conditions for a search to be feasible for a single
pursuer.

Other results for the single pursuer scenario that build upon this foundation
provide results such as completeness [11], optimality [37], establishing and
maintaining visibility of a moving agent [29, 30] or consider more restrictive
scenarios with respect to pursuer parameters such as sensing, actuation and
speed [27, 9, 41, 26, 36, 28].

The community has placed increased emphasis on the study of richer scenarios
where a team of pursuers cooperate during the search [20, 16, 10, 35, 14, 19,
8]. Stiffler and O’Kane [34] present an algorithm utilizing a cylindrical
algebraic decomposition that, while complete, relies upon constructing a graph
whose size is doubly exponential in the complexity of the environment. That
work subsequently served as motivation for approaches that utilize heuristics
[35] that seek to overcome the problem complexity by utilizing sampling
techniques.

More generally, sampling based techniques have been employed in a number of
planning contexts where computing an exact solution proves computationally
intractable such as motion planning [18, 23, 22, 32, 17] and manipulation
planning [31, 12, 21]. One caveat of sampling-based methods is that they quite
often suffer from the curse of dimensionality [3] whereby, as the number of
dimensions increases, the search space becomes so vast that the number of
samples required for adequate coverage of the space increases dramatically. A
number of different approaches have been proposed to combat this problem. One
recent result draws samples in lower-dimensional subspaces to search for a
feasible solution, and incrementally reasons about higher dimensions while
utilizing the information gained in the lower dimensional graph [43]. For the
specific multi-robot case in which the configuration space is a Cartesian
product of the configuration spaces of individual agents in the system, one
novel approach seeks to reason about each agent independently (a
subdimension), and only when the agents reach a point where they interact with
one another is there a lifting to a higher-dimensional space [42].

##  III Problem statement

###  III-A The environment, the evader, and the pursuers

Let $E\subset\mathbb{R}^{2}$ be a bounded, closed, connected polygonal set
called the _environment_. An evader moves within $E$. We describe the evader’s
position via a continuous function $e(t):[0,\infty)\rightarrow E$ to represent
the location of the evader at time $t$. There is no restriction on the speed
of the evader, so long as it is finite.

We task $n$ pursuers with the goal of ensuring capture of the evaders
regardless of the evader trajectories. We can assume worst case reasoning in
the sense that there is a singular evader which follows a path that maximizes
its time until detection over all evader trajectories. We consider both
scenarios in which the number of pursuers is known and fixed, an in which the
number of pursuers to utilize is determined by the algorithm as the plan is
generated. Let $p_{i}:[0,\infty)\rightarrow E$ represent the location of the
$i^{\text{th}}$ pursuer as a function of time. We refer to such functions as
_motion strategies_. Each pursuer is equipped with knowledge of $E$ and an
omnidirectional sensor which extends until the nearest point on the boundary
of $E$ in each direction. That is, a pursuer at point $q_{1}\in E$ can see
every point in its visibility polygon, $V(q_{1})=\\{q_{2}\in
E\mid\overline{q_{1}q_{2}}\subseteq E\\}$ where $\overline{q_{1}q_{2}}$
denotes the line segment joining $q_{1}$ and $q_{2}$ in $E$.

$p_{1}(0)$$p_{1}(t)$$p_{1}(T)$$p_{2}(0)$$p_{2}(t)$$p_{2}(T)$$e(0)$$e(t)$$e(T)$

Figure 2: Example evader and pursuer paths. The evader is detected at time
$t$.

###  III-B Objective

The algorithmic problem we address is to find a collection of motion
strategies $\\{p_{1},p_{2},\dots,p_{n}\\}$ such that, for some $t\geq 0$ and
$j\in\\{1,\dots,n\\}$, $e(t)\in V(p_{j}(t))$ for any evader curve $e$. Such a
collection of motion strategies is called a _solution_. Specifically, we
consider two related problems.

#### Fixed

Given an environment $E$ and a positive integer $n$, generate a solution using
exactly $n$ pursuers. Algorithms for this problem can be evaluated by
examining both the time needed to generate a solution as well as the time
needed for the pursuers to execute that solution.

#### Variable

Given an environment $E$, generate a solution that uses as few pursuers as
possible. In addition to the run time and execution time criteria mentioned
above, algorithms for this variant of the problem can also be judged by the
number of pursuers utilized by the computed solution.

##  IV Background

This section concisely summarizes some essential prior results upon which our
new contributions build. Specifically, we describe how the pursuers’ knowledge
about the evader’s possible position can be maintained (Section IV-A) and
present a data structure that encapsulates the progress of a search for a
complete solution (Section IV-B).

###  IV-A Shadows and shadow events

In general, the pursuers will be able to see only a subset of the environment
at any particular time, while the remaining parts of the environment are out
of view of all of the pursuers. Formally, at time $t$, the _shadow region_ ,
$S(t)$, is $E\setminus\bigcup_{i=1}^{n}V(p_{i}(t))$. We call the maximally
path-connected components of $S(t)$ _shadows_.

Figure 3: An example of a cleared (right) and contaminated (left) shadow,
given the pursuer’s movement history. Here, the white region displays the
visibility polygon of a pursuer located at the red circle.

The crucial information about each shadow is whether or not the evader may be
hiding within that shadow. A shadow $s$ is called cleared at time $t$ if,
based on the pursuers’ joint motions up to time $t$, it is not possible for
the evader to be within $s$ without having been seen by one of the pursuers.
Analogously, a shadow is said to be contaminated if it is possible for the
evader to be hiding within it given the pursuers’ motions up to time $t$. As
the pursuers move through the environment, the individual shadows change
continuously. However, the cardinality of the set of shadows changes only when
a _shadow event_ occurs, i.e. a shadow appears, disappears, splits, or merges
with another shadow. The shadow events induce the following changes to the
status of a shadow:

  * •

_Appear_ : A shadow can appear if the pursuers lose vision of a region within
the environment. In this event, the new shadow has a cleared status.

  * •

_Disappear_ : A shadow can disappear if the pursuers gain vision of a region
which was previously a shadow. The label corresponding to the shadow that
disappears is discarded.

  * •

_Merge_ : Two or more shadows can merge into a larger shadow. In this event,
the new shadow is assigned the label cleared only if all merging shadows were
cleared; otherwise, the new shadow is labeled contaminated.

  * •

_Split_ : If a shadow becomes path disconnected, we say it was split. The
newly formed shadows have the status of the initial from which they were
formed.

More detail about these types of shadow events and their clear/contaminated
labels may be found in the work of Guibas, Latombe, LaValle, Lin, and Motwani
[11].

###  IV-B Sample-generated pursuit-evasion graphs

To aid in the search for a joint motion strategy for the pursuers, we utilize
the Sample-Generated Pursuit-Evasion Graph (SG-PEG) data structure; additional
details about the SG-PEG appear in the original paper [35]. An SG-PEG is a
directed graph $G=(V_{G},E_{G})$, representing a portion of the connectivity
of the joint configuration space for a fixed number $n$ of pursuers. Each
vertex in $V_{G}$ represents a joint configuration for the pursuers
$(p_{1},\dots,p_{n})\in E^{n}$. Edges in $E_{G}$ connect pairs of vertices for
which it is possible for each pursuer to make a collision-free straight line
motion between the two corresponding configurations. That is, if an edge
exists between two vertices representing joint configurations
$(p_{1},\dots,p_{n})$ and $(q_{1},\dots,q_{n})$, then
$\overline{p_{i}q_{i}}\subset E$ for each $i\in\\{1,\ldots,n\\}$. One vertex,
corresponding to the starting joint configuration of the robots, is designated
as the _root_ of the graph. Each vertex maintains a list of non-dominated
shadow labels (i.e. clear/contaminated statuses) that are reachable by
traversing the graph along some (possibly non-simple) path from the root.

The primary operation that can be performed on a standard SG-PEG is
AddSample$(p_{1},\dots,p_{n})$ which, given a collision-free joint
configuration, performs three main steps:

  * (i)

It inserts a new vertex $v$ at the given joint configuration.

  * (ii)

For any other vertex $u$ within a pre-defined connection distance in $E^{n}$,
it checks whether the straight-line connection between $v$ and $u$ would be
collision-free. If so, and if the shortest path in the graph between $v$ and
$u$ is sufficiently long, it creates edges $vu$ and $uv$.

  * (iii)

For each new edge thusly added, AddSample computes the shadow events described
in Section IV-A induced by motion along that edge. It then propagates the
reachable shadow label information across the new edge and then recursively
across the graph, to determine what new reachable shadow labels, if any, are
now possible at which vertices, due to this new edge.

The utility of the SG-PEG is that if any vertex $v$ has a reachable shadow
label that is fully cleared (i.e. it has a reachable shadow label set in which
each shadow bears a clear label), then a solution can be extracted from the
graph by tracing back via the appropriate edges to the root vertex.

##  V Algorithm description

Our approach to this problem is based on two significant additions and one
modification to the prior algorithm of Stiffler and O’Kane [35]. The basic
idea of that prior algorithm is to generate random samples in $E^{n}$ and use
them to construct an SG-PEG, continuing until the SG-PEG indicates that it
contains a solution. Algorithm 1 shows the enhancements that we propose. New
elements in comparison to the prior algorithm are highlighted: modifications
to the sampling strategy in purple text and new additions in blue text. Note
that, $n$, the number of robots has been removed in our variant. Details about
these changes appear below.

Algorithm 1 Solve($E$, $n$, $C$, $S$)

1:an environment $E$, a number of pursuers $n$,
an expansion criterion $C$ and a sampler $S$

2:$G\leftarrow$ empty SG-PEG for $n$ pursuers 1 pursuer

3:$p\leftarrow{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\textsc{S.getSample}()}$

4:$G.\textsc{addSample}(p)$

5:$G.\textsc{setRoot}(p)$

6:while no solution has been found do

7:
$p\leftarrow{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}S.\textsc{getSample}()}$

8: $G.\textsc{addSample}(p)$

9: if $C$ is met then

10:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}G.\textsc{addPursuer}()}$

11:$X\leftarrow\textsc{extractSolution}()$

12:${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X^{\prime}\leftarrow\textsc{refineSolution}(X)}$

13:return $X^{\prime}$

###  V-A Web sampling

Stiffler and O’Kane proposed a handful of sampling distributions, but none of
them proved significantly more effective than simple uniform random sampling
of the joint configuration space. This approach appears not to be particularly
effective in this domain, because the environment is comprised of regions
whose surveyance is essential to finding a solution. To combat this issue, we
propose a new strategy for generating samples, which specifically takes into
account the visibility component of the problem. Specifically, the goal is to
generate a small collection of samples $W$ that has two properties: (a) each
point in $E$ is seen by at least one point in $W$, and (b) a pursuer moving
between points in $W$ along straight line segments in $E$ can travel between
any pair of points in $W$, i.e. $W$ forms a ‘connected roadmap’ of $E$.

The approach is based on a randomized structure called a _web_ in $E$, which
is constructed in two steps. First, we construct a set of _initial points_
$P\subset E$. Each initial point is selected sequentially and randomly, from
the region outside the union of visibility polygons of the previously selected
points. The process continues until $\bigcup_{p\in P}V(p)=E$. Then the
algorithm selects a collection of _intersection points_ $Q\subseteq E$ by
examining pairs of initial points $\\{p_{i},p_{j}\\}\subseteq P$, and placing
a point uniformly at random within $V(p_{i})\cap V(p_{j})$, if that
intersection is non-empty. A web is simply the combination $W=P\cup Q$. Figure
4 illustrates this concept.

We utilized webs to generate samples from $E^{n}$ in Lines 3 and 7 by
generating a separate web for each pursuer and sampling, without replacement,
from those points. If the points in any of the webs are exhausted, we generate
another set of webs and continue.

Figure 4: [left] An example web. Red points are initial points; the blue are
intersection points. Green edges connect each intersection point to the
initial points from which it is induced. [right] The distribution induced by
web sampling, based upon 750 generated webs. Note the higher density at
junctions and corners.

###  V-B Variable numbers of pursuers

In the prior algorithm, the number of pursuers in the solution was required as
an input. This information was necessary because the SG-PEG data structure
stores joint configurations drawn from $E^{n}$; thus $n$ must be known to
construct an SG-PEG.

To alleviate this limitation, we instead propose a sequential process, in
which the number of pursuers is gradually increased as the algorithm proceeds.
Realizing this approach in the planner requires us to resolve two
complications.

First, the algorithm requires a mechanism to transition, in mid-stream, from
an $n$-pursuer SG-PEG to an $(n+1)$-pursuer SG-PEG (Line 10). One
straightforward approach is to simply discard the existing vertices and edges
and restart the search with an additional pursuer. (This is referred to as the
‘Clear’ option in Section VI.)

However, it may be preferable to ensure that our previous effort is not
wasted. To this end, we propose a new method that _clones_ the first pursuer
in each vertex of the SG-PEG. That is, for each vertex in the SG-PEG, we
replace its joint configuration $(p_{1},p_{2},\dots,p_{n})$ with
$(p_{1},p_{2},\dots,p_{n},p_{1})$. This adds an additional pursuer to the
graph, without changing any of the reachable labels or edges. Thus, the
cloning option is extremely efficient, but it leads to an SG-PEG in which the
newly-added pursuer moves in parallel with another pursuer. Future edges added
at the $(n+1)$-th layer will correspond to independent motions for these two
robots (as they draw from their own unique set of webs).

Next, we must decide when to expand the number of pursuers (Line 9). We
consider two options. First, we propose a method that devotes _fixed effort_
to each stage of the search. The process begins by rapidly generating a
trivial solution by placing pursuers until their visibility fully covers the
environment, which results in a solution that requires no movement from the
pursuers. This gives a (generally very loose) upper bound $N$ on the number of
pursuers required. Then, given a target total run time of $T_{\text{limit}}$
seconds, we apportion the time between the possible numbers of pursuers
$1,\ldots,N$ via a Poisson distribution. The Poisson distribution was selected
due to the placement of the mean, as well as its skew and shape. We choose a
tunable parameter $\alpha$ which determines the fraction of time to spend on
the final step that utilizes $N$ pursuers, so that according to the definition
of the Poisson distribution, we have $\alpha=\lambda^{N}e^{-\lambda}/N!$. From
this equation, the algorithm numerically computes the Poisson parameter
$\lambda$ and allocates $T_{\text{limit}}\lambda^{i-1}e^{-\lambda}/(i-1)!$ to
the search with $i$ pursuers before proceeding to $i+1$. Because of the
existence of the upper bound $N$, this method will always produce a solution,
although it may require a large number of pursuers.

As an alternative, we also consider a stalled progress approach, based upon
monitoring the minimum sum of the contaminated shadow area across all vertices
of the graph. (n.b. We have a solution if and only if this value reaches $0$.)
If this value fails to improve by at least 5% after adding $M$ samples, we add
a new pursuer. To enable a fair comparison to the fixed effort method, we once
again return a trivial solution if no solution is found with fewer pursuers.

###  V-C Solution refinement

Because of the sampling-based nature of this algorithm, its outputs are likely
to have extraneous motions. This issue is noticeably more severe in our
context than for traditional sampling-based motion planning because the
generated solutions may travel several times along certain edges in an effort
to clear specific shadows. In this section, we introduce a post processing
method which takes a joint motion strategy and optimizes it by removing
unnecessary pursuer motions.

Our method is similar to standard shortcut-based path smoothing. We select two
points $z_{a}$ and $z_{b}$ at distance $c$ along the solution path in $E^{n}$,
and check whether taking a shortcut directly from $z_{a}$ to $z_{b}$ yields a
path that is still a correct solution. Figure 5 depicts the process. Our check
features one important difference from traditional path smoothing: In addition
to ensuring that the refined solution is collision-free, we must also ensure
that it remains a correct solution, i.e. that the refinement does not allow
any shadows to remain contaminated. We do this by tracking forward through the
shortened path, applying the shadow events experienced along that path —Recall
Section IV-A— to update the shadow labels.

Given this shortcut operation, we greedily optimize the path, proceeding
systematically over decreasing values of $c$ and increasing positions of
$z_{a}$. (From these two, $z_{b}$ is readily computed.) Each time we discover
a shortcut yielding a correct solution, that shortened solution replaces the
previous solution, and the process continues. See Figure 6.

$z_{1}$$z_{a}$$z_{b}$$z_{i}$$z_{1}$$z_{a}$$z_{b}$$z_{i}$$c$$c^{\prime}$

Figure 5: A cut of length $c$ during solution refinement.

Figure 6: Refining a solution. [left] Before. [right] After.

##  VI Evaluation

Table I: Simulation results for the Office environment (Figure 1).

| success | comp time (s) | num robots | num vertices | num edges
---|---|---|---|---|---
| rate | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
WS ($n=2$) | 100% | 87.201 | 58.707 | 2.000 | 0.000 | 74.360 | 50.392 | 137.440 | 103.644
SO14 ($n=2$) | 96% | 96.890 | 78.231 | 2.000 | 0.000 | 117.875 | 62.007 | 219.167 | 131.542
WS ($n=3$) | 100% | 68.953 | 56.738 | 3.000 | 0.000 | 109.160 | 55.984 | 157.040 | 105.265
SO14 ($n=3$) | 100% | 63.205 | 25.110 | 3.000 | 0.000 | 330.440 | 210.853 | 542.080 | 453.409
WS ($n=4$) | 100% | 57.248 | 52.329 | 4.000 | 0.000 | 177.760 | 73.723 | 167.960 | 103.567
SO14 ($n=4$) | 100% | 73.448 | 65.325 | 4.000 | 0.000 | 1258.480 | 774.096 | 1830.920 | 1655.530
WS ($n=5$) | 100% | 91.633 | 80.529 | 5.000 | 0.000 | 392.520 | 229.407 | 275.920 | 224.627
SO14 ($n=5$) | 80% | 235.866 | 129.786 | 5.000 | 0.000 | 4081.000 | 1361.404 | 4495.150 | 2546.067
FE Clone $(\alpha=0.001)$ | 100% | 138.097 | 71.992 | 3.440 | 0.768 | 138.720 | 88.246 | 186.720 | 89.464
FE Clear $(\alpha=0.001)$ | 100% | 111.114 | 112.003 | 3.280 | 2.390 | 866.360 | 2702.653 | 732.200 | 1379.524
SP Clone $(M=30)$ | 100% | 193.867 | 55.951 | 2.520 | 2.365 | 117.280 | 79.072 | 192.200 | 120.596
SP Clear $(M=30)$ | 100% | 84.824 | 29.878 | 7.640 | 4.636 | 222.360 | 107.938 | 185.160 | 35.873

Table II: Simulation results for the H environment (Figure 4).

| success | comp time (s) | num robots | num vertices | num edges
---|---|---|---|---|---
| rate | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
WS ($n=2$) | 100% | 18.716 | 9.816 | 2.000 | 0.000 | 71.600 | 49.019 | 119.160 | 103.625
SO14 ($n=2$) | 100% | 33.885 | 14.777 | 2.000 | 0.000 | 105.760 | 77.638 | 193.640 | 158.844
WS ($n=3$) | 100% | 20.151 | 11.281 | 3.000 | 0.000 | 143.200 | 46.871 | 168.720 | 84.149
SO14 ($n=3$) | 100% | 35.965 | 20.354 | 3.000 | 0.000 | 212.560 | 152.480 | 349.840 | 305.536
WS ($n=4$) | 100% | 27.131 | 10.502 | 4.000 | 0.000 | 261.520 | 94.841 | 211.920 | 116.173
SO14 ($n=4$) | 96% | 43.636 | 42.848 | 4.000 | 0.000 | 639.042 | 365.724 | 972.042 | 704.745
WS ($n=5$) | 100% | 47.967 | 24.342 | 5.000 | 0.000 | 413.840 | 119.927 | 196.800 | 77.066
SO14 ($n=5$) | 96% | 81.949 | 62.208 | 5.000 | 0.000 | 1743.708 | 1512.375 | 2422.125 | 2732.005
FE Clone $(\alpha=0.001)$ | 100% | 27.065 | 9.973 | 2.000 | 0.000 | 48.120 | 16.269 | 79.440 | 31.466
FE Clear $(\alpha=0.001)$ | 100% | 21.538 | 8.483 | 2.000 | 0.000 | 71.360 | 24.124 | 115.520 | 48.321
SP Clone $(M=30)$ | 100% | 42.422 | 13.620 | 2.400 | 1.607 | 76.120 | 29.992 | 129.320 | 46.703
SP Clear $(M=30)$ | 100% | 19.637 | 6.906 | 7.920 | 3.081 | 204.840 | 62.487 | 136.640 | 31.579

Table III: Simulation results for the Spider environment (Figure 6).

| success | comp time (s) | num robots | num vertices | num edges
---|---|---|---|---|---
| rate | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
WS ($n=2$) | 100% | 151.738 | 87.515 | 2.000 | 0.000 | 54.240 | 34.170 | 90.920 | 65.193
SO14 ($n=2$) | 84% | 312.341 | 115.955 | 2.000 | 0.000 | 152.952 | 90.760 | 296.619 | 182.206
WS ($n=3$) | 100% | 91.825 | 41.326 | 3.000 | 0.000 | 50.120 | 36.003 | 68.280 | 58.533
SO14 ($n=3$) | 96% | 211.234 | 89.930 | 3.000 | 0.000 | 90.167 | 33.983 | 160.750 | 65.811
WS ($n=4$) | 100% | 84.356 | 26.550 | 4.000 | 0.000 | 55.520 | 26.590 | 61.880 | 40.169
SO14 ($n=4$) | 96% | 216.941 | 83.815 | 4.000 | 0.000 | 142.708 | 283.093 | 257.083 | 560.368
WS ($n=5$) | 100% | 92.822 | 42.587 | 5.000 | 0.000 | 75.800 | 33.582 | 72.920 | 47.970
SO14 ($n=5$) | 92% | 222.129 | 77.185 | 5.000 | 0.000 | 81.261 | 31.517 | 123.087 | 55.083
FE Clone $(\alpha=0.001)$ | 100% | 249.742 | 116.423 | 5.080 | 1.631 | 107.720 | 40.658 | 117.200 | 46.227
FE Clear $(\alpha=0.001)$ | 100% | 258.762 | 124.280 | 5.080 | 2.159 | 196.200 | 188.685 | 184.200 | 110.659
SP Clone $(M=30)$ | 88% | 403.098 | 91.530 | 3.727 | 0.827 | 163.682 | 35.301 | 275.955 | 50.614
SP Clear $(M=30)$ | 100% | 236.300 | 134.572 | 4.200 | 4.021 | 139.680 | 102.347 | 184.440 | 65.614

This section evaluates the performance of the proposed approach. We
implemented the algorithm in C++ and executed it on a computer with an Intel
i7-7500U processor and 12GB of memory, running Ubuntu 18.04.2 64-bit.

We performed simulations in the environments shown in Figures 1 (_Office_), 4
(_H_), and 6 (_Spider_). This selection of environments is intended to provide
a variety common environmental traits. The H environment contains narrow
corridors, the Spider environment possesses numerous hard to reach areas, and
the Office environment is somewhat uniformly spread out, with a complex
boundary.

We generated solution strategies for these environments using both classes of
algorithms described thus far: those that utilize a fixed number of pursuers
and those that can vary the number of pursuers. In the former case, we
considered both web sampling (WS) and uniform random sampling (SO14) [35] and
varied the fixed number of robots between 2 and 5. In the latter case, we
considered all four combinations of expansion criterion (fixed effort (FE) or
stalled progress (SP)) and graph expansion method (clone pursuer (Clone) or
clear progress (Clear)).

For each of these scenarios, we executed 25 trials and recorded the
computation time in seconds, number of pursuers used in the returned solution,
as well as the total numbers of vertices and edges generated. Each experiment
was allotted 10 minutes of computation time; if no solution was produced in
that time, we considered the trial to be a failure. Failed trials are excluded
from the statistics, but it should be noted that if they were included, they
would contribute a run time of at least 10 minutes. The results, summarized
via the means $(\mu)$ and standard deviations $(\sigma)$, appear in Tables II,
I and III. A number of conclusions may be drawn from the results.

#### WS improves performance over SO14

First, in all of the tested environments, our WS method outperformed SO14 by a
wide margin. The smallest improvement in computation time occurred in the
Office environment, perhaps due to the uniform nature of the environment and
the complexity of the geometry calculations.

#### Clone and Clear appear to be complementary

For the simulations with a variable number of pursuers, we look to compare the
performance between the cloning method and the clear method when expanding a
graph. When using FE as the expansion criterion, the results are remarkably
similar between the two methods. At first glance, one may assume the cloning
method should outperform the clearing method due to the larger amount of
information the graph contains. This however, is not always the case, because
an increased number of vertices means an increased amount of time to add each
new sample, due to the propagation of reachable labels across the graph. When
SP was the expansion criterion, clearing has a faster computation time, but
also a much higher mean and standard deviation for the number of pursuers. It
was often the case that SP with clearing would return a trivial solution, as
the algorithm cleared a substantial amount of meaningful calculations
performed.

#### Allowing the number of pursuers to vary incurs only a modest
computational cost

Lastly, we compare the fixed number of pursuers using WS, to the variable
number of pursuers methods. For each environment, the run times of the
variable number of pursuers were within approximately a factor of 2 of that of
the fixed number of pursuers. A portion of this additional time comes from the
variable number of pursuers constructing a single pursuer graph, in
environments which all require at least 2 pursuers to solve.

Finally, for each environment, we refined all 25 solutions generated by WS
with 2 pursuers. The results are summarized in Table IV, which shows the mean
and standard deviation of the computation time (in seconds) along with the
length of the solution path (in meters) before and after it was refined. The
results show that this approach effectively and consistently reduces the path
lengths.

Table IV: Refinement results for the solutions produced by WS ($n=2$).

| comp | length | length
---|---|---|---
| time (s) | before (m) | after (m)
| $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
Office | 29.6 | 37.5 | 254.5 | 114.5 | 136.9 | 97.4
H | 6.4 | 5.6 | 256.5 | 109.4 | 100.0 | 31.7
Spider | 50.9 | 61.9 | 360.3 | 222.3 | 168.8 | 139.0

##  VII Conclusion

This paper presents a sampling-based algorithm for a visibility-based pursuit-
evasion problem that generates a joint motion strategy for a team of robots in
a polygonal environment. The three primary contributions are a novel sampling
strategy for this domain, an iterative algorithm for generating a joint motion
strategy for the pursuers, and a post-processing path-smoothing algorithm that
refines the strategy returned by the main algorithm. The algorithm was shown
to outperform existing techniques.

Future work might build upon the results in this paper. First, possibilities
remain for enhancing the post processing step. There remain a number of open
questions on how these kinds of path smoothing algorithms can be best applied
to the pursuit-evasion domain. Second, is the development of an anytime
algorithm that begins with an uninteresting solution —for example, one
utilizing enough pursuers to ensure that their visibility polygons fully cover
the environment— and attempts to work backwards, eliminating robots, by
searching for solutions in the reduced joint sub-space.

[sorting=nyt]

## References

  * [1] Jose J. Acevedo, Begoña C. Arrue, Ivan Maza and Anibal Ollero  “A Decentralized Algorithm for Area Surveillance Missions Using a Team of Aerial Robots with Different Sensing Capabilities”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2014
  * [2] Tauhidul Alam, Md Mahbubur Rahman, Leonardo Bobadilla and Brian Rapp  “Multi-Vehicle Patrolling with Limited Visibility and Communication Constraints”  In _Military Communications Conference_ , 2017, pp. 465–479
  * [3] R. Bellman  “Dynamic Programming”  Princeton, NJ: Princeton University Press, 1957
  * [4] Philip Dames, Pratap Tokekar and Vijay Kumar  “Detecting, localizing, and tracking an unknown number of moving targets using a team of mobile robots”  In _International Journal of Robotics Research_ 36.13-14, 2017, pp. 1540–1553
  * [5] M. Duarte et al.  “Application of swarm robotics systems to marine environmental monitoring”  In _MTS/IEEE OCEANS - Shanghai_ , 2016  DOI: 10.1109/OCEANSAP.2016.7485429
  * [6] Matthew Dunbabin and Lino Marques  “Robots for Environmental Monitoring: Significant Advancements and Applications”  In _IEEE Robotics and Automation Magazine_ 19, 2012, pp. 24–39
  * [7] S.. Feng, S.. Han, K. Gao and J. Yu  “Efficient Algorithms for Optimal Perimeter Guarding”  In _Proc. Robotics: Science and Systems_ , 2019
  * [8] A. Ganguli, J. Cortes and F. Bullo  “Visibility-based multi-agent deployment in orthogonal environments”  In _2007 American Control Conference_ , 2007, pp. 3426–3431  DOI: 10.1109/ACC.2007.4283034
  * [9] B.. Gerkey, S. Thrun and G. Gordon  “Visibility-based Pursuit-evasion with Limited Field of View.”  In _International Journal of Robotics Research_ 25.4, 2006, pp. 299–315
  * [10] Livia Gregorin et al.  “Heuristics for the Multi-Robot Worst-Case Pursuit-Evasion Problem”  In _IEEE Access_ 5, 2017, pp. 17552–17566
  * [11] L.. Guibas et al.  “Visibility-Based Pursuit-Evasion in a Polygonal Environment”  In _International Journal on Computational Geometry and Applications_ 9.5, 1999, pp. 471–494
  * [12] Kris Hauser  “The Minimum Constraint Removal Problem with Three Robotics Applications”  In _International Journal of Robotics Research_ 33.1, 2014, pp. 5–17
  * [13] G. Hollinger, A. Kehagias and S. Singh  “Probabilistic Strategies for Pursuit in Cluttered Environments with Multiple Robots”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2007
  * [14] V. Isler, S. Kannan and S. Khanna  “Randomized pursuit-evasion in a polygonal environment”  In _IEEE Transactions on Robotics_ 21.5, 2005, pp. 875–884  DOI: 10.1109/TRO.2005.851373
  * [15] Volkan Isler et al.  “Finding and tracking targets in the wild: Algorithms and field deployments”  In _Proc. IEEE International Symposium on Safety, Security, and Rescue Robotics_ , 2015
  * [16] Francesco Bullo Joseph W.  “Distributed pursuit-evasion without mapping or global localization via local frontiers”  In _Autonomous Robots_ 32, 2012, pp. 81–95
  * [17] S. Karaman and E. Frazzoli  “Sampling-based Algorithms for Optimal Motion Planning”  In _International Journal of Robotics Research_ 30.7, 2011, pp. 846–894
  * [18] L.. Kavraki, P. Svestka, J.-C. Latombe and M.. Overmars  “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”  In _IEEE Transactions on Robotics and Automation_ 12.4, 1996, pp. 566–580
  * [19] A. Kolling and S. Carpin  “The GRAPH-CLEAR problem: definition, theoretical properties and its connections to multirobot aided surveillance”  In _2007 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2007, pp. 1003–1008  DOI: 10.1109/IROS.2007.4399368
  * [20] A. Kolling and S. Carpin  “Multi-robot pursuit-evasion without maps”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2010, pp. 3045–3051
  * [21] A. Krontiris and K.. Bekris  “Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-based Planner”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2016
  * [22] S.. LaValle and J.. Kuffner  “Rapidly-Exploring Random Trees: Progress and Prospects”  In _Proc. Workshop on the Algorithmic Foundations of Robotics_ , 2000
  * [23] J. Marble and K.. Bekris  “Asymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners”  In _IEEE Transactions on Robotics_ 29.2, 2013, pp. 432–444
  * [24] N. Mimmo, P. Bernard and L. Marconi  “Avalanche victim search via robust observers”  In _Proc. IEEE International Conference on Robotics and Automation_ , pp. 4066–4072  DOI: 10.1109/ICRA40945.2020.9196646
  * [25] S. Park, J. Lee and K. Chwa  “Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher”  In _Proc. International Colloquium on Automata, Languages and Programming_ Springer-Verlag, 2001, pp. 281–290
  * [26] S. Rajko and S.. LaValle  “A Pursuit-Evasion Bug Algorithm”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2001, pp. 1954–1960
  * [27] S. Sachs, S.. LaValle and S. Rajko  “Visibility-Based Pursuit-Evasion in an Unknown Planar Environment”  In _International Journal of Robotics Research_ 23.1, 2004, pp. 3–26  DOI: 10.1177/0278364904039610
  * [28] Florian Shkurti and Gregory Dudek  “On the complexity of searching for an evader with a faster pursuer”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2013, pp. 4062–4067  DOI: 10.1109/ICRA.2013.6631150
  * [29] Florian Shkurti and Gregory Dudek  “Topologically distinct trajectory predictions for probabilistic pursuit”  In _Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2017, pp. 5653–5660  DOI: 10.1109/IROS.2017.8206454
  * [30] Florian Shkurti, Nikhil Kakodkar and Gregory Dudek  “Model-Based Probabilistic Pursuit via Inverse Reinforcement Learning”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2018, pp. 7804–7811  DOI: 10.1109/ICRA.2018.8463196
  * [31] T. Siméon, J.-P. Laumond, J. Cortés and A. Sahbani  “Manipulation Planning with Probabilistic Roadmaps”  In _International Journal of Robotics Research_ , 2004
  * [32] K. Solovey, O. Salzman and D. Halperin  “Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-Robot Motion Planning”  In _Proc. Workshop on the Algorithmic Foundations of Robotics_ , 2014
  * [33] N.. Stiffler and J.. O’Kane  “Visibility-Based Pursuit-Evasion with Probabilistic Evader Models”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2011, pp. 4254–4259
  * [34] N.. Stiffler and J.. O’Kane  “A Complete Algorithm for Visibility-Based Pursuit-Evasion with Multiple Pursuers”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2014, pp. 1660–1667
  * [35] N.. Stiffler and J.. O’Kane  “A Sampling Based Algorithm for Multi-Robot Visibility-Based Pursuit-Evasion”  In _Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2014, pp. 1782–1789
  * [36] N.. Stiffler and J.. O’Kane  “Pursuit-Evasion with Fixed Beams”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2016, pp. 4251–4258
  * [37] N.. Stiffler and J.. O’Kane  “Complete and Optimal Visibility-Based Pursuit-Evasion”  In _International Journal of Robotics Research_ 36, 2017, pp. 923–946
  * [38] I. Suzuki and M. Yamashita  “Searching for a Mobile Intruder in a Polygonal Region”  In _SIAM Journal on Computing_ 21.5, 1992, pp. 863–888
  * [39] Kshitij Tiwari and Nak Young Chong  “Multi-robot Exploration for Environmental Monitoring: The Resource Constrained Perspective”  Academic Press, 2019
  * [40] Pratap Tokekar, Deepak Bhadauria, Andrew Studenski and Volkan Isler  “A Robotic System for Monitoring carp in Minnesota Lakes”  In _Journal of Field Robotics_ 27.3, 2010, pp. 681–685
  * [41] B. Tovar and S.. LaValle  “Visibility-based Pursuit-Evasion with Bounded Speed”  In _International Journal of Robotics Research_ 27, 2008, pp. 1350–1360
  * [42] G. Wagner, M. Kang and H. Choset  “Probabilistic Path Planning for Multiple Robots with Subdimensional Expansion”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2012
  * [43] Marios Xanthidis, Joel M. Esposito, Ioannis Rekleitis and Jason M. O’Kane  “Motion Planning by Sampling in Subspaces of Progressively Increasing Dimension”  In _Journal of Intelligent and Robotic Systems_ , 2020


anyonic string-particle braiding has only been appreciated more recently in
the context of 3+1D fractional topological insulators [95, 96].

In 1+1D Bose-Fermi correspondences are found in the conventional way, but
there is much less exploration with regards to relativistic statistical
transmutation in this context. A potential route is the connection between
local chiral and singular gauge transformations [97], which signals, as
expected, a deep interplay with quantum anomalies.

Large Gauge = Local Chiral = Composite Dual Transformations

There is a suggestive connection between “twisting” and “chirality” in the
context of relativistic fermions. In fact, as shown by Fosco and Schaposnik
[97], both the local chiral and large gauge transformations can decouple a
gauge field because they are equivalent. In addition, we now understand that
the large gauge transformation is also a composite particle duality, meaning
that fermions in the presence of a theta terms can be re-expressed as free
dyons. In other words

$\psi_{C}(x)=\mathcal{W}^{\dagger}(x)\psi(x)=\psi^{\prime}(x)\;.$ (134)

As stated, the effect of a large gauge transformation generated by the dual
field $\tilde{\theta}$ defined by
$\partial^{\mu}\tilde{\theta}=\epsilon^{\mu\nu}\partial_{\nu}\theta$ is
equivalent to the local chiral transformation generated by the regular field
$\theta$. This implies that a gauge coupling term of the form

$q\bar{\psi}\gamma^{\mu}\partial_{\mu}[\tilde{\theta}(t,x)+\gamma_{5}\theta(t,x)]\psi=0\
$ (135)

vanishes. This equation becomes evident by noticing that the Levi-Civita
symbol is, in fact, a pseudo-tensor that in 1+1D can be expressed as a
2$\times$2 matrix, so that

$\epsilon_{\mu\nu}\partial^{\nu}\theta=\begin{pmatrix}0&1\\\
-1&0\end{pmatrix}\begin{pmatrix}-1&0\\\
0&1\end{pmatrix}\begin{pmatrix}\partial_{0}\\\
\partial_{1}\end{pmatrix}\,\theta=\hat{\sigma}^{x}\begin{pmatrix}\partial_{0}\\\
\partial_{1}\end{pmatrix}\,\theta=-\gamma_{5}\begin{pmatrix}\partial_{0}\\\
\partial_{1}\end{pmatrix}\,\theta\;.$ (136)

Notice that these fields are similar to Goldstone-Wilczek scalar mass fields,
but here they are “gauge mass fields” that mutually cancel. In 1+1D a gauge
field can always be expressed as the sum of longitudinal and transverse
components, but it can also be written as a pure gauge containing trivial and
topologically non-trivial parts

$a_{\mu}(t,x)=\partial_{\mu}\varphi(t,x)-\epsilon_{\mu\nu}\partial^{\nu}\theta(t,x)=\partial_{\mu}\big{[}\varphi(t,x)+\tilde{\theta}(t,x)\big{]}\;.$
(137)

This implies that for a non-null electric field $f_{10}$ we find

$\epsilon^{\mu\nu}\partial_{\mu}a_{\nu}=\epsilon^{\mu\nu}\partial_{\mu}\partial_{\nu}\tilde{\theta}(t,x)\neq
0\;,$ (138)

so $\tilde{\theta}$ is a singular pure gauge. For a massless fermion in a
$\text{U}(1)$ dynamical gauge field

$\mathcal{L}=-\frac{1}{4}f_{\mu\nu}f^{\mu\nu}+i\bar{\psi}\gamma^{\mu}D_{\mu}\psi\;,$
(139)

the system presents a chiral anomaly (even for a background gauge field),
namely $\partial_{\mu}j^{\mu}_{5}=\frac{q}{2\pi}\epsilon^{\mu\nu}f_{\mu\nu}$.
A local chiral transformation of the form

$\psi^{\prime}(t,x)=e^{-i\alpha(t,x)\gamma_{5}}\,\psi(t,x)$ (140)

removes the gauge field from Lagrangian

$\mathcal{L}^{\prime}=-\frac{1}{4}f_{\mu\nu}f^{\mu\nu}+i\bar{\psi}^{\prime}\gamma^{\mu}\partial_{\mu}\psi^{\prime}\;,$
(141)

at the expense of changing the path integral measure

$[\mathcal{D}\psi][\mathcal{D}\bar{\psi}]=[\mathcal{D}\psi^{\prime}][\mathcal{D}\bar{\psi}^{\prime}]\,e^{i\frac{q^{2}}{2\pi}\int
dtdx\;\alpha(t,x)\,\epsilon^{\mu\nu}f_{\mu\nu}}=[\mathcal{D}\psi^{\prime}][\mathcal{D}\bar{\psi}^{\prime}]\,e^{2im\int
dtdx\;\alpha(t,x)\,\bar{\psi}\gamma_{5}\psi}$ (142)

yielding an effective theta term. This must be the case, otherwise, the local
chiral transformation would transform the Schwinger model (or
$\text{QED}_{2}$) in a theory of decoupled massless fermions and photons.
However, it is known that such a theory is confining, meaning that there is a
mass gap. In other words, Schwinger photons acquire a mass $m=q/\sqrt{\pi}$
through dynamical chiral symmetry breaking, so it cannot be equivalent to a
theory with massless photons. This is precisely captured by the change of the
path integral measure. Furthermore, when a fermionic mass term
$m\bar{\psi}\psi$ is incorporated, the axial current is not conserved,
yielding $\partial_{\mu}j^{\mu}_{5}=2mi\bar{\psi}\gamma_{5}\psi$. the
corresponding mass term transforms like

$m\bar{\psi}\psi=2im\alpha(t,x)\bar{\psi}^{\prime}\gamma_{5}\psi^{\prime}\;.$
(143)

On the other hand, a local theta term can be introduced (or removed) in the
system by means of a large gauge transformation

$\psi^{\prime}(t,x)=e^{-i\tilde{\theta}(t,x)}\,\psi(t,x)\;.$ (144)

In 1+1D, this amounts to adding or subtracting a background electric field.
Alternatively, in an Euclidean ring, this is adding or removing local flux
through the ring. We thus see, a mass breaks chiral symmetry, and a background
gauge field also breaks chiral symmetry. In a sense “gauge mass” and “physical
mass” have an equivalent effect. A theta term can be thought of as a chiral
background gauge field $q\bar{\psi}\gamma^{\mu}\gamma_{5}a_{\mu}^{5}\psi$,
which nows plays the role of a chiral gauge mass. Trying to remove a
background gauge field through a chiral transformation introduces a theta
term, and such a theta term can be transformed upon chiral transformation.

## References

  * Valentí-Rojas  _et al._ [2023] G. Valentí-Rojas, A. J. Baker, A. Celi, and P. Öhberg, Phys. Rev. Res. 5, 023128 (2023).
  * Leinaas and Myrheim [1977] J. M. Leinaas and J. Myrheim, Il Nuovo Cimento B (1971-1996) 37, 1 (1977).
  * Polyakov [1988] A. M. Polyakov, Modern Physics Letters A 3, 325 (1988).
  * Schonfeld [1981] J. F. Schonfeld, Nucl. Phys. B 185, 157 (1981).
  * Deser  _et al._ [1982] S. Deser, R. Jackiw, and S. Templeton, Ann. Phys. 140, 372 (1982).
  * Tsui  _et al._ [1982] D. C. Tsui, H. L. Stormer, and A. C. Gossard, Phys. Rev. Lett. 48, 1559 (1982).
  * Laughlin [1983] R. B. Laughlin, Phys. Rev. Lett. 50, 1395 (1983).
  * Girvin and MacDonald [1987] S. Girvin and A. H. MacDonald, Phys. Rev. Lett. 58, 1252 (1987).
  * Zhang  _et al._ [1989] S. C. Zhang, T. H. Hansson, and S. Kivelson, Phys. Rev. Lett. 62, 82 (1989).
  * Read [1989] N. Read, Phys. Rev. Lett. 62, 86 (1989).
  * Hasenfratz and ’t Hooft [1976] P. Hasenfratz and G. ’t Hooft, Phys. Rev. Lett. 36, 1119 (1976).
  * Goldhaber [1976] A. S. Goldhaber, Phys. Rev. Lett. 36, 1122 (1976).
  * Lieb [1965] D. M. E. Lieb, Journal of Mathematical Physics 6, 304 (1965).
  * Luther and Emery [1974] A. Luther and V. J. Emery, Phys. Rev. Lett. 33, 589 (1974).
  * Haldane [1981] F. Haldane, Journal of Physics C: Solid State Physics 14, 2585 (1981).
  * Mandelstam [1975] S. Mandelstam, Phys. Rev. D 11, 3026 (1975).
  * Coleman [1975] S. Coleman, Phys. Rev. D 11, 2088 (1975).
  * Jackiw and Rebbi [1976] R. Jackiw and C. Rebbi, Phys. Rev. Lett. 36, 1116 (1976).
  * Su  _et al._ [1979] W. P. Su, J. R. Schrieffer, and A. J. Heeger, Phys. Rev. Lett. 42, 1698 (1979).
  * Goldstone and Wilczek [1981] J. Goldstone and F. Wilczek, Phys. Rev. Lett. 47, 986 (1981).
  * Su and Schrieffer [1981] W. P. Su and J. R. Schrieffer, Phys. Rev. Lett. 46, 738 (1981).
  * Blankenbecler and Boyanovsky [1985] R. Blankenbecler and D. Boyanovsky, Phys. Rev. D 31, 2089 (1985).
  * Jackiw and Pi [2007] R. Jackiw and S.-Y. Pi, Phys. Rev. Lett. 98, 266402 (2007).
  * Chamon  _et al._ [2008a] C. Chamon, C.-Y. Hou, R. Jackiw, C. Mudry, S.-Y. Pi, and G. Semenoff, Phys. Rev. B 77, 235431 (2008a).
  * Chamon  _et al._ [2008b] C. Chamon, C.-Y. Hou, R. Jackiw, C. Mudry, S.-Y. Pi, and A. P. Schnyder, Phys. Rev. Lett. 100, 110405 (2008b).
  * Moessner and Moore [2021] R. Moessner and J. E. Moore,  _Topological phases of matter_ (Cambridge University Press, 2021).
  * Fradkin [2013] E. Fradkin,  _Field Theories of Condensed Matter Physics_, 2nd ed. (Cambridge University Press, 2013).
  * Valentí-Rojas  _et al._ [2020] G. Valentí-Rojas, N. Westerberg, and P. Öhberg, Phys. Rev. Research 2, 033453 (2020).
  * Wilczek [1982a] F. Wilczek, Phys. Rev. Lett. 48, 1144 (1982a).
  * Wilczek [1982b] F. Wilczek, Phys. Rev. Lett. 49, 957 (1982b).
  * Ezawa [2013] Z. F. Ezawa,  _Quantum Hall effects: Recent theoretical and experimental developments_, 3rd ed. (World Scientific Publishing Company, 2013).
  * Jain [2007] J. K. Jain,  _Composite fermions_ (Cambridge University Press, 2007).
  * Note [1] Here $\tilde{\mathcal{U}}$ is simply used to indicate that it is a particular case of the general case $\mathcal{U}$. This is merely a stylistic point.
  * Kadanoff and Ceva [1971] L. P. Kadanoff and H. Ceva, Phys. Rev. B 3, 3918 (1971).
  * Hasenfratz [1979] P. Hasenfratz, Physics Letters B 85, 338 (1979).
  * Fradkin [2017] E. Fradkin, Journal of Statistical Physics 167, 427 (2017).
  * Marino [2017] E. C. Marino,  _Quantum field theory approach to condensed matter physics_ (Cambridge University Press, 2017).
  * Note [2] We emphasise once again that such a transformation can be defined without any reference to it being a gauge transformation, but merely a local canonical transformation.
  * Note [3] Here we are not debating whether they transmute to anyons or only to fermions/bosons. The specific statistical nature of the composite fields will depend on dimensionality and locality, but the ability to go from bare to composite will not.
  * Zhang [1995] S. C. Zhang, in  _Low-Dimensional Quantum Field Theories for Condensed Matter Physicists_ (World Scientific, 1995) pp. 191–224.
  * Note [4] This is a Physicist’s proof and unlikely to satisfy a Mathematician’s standards by any means.
  * Le Guillou  _et al._ [1996] J. C. Le Guillou, C. Núñez, and F. A. Schaposnik, Annals of Physics 251, 426 (1996).
  * Fradkin and Schaposnik [1994] E. Fradkin and F. A. Schaposnik, Physics Letters B 338, 253 (1994).
  * Frohlich  _et al._ [1995] J. Frohlich, R. Gotschmann, and P. A. Marchetti, Journal of Physics A: Mathematical and General 28, 1169 (1995).
  * Burgess and Quevedo [1994] C. Burgess and F. Quevedo, Nuclear Physics B 421, 373 (1994).
  * Burgess  _et al._ [1994] C. Burgess, C. Lütken, and F. Quevedo, Physics Letters B 336, 18 (1994).
  * Schaposnik [1995] F. Schaposnik, Physics Letters B 356, 39 (1995).
  * Fosco and Schaposnik [2018] C. D. Fosco and F. A. Schaposnik, Physics Letters B 782, 224 (2018).
  * Schaposnik [1998] F. A. Schaposnik, AIP Conference Proceedings 419, 151 (1998).
  * Banerjee and Marino [1997] R. Banerjee and E. Marino, Nuclear Physics B 507, 501 (1997).
  * Chan  _et al._ [2013] A. Chan, T. L. Hughes, S. Ryu, and E. Fradkin, Phys. Rev. B 87, 085132 (2013).
  * Cirio  _et al._ [2014] M. Cirio, G. Palumbo, and J. K. Pachos, Phys. Rev. B 90, 085114 (2014).
  * Note [5] We notice that it is in itself remarkable that there exist results in even spacetime dimensions. It is often mentioned in literature that it only makes sense to talk about fractional quantum Hall effect in 2d, 4d, 6d and so on. We challenge that view.
  * Schwinger [1966] J. Schwinger, Phys. Rev. 144, 1087 (1966).
  * Schwinger [1968] J. Schwinger, Phys. Rev. 173, 1536 (1968).
  * Schwinger [1969] J. Schwinger, Science 165, 757 (1969).
  * Witten [1979] E. Witten, Physics Letters B 86, 283 (1979).
  * Wang  _et al._ [2015] J. Wang, B. Lian, X.-L. Qi, and S.-C. Zhang, Phys. Rev. B 92, 081107 (2015).
  * Note [6] The axion and BF terms coincide in 1+1D. If not subsidised with further dynamics, the axion field decouples from matter and does not play other role than a constant background.
  * Note [7] These defects can, in principle, live freely in the system. Here, we consider the case in which they couple and bind to matter.
  * Marino [1993] E. C. Marino, Nucl. Phys. B 408, 551 (1993).
  * Kleinert [1989] H. Kleinert,  _Gauge fields in condensed matter_, Vol. 2 (World Scientific, 1989).
  * Fradkin [2021] E. Fradkin,  _Quantum field theory: an integrated approach_ (Princeton University Press, 2021).
  * Karch and Tong [2016a] A. Karch and D. Tong, Phys. Rev. X 6, 031043 (2016a).
  * Karch  _et al._ [2019] A. Karch, D. Tong, and C. Turner, SciPost Phys. 7, 7 (2019).
  * Note [8] This should be considered as opposed to more conventional Maxwell-like theories with propagating modes that exist even in the absence of matter, namely photons. There is no free photons in the theories proposed.
  * Note [9] It is important to distinguish this operator from conventional disorder (i.e. kink, vortex, monopole) operators we find in conventional literature.
  * Horvathy and Zhang [2009] P. A. Horvathy and P. Zhang, Physics Reports 481, 83 (2009).
  * Kou  _et al._ [2008] S.-P. Kou, M. Levin, and X.-G. Wen, Phys. Rev. B 78, 155134 (2008).
  * Olesen  _et al._ [2015] T. Olesen, N. D. Vlasii, and U.-J. Wiese, Annals of physics 361, 303 (2015).
  * Freedman  _et al._ [2004] M. Freedman, C. Nayak, K. Shtengel, K. Walker, and Z. Wang, Annals of Physics 310, 428 (2004).
  * Note [10] An example can be Cooper-pairing like terms such as $\hat{c}_{\mathbf{j}}\hat{c}_{\mathbf{j}}$ or $\hat{c}^{\dagger}_{\mathbf{j}}\hat{c}^{\dagger}_{\mathbf{j}}$.
  * Shankar [2017] R. Shankar,  _Quantum field theory and condensed matter: An introduction_ (Cambridge University Press, 2017).
  * Sachdev [1999] S. Sachdev, Physics world 12, 33 (1999).
  * Note [11] This is because $\hat{\sigma}^{x}=\hat{c}^{\dagger}+\hat{c}\tmspace+{.2777em}$, which is highly non-local. Alternatively, we can consider a non-rotated Jordan-Wigner transformation but a rotated Ising model $\hat{H}^{\prime}=-J\sumop\kp@slimits_{j}\hat{\sigma}^{z}_{j}-J\gamma\sumop\kp@slimits_{j}\hat{\sigma}^{x}_{j}\hat{\sigma}^{x}_{j+1}\,$ [98].
  * Note [12] This is not the case for conventional gauge fields like the one in quantum electrodynamics as there are non-trivial solutions even in the absence of matter.
  * Frölian  _et al._ [2022] A. Frölian, C. S. Chisholm, E. Neri, C. R. Cabrera, R. Ramos, A. Celi, and L. Tarruell, Nature 608, 293 (2022).
  * Kwan  _et al._ [2023] J. Kwan, P. Segura, Y. Li, S. Kim, A. V. Gorshkov, A. Eckardt, B. Bakkali-Hassani, and M. Greiner, arXiv preprint 10.48550/arXiv.2306.01737 (2023).
  * Note [13] We expect the differences to be analogous, for instance, to those between the Dirac and the ’t Hooft-Polyakov monopoles.
  * Note [14] In the models in which this is allowed.
  * Valiente [2020] M. Valiente, Phys. Rev. A 102, 053304 (2020).
  * Valiente [2021] M. Valiente, Phys. Rev. A 103, L021302 (2021).
  * Savit [1980] R. Savit, Rev. Mod. Phys. 52, 453 (1980).
  * Shapere and Wilczek [1989] A. Shapere and F. Wilczek, Nuclear Physics B 320, 669 (1989).
  * Kapustin and Seiberg [2014] A. Kapustin and N. Seiberg, Journal of High Energy Physics 2014, 1 (2014).
  * Seiberg  _et al._ [2016] N. Seiberg, T. Senthil, C. Wang, and E. Witten, Annals of Physics 374, 395 (2016).
  * Karch and Tong [2016b] A. Karch and D. Tong, Phys. Rev. X 6, 031043 (2016b).
  * Murugan and Nastase [2021] J. Murugan and H. Nastase, arXiv preprint 10.48550/arXiv.2103.12667 (2021).
  * Fustero  _et al._ [1989] X. Fustero, R. Gambini, and A. Trias, Phys. Rev. Lett. 62, 1964 (1989).
  * Kleinert [2008] H. Kleinert, AIP Conference Proceedings 966, 293 (2008).
  * Lüders and Zumino [1958] G. Lüders and B. Zumino, Phys. Rev. 110, 1450 (1958).
  * Baez  _et al._ [2007] J. C. Baez, A. S. Crans, and D. K. Wise, Advances in Theoretical and Mathematical Physics 11, 707 (2007).
  * Balachandran  _et al._ [1987] A. Balachandran, H. Gomm, and R. Sorkin, Nuclear Physics B 281, 573 (1987).
  * Forte [1991] S. Forte, Physics Letters B 253, 403 (1991).
  * Ye and Gu [2015] P. Ye and Z.-C. Gu, Phys. Rev. X 5, 021029 (2015).
  * Wang  _et al._ [2019] Q.-R. Wang, M. Cheng, C. Wang, and Z.-C. Gu, Phys. Rev. B 99, 235137 (2019).
  * Fosco and Schaposnik [2000] C. Fosco and F. Schaposnik, Physics Letters B 477, 341 (2000).
  * Kogut [1979] J. B. Kogut, Rev. Mod. Phys. 51, 659 (1979).


# A note on the invertibility of oriented graphs

Natalie Behague Mathematics institute, University of Warwick, Coventry, UK.
Email<EMAIL_ADDRESS>Supported by a PIMS postdoctoral fellowship while at
the University of Victoria. Tom Johnston School of Mathematics, University of
Bristol, Bristol, BS8 1UG, UK and Heilbronn Institute for Mathematical
Research, Bristol, BS8 1UG, UK. Email<EMAIL_ADDRESS>Natasha
Morrison33footnotemark: 3 Department of Mathematics and Statistics, University
of Victoria, Canada.Research supported by NSERC Discovery Grant
RGPIN-2021-02511 and NSERC Early Career Supplement DGECR-2021-00047. Email:
<EMAIL_ADDRESS>Shannon Ogden33footnotemark: 3 Supported by NSERC CGS M and
NSERC Vanier CGS. Email<EMAIL_ADDRESS>
###### Abstract

For an oriented graph $D$ and a set $X\subseteq V(D)$, the inversion of $X$ in
$D$ is the graph obtained from $D$ by reversing the orientation of each edge
that has both endpoints in $X$. Define the inversion number of $D$, denoted
$\operatorname{inv}(D)$, to be the minimum number of inversions required to
obtain an acyclic oriented graph from $D$. We show that
$\operatorname{inv}({D_{1}\rightarrow D_{2}})>\operatorname{inv}(D_{1})$, for
any oriented graphs $D_{1}$ and $D_{2}$ such that
$\operatorname{inv}(D_{1})=\operatorname{inv}(D_{2})\geq 1$. This resolves a
question of Aubian, Havet, Hörsch, Klingelhoefer, Nisse, Rambaud and Vermande.
Our proof proceeds via a natural connection between the graph inversion number
and the subgraph complementation number.

##  1 Introduction

Given an oriented graph $D$ and a set $X\subseteq V(D)$, the _inversion_ of
$X$ in $D$ is the oriented graph obtained from $D$ by reversing the
orientation of each edge that has both endpoints in $X$. In this case, we say
that we _invert_ $X$ in $D$. Given a family of sets $X_{1},...,X_{k}\subseteq
V(D)$, the _inversion_ of $X_{1},...,X_{k}$ in $D$ is the oriented graph
obtained by inverting each set in turn: inverting $X_{1}$ in $D$, then $X_{2}$
in the resulting oriented graph, and so on. Note that the order in which we
perform these inversions does not impact the final oriented graph.

If inverting $X_{1},...,X_{k}$ in $D$ produces an acyclic oriented graph, then
these sets form a _decycling family_ of $D$. The inversion number was
introduced by Belkechine [4] and early results on the topic were obtained by
Belkechine, Bouaziz, Boudabbous and Pouzet [5].

Given oriented graphs $D_{1}$ and $D_{2}$, the _dijoin_ from $D_{1}$ to
$D_{2}$, denoted by $D_{1}\rightarrow D_{2}$ is the oriented graph constructed
from vertex-disjoint copies of $D_{1}$ and $D_{2}$ by adding all edges $uv$
where $u\in V(D_{1})$ and $v\in V(D_{2})$. Bang-Jensen, Costa Ferreira da
Silva and Havet [3] observed that if $D_{1}$ and $D_{2}$ are oriented graphs
then $\operatorname{inv}(D_{1}\rightarrow
D_{2})\leq\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})$, and
conjectured that equality holds for all $D_{1},D_{2}$. They proved that the
conjecture holds if $\operatorname{inv}(D_{1})=\operatorname{inv}(D_{2})=1$.

However, this conjecture was shown to be false by two simultaneous papers [1,
2]. The authors of [2] provide a whole family of counterexamples, showing that
for every odd $k\geq 3$ there is a tournament $D_{1}$ with
$\operatorname{inv}(D_{1})=k$ such that for any oriented graph $D_{2}$ with
$\operatorname{inv}(D_{2})\geq 1$, we have
$\operatorname{inv}(D_{1}\rightarrow
D_{2})\leq\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})-1$. Thus the
trivial upper bound on the inversion number of a dijoin is not always tight.

For a trivial lower bound, it is easy to see that
$\operatorname{inv}(D_{1}\rightarrow
D_{2})\geq\max\\{\operatorname{inv}(D_{1}),\operatorname{inv}(D_{2})\\}$. As a
first step towards investigating the tightness of this lower bound, Aubian,
Havet, Hörsch, Klingelhoefer, Nisse, Rambaud and Vermande asked the following
question.

######  Question 1.1 ([2, Problem 5.5]).

Does there exist a non-acyclic oriented graph $D$ such that

$\operatorname{inv}(D\rightarrow D)=\operatorname{inv}(D)?$

We answer this question in the negative. In fact, we prove the following
slightly more general result.

######  Theorem 1.2.

Let $D_{1}$ and $D_{2}$ be oriented graphs such that
$\operatorname{inv}(D_{1})=\operatorname{inv}(D_{2})\geq 1$. Then
$\operatorname{inv}({D_{1}\rightarrow D_{2}})>\operatorname{inv}(D_{1})$.

In order to prove this theorem, we use a natural connection between the
subgraph complementation number, as studied by Buchanan, Purcell and Rombach
in [6], and the inversion number, which we believe may be useful in future
research on this topic. This allows us to deduce that the inversion number of
a digraph $D$ is either $\operatorname{tmr}(D)$ or $\operatorname{tmr}(D)+1$,
where $\operatorname{tmr}(D)$ is the minimum rank across a family of matrices
(see Section 3). The same connection is made in [7], however we are able to
classify when $\operatorname{inv}(D)=\operatorname{tmr}(D)+1$, which is a
vital ingredient in our proof. We discuss this further in Section 3, after
first noting some easy observations in Section 2. We prove Theorem 1.2 in
Section 4. Some open problems and conjectures are given in Section 5.

##  2 Preliminaries

In this section, we recall some definitions and notation pertaining to
oriented graphs, and present some basic results on the inversion number of
oriented graphs, which will be useful in later sections. We begin with the
following simple observation.

Recall that an _oriented_ graph (or _digraph_) is a pair $D=(V,E)$, where $V$
is a collection of vertices and $E$ is a collection of ordered subsets of
$V^{(2)}$. For $u,v\in V$, we write $uv$ to denote the _edge oriented (or
directed) from u to v_. We restrict our attention to _simple_ oriented graphs,
that is, for each $u\not=v\in V$, at most one of $uv$ and $vu$ is present in
$E$. A _tournament_ is an oriented graph where exactly one of $uv$ and $vu$ is
present for all $u\not=v\in V$.

The _out-neighbourhood_ of a vertex $v$, denoted $N^{+}(v)$, is the set of all
vertices $u\in V$ such that $vu\in E$. The _in-neighbourhood_ of $v$, denoted
$N^{-}(v)$, is the set of all vertices $u\in V$ such that $uv\in E$. A vertex
$v$ is a _source_ if $N^{-}(v)$ is empty, and $v$ is a _sink_ if $N^{+}(v)$
empty.

######  Observation 2.1.

If $D_{1}\subseteq D_{2}$, then
$\operatorname{inv}(D_{1})\leq\operatorname{inv}(D_{2})$.

In addition, we have the following trivial upper bound on the inversion number
of an oriented graph.

######  Proposition 2.2.

For an oriented graph $D$ of order $n\geq 1$, $\operatorname{inv}(D)\leq n-1$.

###### Proof.

Let $V(D)=\\{1,...,n\\}$. For $1\leq i\leq n-1$, let
$X_{i}=N^{+}(i)\cup\\{i\\}\setminus\\{1,...,i-1\\}$. The inversion of
$X_{1},...,X_{n-1}$ in $D$ is the transitive tournament with edges $ij$ for
all $i>j$. ∎

The following result can help to reduce a problem about oriented graphs to a
problem about tournaments only.

######  Proposition 2.3.

For every oriented graph $D$, there is a tournament $D^{*}$ on the same vertex
set with $D\subseteq D^{*}$ and
$\operatorname{inv}(D^{*})=\operatorname{inv}(D)$.

###### Proof.

Let $k\coloneqq\operatorname{inv}(D)$. Let $T$ be the acyclic oriented graph
that is reached from $D$ after applying a decycling family
$X_{1},X_{2},\ldots,X_{k}$. There exists a transitive tournament $T^{*}$ on
the same vertex set with $T\subseteq T^{*}$. Inverting the sets
$X_{1},X_{2},\ldots,X_{k}$ in $T^{*}$ gives a tournament $D^{*}$ with
$D\subseteq D^{*}$. Clearly $\operatorname{inv}(D^{*})\leq k$ and so by
Observation 2.1, $\operatorname{inv}(D^{*})=k$. ∎

We conclude this section with two results that consider the effect that the
removal of a single vertex has on the inversion number of an oriented graph.

######  Proposition 2.4.

Let $D$ be an oriented graph on $n\geq 2$ vertices. If $v\in V(D)$ is a sink
or a source, then $\operatorname{inv}(D-v)=\operatorname{inv}(D)$.

###### Proof.

By 2.1, $\operatorname{inv}(D-v)\leq\operatorname{inv}(D)$. Now, since $v$ is
a sink or a source, a decycling family of $D-v$ is also a decycling family of
$D$. Hence, $\operatorname{inv}(D-v)\geq\operatorname{inv}(D)$. ∎

Given an oriented graph $D$, we say that $u,v\in V(D)$ are _twin_ vertices if
$N^{+}(u)\setminus\\{v\\}=N^{+}(v)\setminus\\{u\\}$ and
$N^{-}(u)\setminus\\{v\\}=N^{-}(v)\setminus\\{u\\}$.

######  Proposition 2.5.

Let $D$ be an oriented graph on $n\geq 2$ vertices. If $u,v\in V(D)$ are twin
vertices, then $\operatorname{inv}(D-v)=\operatorname{inv}(D)$.

###### Proof.

By 2.1, $\operatorname{inv}(D-v)\leq\operatorname{inv}(D)$. Now, suppose
$X_{1},...,X_{k}$ is a decycling family of $D-v$. For $1\leq i\leq k$, let
$Y_{i}=X_{i}$ if $u\notin X_{i}$, and $Y_{i}=X_{i}\cup\\{v\\}$ if $u\in
X_{i}$. Then $Y_{1},...,Y_{k}$ is a decycling family of $D$, and
$\operatorname{inv}(D-v)\geq\operatorname{inv}(D)$. ∎

##  3 Subgraph complementation and tournament minimum rank

###  3.1 Background on subgraph complementation

In our work we will make use of results from [6]. In order to state these
results, we first require the following definitions.

Given an (undirected) graph $G$ of order $n\geq 1$ and a set $X\subseteq
V(G)$, the _subgraph complementation_ of $X$ in $G$ is the graph obtained from
$G$ by complementing the edges in $G[X]$. In this case, we say that we
_complement_ $X$ in $G$. Given a family of sets $X_{1},...,X_{k}\subseteq
V(G)$, the _subgraph complementation_ of $X_{1},...,X_{k}$ in $G$ is the graph
obtained by complementing each set in turn: complementing $X_{1}$ in $G$, then
$X_{2}$ in the resulting graph, and so on. Note that the order in which we
perform these subgraph complementations does not impact the final graph.

If complementing $X_{1},...,X_{k}$ in $G$ results in the empty graph
$\overline{K_{n}}$, then these sets form a _subgraph complementing system_ of
$G$. The _subgraph complementation number_ of $G$, denoted by $c_{2}(G)$, is
the minimum number of sets in a subgraph complementing system of $G$.

Note that $\mathcal{F}$ is a subgraph complementing system of $G$ if and only
if each pair of adjacent vertices appears together in an odd number of sets in
$\mathcal{F}$, while each pair of non-adjacent vertices appears together in an
even number of sets in $\mathcal{F}$.

Let $\mathcal{M}(G)$ be the collection of all $n\times n$ matrices with
entries in $\\{0,1\\}$ that can be obtained from the adjacency matrix111Recall
that the _adjacency matrix_ of $G$, denoted $A(G)$, is the $n\times n$ matrix
such that $A_{i,j}=1$ whenever $ij\in E(G)$ and 0 otherwise. of $G$ by
altering diagonal entries. In this paper the rank of a matrix is always taken
over $\mathbb{F}_{2}$ and we will refer to the rank of a matrix taken over
$\mathbb{F}_{2}$ as simply the rank. Define the _minimum rank_ of a graph $G$,
denoted by $\operatorname{mr}(G)$, to be the minimum rank of a matrix in
$\mathcal{M}(G)$.

Buchanan, Purcell, and Rombach [6] showed that the quantities
$\operatorname{mr}(G)$ and $c_{2}(G)$ cannot differ by more than $1$. In
addition, they characterized the graphs for which they differ.

######  Lemma 3.1 ([6] Corollary 4.7 and Theorem 4.12).

Let $G$ be a graph. Then either

  1. 1.

$c_{2}(G)=\operatorname{mr}(G)$, or

  2. 2.

$c_{2}(G)=\operatorname{mr}(G)+1$, in which case $\operatorname{mr}(G)$ is
even.

Moreover, if $G$ is non-empty then $c_{2}(G)=\operatorname{mr}(G)+1$ if and
only if the unique matrix $M\in\mathcal{M}(G)$ of minimum rank has all
diagonal entries equal to zero.

Although it will not be directly relevant for our application of the result,
the interested reader might like to know that the proof of Lemma 3.1 uses an
equivalent form of the problem. A $d$-dimensional _faithful orthogonal
representation_ of a graph $G$ over the field $\mathbb{F}_{2}$ is a function
$\phi:V(G)\rightarrow\mathbb{F}_{2}^{d}$ where non-adjacent vertices are
assigned orthogonal vectors; that is, $\phi(u)\cdot\phi(v)=0$ for all
$uv\notin E(G)$, and adjacent vertices are assigned non-orthogonal vectors;
that is, $\phi(u)\cdot\phi(v)=1$. The $d$-dimensional faithful orthogonal
representations of $G$ over $\mathbb{F}_{2}$ are in bijective correspondence
with the subgraph complementation systems of $G$, where a representation
$\phi$ corresponds to the system $\\{X_{1},...,X_{d}\\}$ with $v\in V(G)$
included in $X_{i}$ if and only if the $i$th entry of $\phi(v)$ is $1$.

This approach bears a strong similarity to the analysis used in [2] to prove
that for every odd $k\geq 3$ there is a tournament $D_{1}$ with
$\operatorname{inv}(D_{1})=k$ such that for any oriented graph $D_{2}$ with
$\operatorname{inv}(D_{2})\geq 1$, we have
$\operatorname{inv}(D_{1}\rightarrow
D_{2})\leq\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})-1$.

###  3.2 Tournament minimum rank

Suppose $D$ is a tournament on $n$ vertices and $T$ is a transitive tournament
on the same vertex set. Let $G_{D,T}$ be the (undirected) graph on the same
vertex set as $D$ with edge $ij$ present if and only if the edge between
vertices $i$ and $j$ has opposite orientations in $D$ and $T$. Clearly, a
series of inversions that takes $D$ to $T$ corresponds exactly to a subgraph
complementing system of $G_{D,T}$.

Let $\mathcal{T}$ be the collection of all (labelled) $n$-vertex transitive
tournaments and define

$\mathcal{M}^{*}(D)=\bigcup_{T\in\mathcal{T}}\mathcal{M}(G_{D,T}).$

Define the _tournament minimum rank_ of a tournament $D$, denoted
$\operatorname{tmr}(D)$, as:

$\operatorname{tmr}(D):=\\{\operatorname{mr}(M):M\in\mathcal{M}^{*}(D)\\}.$

The following result is a direct consequence of Lemma 3.1 and provides a
useful relationship between $\operatorname{inv}(D)$ and
$\operatorname{tmr}(D)$.

######  Corollary 3.2 (Corollary to Lemma 3.1).

Let $D$ be a tournament. Then either

  1. 1.

$\operatorname{inv}(D)=\operatorname{tmr}(D)$, or

  2. 2.

$\operatorname{inv}(D)=\operatorname{tmr}(D)+1$, in which case
$\operatorname{tmr}(D)$ is even.

Moreover, if $D$ is not transitive, then
$\operatorname{inv}(D)=\operatorname{tmr}(D)+1$ if and only if every matrix
$M\in\mathcal{M}^{*}(D)$ with minimum rank has every diagonal entry equal to
zero.

###### Proof.

Let $T$ be an $n$-vertex transitive tournament. If transforming $D$ into $T$
requires $\ell$ inversions, then $c_{2}(G_{D,T})=\ell$. So, by definition of
the inversion number,

$\operatorname{inv}(D)=\min_{T\in\mathcal{T}}c_{2}(G_{D,T}).$

Hence, by Lemma 3.1 and the definition of minimum tournament rank, either

$\operatorname{inv}(D)=\min_{T\in\mathcal{T}}\operatorname{mr}(G_{D,T})=\operatorname{tmr}(D),$

or $\operatorname{inv}(D)=\operatorname{tmr}(D)+1$ and $\operatorname{tmr}(D)$
is even. Moreover, if $D$ is not transitive then $G_{D,T}$ is non-empty for
any $T\in\mathcal{T}$ and Lemma 3.1 also yields that
$\operatorname{inv}(D)=\operatorname{tmr}(D)+1$ if and only if every matrix of
$D$ with minimum rank has every diagonal entry equal to zero. ∎

It is interesting to note that all of the examples in [1, 2] of pairs of
graphs $D_{1},D_{2}$ with $\operatorname{inv}(D_{1}\rightarrow
D_{2})<\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})$ have that $D_{i}$
is a tournament with $\operatorname{inv}(D_{i})=\operatorname{tmr}(D_{i})+1$
for at least one $i$. In fact, the following result holds.

######  Lemma 3.3.

Let $D_{1}$ be a tournament with
$\operatorname{inv}(D_{1})=\operatorname{tmr}(D_{1})+1$, and let $D_{2}$ be
any oriented graph with $\operatorname{inv}(D_{2})\geq 1$. Then
$\operatorname{inv}(D_{1}\rightarrow
D_{2})\leq\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})-1$.

This can be proved using a similar argument to that used in [2].
Alternatively, we can directly apply Corollary 3.2, as follows.

###### Proof.

Let $D_{1}$ be a tournament satisfying
$\operatorname{inv}(D_{1})=\operatorname{tmr}(D_{1})+1$. Applying Proposition
2.3, let $D_{2}^{*}$ be a tournament containing $D_{2}$ with
$\operatorname{inv}(D_{2}^{*})=\operatorname{inv}(D_{2})$. We see that

$\displaystyle\operatorname{inv}(D_{1}\rightarrow
D_{2})\leq\operatorname{inv}(D_{1}\rightarrow D_{2}^{*})$
$\displaystyle\leq\operatorname{tmr}(D_{1}\rightarrow D_{2}^{*})+1$
$\displaystyle\leq\operatorname{tmr}(D_{1})+\operatorname{tmr}(D_{2}^{*})+1$
$\displaystyle\leq\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2}^{*})=\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2}).$

Suppose for contradiction that we have equality. Then

$\displaystyle\operatorname{inv}(D_{1}\rightarrow D_{2}^{*})$
$\displaystyle=\operatorname{tmr}(D_{1}\rightarrow D_{2}^{*})+1,$ (1)
$\displaystyle\operatorname{tmr}(D_{1}\rightarrow D_{2}^{*})$
$\displaystyle=\operatorname{tmr}(D_{1})+\operatorname{tmr}(D_{2}^{*}),\quad\text{and}$
(2) $\displaystyle\operatorname{inv}(D_{2}^{*})$
$\displaystyle=\operatorname{tmr}(D_{2}^{*}).$ (3)

Using (3) and $\operatorname{inv}(D_{2}^{*})\geq 1$ (so $D_{2}^{*}$ is not
transitive), Corollary 3.2 tells us there is some minimum rank matrix
$M_{2}\in\mathcal{M}^{*}(D_{2}^{*})$ with a non-zero diagonal entry. Then,
letting $M_{1}$ be a minimum rank matrix in $\mathcal{M}^{*}(D_{1})$, the
matrix

$\begin{bmatrix}M_{1}&0\\\ 0&M_{2}\end{bmatrix}$

is a matrix in $\mathcal{M}^{*}(D_{1}\rightarrow D_{2}^{*})$ with a non-zero
entry on the diagonal and rank
$\operatorname{tmr}(D_{1})+\operatorname{tmr}(D_{2}^{*})$ which is equal to
$\operatorname{tmr}(D_{1}\rightarrow D_{2}^{*})$ by (2). Applying Corollary
3.2 again, this implies that $\operatorname{inv}(D_{1}\rightarrow
D_{2}^{*})=\operatorname{tmr}(D_{1}\rightarrow D_{2}^{*})$, contradicting (1).
∎

##  4 Proof of Theorem 1.2

In Problem 5.5 of [2], Aubian, Havet, Hörsch, Klingelhoefer, Nisse, Rambaud,
and Vermande ask whether there exists a non-acyclic oriented graph $D$ such
that $\operatorname{inv}({D\rightarrow D})=\operatorname{inv}(D)$, and answer
this question in the negative. The goal of this section is to prove Theorem
1.2, which is a more general result. We restate it below for convenience.

See 1.2

In fact, we may focus our attention exclusively on the tournament case.

######  Lemma 4.1.

Let $D_{1}$ and $D_{2}$ be tournaments such that
$\operatorname{inv}(D_{1})=\operatorname{inv}(D_{2})\geq 1$. Then
$\operatorname{inv}({D_{1}\rightarrow D_{2}})>\operatorname{inv}(D_{1})$.

Before we prove Lemma 4.1, we demonstrate why this suffices to prove Theorem
1.2.

###### Proof of Theorem 1.2.

Suppose for a contradiction that there exist oriented graphs $D_{1},D_{2}$
with
$\operatorname{inv}(D_{1})=\operatorname{inv}(D_{2})=\operatorname{inv}(D_{1}\rightarrow
D_{2})$. Let $k\coloneqq\operatorname{inv}(D_{1})$.

Apply Proposition 2.3 to obtain a tournament $(D_{1}\rightarrow D_{2})^{*}$
with $({D_{1}\rightarrow D_{2}})\subseteq({D_{1}\rightarrow D_{2}})^{*}$ and

$\operatorname{inv}((D_{1}\rightarrow
D_{2})^{*})=\operatorname{inv}(D_{1}\rightarrow D_{2})=k.$

Since $(D_{1}\rightarrow D_{2})^{*}$ contains every edge of $D_{1}\rightarrow
D_{2}$ it is the dijoin of two tournaments $E_{1}$ and $E_{2}$, where
$E_{1}\supseteq D_{1}$ and $E_{2}\supseteq D_{2}$. By Observation 2.1, both
$E_{1}$ and $E_{2}$ have inversion number at least $k$. Hence

$k=\operatorname{inv}((D_{1}\rightarrow
D_{2})^{*})=\operatorname{inv}(E_{1}\rightarrow
E_{2})\geq\operatorname{inv}(E_{1})\geq k$

and

$k=\operatorname{inv}((D_{1}\rightarrow
D_{2})^{*})=\operatorname{inv}(E_{1}\rightarrow
E_{2})\geq\operatorname{inv}(E_{2})\geq k.$

Therefore, we have two tournaments $E_{1},E_{2}$ with
$\operatorname{inv}(E_{1})=k=\operatorname{inv}(E_{2})=\operatorname{inv}(E_{1}\rightarrow
E_{2})$, contradicting Lemma 4.1. ∎

In order to prove Lemma 4.1 we will require a lemma about the structure of
certain symmetric matrices. Call an $n\times m$ matrix with entries in
$\\{0,1\\}$ a _staircase matrix_ if its entries increase down each column and
decrease along each row (so that the $1$s form the shape of a staircase in the
bottom left). We need the following lemma.

######  Lemma 4.2.

Let $M$ be a symmetric $(n+m)\times(n+m)$ matrix with entries in $\\{0,1\\}$
of the form

$\begin{bmatrix}A&C\\\ C^{T}&B\end{bmatrix}$

where $A$ is a symmetric $n\times n$ matrix, $B$ is a symmetric $m\times m$
matrix and $C$ is an $n\times m$ staircase matrix. If
$m\geq\operatorname{rank}(A)+1$ then one of the following holds:

  1. 1.

$\operatorname{rank}(M)\geq\operatorname{rank}(A)+1$, or

  2. 2.

there two adjacent columns of $B$ with the same entries, or

  3. 3.

the final column of $B$ contains only zeroes.

###### Proof.

Suppose that $M$ is a matrix of the given form. Clearly
$\operatorname{rank}(M)\geq\operatorname{rank}(A)$, so suppose that
$\operatorname{rank}(M)=\operatorname{rank}(A)=k$. It must therefore be
possible to write each row of $B$ as a linear combination of rows of $C$ over
$\mathbb{F}_{2}$.

Since $\operatorname{rank}(M)=k$, it follows that the staircase $C$ must
contain at most $k$ distinct non-zero columns (‘steps’). Since $m\geq k+1$,
this means that either $C$ contains two consecutive columns with the same
entries or $C$ contains a zero column. We split into two cases.

######  Case 1.

Suppose that $C$ contains two adjacent columns with the same entries, say
column $i$ and $i+1$. Since each row of $B$ can be written as a linear
combination of rows of $C$ over $\mathbb{F}_{2}$, this implies that columns
$i$ and $i+1$ of $B$ must also contain the same entries.

######  Case 2.

Suppose that $C$ contains a zero column. Since $C$ is a staircase matrix, the
final column of $C$ must be a zero column. Since each row of $B$ can be
written as a linear combination of rows of $C$, this implies that the final
column of $B$ also contains only zeroes.

∎

We are now armed with all the tools necessary to prove Lemma 4.1.

###### Proof of Lemma 4.1.

Suppose for a contradiction that there exist non-transitive tournaments
$D_{1}$ and $D_{2}$ with
$\operatorname{inv}(D_{1})=\operatorname{inv}(D_{2})=\operatorname{inv}({D_{1}\rightarrow
D_{2}})$. Take $D_{1},D_{2}$ to be tournaments with this property such that
$|V(D_{1})|+|V(D_{2})|$ is minimal, where $n_{1}:=|V(D_{1})|$ and
$n_{2}:=|V(D_{2})|$. Let $n:=n_{1}+n_{2}$ and
$k\coloneqq\operatorname{inv}(D_{1})$. Note that Proposition 2.2 tells us that
$k+1\leq n_{1},n_{2}$.

Our goal is to show that every minimum rank matrix in
$\mathcal{M}^{*}(D_{1}\rightarrow D_{2})$ has rank $k$ and only zero entries
on the diagonal. Then, by Corollary 3.2, we are able to conclude that
$\operatorname{inv}({D_{1}\rightarrow D_{2}})=k+1$ to obtain a contradiction.

Suppose that $M$ is a matrix of minimum rank in
$\mathcal{M}^{*}(D_{1}\rightarrow D_{2})$, where
$M\in\mathcal{M}(G_{D_{1}\rightarrow D_{2},T})$ for some transitive tournament
$T$. Note that $T$ naturally induces an order on its vertices, with the source
as the first vertex and the sink as the last vertex. We fix a different
ordering $\phi:V(T)\rightarrow[n]$ of the vertices of $T$ (and thus of
$D_{1}\rightarrow D_{2}$), which is obtained by first taking all vertices in
the copy of $D_{1}$ in the order induced by the natural ordering on $T$, and
then taking all vertices in the copy of $D_{2}$ in the order induced by $T$.
That is, $\phi(u)<\phi(v)$ if and only if either $u\in V(D_{1})$ and $v\in
V(D_{2})$, or $u,v\in V(D_{1})$ and $u<v$, or $u,v\in V(D_{2})$ and $u<v$.

Note that permuting both the rows and the columns of $M$ by a given
permutation does not change the rank of $M$ or the diagonal entries. Therefore
we may, and will, assume that our matrix $M$ has rows and columns ordered
according to the vertex ordering $\phi$.

Now, since $M$ has minimum rank, by Corollary 3.2,
$\operatorname{rank}(M)\in\\{k-1,k\\}$. Moreover, by our choice of vertex
order, $M$ has the form

$\begin{bmatrix}A&C\\\ C^{T}&B\end{bmatrix}$ (4)

where $A$ is an $n_{1}\times n_{1}$ symmetric matrix, $B$ is an $n_{2}\times
n_{2}$ symmetric matrix and $C$ is an $n_{1}\times n_{2}$ staircase matrix. In
particular, $A\in\mathcal{M}^{*}(D_{1})$ and $B\in\mathcal{M}^{*}(D_{2})$.

Clearly $\operatorname{rank}(A)\leq\operatorname{rank}(M)\leq k$. Since
$A\in\mathcal{M}^{*}(D_{1})$, by Corollary 3.2,

$\operatorname{rank}(A)\geq\operatorname{tmr}(D_{1})\geq\operatorname{inv}(D_{1})-1=k-1.$

The corresponding inequalities also hold for $B$, and thus
$\operatorname{rank}(A),\operatorname{rank}(B)\in\\{k-1,k\\}$.

######  Claim 1.

$\operatorname{rank}(A)=\operatorname{rank}(B)=k-1$ and
$\operatorname{rank}(M)=k$.

###### Proof of Claim.

First suppose, in order to obtain a contradiction, that
$\operatorname{rank}(A)=\operatorname{rank}(M)$. Since $n_{2}\geq
k+1\geq\operatorname{rank}(A)+1$, by Lemma 4.2 we can immediately deduce that
either there are two adjacent columns of $B$ that have the same entries, or
the final column of $B$ contains only zeroes.

Suppose there are two adjacent columns $i$ and $i+1$ of $B$ with the same
entries. Consider the out-neighbourhoods of the vertices $u$ and $v$ in
$D_{2}$, where $\phi(u)=i$ and $\phi(v)=i+1$. By definition of $\phi$, a
vertex $w\in D_{2}$ is in $N^{+}(u)$ if and only if either $\phi(w)<i$ and
$B_{\phi(w),i}=1$, or $\phi(w)>i$ and $B_{\phi(w),i}=0$. Similarly, a vertex
$w\in D_{2}$ is in $N^{+}(v)$ if and only if either $\phi(w)<i+1$ and
$B_{\phi(w),i+1}=1$, or $\phi(w)>i+1$ and $B_{\phi(w),i+1}=0$. Since
$B_{j,i}=B_{j,i+1}$ for all $j$, we see that
$N^{+}(u)\setminus\\{v\\}=N^{+}(v)\setminus\\{u\\}$. In particular, $u$ and
$v$ are twin vertices in $D_{2}$. Let $D_{2}^{\prime}=D_{2}-u$. By Proposition
2.5, $\operatorname{inv}(D_{2}^{\prime})=\operatorname{inv}(D_{2})$.

Otherwise, suppose that the final column of $B$ is all zeros. This means that
the vertex $u$ with $\phi(u)=n$ is a sink in $D_{2}$. Let
$D_{2}^{\prime}=D_{2}-u$. By Proposition 2.4,
$\operatorname{inv}(D_{2}^{\prime})=\operatorname{inv}(D_{2})$.

In either case, by Observation 2.1,

$k=\operatorname{inv}(D_{2})=\operatorname{inv}(D_{2}^{\prime})\leq\operatorname{inv}({D_{1}\rightarrow
D_{2}^{\prime}})\leq\operatorname{inv}({D_{1}\rightarrow D_{2}})=k.$

In particular,
$\operatorname{inv}(D_{2}^{\prime})=\operatorname{inv}({D_{1}\rightarrow
D_{2}^{\prime}})=k$ and $D_{2}^{\prime}$ has one fewer vertex than $D_{2}$,
contradicting the minimality of $|V(D_{1})|+|V(D_{2})|$. Hence
$\operatorname{rank}(A)<\operatorname{rank}(M)$.

Now suppose $\operatorname{rank}(B)=\operatorname{rank}(M)$. This follows
along the same lines as the previous case, the only difference being that we
must apply Lemma 4.2 to $M$ with rows and columns in reverse. Either there are
two adjacent columns of $A$ that have the same entries or the first column of
$A$ contains only zeroes, corresponding to $D_{1}$ containing twin vertices or
a source vertex, respectively. The proof then proceeds as before, and thus
$\operatorname{rank}(B)<\operatorname{rank}(M)$. Therefore,
$\operatorname{rank}(A)=\operatorname{rank}(B)=k-1$ and
$\operatorname{rank}(M)=k$. ∎

By Claim 1, $\operatorname{inv}(D_{1})=\operatorname{rank}(A)+1$ and
$\operatorname{inv}(D_{2})=\operatorname{rank}(B)+1$. Hence, by Corollary 3.2,
$A$ and $B$ (and thus $M$) must have zero entries on the diagonal. Therefore,
every matrix of $D_{1}\rightarrow D_{2}$ of minimum rank has rank $k$ and
every diagonal entry equal to zero. By Corollary 3.2, we conclude that
$\operatorname{inv}({D_{1}\rightarrow D_{2}})=k+1$, which is a contradiction.
∎

##  5 Open problems

In light of Lemma 3.3, and the fact that all of the examples in [1, 2] of
pairs of graphs $D_{1},D_{2}$ with $\operatorname{inv}(D_{1}\rightarrow
D_{2})<\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})$ can be obtained by
an application of this lemma, we ask whether these are all such examples.

######  Question 5.1.

Do there exist tournaments $D_{1},D_{2}$ with
$\operatorname{inv}(D_{i})=\operatorname{tmr}(D_{i})$ for $i=1,2$ and
$\operatorname{inv}(D_{1}\rightarrow
D_{2})<\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})$?

Note that by Corollary 3.2, for any tournament $D$, if $\operatorname{inv}(D)$
is even, then $\operatorname{inv}(D)=\operatorname{tmr}(D)$. Hence, a negative
answer to this question would disprove the following pair of similar
conjectures (the latter of which is strictly stronger than the former).

######  Conjecture 5.2 ([1, Conjecture 8.9]).

For all $\ell,r\in\mathbb{N}$ with $\ell\geq 3$ or $r\geq 3$ there exist
oriented graphs $D_{1}$ and $D_{2}$ with $\operatorname{inv}(D_{1})=\ell$ and
$\operatorname{inv}(D_{2})=r$, but $\operatorname{inv}(D_{1}\rightarrow
D_{2})<\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})$.

######  Conjecture 5.3 ([2, Conjecture 5.3]).

For all $\ell\geq 3$ there exists an oriented graph $D_{1}$ with
$\operatorname{inv}(D_{1})=\ell$ such that for all $D_{2}$ with
$\operatorname{inv}(D_{2})\geq 1$, we have
$\operatorname{inv}(D_{1}\rightarrow
D_{2})<\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})$.

One approach to answering Question 5.1 would be to bound the tournament
minimum rank of the dijoin of two tournaments.

######  Question 5.4.

Do there exist tournaments $D_{1},D_{2}$ with
$\operatorname{tmr}(D_{1}\rightarrow
D_{2})<\operatorname{tmr}(D_{1})+\operatorname{tmr}(D_{2})$?

A negative answer to this question would be a very strong result that would
also answer Question 5.1 in the negative, and therefore resolve the two
conjectures above. Moreover, we could immediately conclude that

$\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2})-2\leq\operatorname{inv}(D_{1}\rightarrow
D_{2})\leq\operatorname{inv}(D_{1})+\operatorname{inv}(D_{2}).$

for all oriented graphs $D_{1},D_{2}$, by a simple application of Proposition
2.3 and Corollary 3.2.

One place to start would be to answer Question 5.4 in the special case when
one of the tournaments is $\overrightarrow{C_{3}}$, the directed cycle on
three vertices.

######  Conjecture 5.5.

For all tournaments $D$, we have
$\operatorname{tmr}(D\rightarrow\overrightarrow{C_{3}})=\operatorname{tmr}(D)+1=\operatorname{tmr}(\overrightarrow{C_{3}}\rightarrow
D)$.

We can generalise the idea of dijoins to sequences of graphs. Given a finite
sequence $D_{1},...,D_{k}$ of oriented graphs, the $k$_-join_ of
$D_{1},...,D_{k}$, denoted by $[D_{1},...,D_{k}]$, is the oriented graph
constructed from vertex-disjoint copies of $D_{1},...,D_{k}$ by adding all
edges $uv$ where $u\in V(D_{i})$ and $v\in V(D_{j})$ for $i<j$. For ease of
notation, we write $[D]_{k}$ for the $k$-join of $k$ copies of the same
oriented graph $D$.

Pouzet, Kaddour and Thatte [7] proved that
$\operatorname{inv}\left(\left[\overrightarrow{C_{3}}\right]_{k}\right)=k$ for
all $k$, where $\overrightarrow{C_{3}}$ is the directed cycle on three
vertices. Further to this, Alon, Powierski, Savery, Scott and Wilmer [1]
proved that if $D_{1},D_{2},\ldots,D_{k}$ are oriented graphs with
$\operatorname{inv}(D_{i})\leq 2$ for all $i$ and
$\operatorname{inv}(D_{i})=2$ for at most one $i$, then

$\operatorname{inv}([D_{1},D_{2},\ldots,D_{k}])=\sum_{i=1}^{k}\operatorname{inv}(D_{i})$

They conjecture that the condition that $\operatorname{inv}(D_{i})=2$ for at
most one $i$ is unnecessary.

######  Conjecture 5.6 ([1, Conjecture 8.8]).

Let $k\in\mathbb{N}$, and let $D_{1},\ldots,D_{k}$ be oriented graphs
satisfying $\operatorname{inv}(D_{i})\leq 2$ for all $i$. Then
$\operatorname{inv}([D_{1},\ldots,D_{k}])=\sum_{i=1}^{k}\operatorname{inv}(D_{i})$.

A negative answer to Question 5.4 would immediately lead to a proof of this
conjecture. In addition, combined with Corollary 3.2, it would give an
affirmative answer to the following question, yielding a more general result.

######  Question 5.7.

Let $k\in\mathbb{N}$, and let $D_{1},\ldots,D_{k}$ be oriented graphs such
that, for every $i$, either $\operatorname{inv}(D_{i})=1$ or
$\operatorname{inv}(D_{i})$ is even for all $i$. Is
$\operatorname{inv}([D_{1},\ldots,D_{k}])=\sum_{i=1}^{k}\operatorname{inv}(D_{i})$?

## References

  * [1] Noga Alon, Emil Powierski, Michael Savery, Alex Scott, and Elizabeth Wilmer.  Invertibility of digraphs and tournaments.  SIAM J. Discrete Math., 38(1):327–347, 2024.  doi:10.1137/23M1547135.
  * [2] Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud, and Quentin Vermande.  Problems, proofs, and disproofs on the inversion number, 2022.  arXiv:2212.09188.
  * [3] Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, and Frédéric Havet.  On the inversion number of oriented graphs.  Discrete Math. Theor. Comput. Sci., 23(2):Paper No. 8, 29, [2021–2023].
  * [4] Houmem Belkhechine.  Indécomposabilité des graphes et des tournois.  Theses, Université Claude Bernard Lyon I; Université de Sfax. Faculté des sciences, July 2009.  URL: https://theses.hal.science/tel-00609544.
  * [5] Houmem Belkhechine, Moncef Bouaziz, Imed Boudabbous, and Maurice Pouzet.  Inversion dans les tournois.  C. R. Math. Acad. Sci. Paris, 348(13-14):703–707, 2010.  doi:10.1016/j.crma.2010.06.022.
  * [6] Calum Buchanan, Christopher Purcell, and Puck Rombach.  Subgraph complementation and minimum rank.  Electron. J. Combin., 29(1):Paper No. 1.38, 20, 2022.  doi:10.37236/10383.
  * [7] Maurice Pouzet, Hamza Si Kaddour, and Bhalchandra D. Thatte.  On the Boolean dimension of a graph and other related parameters.  Discrete Math. Theor. Comput. Sci., 23(2):Paper No. 5, 20, [2021–2023].