# Rainbow odd cycles

Ron Aharoni111Department of Mathematics, Technion – Israel Institute of
Technology, Technion City, Haifa 3200003, Israel.${\ }^{,}$ Email:
<EMAIL_ADDRESS>Supported in part by the United States–Israel Binational
Science Foundation grant no. 2006099, the Israel Science Foundation grant no.
2023464 and the Discount Bank Chair at the Technion. This paper is part of a
project that has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant
agreement no. 823748. Joseph Briggs11footnotemark: 1${\ }^{,}$ Email:
<EMAIL_ADDRESS>Ron Holzman11footnotemark: 1${\ }^{,}$ Email:
<EMAIL_ADDRESS>Research partly done during a visit at the Department
of Mathematics, Princeton University, supported by the H2020-MSCA-RISE project
CoSP–GA no. 823748. Zilin Jiang School of Mathematical and Statistical
Sciences, and School of Computing, Informatics and Decision Systems
Engineering, Arizona State University, Tempe, AZ 85281. Email<EMAIL_ADDRESS>The work was done when Z. Jiang was an Applied Mathematics Instructor at
Massachusetts Institute of Technology, and was supported in part by an
AMS–Simons Travel Grant, and by U.S. taxpayers through the NSF grant
DMS-1953946.

###### Abstract

We prove that every family of (not necessarily distinct) odd cycles
$O_{1},\dots,O_{2\lceil n/2\rceil-1}$ in the complete graph $K_{n}$ on $n$
vertices has a rainbow odd cycle (that is, a set of edges from distinct
$O_{i}$’s, forming an odd cycle). As part of the proof, we characterize those
families of $n$ odd cycles in $K_{n+1}$ that do not have any rainbow odd
cycle. We also characterize those families of $n$ cycles in $K_{n+1}$, as well
as those of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$, without any
rainbow cycle.

##  1 Introduction

Given a family $\mathcal{E}$ of sets, an $\mathcal{E}$-_rainbow set_ is a set
$R\subseteq\cup\,\mathcal{E}$ with an injection $\sigma\colon R\to\mathcal{E}$
such that $e\in\sigma(e)$ for all $e\in R$. The term rainbow set originates in
viewing every member of $\mathcal{E}$ as a color, and every $e\in R$ as
colored by $\sigma(e)$. When we speak of a rainbow set, we often keep in mind
the injection $\sigma$, and we say that $\sigma(e)\in\mathcal{E}$ is
_represented_ by $e$ in $R$.

######  Remark.

Throughout we use the term “family” in the sense of “multiset” allowing
repeated members.

A recurring theme in the study of rainbow sets is finding an
$\mathcal{E}$-rainbow set satisfying a property $\mathcal{P}$, assuming that
every member of $\mathcal{E}$ satisfies $\mathcal{P}$, and that $\mathcal{E}$
is large. A classic result of this type is Bárány’s colorful Carathéodory
theorem [5]: every family of $n+1$ subsets of $\mathbb{R}^{n}$, each
containing a point $a$ in its convex hull, has a rainbow set satisfying the
same property. An application mentioned in [5] is a theorem due to Frank and
Lovász, on rainbow directed cycles. Other results of this type are about
rainbow matchings. For example, improving a theorem of Drisko [7], Aharoni and
Berger [1, Theorem 4.1] proved that $2n-1$ matchings of size $n$ in any
bipartite graph have a rainbow matching of size $n$. In [4] the examples
showing sharpness of this result were characterized, and in [3] the theorem
was given a topological proof. A more general context is that of independent
sets in graphs, see, e.g., [2, 10, 9].

In this paper we study conditions for the existence of rainbow cycles, with or
without a parity constraint on their lengths. Hereafter a cycle is viewed as a
set of edges. Our main result is:

######  Theorem 1.1.

Every family of $2\lceil n/2\rceil-1$ odd cycles in the complete graph $K_{n}$
on $n$ vertices has a rainbow odd cycle.

Put more explicitly, the theorem states that when $n$ is odd, every family of
$n$ odd cycles in $K_{n}$ has a rainbow odd cycle; when $n$ is even $n-1$ odd
cycles suffice. The case of $n$ odd is relatively easy, and the main effort
goes into the even case. The proof is done in Section 2 via a characterization
of families of $n$ odd cycles in $K_{n+1}$ without any rainbow odd cycle.

In Section 3 we deal with rainbow cycles of general length. The fact that $n$
cycles in $K_{n}$ have a rainbow cycle is easy, and the main result is a
characterization of families of $n$ cycles in $K_{n+1}$ without any rainbow
cycle. In Section 4, we consider rainbow cycles in edge-disjoint families; our
result in this case turns out to be a rediscovery, with a short proof, of a
theorem of [8]. In Section 5 we conclude with a generalization to matroids,
and a result on rainbow even cycles.

##  2 Rainbow odd cycles

We start with an observation which yields Theorem 1.1 in the case of $n$ odd.

######  Proposition 2.1.

Every family of $n$ odd cycles in $K_{n}$ has a rainbow odd cycle.222A
reworded version of Proposition 2.1, suggested by the first author, appeared
as Problem 3 of Day 1 in the 12th Romanian Master in Mathematics, RMM 2020.

###### Proof.

Let $R$ be a maximal rainbow forest. Since $R$ has fewer than $n$ edges, one
of the odd cycles, say $O$, is not represented in $R$. By the maximality of
$R$, no edge in $O$ connects two components of $R$. Thus $O$ is contained in a
connected component $T$ of $R$. Since $O$ is of odd length, one of its edges
does not obey the bipartition of $T$. Adding that edge to $T$ yields a rainbow
subgraph that supports an odd cycle. ∎

A Hamiltonian cycle on $n$ vertices repeated $n-1$ times shows the sharpness
of Proposition 2.1 only for $n$ odd. This example can be generalized as
follows.

######  Definition 2.2.

A family $\mathcal{O}$ of cycles is a _pruned cactus_ if all the cycles in
$\mathcal{O}$ are identical to a cycle on $\lvert\mathcal{O}\rvert+1$
vertices, or $\mathcal{O}$ can be partitioned into two pruned cacti
$\mathcal{O}_{1},\mathcal{O}_{2}$ such that $\cup\,\mathcal{O}_{1}$ and
$\cup\,\mathcal{O}_{2}$ share exactly one vertex.333A cactus graph is a
connected graph in which two cycles have at most one vertex in common. A
pruned cactus $\mathcal{O}$ is named after the fact that $\cup\,\mathcal{O}$
is a $2$-edge-connected cactus graph.

Figure 1: Underlying graphs of two pruned cacti. The one on the right is
composed of odd cycles.

Given a pruned cactus $\mathcal{O}$, by our recursive definition, one can
check that $\mathcal{O}$ has no rainbow cycle, and the underlying graph
$\cup\,\mathcal{O}$ contains exactly $\lvert\mathcal{O}\rvert+1$ vertices (see
Figure 1). A key result towards the proof of Theorem 1.1 is that the converse
is also true for $\mathcal{O}$ composed of only odd cycles. For technical
reasons, we shall switch as from now to cycles in $K_{n+1}$ rather than
$K_{n}$.

######  Theorem 2.3.

If a family of $n$ odd cycles in $K_{n+1}$ has no rainbow odd cycle, then it
is a pruned cactus.

Clearly, the cardinality of a pruned cactus composed solely of odd cycles is
even. Therefore, when $n$ is even, $n-1$ odd cycles cannot form a pruned
cactus, and so Theorem 1.1 follows from Theorem 2.3.

For the inductive proof of Theorem 2.3, we need the following technical lemma.

######  Lemma 2.4.

Let $\mathcal{O}:=\left\\{O_{1},\dots,O_{n}\right\\}$ be a family of odd
cycles in $K_{n+1}$ without any rainbow odd cycle, and denote
$\mathcal{K}:=\left\\{O_{1},\dots,O_{k}\right\\}$, where $k<n$. Suppose that
$Q$ is a $(k+1)$-vertex subgraph of $\cup\,\mathcal{K}$ and $V\subseteq V(Q)$
such that every pair of vertices in $V$ can be connected by a
$\mathcal{K}$-rainbow even path in $Q$. Then

  1. (a)

No edge in $O_{k+1},\dots,O_{n}$ has both endpoints in $V$.

Moreover, let $\pi$ be the contraction444A contraction operation removes all
edges between any pair of contracted vertices. that replaces $V(Q)$ with a
single vertex $\bar{v}$, and suppose that $P_{k+1},\dots,P_{n}$ are subgraphs
of $O_{k+1},\dots,O_{n}$ such that each $P_{i}$ avoids the vertices in
$V(Q)\setminus V$. Denote
$\bar{\mathcal{P}}:=\left\\{\pi(P_{k+1}),\dots,\pi(P_{n})\right\\}$. Then the
following holds.

  1. (b)

There is no $\bar{\mathcal{P}}$-rainbow odd cycle in $\pi(K_{n+1})$.

  2. (c)

If $\bar{\mathcal{P}}$ is a pruned cactus of odd cycles, then
$\cup\,\bar{\mathcal{P}}$ is spanning in $\pi(K_{n+1})$, and no
$O_{i}\setminus P_{i}$ contains an edge of the form $uv$ with $u\not\in
V(Q)\cup V(P_{i})$ and $v\in V\cap V(P_{i})$.

###### Proof.

Note that any edge in $O_{k+1},\dots,O_{n}$ with both endpoints in $V$ can be
completed to an $\mathcal{O}$-rainbow odd cycle by a $\mathcal{K}$-rainbow
even path in $Q$.

Assume for the sake of contradiction that there is a
$\bar{\mathcal{P}}$-rainbow odd cycle $C$ in $\pi(K_{n+1})$. Edges of the form
$u\bar{v}$ after the contraction correspond to edges of the form $uv$ with
$v\in V$ before the contraction. Hence, prior to the contraction, $C$ was
either itself an $(\mathcal{O}\setminus\mathcal{K})$-rainbow odd cycle (which
does not exist), or an ($\mathcal{O}\setminus\mathcal{K}$)-rainbow odd path
between a pair of vertices in $V$, which can be completed to an
$\mathcal{O}$-rainbow odd cycle by a $\mathcal{K}$-rainbow even path in $Q$.

To prove (c), suppose that the family $\bar{\mathcal{P}}$ is a pruned cactus
of odd cycles. Notice that $\pi(K_{n+1})$ has $n+1-\lvert V(Q)\rvert+1=n-k+1$
vertices, and the underlying graph $\cup\,\bar{\mathcal{P}}$ of the pruned
cactus $\bar{\mathcal{P}}$ has $\lvert\bar{\mathcal{P}}\rvert+1=n-k+1$
vertices. Thus $\cup\,\bar{\mathcal{P}}$ is spanning in $\pi(K_{n+1})$, and so
$\bar{v}$ is on $\cup\,\bar{\mathcal{P}}$. Finally, suppose on the contrary
that some $O_{i}\setminus P_{i}$ contains an edge $uv$ with $u\not\in V(Q)\cup
V(P_{i})$ and $v\in V\cap V(P_{i})$. Since $\bar{v}=\pi(v)$ is on $\pi(P_{i})$
and $u$ is not on $\pi(P_{i})$, one can find a $\bar{\mathcal{P}}$-rainbow
even path from $\bar{v}$ to $u$, in which $\pi(P_{i})$ is not represented.
This $\bar{\mathcal{P}}$-rainbow even path can then be completed by the edge
$\pi(uv)=u\bar{v}$ to a
$\left\\{\pi(P_{k+1}),\dots,\pi(P_{i-1}),\pi(uv),\pi(P_{i+1}),\dots,\pi(P_{n})\right\\}$-rainbow
odd cycle. However this contradicts (b) for $uv$ is an edge of $O_{i}$ that
avoids $V(Q)\setminus V$. ∎

The last ingredient is a corollary of Rado’s theorem for matroids [11], that
gives a necessary and sufficient condition for a family of connected subgraphs
to have a rainbow spanning tree.

######  Theorem 2.5 (Rado’s theorem for matroids).

Given a matroid with ground set $E$, for every family
$\left\\{E_{1},\dots,E_{m}\right\\}$ of subsets of $E$, there exists a rainbow
independent set of size $m$ if and only if $\mathrm{rank}(E_{I})\geq\lvert
I\rvert$ for every $I\subseteq[m]$, where $E_{I}$ is shorthand for
$\bigcup_{i\in I}E_{i}$.

######  Corollary 2.6.

For every family $\left\\{E_{1},\dots,E_{m}\right\\}$ of connected subgraphs
(viewed as edge sets) in $K_{m+1}$, the family has a rainbow spanning tree if
and only if $\lvert V(E_{I})\rvert\geq\lvert I\rvert+1$ for every
$I\subseteq[m]$.

###### Proof.

The “only if” direction is easy to check. For the “if” direction, it suffices
to verify the rank inequalities in Rado’s theorem for matroids. Recall that,
in a graphic matroid, $\mathrm{rank}(E)=\lvert V(E)\rvert-c(E)$ for every edge
set $E$, where $c(E)$ is the number of connected components of $E$. Pick an
arbitrary $I\subseteq[m]$. Because each $E_{i}$ is connected, we can partition
$I$ into sets $I_{1},\dots,I_{c}$, where $c:=c(E_{I})$, such that
$E_{I_{1}},\dots,E_{I_{c}}$ are the connected components of $E_{I}$. Since
$\lvert V(E_{I_{j}})\rvert\geq\lvert I_{j}\rvert+1$ for all $j\in[c]$, we have
the desired inequality

$\mathrm{rank}(E_{I})=\lvert
V(E_{I})\rvert-c(E_{I})=\sum_{j=1}^{c}\left(\lvert
V(E_{I_{j}})\rvert-1\right)\geq\sum_{j=1}^{c}\lvert I_{j}\rvert=\lvert
I\rvert.\qed$

###### Proof of Theorem 2.3.

We do this by induction. The base case $n=2$ is trivial. Suppose $n\geq 3$,
and let $\mathcal{O}=\left\\{O_{1},\dots,O_{n}\right\\}$ be a family of odd
cycles in $K_{n+1}$ without any rainbow odd cycle. We break the inductive step
into three cases.

#### Case 1:

There exists a proper subfamily $\mathcal{K}$ of $\mathcal{O}$ such that
$\lvert V(\cup\,\mathcal{K})\rvert\leq\lvert\mathcal{K}\rvert+1$.

Since there is no $\mathcal{K}$-rainbow odd cycle, by the induction hypothesis
$\mathcal{K}$ is a pruned cactus. By passing to a subfamily of $\mathcal{K}$,
we may assume without loss of generality that
$\mathcal{K}=\left\\{O_{1},\dots,O_{k}\right\\}$, for some $k<n$, and
$O_{1},\dots,O_{k}$ are identical to an odd cycle $O$ on $k+1$ vertices. Note
that every pair of vertices in $V(O)$ can be connected by a
$\mathcal{K}$-rainbow even path in $O$. By Lemma 2.4(a), for every
$i\in\left\\{k+1,\dots,n\right\\}$, the arcs of $O_{i}$ defined by its
vertices shared with $O$ are of length $\geq 2$. Since $O_{i}$ is odd, there
exists an odd arc, call it $P_{i}$. In case $O_{i}$ and $O$ are vertex-
disjoint, set $P_{i}:=O_{i}$.

Let $\pi$ be the contraction of $V(O)$ to a single vertex $\bar{v}$. By our
choice of $P_{i}$, for each $i>k$, $\pi(P_{i})$ is an odd cycle, and so Lemma
2.4(b) and the inductive hypothesis imply that the family
$\bar{\mathcal{P}}:=\left\\{\pi(P_{k+1}),\dots,\pi(P_{n})\right\\}$ is a
pruned cactus.

######  Claim.

For every $i>k$, $P_{i}=O_{i}$, in other words, $O_{i}$ and $O$ share at most
$1$ vertex.

Assume for contradiction that $P_{i}\neq O_{i}$ for some $i>k$. Let $uv$ be an
edge in $O_{i}\setminus P_{i}$ with $u\not\in V(P_{i})$ and $v\in V(P_{i})$.
Note in addition that $u\not\in V(O)$ by Lemma 2.4(a), while $v\in V(O)$,
which conflicts with Lemma 2.4(c).

######  Claim.

For every $i,j>k$, if $\pi(O_{i})=\pi(O_{j})$, then $O_{i}=O_{j}$.

Suppose on the contrary that $\pi(O_{i})=\pi(O_{j})$ and $O_{i}\neq O_{j}$ for
some $i,j>k$. Let $v_{i},v_{j}$ be respectively the vertices of $O_{i},O_{j}$
shared with $O$. Then there exists an $\left\\{O_{i},O_{j}\right\\}$-rainbow
cherry with endpoints $v_{i},v_{j}$ and center not in $V(O)$, which can be
completed to an $\mathcal{O}$-rainbow odd cycle by a $\mathcal{K}$-rainbow odd
path in $O$.

By Lemma 2.4(c), $\bar{v}\in V(\cup\,\bar{\mathcal{P}})$, implying that
$\cup\,\mathcal{O}$ is connected. By the last claim, for $i>k$, the
multiplicity of every $O_{i}$ in $\mathcal{O}$ is equal to the multiplicity of
$\pi(O_{i})$ in $\bar{\mathcal{P}}$, which, by the fact that
$\bar{\mathcal{P}}$ is a pruned cactus, is $\lvert O_{i}\rvert-1$. Together,
this means that $\mathcal{O}$ is a pruned cactus, as desired.

#### Case 2:

Every odd cycle $O_{i}$ is Hamiltonian.

Let $S$ be an $\mathcal{O}$-rainbow star of maximum size, say $k$, and let $c$
be its center.555A _star_ of size $k$ is a set of $k\geq 2$ edges, sharing one
vertex that is called the _center_ of the star. Without loss of generality, we
may assume that the cycles represented in $S$ are $O_{1},\dots,O_{k}$. We may
further assume that the cycles in $\mathcal{O}$ are not identical for
otherwise $\mathcal{O}$ is already a pruned cactus.

######  Claim.

The size $k$ of $S$ satisfies $3\leq k<n$.

Because the cycles in $\mathcal{O}$ are not identical, there is a vertex $v$
in $\cup\,\mathcal{O}$ of degree at least $3$. A quick argument shows an
$\mathcal{O}$-rainbow star of size $3$ centered at $v$, meaning that $k\geq
3$. Negation of the second inequality means that $c$ is connected in $S$ to
all other vertices of the graph. Suppose $O_{1}$ is represented by $cv$ in
$S$. In the absence of an $\mathcal{O}$-rainbow triangle, no edge of $O_{1}$
has both endpoints in $V(K_{n+1})\setminus\left\\{c,v\right\\}$. Because
$\lvert V(K_{n+1})\setminus\left\\{c,v\right\\}\rvert=n-1\geq 2$, it is
impossible for $O_{1}$ to be Hamiltonian given that $cv$ is already in
$O_{1}$.

Let $V$ be the set of leaves of $S$. Since $\mathcal{O}$ has no rainbow
triangle, the cycles $O_{k+1},\dots,O_{n}$ do not connect pairs of vertices of
$V$. By the maximality of $S$, these cycles enter and exit $c$ through $V$.
Therefore, for every $i>k$, $V$ partitions $O_{i}$ into arcs of length at
least two, and at least one of these arcs, call it $P_{i}$, is odd and does
not contain $c$.

Let $\pi$ be the contraction that replaces $V(S)$ by a single vertex
$\bar{v}$. As in Case 1, the family $\\{\pi(P_{k+1}),\dots,\pi(P_{n})\\}$ is a
pruned cactus of odd cycles.

Since $k\geq 3$, $V$ partitions $O_{n}$ into at least $3$ arcs, one of which
is next to $P_{n}$ and does not contain $c$. Hence $O_{n}\setminus P_{n}$
contains an edge $uv$ with $u\not\in V(S)\cup V(P_{n})$ and $v\in V\cap
V(P_{n})$, which contradicts Lemma 2.4(c).

#### Case 3:

For every proper subfamily $\mathcal{K}$ of $\mathcal{O}$, $\lvert
V(\cup\,\mathcal{K})\rvert>\lvert\mathcal{K}\rvert+1$, and some $O_{i}$ is not
Hamiltonian.

Without loss of generality, assume that $O_{n}$ does not contain some vertex
$v$. Set $V:=V(K_{n+1})\setminus\left\\{v\right\\}$. We apply Corollary 2.6 to
the family of subgraphs $O_{1}[V],\dots,O_{n-1}[V]$ induced by $V$, and obtain
an $\left\\{O_{1},\dots,O_{n-1}\right\\}$-rainbow tree that spans $V$. This
rainbow tree together with $O_{n}$ would give rise to an $\mathcal{O}$-rainbow
odd cycle. ∎

##  3 Rainbow cycles

Here is a cheap bound on the size of the family that ensures a rainbow set
with a certain property.

######  Proposition 3.1.

Given a ground set $E$ and a property $\mathcal{P}\subseteq 2^{E}$ with
$\varnothing\not\in\mathcal{P}$ that is closed upwards, every family of $m+1$
subsets $E_{1},\dots,E_{m+1}$ of $E$ with each $E_{i}\in\mathcal{P}$ has a
rainbow set in $\mathcal{P}$, where

$m:=\max\left\\{\lvert F\rvert\colon F\subseteq E\text{ and
}F\not\in\mathcal{P}\right\\}.$

###### Proof.

Take $R$ to be a rainbow subset of $E$ not in $\mathcal{P}$ of maximum size.
Since $R\not\in\mathcal{P}$, $\lvert R\rvert\leq m$ and some $E_{i}$ is not
represented in $R$. Because $E_{i}\in\mathcal{P}$, $E_{i}\neq\varnothing$, and
moreover because $\mathcal{P}$ is closed upwards, $E_{i}\not\subseteq R$. Take
$e\in E_{i}\setminus R$ and define $R^{\prime}:=R\cup\left\\{e\right\\}$,
which is rainbow. By the maximality of $R$, we know that
$R^{\prime}\in\mathcal{P}$. ∎

For rainbow cycles, simply note that a subgraph of $K_{n}$ without cycles,
that is a forest, contains at most $n-1$ edges.

######  Proposition 3.2.

Every family of $n$ cycles in $K_{n}$ has a rainbow cycle. ∎

The sharpness of Proposition 3.2 is witnessed by a pruned cactus. But there is
a more general construction showing this.

######  Definition 3.3.

A family $\mathcal{O}$ of cycles is a _saguaro_ if the family $\mathcal{O}$ is
already a pruned cactus, or the family $\mathcal{O}$ can be partitioned into
three subfamilies $\mathcal{O}_{1},\left\\{O\right\\},\mathcal{O}_{2}$ such
that $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$ are two vertex-disjoint saguaros,
and $O$ is an even cycle along which its vertices alternate between
$V(\cup\,\mathcal{O}_{1})$ and $V(\cup\,\mathcal{O}_{2})$.

We prove that this recursive construction is an exhaustive characterization of
families of $n$ cycles in $K_{n+1}$ without any rainbow cycle.

######  Theorem 3.4.

For every family $\mathcal{O}$ of $n$ cycles in $K_{n+1}$, no rainbow cycle
exists if and only if the family is a saguaro.

Our proof strategy parallels the proof of Theorem 2.3, with a few detours. A
complication arises when an even cycle, after contracting its maximum
independent set, becomes a star. To handle this problem, we shall use the
following:

######  Proposition 3.5.

Let $v$ be a vertex of $K_{m+1}$, and let
$\mathcal{E}:=\left\\{E_{1},\dots,E_{m}\right\\}$ be a family of subgraphs of
$K_{m+1}$, where each $E_{i}$ is either a star centered at $v$ or a cycle.
Suppose that $\mathcal{E}$ has no rainbow cycle, and every star in
$\mathcal{E}$ is edge-disjoint from all the other members of $\mathcal{E}$. If
$E_{1}$ is a star, then there are $\ell$ cycles in $\mathcal{E}$ avoiding $v$,
for some $0<\ell<m$, whose union with $E_{1}$ contains at most $\ell+2$
vertices.

###### Proof.

Let $R$ be a maximal $\left\\{E_{2},\dots,E_{m}\right\\}$-rainbow tree
containing $v$. We may assume that such a tree exists, since otherwise
$E_{2},\dots,E_{m}$ are cycles as required.

Without loss of generality, assume that $E_{2},\dots,E_{k}$ are represented in
$R$, where $k=\lvert V(R)\rvert$. Since $E_{1}$ is edge-disjoint from $E_{i}$
for $i\neq 1$, it is edge-disjoint from $R$. Furthermore, since $\mathcal{E}$
has no rainbow cycle, $R$ does not contain any leaf of $E_{1}$. Since a star
has at least two edges, it follows that $k\leq m-1$.

######  Claim.

For every $i>k$, $E_{i}$ is a cycle that is vertex-disjoint from $R$.

The fact that $E_{i}$ is a cycle follows from the maximality of $R$ and the
requirement that every star in $\mathcal{E}$ is edge-disjoint from all other
members of $\mathcal{E}$. The disjointness from $R$ follows from the
assumption that $\mathcal{E}$ has no rainbow cycle.

Let $\ell=m-k$. By the claim, $E_{k+1},\dots,E_{m}$ are the desired $\ell$
cycles since their vertex sets, as well as that of $E_{1}$, are contained in
$(V(K_{m+1})\setminus V(R))\cup\left\\{v\right\\}$, which is of size
$m+1-k+1=\ell+2$. ∎

Unlike in a pruned cactus, not every cycle in a saguaro is repeated more than
once. We say an $\ell$-cycle is _common_ in the family if it is repeated
exactly $\ell-1$ times. We shall use the following technical lemma that is
analogous to Lemma 2.4.

######  Lemma 3.6.

Let $\mathcal{O}:=\left\\{O_{1},\dots,O_{n}\right\\}$ be a family of cycles in
$K_{n+1}$ without any rainbow cycle, and denote
$\mathcal{K}:=\left\\{O_{1},\dots,O_{k}\right\\}$, where $k<n$. Suppose that
$Q$ is a $(k+1)$-vertex subgraph of $\cup\,\mathcal{K}$, and $V\subseteq V(Q)$
such that every pair of vertices in $V$ can be connected by a
$\mathcal{K}$-rainbow path of length at least $2$ in $Q$. Then

  1. (a)

No edge in $O_{k+1},\dots,O_{n}$ has both endpoints in $V$.

Moreover, let $\pi$ be the contraction that replaces $V(Q)$ by a single vertex
$\bar{v}$, and suppose $P_{k+1},\dots,P_{n}$ are subgraphs of
$O_{k+1},\dots,O_{n}$ such that each $P_{i}$ avoids the vertices in
$V(Q)\setminus V$. Denote
$\bar{\mathcal{P}}:=\left\\{\pi(P_{k+1}),\dots,\pi(P_{n})\right\\}$. Then the
following holds.

  1. (b)

There is no $\bar{\mathcal{P}}$-rainbow cycle in $\pi(K_{n+1})$.

  2. (c)

If $\bar{\mathcal{P}}$ is a saguaro of cycles, then $\cup\,\bar{\mathcal{P}}$
is spanning in $\pi(K_{n+1})$. Moreover, for every $\pi(P_{i})$ that is common
in $\bar{\mathcal{P}}$, $O_{i}\setminus P_{i}$ does not contain any edge of
the form $uv$ with $u\not\in V(Q)\cup V(P_{i})$ and $v\in V\cap V(P_{i})$.

We leave the proof to the readers as it is similar to that of Lemma 2.4.

###### Proof of Theorem 3.4.

The “if” direction is easy to check. We show the “only if” direction by
induction. The base case $n=2$ is trivial. Suppose $n\geq 3$, and
$\mathcal{O}:=\left\\{O_{1},\dots,O_{n}\right\\}$ is a family of cycles in
$K_{n+1}$ without any rainbow cycle. We break the inductive step into three
cases.

#### Case 1:

There exists a proper subfamily $\mathcal{K}$ of $\mathcal{O}$ such that
$\lvert V(\cup\,\mathcal{K})\rvert\leq\lvert\mathcal{K}\rvert+1$.

Let $\mathcal{K}$ be maximal with this property. Without loss of generality,
$\mathcal{K}=\left\\{O_{1},\dots,O_{k}\right\\}$, where
$k:=\lvert\mathcal{K}\rvert<n$. Set $V:=V(\cup\,\mathcal{K})$. By the
induction hypothesis, $\mathcal{K}$ is a saguaro. In particular, as can be
observed in any saguaro, $\lvert V\rvert=k+1$ and every pair of vertices in
$V$ can be connected by a $\mathcal{K}$-rainbow path of length at least $2$.
For every $i>k$, by Lemma 3.6(a), the arcs of $O_{i}$ defined by its vertices
on $V$ are of length at least $2$. If there exists an arc of length $\geq 3$,
choose one such arc and denote it by $P_{i}$. If there is no such arc, set
$P_{i}:=O_{i}$. In case $O_{i}$ avoids $V$, also set $P_{i}:=O_{i}$.

Let $\pi$ be the contraction that replaces $V$ by a single vertex $\bar{v}$.
Then $\pi(P_{i})$ is a cycle, with one possible exception: the vertices of
$O_{i}$ alternate between $V$ and $V(K_{n+1})\setminus V$. In the latter case,
$P_{i}=O_{i}$ and $\pi(P_{i})$ is a star centered at $\bar{v}$ (with at least
$2$ edges).

We next break the current case into two subcases.

Subcase 1.1: For every $i>k$, $\pi(P_{i})$ is a cycle.

Lemma 3.6(b) and the inductive hypothesis imply that the family
$\bar{\mathcal{P}}:=\left\\{\pi(P_{k+1}),\dots,\pi(P_{n})\right\\}$ is a
saguaro. By Lemma 3.6(c), $\bar{v}\in V(\cup\,\bar{\mathcal{P}})$. As can be
observed in any saguaro, there is a common cycle in $\bar{\mathcal{P}}$ that
contains $\bar{v}$. Let this cycle have length $\ell+1$, and assume without
loss of generality that it appears in $\bar{\mathcal{P}}$ as
$\pi(P_{k+1}),\dots,\pi(P_{k+\ell})$.

######  Claim.

For every $i\in\left\\{k+1,\dots,k+\ell\right\\}$, $P_{i}=O_{i}$.

Suppose on the contrary that $P_{i}\neq O_{i}$ for some
$i\in\left\\{k+1,\dots,k+\ell\right\\}$. Then one of the two edges in $O_{i}$,
say $uv$, adjacent to $P_{i}$, satisfies $u\not\in V$ and $v\in V(P_{i})\cap
V$, contradicting Lemma 3.6(c).

Since $\pi(O_{k+1}),\dots,\pi(O_{k+\ell})$ are the same cycle of length
$\ell+1$, the union of $O_{1},\dots,O_{k+\ell}$ contains $k+\ell+1$ vertices.
By the maximality property of $\mathcal{K}$, there follows $k+\ell=n$, in
other words, $\pi(O_{k+1}),\dots,\pi(O_{n})$ are the same cycle.

######  Claim.

The cycles $O_{k+1},\dots,O_{n}$ also coincide.

The reason is that if $O_{i}\neq O_{j}$ for some $i,j>k$, then there exists an
$\left\\{O_{i},O_{j}\right\\}$-rainbow cherry with endpoints in $V$, that can
be completed to an $\mathcal{O}$-rainbow cycle by a $\mathcal{K}$-rainbow
path.

As in the parallel stage of the proof of Theorem 2.3, the last claim implies
that $\mathcal{O}$ is a saguaro.

Subcase 1.2: For some $i>k$, $\pi(P_{i})$ is a star centered at $\bar{v}$.

Without loss of generality $\pi(P_{k+1})$ is a star centered at $\bar{v}$. By
Lemma 3.6(b), $\bar{\mathcal{P}}$ consists of stars centered at $\bar{v}$ and
of cycles, and it does not have a rainbow cycle.

######  Claim.

Every star in $\bar{\mathcal{P}}$ is edge-disjoint from all the other members
of $\bar{\mathcal{P}}$.

Indeed, assume that for some $i,j>k$ we have an edge $u\bar{v}$ shared by
$\pi(P_{i})$ and $\pi(P_{j})$, where $\pi(P_{i})$ is a star centered at
$\bar{v}$. Then in $O_{i}$ the vertex $u$ has two neighbors in $V$ and in
$O_{j}$ it has at least one neighbor in $V$. Hence there is an
$\left\\{O_{i},O_{j}\right\\}$-rainbow cherry with endpoints in $V$ and center
$u$, which can be completed to an $\mathcal{O}$-rainbow cycle by a
$\mathcal{K}$-rainbow path.

By Proposition 3.5 it follows that there exist $\ell$ cycles in
$\bar{\mathcal{P}}$ avoiding $\bar{v}$, say
$\pi(P_{k+2}),\dots,\pi(P_{k+\ell+1})$, whose union with $\pi(P_{k+1})$
contains at most $\ell+2$ vertices, one of them being $\bar{v}$. Note that if
$\pi(P_{i})$ is a cycle avoiding $\bar{v}$, then $P_{i}=O_{i}$. Hence the
union of $O_{1},\dots,O_{k+\ell+1}$ contains at most $(k+1)+(\ell+1)$
vertices. To reconcile this with our choice of $\mathcal{K}$, the only way out
is that $k+\ell+1=n$ and none of $\pi(P_{k+2}),\dots,\pi(P_{n})$ contains
$\bar{v}$. Thus all of $O_{k+2},\dots,O_{n}$ avoid $V$, and so the union of
these $n-k-1$ cycles contains at most $n-k$ vertices. By the induction
hypothesis, the subfamily $\left\\{O_{k+2},\dots,O_{n}\right\\}$ is a saguaro
of cycles that avoid $V$. Recall that the vertices of $O_{k+1}$ alternate
between $V$ and $V(K_{n+1})\setminus V$. Therefore $\mathcal{O}$ is a saguaro.

#### Case 2:

Every cycle $O_{i}$ is Hamiltonian.

Let $S$ be an $\mathcal{O}$-rainbow star of maximum size, say $k$. Without
loss of generality, assume that the cycles represented in $S$ are
$O_{1},\dots,O_{k}$. Denote $\mathcal{K}:=\left\\{O_{1},\dots,O_{k}\right\\}$.
As in the proof of Theorem 2.3, using the fact that $\mathcal{O}$ has no
rainbow cycle, we can deduce that $k<n$. As there, if $k=2$ then all the
cycles in $\mathcal{O}$ are identical, so we may assume $k\geq 3$.

Let $c$ be the center of $S$ and $V$ the set of its leaves. Notice that every
pair of vertices in $V$ can be connected by a $\mathcal{K}$-rainbow cherry.
For an arbitrary $i>k$, by Lemma 3.6(a), $V$ is an independent set of $O_{i}$,
and so $k\leq(n+1)/2$.

Suppose for a moment that $k=(n+1)/2$. Since $n-k=k-1\geq 2$, there are at
least $2$ cycles in $\mathcal{O}\setminus\mathcal{K}$, and there is a vertex
$u\not\in V(S)$. Note that $V$ partitions both $O_{k+1}$ and $O_{k+2}$ into
arcs of length $2$. The two arcs through $u$ obtained respectively from
$O_{k+1}$ and $O_{k+2}$ yield an $\left\\{O_{k+1},O_{k+2}\right\\}$-rainbow
cherry with endpoints in $V$ and center $u$, which can be completed to an
$\mathcal{O}$-rainbow square by a $\mathcal{K}$-rainbow cherry in $S$.

Therefore $k<(n+1)/2$. Now, for every $i>k$, one of the arcs, call it $P_{i}$,
of $O_{i}$ defined by $V$ is of length at least $3$. By the maximality of $S$,
$P_{i}$ does not contain $c$. Let $\pi$ be the contraction that replaces
$V(S)$ by $\bar{v}$. Again the family
$\bar{\mathcal{P}}:=\left\\{\pi(P_{k+1}),\dots,\pi(P_{n})\right\\}$ is a
saguaro of cycles. Say $\pi(P_{n})$ is a common cycle in $\bar{\mathcal{P}}$.
Because $O_{n}$ is partitioned into at least $3$ arcs by $V$, one of the two
edges in $O_{n}$, say $uv$, adjacent to $P_{n}$ satisfies $u\not\in V(S)\cup
V(P_{n})$ and $v\in V\cap V(P_{n})$, which contradicts Lemma 3.6(c).

#### Case 3:

For every proper subfamily $\mathcal{K}$ of $\mathcal{O}$, $\lvert
V(\cup\,\mathcal{K})\rvert>\lvert\mathcal{K}\rvert+1$, and some $O_{i}$ is not
Hamiltonian.

The analysis of the last case can be taken verbatim from Theorem 2.3. ∎

##  4 Edge-disjoint families

Here we continue to pursue a rainbow cycle, but make the additional assumption
that our family consists of pairwise disjoint sets of edges. In terms of
colors, this amounts to the natural restriction that every edge of the
underlying graph gets just one color.666When an edge gets two colors, one may
or may not want to consider this a rainbow cycle of length $2$ (a _digon_). In
this paper we consider only cycles of length $3$ or more. If digons are
allowed, then the restriction to edge-disjoint families serves to avoid this
trivial kind of rainbow cycle.

For a family $\mathcal{E}$ of $n$ disjoint edge sets in $K_{n}$, we no longer
need to assume that each set in $\mathcal{E}$ is a cycle in order to guarantee
a rainbow cycle. The following trivial observation holds.

######  Proposition 4.1.

Every family of $n$ edge-disjoint nonempty subgraphs of $K_{n}$ has a rainbow
cycle. ∎

The sharpness of the above is witnessed by a family of single edges forming a
spanning tree. But there is a more general construction showing this.

######  Definition 4.2.

A family $\mathcal{E}$ of graphs is a _linkleaf_ if it is an empty family
(which we consider as having a ground set of one vertex), or the family
$\mathcal{E}$ can be partitioned into three subfamilies
$\mathcal{E}_{1},\\{E\\},\mathcal{E}_{2}$ such that $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ are two (possibly empty) vertex-disjoint linkleaves, and $E$
is a nonempty bipartite graph with respect to the bipartition
$V(\cup\,\mathcal{E}_{1}),V(\cup\,\mathcal{E}_{2})$.

We prove below that this recursive construction is a characterization of
families of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$ without any
rainbow cycle.

######  Theorem 4.3.

For every family $\mathcal{E}$ of $n$ edge-disjoint nonempty subgraphs of
$K_{n+1}$, no rainbow cycle exists if and only if the family is a linkleaf.

The main part of the proof consists of the following lemma.

######  Lemma 4.4.

Let $\mathcal{E}$ be a family of $n$ edge-disjoint nonempty subgraphs of
$K_{n+1}$, where $n\geq 1$. If $\mathcal{E}$ has no rainbow cycle then
$\mathcal{E}$ has a monochromatic cut, that is, a partition
$V(\cup\,\mathcal{E})=V_{1}\cup V_{2}$ such that exactly one member of
$\mathcal{E}$ has an edge (or more) from $V_{1}$ to $V_{2}$.

###### Proof of Theorem 4.3 assuming Lemma 4.4.

The “if” direction can easily be verified from the construction. For the “only
if” direction we use induction. The base case $n=0$ is trivial. Let
$\mathcal{E}$ be a family of $n\geq 1$ edge-disjoint nonempty subgraphs of
$K_{n+1}$ without any rainbow cycle. By Lemma 4.4, there exists a partition of
$V(K_{n+1})$ into $V_{1}$, say of size $k+1$, and $V_{2}$, say of size
$\ell+1$, where $k+\ell=n-1$, and a unique member $E$ of $\mathcal{E}$ having
an edge or more from $V_{1}$ to $V_{2}$. Since $\mathcal{E}$ has no rainbow
cycle, by Proposition 4.1, at most $k$ of the subgraphs have an edge or more
in $V_{1}$ and at most $\ell$ of them have an edge or more in $V_{2}$. Because
the total number of members of $\mathcal{E}$ is $k+\ell+1$, exactly $k$ of
them are contained in $V_{1}$, exactly $\ell$ of them are contained in
$V_{2}$, and $E$ has only edges from $V_{1}$ to $V_{2}$. It follows from the
induction hypothesis that $\mathcal{E}$ is a linkleaf. ∎

###### Proof of Lemma 4.4.

Assume for the sake of contradiction that the family
$\mathcal{E}:=\left\\{E_{1},\dots,E_{n}\right\\}$ has neither a rainbow cycle
nor a monochromatic cut. Pick an arbitrary edge $e_{i}$ from $E_{i}$ for each
$i$, and let $T$ be the rainbow set $\left\\{e_{1},\dots,e_{n}\right\\}$.
Since $T$ contains no cycle, $T$ must be a rainbow spanning tree.

We form a digraph $D$ with vertex set $[n]$, in which an arrow goes from $i$
to $j$, for $i\neq j$, if some edge of $E_{j}$ reconnects
$T\setminus\left\\{e_{i}\right\\}$. Due to the nonexistence of monochromatic
cuts in the family, for every $i$, some edge in $E_{j}$, for some $j\neq i$,
reconnects $T\setminus\left\\{e_{i}\right\\}$. Thus the minimum out-degree of
$D$ is at least $1$.

Without loss of generality, let $1\to 2\to\dots\to k\to 1$ be a minimum
circuit in $D$. As such, let $f_{i}$ be an edge in $E_{i}$ that reconnects
$T\setminus\\{e_{i-1}\\}$, for each $i\in[k]$, under the convention that
$e_{0}:=e_{k}$. Write $O_{i}$ for the unique cycle formed by adding $f_{i}$ to
$T$. Certainly $e_{i-1}$ is in $O_{i}$, and moreover $e_{i}$ is in $O_{i}$ as
$O_{i}$ cannot be rainbow. By the minimality of the circuit, for each
$i,j\in[k]$ with $i\neq j$ and $i\neq j-1\pmod{k}$, we have $i\not\to j$ in
$D$, which means that $f_{j}$ does not reconnect
$T\setminus\left\\{e_{i}\right\\}$, and so $e_{i}\not\in O_{j}$.

To summarize, for each $i,j\in[k]$, $e_{i}\in O_{j}$ if and only if $i=j$ or
$i=j-1\pmod{k}$. Set $O:=O_{1}\bigtriangleup\dots\bigtriangleup O_{k}$, where
$\bigtriangleup$ stands for symmetric difference. Note that

$\left\\{f_{1},\dots,f_{k}\right\\}\subseteq
O\subseteq(T\setminus\left\\{e_{1},\dots,e_{k}\right\\})\cup\left\\{f_{1},\dots,f_{k}\right\\}.$

By the first inclusion $O$ is nonempty, and by the second inclusion, it is
rainbow. Since $O$ is Eulerian, it contains a rainbow cycle. ∎

######  Remark.

It has come to our attention that Theorem 4.3 already appeared in [8], and
very recently it was generalized for binary matroids by Bérczi and Schwarcz
[6]. We still include our proof as it is elementary and transparent, and
moreover it can be easily adapted for binary matroids. In the adapted proof,
the binary-ness of the matroids is only needed in the last step of Lemma 4.4
to show $O$, a symmetric difference of circuits, is a disjoint union of
circuits. The rest of our argument works over arbitrary matroids.

##  5 Concluding remarks

###  5.1 Rainbow spanning in matroids

Proposition 2.1 can be seen as a special case of the following rainbow result
for matroids.

######  Proposition 5.1.

Let $M$ be a matroid of rank $n$ and let $e$ be an element in the ground set
$E$ of $M$. For every family $\left\\{A_{1},\dots,A_{n}\right\\}$ of subsets
of $E$, if each $A_{i}$ contains $e$ in its closure, then the family has a
rainbow set that contains $e$ in its closure.

###### Proof.

Let $R$ be a maximal rainbow set such that $R\cup\left\\{e\right\\}$ is
independent in $M$. If $e\in R$ we are done, so assume $e\not\in R$. As the
rank of $M$ is $n$, we know that $\lvert R\rvert<n$, and hence some $A_{i}$ is
not represented in $R$. Denote by $\mathrm{span}(\cdot)$ the closure operator
in $M$. Since $e\in\mathrm{span}(A_{i})\setminus\mathrm{span}(R)$, there
exists $a\in A_{i}\setminus\mathrm{span}(R)$. The set
$R^{\prime}:=R\cup\left\\{a\right\\}$ is then a rainbow independent set, and
by the maximality of $R$, we have that $R^{\prime}\cup\left\\{e\right\\}$ is
dependent, which implies $e\in\mathrm{span}(R^{\prime})$. ∎

To see that Proposition 2.1 follows from Proposition 5.1, note that for every
edge set $O$ whose vertex set is contained in $[n]$, $O$ contains an odd cycle
if and only if $e_{0}\in\mathrm{span}(A)$, where $e_{0},e_{1},\dots,e_{n}$
form the standard basis of $\mathbb{F}_{2}^{n+1}$ and
$A:=\left\\{e_{0}+e_{i}+e_{j}\colon\left\\{i,j\right\\}\in O\right\\}$. This
observation allows us to go back and forth between odd cycles in $K_{n}$ and
subsets of $E$ that contain $e_{0}$ in their closures, where

$E:=\left\\{(x_{0},x_{1},\dots,x_{n})\in\mathbb{F}_{2}^{n+1}\colon
x_{1}+\dots+x_{n}=0\right\\}$

is the ground set of a binary matroid of rank $n$.

###  5.2 Rainbow even cycles

Perhaps surprisingly, the analog of Proposition 2.1 and Proposition 3.2 for
even cycles is false. Figure 2 shows a family of $6$ squares ($4$-cycles) on
$6$ vertices without a rainbow even cycle. By gluing copies of this
construction, so that every new copy shares one vertex with the union of the
previous ones, we get a family of roughly $6n/5$ squares on $n$ vertices
without a rainbow even cycle.

Figure 2: A family of $6$ squares on $6$ vertices without any rainbow even
cycle.

To get an upper bound on the number of even cycles needed to guarantee a
rainbow even cycle, we observe that each connected component of a graph
without even cycles is a cactus graph.777Indeed, if two odd cycles share two
vertices, this gives rise to an even cycle. Note that the densest cactus graph
on $n$ vertices is a triangular cactus graph888A cactus graph is triangular
when every cycle in it is a triangle. (with one bridge if $n$ is even). Thus
the maximum number of edges in a graph on $n$ vertices without even cycles is
$\lfloor{3(n-1)/2}\rfloor$. From Proposition 3.1 we have the following rainbow
result.

######  Proposition 5.2.

Every family of $\lfloor 3(n-1)/2\rfloor+1$ even cycles in $K_{n}$ has a
rainbow even cycle.∎

This upper bound is not sharp: for example, $4$ even cycles on $4$ vertices
always have a rainbow even cycle.999The upper bound becomes sharp if the
family is allowed to consist of digons. This is seen by taking a triangular
cactus graph on $n$ vertices with $\lfloor 3(n-1)/2\rfloor$ edges, and using
one digon for each of its edges. Strictly speaking, however, this takes us
from graphs to multigraphs. We leave the determination of the exact number
needed in general (between roughly $6n/5$ and $3n/2$) as an open problem.

## Acknowledgements

We acknowledge the financial support from the Ministry of Educational and
Science of the Russian Federation in the framework of MegaGrant no.
075-15-2019-1926 when the first author worked on Sections 2 and 3 of the
paper.

## References

  * [1] Ron Aharoni and Eli Berger.  Rainbow matchings in $r$-partite $r$-graphs.  Electron. J. Combin., 16(1):Research Paper 119, 9, 2009.
  * [2] Ron Aharoni, Joseph Briggs, Jinha Kim, and Minki Kim.  Rainbow independent sets in certain classes of graphs, 2019.  arXiv:1909.13143 [math.CO].
  * [3] Ron Aharoni, Ron Holzman, and Zilin Jiang.  Rainbow fractional matchings.  Combinatorica, 39(6):1191--1202, 2019.  arXiv:1805.09732 [math.CO].
  * [4] Ron Aharoni, Dani Kotlar, and Ran Ziv.  Uniqueness of the extreme cases in theorems of Drisko and Erdős--Ginzburg--Ziv.  European J. Combin., 67:222--229, 2018.  arXiv:1511.05775[math.CO].
  * [5] Imre Bárány.  A generalization of Carathéodory’s theorem.  Discrete Math., 40(2-3):141--152, 1982.
  * [6] Kristóf Bérczi and Tamás Schwarcz.  Rainbow and monochromatic circuits and cuts in binary matroids, 2021.  arXiv:2012.05037 [math.CO].
  * [7] Arthur A. Drisko.  Transversals in row-Latin rectangles.  J. Combin. Theory Ser. A, 84(2):181--195, 1998.
  * [8] Dean Hoffman, Paul Horn, Peter Johnson, and Andrew Owens.  On rainbow-cycle-forbidding edge colorings of finite graphs.  Graphs Combin., 35(6):1585--1596, 2019.
  * [9] Jinha Kim, Minki Kim, and O-joung Kwon.  Rainbow independent sets on dense graph classes, 2020.  arXiv:2001.10566 [math.CO].
  * [10] Minki Kim and Alan Lew.  Complexes of graphs with bounded independence number.  Sém. Lothar. Combin., 84B:Art. 39, 12, 2020.
  * [11] R. Rado.  A theorem on independence relations.  Quart. J. Math., Oxford Ser., 13:83--89, 1942.


# Over-communicate no more:
Situated RL agents learn concise communication protocols

Aleksandra Kalinowska<EMAIL_ADDRESS>
Elnaz Davoodi<EMAIL_ADDRESS>
Florian Strub<EMAIL_ADDRESS>
Kory W. Mathewson<EMAIL_ADDRESS>
Ivana Kajić<EMAIL_ADDRESS>
Michael Bowling<EMAIL_ADDRESS>
Todd D. Murphey<EMAIL_ADDRESS>
Patrick M. Pilarski<EMAIL_ADDRESS>
###### Abstract

While it is known that communication facilitates cooperation in multi-agent
settings, it is unclear how to design artificial agents that can learn to
effectively and efficiently communicate with each other. Much research on
communication emergence uses reinforcement learning (RL) and explores
unsituated communication in one-step referential tasks—the tasks are not
temporally interactive and lack time pressures typically present in natural
communication. In these settings, agents may successfully learn to
communicate, but they do not learn to exchange information concisely—they tend
towards over-communication and an inefficient encoding. Here, we explore
situated communication in a multi-step task, where the acting agent has to
forgo an environmental action to communicate. Thus, we impose an opportunity
cost on communication and mimic the real-world pressure of passing time. We
compare communication emergence under this pressure against learning to
communicate with a cost on articulation effort, implemented as a per-message
penalty (fixed and progressively increasing). We find that while all tested
pressures can disincentivise over-communication, situated communication does
it most effectively and, unlike the cost on effort, does not negatively impact
emergence. Implementing an opportunity cost on communication in a temporally
extended environment is a step towards embodiment, and might be a pre-
condition for incentivising efficient, human-like communication.

##  1 Introduction

Effective communication is a key skill for collaboration in a multi-agent
setting (?). As humans, we share communication protocols and cooperative
conventions that have evolved over thousands of generations to optimize
communication efficiency. As an example, we communicate in accordance with
cooperative principles, such as Grice’s maxims of conversation (?). In line
with the maxim of quantity, we are known to try to be as informative as
possible, giving only as much information as is needed (?). If future
artificial systems are to cooperate with humans, it will be beneficial for
their communication protocols to follow these patterns (?, ?). As a result,
understanding the process of communication emergence and the pressures that
shape the emergent communication protocols is of interest to the scientific
community.

With a recent increase in available computational power, the field has seen a
lot of progress with communication successfully emerging between reinforcement
learning (RL) agents in a range of learning environments (?, ?). However,
prior work shows that the emerged communication protocols often do not share
properties of natural languages (?) and that artificial agents tend towards an
anti-efficient encoding (?). This likely happens because in many of the
studied environments, communication is not situated—the action space of the
agent does not include both communicative and environmental actions (?, ?).
Agents do not learn to reason about whether to communicate; instead,
communication is guaranteed and free to the agents. When free, excessive use
of communication does not negatively affect the outcome of the game (or cause
agent frustration), as it might in a real-world situation (?). As a possible
solution, we explore situated communication and show it is possible to obtain
concise communication protocols by providing the agent with an action-
communication trade-off.

In this work, we compare pressures that can incentivise conciseness during
communication emergence. As our testbed, we use a cooperative multi-step
navigation task with two RL agents. In the task, a speaker provides navigation
hints to help a listener reach a goal within a gridworld maze. We explore
three training regimes: (i) unsituated communication (cheap talk); the speaker
sends a message to the listener at each timestep without any cost, similar to
the communication paradigm in existing work (?, ?, ?), (ii) unsituated
communication with a per-message penalty; the speaker experiences a cost on
communication effort (either fixed or progressively increasing), similar to
prior work (?) when fixed, (iii) situated communication as introduced by
Wagner et al. (2003); the listener has to forgo an action to solicit
information from the advising agent, experiencing an opportunity cost on
communication. Using the collaborative navigation task, we evaluate how the
different pressures in the three training regimes can incentivise sparse
information sharing during communication emergence. We find that situated
communication (regime iii) outperforms an internal cost on communication
effort (regime ii) in terms of both conciseness of the emerged communication
protocol and overall task performance.

##  2 Background

Initially, emergent communication between RL agents was largely studied in
one-step referential games, such as the Lewis task (?, ?, ?, ?, ?). The Lewis
task (?) is a cooperative game, where the speaker sees an artifact (e.g., an
image) and communicates a message from a fixed vocabulary (e.g., a symbol) to
the listener, who then interprets the message to select a target item from
among a set of distractors. This type of learning environment is known to
successfully enable language development (?). However, this setting does not
recreate the temporal aspects of a real-world environment, which may influence
the structure of the emergent languages.

Recent work increasingly explores multi-step tasks that enable temporally
extended dialogue, more similar to real-world environments (?, ?, ?, ?, ?, ?,
?). Cao et al. (2018) investigate multi-step negotiation. Jaques et al. (2019)
test communication emergence during Sequential Social Dilemmas in
environments, such as Harvest or Cleanup. Evtimova et al. (2018) propose a
multi-modal, multi-step referential task (a modified version of the Lewis
task). Bouchacourt and Baroni (2019) introduce a fruit-tool matching game,
similar to a multi-step Lewis task but with a preference-based reward. Here,
we build on this body of work by introducing a multi-step navigation task in a
gridworld environment. In Appendix A.2, we elaborate on how our task compares
to existing work and on the direct impact of introducing multi-step
communication in this task.

The literature predominantly considers two types of communication: (i)
communication through a cheap talk channel (?, ?) and (2) communication
through environmental actions (?). In cheap talk, agents have a designated
communication channel where they share messages at every timestep—the messages
are free to the agents and agents do not reason about whether to communicate.
Many authors find that selfish agents do not learn to effectively use an
ungrounded cheap talk communication channel (?, ?). However, one can
incentivise communication in a cheap talk channel by rewarding an intrinsic
motivation to influence others (?) or by introducing a pro-social reward (?,
?), as we do in our work. On the other hand, when communicating through
actions, agents’ environmental actions are made visible to other agents,
enabling the environmental actions to be used for communication. Note that
environmental actions are binding—they impact the state of the environment and
the resulting reward, so agents do not have an inconsequential way to exchange
information as with a cheap talk channel. In these scenarios, cooperation has
a high success rate (?, ?, ?), but the communication is inflexible and
directly connected with the task—there is mixed opinion whether agents are
actually communicating (?). In this work, we evaluate a third type of
communication that we refer to as situated communication as introduced by
Wagner et al. (2003) and used e.g. by Lowe et al. (2019) in matrix games, such
as the Prisoner’s Dilemma. When using situated communication, the listener has
to actively choose between communicative and environmental actions. While only
environmental actions directly affect the environment and allow the agent to
obtain a reward, the agent can choose to forgo an environmental action to
communicate.

In most studies, the emerged language structures are analyzed for shared
commonalities with natural languages, such as compositionality or encoding
efficiency. Although desired, it is nontrivial for such properties to emerge
spontaneously (?). As a result, researchers introduce pressures during
training and/or structure the learning process to incentivise specific
language properties. To encourage compositionality in the emergent
communication protocol, one can introduce populations of agents (?, ?) or the
need for a language to be easily teachable (?). Efficient communication can be
incentivised by modifying the agents’ reward structure, e.g., by adding an
internal cost of articulation (?) or by prioritizing messages based on a
metric of confidence (?). Sparse communication has also been shown to emerge
in mixed and competitive settings, where communicating too much might harm
agent performance, e.g., in the case of prey coordinating an escape from
predators (?). In parallel, researchers have studied communication patterns
during competitive games—e.g., auctions—where the capacity of the
communication channel is externally bounded (?). Here, we propose situating
the communication in a multi-step task as a mechanism to shape the properties
of the emergent communication protocol.

In our experiments, we study the emergence of communication in a cooperative
multi-step navigation task. Like humans or robots that can only observe a
small part of the world in their proximity, the listener has a limited view of
its environment and has to rely on the speaker for guidance (?). The task is
an abstraction of a real-world task (?) where a person receives guidance from
an oracle while navigating towards a goal. As our primary testbed, we consider
a maze with T-junctions (i.e. junctions with a left/right turn) (?). The well-
defined decision points enable us to more easily quantify the amount of
information exchanged by the agents.

##  3 Environment

We define a cooperative navigation task as a Markov Decision Process (MDP)
with two RL agents. We test three environments: T-maze, dead ends, and four
rooms, as shown in Fig. 1. The T-maze serves as our primary testbed. All three
environments are set up as a pixel-based gridworld with a maze inside.
Features of the world are encoded with binary vectors and represented with
colors: walls are black ($[1,1,1]$), the maze is white ($[0,0,0]$), the agent
is green ($[0,1,0]$), and the target is blue ($[0,0,1]$), as shown in Fig. 10
in the Appendix. The full environmental representation is defined as a
$9\times 9\times 3$ matrix (height by width by RGB).

Figure 1: Experimental setup. (left) Gridworld environment & navigation task,
(right) experimental conditions.

The agents. There are two independent RL agents, a speaker and a listener
(i.e. acting agent). The speaker does not reside within the gridworld and
cannot take environmental actions (i.e. navigate the maze) but instead can
communicate information to the listener. The speaker’s action (i.e. message)
space spans $5$ symbols $[0,1,...,4]$. We refer to the message $m_{t}=0$ as a
null message, and $m_{t}\in[1,2,3,4]$ as non-zero messages. At each timestep,
the speaker can see the entire gridworld, including the location of the agent
and the location of the goal. The speaker’s view of the world map is rotated
to align with the direction that the listener is facing. The listener is
embedded in the gridworld and can take actions to move through the maze. The
action space of the listener spans $5$ actions [move up, move down, move
right, move left, stay in place]. The listener’s observation consists of the
environmental view (if any) concatenated with the message from the speaker. We
test the listener under two conditions: (1) with no visibility, where the
listener’s observation consists solely of the speaker’s message, and (2) with
partial visibility, where the listener can see the $3$ pixels directly in
front of them. The second variant gives the listener some environmental
context to take actions without needing to rely solely on communication. We
test agents with and without memory. Agents without memory have to rely only
on their current observations to take an action. Agents with memory have an
internal representation of the history of an episode—they can use accumulated
knowledge from prior timesteps to make decisions in the current timestep.

The task. The goal of the agents is to cooperate so that the listener reaches
the target. In each experimental episode, both agents receive a reward $R=1$
if the listener reaches the target before the episode terminates. Episode
timeout is set to $100$ steps with a gamma discount factor of $\gamma=0.99$.
In all three environments, the goal locations are randomly assigned to one of
the pixels indicated with a star in Fig. 1. There are $4$, $5$, and $32$
possible goal locations in the T-maze, dead ends, and four rooms environments,
respectively. In each episode, the listener agent starts from the ‘START’ cell
indicated in Fig. 1. In the T-maze, the agent always starts from the bottom
middle cell and the goal locations are randomly assigned to one of the $4$
corners of the maze.

##  4 Situated vs. Unsituated Communication

Wagner et al. (2003) classify simulated environments for communication
emergence based on the action space of the simulated agents. They define two
types of actions: (1) communicative (i.e. sending or receiving
signals)—actions that do not affect the state of the world or other agents,
and (2) non-communicative (i.e. environmental)—actions that affect the
environment and/or modify the agent’s own internal state. Depending on the
actions available to the agents, they define situated and unsituated
simulations of communication emergence:

  1. 1.

unsituated: an agent’s actions are only communicative (or only non-
communicative)

  2. 2.

situated: an agent’s actions include both communicative and non-communicative
actions.

Given these definitions, we define two modes of communication based on the
actions available to the listener. During unsituated communication in our
task, the speaker generates a $1$-token message at every timestep and the
message is broadcasted to the listener before they choose an action. We refer
to the listener using this mode of communication as a passive listener,
because it passively receives the speaker’s message at every timestep. When
messages are free, this communication mode is equivalent to cheap talk. In
situated communication, the listener can actively choose between (i) taking an
environmental action and (ii) soliciting a message. The message is only
broadcasted to the listener after they ask for information—we refer to this
listener as active. The active listener can solicit to receive information in
a following timestep by choosing a stay in place action at the current
timestep. The active listener experiences an opportunity cost to
communication—they have to forego an environmental move (that could bring them
closer to the target) to obtain information and make an informed decision. As
a result, they have to learn whether to communicate at all.

Similar to much of the existing work in the field (?), the communication in
our experiments is asymmetrical (i.e. the action space of the speaker and
listener are different). During unsituated communication, we simulate a
passive listener that can take environmental actions and receive signals from
a speaker but cannot send signals itself. If the agents’ action spaces were
symmetrical (the scenario considered by Wagner et al., 2003), this would be a
somewhat degenerate case—communication would never emerge between two agents
who can only receive signals and take environmental actions. As a result, our
definition of unsituated communication deviates slightly from the definition
introduced by Wagner et al. (2003).

##  5 Experimental Setup

Agent architectures. The speaker and the listener are designed as two
independent RL agents. Both agents have the same architecture without sharing
weights or gradient values. They both have a 2-layer Convolutional Neural
Network (CNN) that generates an $8-32$ bit representation $s$ of the
environment. In the case of the listener, this representation of the
environment gets concatenated with the message received from the speaker. In
both cases, the vector gets passed into a fully connected layer that generates
the agent’s action. Agents with memory, have an additional single-layer LSTM
(?) after their fully connected layer.

We train the agents using neural fitted Q learning (?), with an Adam optimizer
(?) and $Q_{t}(\lambda$) where $\lambda=0.9$. The Q values are updated using
temporal difference (TD) error where the bootstrapped $Q_{t}(\lambda$) is
defined as follows:

$Q_{t}(\lambda)=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}Q_{t}^{(n)}$

During training, agents use an $\epsilon$-greedy policy with the exploration
rate set as $\epsilon=0.01$.

Hyperparameters. For each experiment, we run a hyperparameter sweep over
learning rates of the speaker and listener $\alpha\in\\{10^{-5},10^{-6}\\}$
and over the size of the environmental representation $s\in\\{8,16\\}$, which
denotes the size of the output vector of the convolutional layers of the
agents’ networks. We run the simulation with each hyperparameter setting $10$
times with different random seeds. For each experiment, we present the best
mean over the $10$ replicas. The best mean is selected based on the metric of
solution optimality (the normalized reward per step). When we plot metric
means, we include the standard error of the mean.

Message penalties. In unsituated communication, we test the consequences of
introducing a cost of articulation for the speaker. In the baseline scenario
(i.e. cheap talk), all messages are free to the agent. With a cost of
articulation, each non-zero message incurs a penalty, while a null message
(the symbol $0$) remains free to the agent. We test two penalty mechanisms: a
fixed per-message penalty and a progressive per-message penalty. When fixed,
the per-message penalty remains constant throughout the entire duration of
training. We test fixed penalties with values $m_{p}\in\\{0.01,0.05,0.1\\}$.

As the second mechanism, we introduce a penalty curriculum with a scheduler
that progressively increases the penalty between stages. The penalty scheduler
is a mapping from the curriculum stage to the penalty in that stage. We test
two curriculum implementations with the following mappings
$m_{p1}=\\{0:0,1:0.01,2:0.02,3:0.03,4:0.04,5:0.05,...\\}$ and
$m_{p1}=\\{0:0,1:0.01,2:0.05,3:0.1,4:0.2,5:0.3\\}$. Both curricula start with
no per-message penalty in stage $0$, allowing cost-less exploration of a
successful communication protocol. In the next stage, both curricula impose a
small penalty that progressively increases over the time of training.
Intuitively, the first curriculum is more gradual, enabling a more stable
solution; the second curriculum is more rapid, possibly speeding up the
learning process. The agents can progress to the next stage of the curriculum
after $2M$ or $5M$ training steps if they achieve a performance threshold or
if they spend $15M$ steps in their current stage. We test 3 progression
thresholds based on the agents’ success rate in reaching the target: $92\%$,
$95\%$, and $97\%$.

Figure 2: Comparison of pressures for avoiding over-communication (mean over
10 seeds) in the T-maze. Top row illustrates an average metric of
success—under almost all conditions agents are able to find a solution to the
task. Middle row illustrates an average metric of optimality—with context
(i.e., visibility and/or memory) agents require fewer steps to reach the
target. Bottom row illustrates communication conciseness—situated agents are
able to communicate most sparingly.

Evaluation metrics. We evaluate agent performance according to three criteria:
(i) task success (via the mean return per episode), (ii) solution optimality
(via the normalized reward per step), and (iii) communication efficiency (via
communication sparsity). The metric of task success is calculated after each
episode as

$M_{t}(n)=(\sum_{i=1}^{n}R_{i})/n,$ (1)

where $n$ is the number of episodes thus far and $R_{i}$ is the reward for the
$i$th episode. The metric represents the likelihood of the agents succeeding
at reaching the target before episode timeout. When it converges to $1$,
agents are reliably reaching the target in each episode. The normalized reward
per step quantifies the optimality of the path taken to solve the task. If the
task is solved in the optimal number of steps ($s_{opt}=9$), agents obtain a
per-step reward of $1$. Formally, it is calculated as

$M_{o}(n)=s_{opt}\sum_{i=1}^{n}R_{i}/s_{i},$ (2)

where $s_{i}$ is the number of steps the agent took in episode $i$. Finally,
the metric of communication sparsity quantifies the efficiency of information
exchanged between the collaborating agents. We define it as the average
negative logarithm of the number of non-zero messages generated by the speaker
per episode, such that

$M_{s}(n)=(\sum_{i=1}^{n}-\log m_{i})/n,$ (3)

where $m_{i}$ is the number of non-zero messages in episode $i$. Agent pairs
that converge to a higher value form a more efficient communication
protocol—they exchange fewer messages per episode. If agents were able to
solve the task using a single message, their sparsity metric would equal $0$.
As an example, in the T-maze, depending on the listener’s characteristics:
partial or no visibility, the optimal number of messages is equal to two
($M_{s}=-0.7$) or nine ($M_{s}=-2.2$) messages per episode for agents without
memory, and one ($M_{s}=0$) message per episode for agents with memory.

##  6 Results

We experimentally compare two pressures that can incentivise a concise
exchange of information during communication emergence. Specifically, we
consider two types of pressure:

  * •

A per-message penalty: similar to a cost of articulation. During unsituated
communication, we impose a cost on effort through a penalty on non-zero
messages. We test (a) a fixed penalty, and (b) a penalty curriculum with a
progressively increasing per-message penalty.

  * •

An opportunity cost on communication: mimicking the pressure of time in a
real-world situation. We study agents using situated communication, where at
each step the listener faces an action-communication trade-off.

In our experiments, we train agent pairs communicating (1) using cheap talk
(baseline), (2) using unsituated communication with a fixed penalty or a
penalty curriculum, and (3) using situated communication. In all experiments,
we train agents under two visibility and two memory conditions (see Sections 3
& 5 for more details). Without visibility or memory, the acting agent relies
solely on the speaker’s most recent message to take an action. With visibility
and memory, the acting agent has increasingly more contextual information,
allowing for sparser and more efficient communication.

Figure 3: Communication protocols for successful agent pairs in a T-maze
environment. Communication protocols are analogous when the listener has no
context (left-most column). With context, agents with situated communication
learn to exchange information sparsely, communicating mostly at the junctions.

###  6.1 Cheap talk (baseline)

Without pressures to be concise, agents successfully learn to solve the task.
We start by analyzing the learning pattern and behavior of agents without
communication constraints—we use their performance as a reference in our
subsequent analysis. When allowed to communicate, all agents in the T-maze
environment (grey lines in Fig. 2) learn to solve the task—their mean return
per episode converges to $1$. Best agent pairs find an optimal solution—their
normalized reward per step converges to $1$. With both memory and partial
visibility for context, even the average performance is close to optimal
(refer to Fig 2 column D, row 2). Moreover, we analyze the sparsity of the
established communication protocol. With unsituated communication and no
pressures (cheap talk), agents have no incentive to be sparse. As a result,
for all tested conditions, their sparsity metric is equal to the number of
steps needed to solve the task, and lowest compared to agents with added
pressures (refer to the grey lines in Fig. 2 row 3).

For the best-performing agent pairs, we analyze the communication protocol
qualitatively as illustrated in Fig. 3. Best-performing agent pairs agree on
unambiguous meanings of messages and, in some cases, learn synonyms to signal
the same environmental action. Under partial visibility (refer to the bottom
middle heatmap in Fig. 3), the meaning of messages depends on the
environmental context (e.g. message $1$ at the corridor might be consistently
interpreted by the listener as ‘move up’ but at the junction as ‘move right’).
All else equal, successful agents without memory converge to a just-in-time
protocol, where at each time step the listener can unambiguously interpret the
speaker’s message. Interestingly, memory influences timing in the established
communication protocols. The best-performing agents with memory learn a look-
ahead communication protocol. As an example, a speaker with memory might
broadcast the same message for the first $4$ steps of a T-maze episode,
alerting the listener to make a left or right turn at the junction (see the
bottom right heatmap in Fig. 3).

Lastly, we analyze agent performance in two other environments. The learning
curves are illustrated in Fig. 4. In four rooms, baseline agents achieve
similar performance to the T-maze environment. The dead ends maze is more
difficult—not all agents are able to solve the task. Importantly, compared to
the T-maze, both dead ends and four rooms are significantly different from the
listener perspective. In dead ends, when the listener sees a corridor (i.e.
wall-path-wall alternating pixels), it can no longer learn to always go
straight—$4$ out of $5$ times it has to turn when seeing a corridor at the
first junction. As a result, it has to rely more on the messages from the
speaker. Similarly, in four rooms, there are many possible goal locations
($32$ compared to $4$ in the T-maze) and the environmental context is
ambiguous—visibility does not help the listener with decision-making as much
as it does in the T-maze. Again, the listener has to rely more on the
messages. Because the dead ends and four rooms environments are more ambiguous
than the T-maze environment from the listener perspective, we only consider
listeners with context (i.e. memory and partial visibility). With added
pressures, this allows the agent pair to learn to communicate more sparingly
and still succeed at the task.

Figure 4: Comparison of pressures for avoiding over-communication (mean over
10 seeds) in the 3 environments. All agents have memory; listener has partial
visibility. Across all 3 environments, situated agents agree on the most
concise communication protocols without sacrificing their ability to solve the
task.

###  6.2 Unsituated communication with a penalty (fixed and progressive)

A fixed penalty improves communication sparsity but makes communication
emergence more difficult. We test four fixed penalty values to evaluate the
impact of a fixed penalty on communication emergence. In Fig. 5, we illustrate
the learning curves for agents training with a fixed penalty. Note that very
few agent pairs learn to reliably solve the task. Only a few agent pairs find
a quasi-optimal solution. Secondly, note in the bottom plots in Fig. 5 that
when a cost of articulation is introduced, speakers send few non-zero messages
at the beginning of training. The decrease in early exploration of a common
language likely makes it harder for agents to establish a successful
communication protocol and consequently causes difficulty in collaborating to
reach the target.

In summary, when agents converge to a successful communication protocol, the
per-message penalty incentivises sparse communication. However, overall
convergence rates are low. Out of the three tested penalty values, a fixed
penalty $=0.05$ seems to perform best. In Fig. 2 and Fig. 4 for comparison
with other pressures, we include agents trained with a fixed penalty $=0.05$.

A penalty curriculum does not negatively impact performance but it does not as
strongly incentivise conciseness. To mitigate the issue of stifled early
exploration, we implement penalty curricula, in which agents start training
with no per-message penalty. Only after they reach a performance threshold (as
described in Section 5), the speaker begins to experience a penalty for every
non-zero message. As visible in Fig. 2, this strategy significantly improves
convergence rates—agents reliably learn to communicate on par with baseline
agents. However, communication is not sparse. The agents exchange only
slightly fewer messages than baseline agents (refer to the green vs. grey
lines in Fig. 2 row 3). Once they find a communication protocol that works,
they seem unlikely to change it even with an increasing penalty—the sparsity
metric remains relatively constant throughout training. The trend is very
similar in the other two mazes (see Fig. 4).

All in all, introducing a penalty (fixed or progressive) makes the
communication sparser compared to baseline. However, the sparsity of
communication is still suboptimal.

Figure 5: Communication emergence with a cost on communication effort in the
T-maze. Agents without memory. (top) The additional pressure makes learning
more difficult—task performance for blue lines is lower than for the grey
lines (agents using cheap talk). (bottom) The immediate cost of non-zero
messages stifles early exploration.

###  6.3 Situated communication

The pressure of time in a multi-step interaction can incentivise sparse
communication without compromising communication emergence. In the last set of
experiments, we evaluate the impact of situated communication on language
emergence. We find that situated communication incentivises conciseness
without stifling early exploration. Active listeners learn over time that
communication comes at a cost, adjusting when and whether they solicit
information, rather than avoiding communication early on (refer to the orange
lines in Fig. 2 row 3). After training, agents using situated communication
achieve highest communication sparsity. Importantly, the sparsity does not
result in a loss in task performance—agents with an active listener follow
learning patterns similar to baseline agents (refer to Fig. 2 row 1 & 2).

In a T-maze environment, the active listener can learn to near optimally
solicit information, asking ~$2.06$ and ~$9.76$ times per episode given
partial and no visibility, respectively. In order to be theoretically optimal
under the no visibility condition, an active listener without memory requires
$9$ messages per episode ($1$ message per step) and, under partial visibility,
$2$ messages per episode ($1$ at each junction). The heatmaps in Fig. 3
illustrate example communication protocols of successful agent pairs. Under
the no memory and no visibility condition, the listener queries the speaker at
each timestep, in line with the optimal strategy. Under the partial visibility
condition, information solicitation takes place mostly at the junctions, where
the acting agent has a choice between two viable environmental actions.

Interestingly, when we test situated communication between agents with memory,
agents continue to ask for information at the junctions when it is immediately
actionable, as visible in the top right heatmap in Fig. 3. This is non-
obvious—given memory, the active listener could ask for information at any
point in the maze. This result suggests that it is easier for agents to
succeed at the task when they exchange information when it is immediately
actionable. There might be benefit to allowing agents to reason about the
timing of communication in multi-step interactions. We show more results that
support this thesis in Appendix A.2.

Lastly, we test the robustness of situated communication across two other
environments: dead ends and four rooms. As visible in Fig. 4, across all three
environments, active listeners learn to reliably solve the task—they achieve a
mean return per episode equal to $1$—while requiring the least amount of
communication—their sparsity metric is closest to $0$. In some mazes, active
listeners converge to solutions that are slightly suboptimal compared to
agents using other modes of communication, meaning that on average they take
more steps to reach the target. Future work will investigate further how
agents using situated communication can learn to solve the task optimally. A
symmetrical implementation of situated communication, where both agents can
act in the environment, might offer a robust solution.

##  7 Conclusions & Discussion

We find that giving the listener agency to choose whether to communicate
enables agents to learn how to concisely exchange task-relevant information.
By situating the communication in the task, we allow the functional pressure
of time to shape the emergent communication protocol to be sparse, in line
with the Gricean maxim of quantity. A cost of articulation, implemented in the
form of a per-message penalty, is not as effective.

As common in related work and described in Section 4, the current
implementation of communication is asymmetrical—only the speaker has
privileged information and only the listener can take non-communicative
actions in the environment. Our ongoing work will expand this implementation
and situate both the speaker and listener in the environment, enabling both
agents to communicate and take non-communicative actions in the maze-bazed
world. Moreover, we would like to explore more complex cooperative tasks, such
as those in the Overcooked game environment (?, ?). One of the objectives of
achieving concise communication protocols is to design RL agents that can
effectively communicate with people. In the work’s current format, we
anticipate significant societal benefit without negative societal impacts.

## A

###  A.1 Implementation details

Agent architecture is visualized in Fig. 6. All models were implemented in
Python using JAX (?) and Haiku (?). For training, we used GPUs V100 and P100.

Figure 6: Agents’ architecture and mechanism of communication. Figure 7:
Comparison of upfront and real-time messaging. Agents have memory. Real-time
messaging improves convergence on a successful communication protocol. With
upfront messaging, agents learn to solve the task before episode timeout when
the listener has partial visibility. However, convergence is slow and agents
are unlikely to solve the task in the optimal number of steps.

###  A.2 Experimental comparison of upfront vs. real-time messaging

Real-time communication improves language emergence compared to upfront
messaging. As an additional experiment, we compare real-time communication
(multi-step cheap talk) with upfront messaging. In upfront messaging, the
speaker generates a 1-, 2-, or 3-token message at the beginning of each
episode and that message gets broadcasted to the listener at each timestep
throughout the episode. It is a form of unsituated communication, where the
speaker can only generate one message at the beginning of an episode. In both
scenarios, the theoretical capacity of the communication channel allows the
agents to communicate the necessary information, whether the agents choose to
communicate directions, e.g., ‘turn right’, or a goal address, e.g., ‘top left
corner’. With upfront messages of length $1$, $2$, and $3$, the speaker has
$5$, $25$, or $125$ unique messages available for communication, respectively.

In Fig. 7, we plot the best agent pairs as well as the mean over replicas with
the same hyperparameters as the best agent pair. With both real-time and
upfront messaging, agents succeed in establishing a successful communication
protocol when the listener has partial visibility—they converge to a mean
return of $1$ per episode. With no visibility for the acting agent, agent
pairs with upfront messaging do not succeed at solving the task. Moreover, the
real-time agents are more likely to converge to an optimal solution, being
able to solve the T-maze task in $9$ moves. With $1$ upfront token, even the
best agents learn to at-best solve the task in $12$ steps. These agents seem
to reliably learn unique messages to encode the action required at the first
turn or the right/left part of the address, but they do not establish a unique
encoding for the top/bottom portion of the address, as visible in the top
heatmap in Fig. 7. With $3$ upfront tokens, the best agent pair agrees on $4$
distinct symbols to encode the $4$ possible goal locations. However,
convergence is slow and on average agent pairs perform less optimally than
under the real-time communication paradigm. We hypothesize that there are
benefits to allowing communication to emerge from multi-step interactions. Our
findings suggest that it is easier for agents to learn to communicate if they
can exchange information when it is immediately actionable.

Figure 8: Communication emergence with a cost on communication effort. Agents
with memory; speaker experiences a per-message penalty. With memory, overall
performance improves—more agent pairs converge to an optimal solution.
However, relative to baseline, agents with a message penalty have more
difficulty learning to jointly solve the task. In the heatmaps on the right,
we illustrate the communication protocol of the best agent pairs. Note that
the penalty is largely ineffective—the agents send many non-zero messages per
episode.

Figure 9: Best agent pairs training with a penalty curriculum. (top)
Curriculum with mapping $m_{p1}$ (bottom) curriculum with mapping $m_{p2}$.

###  A.3 Additional results for agents with a per-message penalty

In the main paper, we present results for experiments on agents without
memory. In Fig. 8, we present the same experiment on agents with memory.
Overall, agents with memory perform better than agents without memory.
However, the trends remain the same—the penalty negatively impacts convergence
and the best-performing agents that find optimal task solutions do not exhibit
sparse communication protocols.

In Fig. 9, we visualize the learning curves for the two curricula in parallel
with the agents’ progression through the curriculum stages. The curriculum
with mapping $m_{p1}$ achieves better overall performance and is included in
the comparison plots in the main paper (Fig. 2 and Fig. 4).

###  A.4 Additional results for agents using situated communication

Fig. 10 shows a step-by-step example episode for a listener with partial
visibility. The gridworld colors correspond to the color encoding included in
the agents’ observation vectors during the task.

Figure 10: Walk-through of an example episode with situated communication. The
listener learns to solve the task optimally, deciding to stay and ask for
information when at a junction (twice during the episode). At each of the $11$
timesteps, we visualize (left) the speaker’s view of the board with an
overlaid green box indicating the listener’s view, and (right) the speaker’s
message and listener’s action at that step.

###  A.5 Additional results on the impact of pressures on communication
conciseness

In the main text, we plot mean learning curves selected based on the highest
mean normalized reward per step for a given set of hyperparameters. Here, we
include results from the same experiments as in the main text, but instead we
plot learning curves for the best agent pair. Fig. 11 includes the same
comparison as Fig. 2 in the main text; Fig. 12 includes the same comparison as
Fig. 4. In Fig. 12, we present the best performing agent pairs from our
hyperparameter sweep as well as the mean over the $10$ replicas with the same
hyperparameters as the best performing pair. The best performing agent pairs
are selected based on the metric of solution optimality (the normalized reward
per step). Overall, the trends of the best performing agent pairs are
consistent with the mean trends described in the paper.

Figure 11:  Comparison of pressures for avoiding over-communication (best
agent pairs) in the T-maze.

Figure 12: Agents in 3 environments (top) using situated communication
compared to cheap talk, (bottom) using unsituated communication with a fixed
penalty and penalty curriculum.

## References

  * Blumrosen, Nisan, & Segal Blumrosen, L., Nisan, N., & Segal, I. (2007).  Auctions with severely bounded communication.  In Journal of Artificial Intelligence Research, Vol. 28, pp. 233–266.
  * Bouchacourt & Baroni Bouchacourt, D., & Baroni, M. (2019).  Miss tools and mr fruit: Emergent communication in agents learning about object affordances.  In Annual Meeting of the Association for Computational Linguistics.
  * Bradbury et al. Bradbury et al., J. (2020).  Jax: composable transformations of python+ numpy programs.  In http://github.com/google/jax.
  * Cao et al. Cao et al., K. (2018).  Emergent communication through negotiation.  In Int. Conf. on Learning Representations.
  * Carroll et al. Carroll et al., M. (2019).  On the utility of learning about humans for human-AI coordination.  In Advances in Neural Information Processing Systems.
  * Chaabouni et al. Chaabouni et al., R. (2019).  Anti-efficient encoding in emergent communication..
  * Chaabouni et al. Chaabouni et al., R. (2021).  Emergent communication at scale.  In Int. Conf. on Learning Representations.
  * Choi, Lazaridou, & De Freitas Choi, E., Lazaridou, A., & De Freitas, N. (2018).  Compositional obverter communication learning from raw visual input.  In Int. Conf. on Learning Representations.
  * Chopra, Singh, et al. Chopra, A. K., Singh, M. P., et al. (2020).  An evaluation of communication protocol languages for engineering multiagent systems.  In Journal of Artificial Intelligence Research, Vol. 69, pp. 1351–1393.
  * Crandall et al. Crandall et al., J. W. (2018).  Cooperating with machines.  In Nature Communications.
  * Crawford & Sobel Crawford, V. P., & Sobel, J. (1982).  Strategic information transmission.  In Econometrica: Journal of the Econometric Society. JSTOR.
  * Das et al. Das et al., A. (2019).  Tarmac: Targeted multi-agent communication.  In Int. Conf. on Machine Learning.
  * De Vries et al. De Vries et al., H. (2018).  Talk the walk: Navigating New York City through grounded dialogue.  In arXiv preprint arXiv:1807.03367.
  * Deacon & Rawlins Deacon, R. M., & Rawlins, J. N. P. (2006).  T-maze alternation in the rodent.  In Nature Protocols. Nature Publishing Group.
  * Denis et al. Denis et al., M. (1999).  Spatial discourse and navigation: An analysis of route directions in the city of Venice.  In Applied Cognitive Psychology.
  * Eccles et al. Eccles et al., T. (2019).  Biases for emergent communication in multi-agent reinforcement learning.  In Advances in Neural Information Processing Systems.
  * Evtimova et al. Evtimova et al., K. (2018).  Emergent communication in a multi-modal, multi-step referential game.  In Int. Conf. on Learning Representations.
  * Farrell & Rabin Farrell, J., & Rabin, M. (1996).  Cheap talk.  In Journal of Economic Perspectives.
  * Foerster et al. Foerster et al., J. (2016).  Learning to communicate with deep multi-agent reinforcement learning.  In Advances in Neural Information Processing Systems.
  * Grice Grice, H. P. (1975).  Logic and conversation.  In Speech Acts.
  * Hennigan et al. Hennigan et al., T. (2020).  Haiku: Sonnet for JAX..
  * Hochreiter & Schmidhuber Hochreiter, S., & Schmidhuber, J. (1997).  Long short-term memory.  In Neural Computation.
  * Jaques et al. Jaques et al., N. (2019).  Social influence as intrinsic motivation for multi-agent deep reinforcement learning.  In Int. Conf. on Machine Learning.
  * Kajić, Aygün, & Precup Kajić, I., Aygün, E., & Precup, D. (2020).  Learning to cooperate: Emergent communication in multi-agent navigation.  In Meeting of the Cognitive Science Society.
  * Kingma & Ba Kingma, D. P., & Ba, J. (2015).  Adam: A method for stochastic optimization.  In Int. Conf. on Learning Representations.
  * Kirby & Hurford Kirby, S., & Hurford, J. R. (2002).  The emergence of linguistic structure: An overview of the iterated learning model.  In Simulating the Evolution of Language.
  * Knott et al. Knott et al., P. (2021).  Evaluating the robustness of collaborative agents.  In Advances in Neural Information Processing Systems.
  * Kottur et al. Kottur et al., S. (2017).  Natural language does not emerge ‘naturally’ in multi-agent dialog.  In Conf. on Empirical Methods in NLP.
  * Lazaridou & Baroni Lazaridou, A., & Baroni, M. (2020).  Emergent multi-agent communication in the deep learning era.  In arXiv preprint arXiv:2006.02419.
  * Lazaridou et al. Lazaridou et al., A. (2018).  Emergence of linguistic communication from referential games with symbolic and pixel input.  In Int. Conf. on Learning Representations.
  * Lewis Lewis, D. (1969).  Convention.  Harvard University Press.
  * Li & Bowling Li, F., & Bowling, M. (2019).  Ease-of-teaching and language structure from emergent communication.  In Advances in Neural Information Processing Systems.
  * Lowe et al. Lowe et al., R. (2019).  On the pitfalls of measuring emergent communication.  In Int. Conf. on Autonomous Agents and Multiagent Systems.
  * Mordatch & Abbeel Mordatch, I., & Abbeel, P. (2018).  Emergence of grounded compositional language in multi-agent populations.  In AAAI Conf. on Artificial Intelligence.
  * Noukhovitch et al. Noukhovitch et al., M. (2021).  Emergent communication under competition.  In Int. Conf. on Autonomous Agents and Multiagent Systems.
  * Riedmiller Riedmiller, M. (2005).  Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method.  In European Conf. on Machine Learning.
  * Rita, Chaabouni, & Dupoux Rita, M., Chaabouni, R., & Dupoux, E. (2020).  “LazImpa”: Lazy and impatient neural agents learn to communicate efficiently.  In Conf. on Computational Natural Language Learning.
  * Rita et al. Rita et al., M. (2022).  On the role of population heterogeneity in emergent communication.  In Int. Conf. on Learning Representations.
  * Shoham & Leyton-Brown Shoham, Y., & Leyton-Brown, K. (2008).  Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.  Cambridge University Press.
  * Singh, Jain, & Sukhbaatar Singh, A., Jain, T., & Sukhbaatar, S. (2019).  Learning when to communicate at scale in multiagent cooperative and competitive tasks.  In Int. Conf. on Learning Representations.
  * Steels Steels, L. (2003).  Evolving grounded communication for robots.  In Trends in Cognitive Sciences.
  * Steels & Brooks Steels, L., & Brooks, R. (1995).  The Artificial Life Route to Artificial Intelligence: Building Embodied, Situated Agents.
  * Wagner et al. Wagner et al., K. (2003).  Progress in the simulation of emergent communication and language.  In Adaptive Behavior.
  * Zhang, Zhang, & Lin Zhang, S. Q., Zhang, Q., & Lin, J. (2019).  Efficient communication in multi-agent reinforcement learning via variance based control.  In Advances in Neural Information Processing Systems.