# Isomorphic Bisections of Cubic Graphs

S. Das Institut für Mathematik, Freie Universität Berlin, 14195 Berlin,
Germany. E-mail<EMAIL_ADDRESS>Research supported by the Deutsche
Forschungsgemeinschaft (DFG) project 415310276. A. Pokrovskiy Department of
Mathematics, University College London. E-mail:
<EMAIL_ADDRESS>B. Sudakov Department of Mathematics, ETH,
8092 Zurich, Switzerland. E-mail<EMAIL_ADDRESS>Research
supported in part by SNSF grant 200021_196965.

###### Abstract

Graph partitioning, or the dividing of a graph into two or more parts based on
certain conditions, arises naturally throughout discrete mathematics, and
problems of this kind have been studied extensively. In the 1990’s, Ando
conjectured that the vertices of every cubic graph can be partitioned into two
parts that induce isomorphic subgraphs. Using probabilistic methods together
with delicate recolouring arguments, we prove Ando’s conjecture for large
connected graphs.

##  1 Introduction

Graph theory enjoys applications to a wide range of disciplines because graphs
are incredibly flexible mathematical structures, capable of modelling very
complex systems. The study of complicated networks motivates the following
important question: to what extent can a graph be decomposed into simpler
subgraphs?

Spearheading this line of research is the classic problem of graph colouring,
one of the oldest branches of graph theory. When colouring a graph, one seeks
to partition the vertices into as few independent (edgeless) sets as possible.
Indeed, subgraphs cannot get much simpler than independent sets, but such
ambitious goals come at a cost. Not only is the determination of a graph’s
chromatic number a notoriously difficult problem, but even when dealing with
sparse graph classes, one can require many colours. For instance, many
$d$-regular graphs cannot be partitioned into much fewer than $d$ independent
sets.

Often one does not want to have such a large number of parts, and so it is
natural to ask what can be achieved with fewer colours. An early result along
these lines was provided by Lovász [13], who proved that, given a graph $G$ of
maximum degree $d$, some number of colours $t$, and a sequence
$d_{1},d_{2},\ldots,d_{t}$ with $\sum_{i}d_{i}=d-t+1$, one can $t$-colour the
vertices of $G$ such that the $i$th colour class induces a subgraph with
maximum degree $d_{i}$. In particular, we can partition any graph into two
subgraphs, each with half the maximum degree.

While reducing the maximum degree certainly simplifies graphs, it still allows
for large connected subgraphs within the colour classes. A different
objective, therefore, is to find clustered colourings, which are colourings
where each monochromatic component is of bounded size. Alon, Ding, Oporowski
and Vertigan [6] proved, among other results, that any graph with maximum
degree four can be two-coloured such that the largest monochromatic components
are of order at most $57$. However, they also constructed six-regular graphs
with arbitrarily large monochromatic components in every two-colouring.
Answering one of their questions, Haxell, Szabó and Tardos [10] proved that
clustered two-colourings of graphs of maximum degree five always exist. Aside
from improving the bounds on the monochromatic component sizes, subsequent
research has sought to explore which graph classes admit clustered colourings,
and what is possible with more colours. A more general setting, in which the
size of monochromatic components can grow with the size of graph, has also
been studied. For example, it was proved in [12] that any planar $n$-vertex
graph has a two-colouring in which all monochromatic components have size at
most $O(n^{2/3})$, and this is tight. For more results on vertex colourings
with small monochromatic components, we refer the interested reader to the
survey of Wood [16].

The above results show that when we restrict our attention to graphs of small
maximum degree, there is less room for complexity, and therefore we can prove
strong partitioning results. One might further try to achieve more than simply
bounding the size of monochromatic components. Indeed, it appears that in the
case of cubic graphs is also possible to control the structure of such
components. An early result along these lines is due to Akiyama, Exoo and
Harary [4], who proved that every cubic graph admits a two-_edge_ -colouring
in which every monochromatic component is a path, with a short proof of this
result provided by Akiyama and Chvátal [3] soon after. Although these results
allowed for paths of unbounded length, Bermond, Fouquet, Habib and Péroche [8]
conjectured that paths of length at most five suffice, a result that would be
best possible. Partial results, with larger but finite bounds on the path
lengths, were obtained by Jackson and Wormald [11] and by Aldred and Wormald
[5], before the conjecture was proven by Thomassen [15] in 1999.

######  Theorem 1.1.

The edges of any cubic graph can be two-coloured such that each monochromatic
component is a path of length at most five.

One can also try to find different structure in the partition than just
finding path forests with small components. One attractive conjecture of
Wormald [17] from 1987 asks whether we can colour the edges of every cubic
graph with an even number of edges so that the red and blue subgraphs form
_isomorphic_ linear forests. This is known to hold for particular classes of
graphs — it was proved for Jaeger graphs in [8, 17], and for some further
classes of cubic graphs in [9]. Given Wormald’s Conjecture, it is then natural
to ask for analogues when colouring vertices rather than edges. In this
direction, the following striking conjecture was made by Ando in 1990’s.

######  Conjecture 1.2.

The vertices of any cubic graph can be two-coloured such that the two colour
classes induce isomorphic subgraphs.

This conjecture was first mentioned in print by Abreu, Goedgebeur, Labbate and
Mazzuoccolo [2], who drew connections between Conjecture 1.2, Wormald’s
conjecture and a conjecture of Ban and Linial [7] (see Section 4 for
discussion of the latter). They further obtained computational results
verifying the conjecture for graphs on at most $32$ vertices. Hence any
counterexample to Conjecture 1.2 must have at least $34$ vertices. Observe
that any minimal counterexample must be connected, as the components of a
graph can be coloured independently. In this paper we essentially resolve this
problem and prove that large connected cubic graphs satisfy Ando’s conjecture.
This shows that there can be at most finitely many minimal counterexamples.

######  Theorem 1.3.

Every sufficiently large connected cubic graph admits a two-vertex-colouring
$\varphi$ whose colour classes induce isomorphic subgraphs.

The remainder of this paper is organized as follows. In Section 2, we present
the proof of Theorem 1.3. The proof uses probabilistic methods together with
delicate recolouring arguments. In the process of recolouring we use some
gadgets which we call $P_{t}$-reducers. The existence of these structures is
shown in Section 3. Finally, we make some concluding remarks and discuss open
problems in Section 4.

Notation. We shall call the colours used in our two-colourings red and blue.
To show that the red and blue subgraphs are isomorphic, we will need to keep
track of the monochromatic components. Given a fixed graph $H$ and a
red-/blue-colouring $\varphi$ of the vertices of a graph $G$, we denote by
$r_{H}(G,\varphi)$ the number of red components of $G$ under $\varphi$ that
are isomorphic to $H$, and define $b_{H}(G,\varphi)$ similarly for the blue
components. Paths will play a significant role in our argument, and we write
$P_{t}$ for the path of length $t-1$ on $t$ vertices. Given a colouring of a
graph, we call the colouring with colours reversed the _opposite_ colouring.
We will also often explore the neighbourhood of a vertex or a subset in a
graph, and write $B_{d}(v)$ for the radius-$d$ ball around a vertex $v$ and
write $B_{d}(X)$ for the set of all vertices of $G$ within distance at most
$d$ from a subset $X$. We use $N^{d}(X)$ for the set of vertices at distance
exactly $d$ from $X$, and abbreviate $N^{1}(X)$ as $N(X)$ (so $N(X)$ is the
set of external neighbours of $X$ in $G$). Finally, all logarithms are to the
base $e$.

##  2 Proving the theorem

Given a large connected cubic graph, our goal is to colour the vertices such
that the colour classes induce isomorphic subgraphs, and we shall find this
colouring in two stages. In the first, we take a semi-random vertex colouring,
and show that this is very close to having the desired properties. Then, in
the second stage, we make some deterministic local recolourings to balance the
two subgraphs and ensure they are truly isomorphic.

###  2.1 A random colouring

We begin our search for the isomorphic bisection by showing that one may
leverage Thomassen’s result to define a random colouring that will produce
monochromatic subgraphs that are nearly isomorphic. The following proposition
collects the properties of this initial colouring.

######  Proposition 2.1.

For any $d\in\mathbb{N}$ and any sufficiently large cubic graph $G$, there is
a red-/blue-colouring $\varphi$ of the vertices for which the following hold.

  * (a)

Each monochromatic component is a path of length at most $5$.

  * (b)

For each $2\leq t\leq 6$,
$\left|r_{P_{t}}(G,\varphi)-b_{P_{t}}(G,\varphi)\right|\leq 3\sqrt{n\log n}$.

  * (c)

There are sequences of vertices $(u_{i})_{i\in[s]}$ and $(w_{i})_{i\in[s]}$,
for some $s\geq 2^{-2d-5}n$, such that all the balls $B_{d}(u_{i})$ and
$B_{d}(w_{i})$ are pairwise disjoint, and for each $i\in[s]$, $B_{d}(u_{i})$
and $B_{d}(w_{i})$ induce isomorphic subgraphs with opposite colourings.

  * (d)

The colouring $\varphi$ is a bisection; that is, there are an equal number of
red and blue vertices.

In our proof, we will need to show that several random variables, each a
function of the random colouring, lie close to their expected values. For this
we employ McDiarmid’s Inequality [14], which bounds large deviations in random
variables defined on product probability spaces, provided they do not vary too
much in response to changes in individual coordinates.

######  Theorem 2.2 (McDiarmid’s Inequality, 1989).

Let $X=(X_{1},X_{2},\ldots,X_{n})$ be a family of independent random
variables, with $X_{k}$ taking values in a set $A_{k}$ for each $k\in[n]$.
Suppose further that there is some real-valued function $f$ defined on
$\prod_{k\in[n]}A_{k}$ and some $c>0$ such that
$\left|f(x)-f(x^{\prime})\right|\leq c$ whenever $x$ and $x^{\prime}$ differ
only in a single coordinate. Then, for any $m\geq 0$,

$\mathbb{P}\left(\left|f(X)-\mathbb{E}[f(X)]\right|\geq m\right)\leq
2\exp\left(\frac{-2m^{2}}{c^{2}n}\right).$

Armed with this tool, we can now proceed with our proof.

###### Proof of Proposition 2.1.

To prove the proposition, we shall first define a random colouring
$\varphi^{\prime}$ that satisfies properties (a), (b) and (c) while being very
close to a bisection. We shall then make a few small changes to obtain a bona
fide bisection $\varphi$, maintaining the other properties in the process.

To define $\varphi^{\prime}$, we first apply Theorem 1.1 to our cubic graph
$G$. This results in a partition of the edges of $G$ into two spanning linear
forests, $F_{1}$ and $F_{2}$, neither of which contains a path of length $6$
or more. We then take $\varphi^{\prime}$ to be a uniformly random proper
colouring of $F_{1}$. Observe that this is equivalent to selecting,
independently for each path component of $F_{1}$, one of its two proper
colourings uniformly. Thus, our probability space is a product space, with
each coordinate corresponding to a colouring of a path component of $F_{1}$,
of which there are at most $n$.

We now verify in turn that the first three properties hold. For (a), observe
that since $\varphi^{\prime}$ is a proper colouring of $F_{1}$, the only
monochromatic components are subgraphs of $F_{2}$. It thus follows immediately
that each such component is a path of length at most $5$.

To establish (b), we seek to apply Theorem 2.2 to the random variable
$r_{P_{t}}(G,\varphi^{\prime})$. To do so, we must understand how changing the
colouring of an individual path component of $F_{1}$ can affect
$r_{P_{t}}(G,\varphi^{\prime})$. Since the component in $F_{2}$ of each vertex
is simply a path, changing the colouring of an individual vertex can affect at
most two monochromatic copies of $P_{t}$. As each path component in $F_{1}$ is
of length at most $5$, the colouring of each such path therefore affects at
most $12$ copies of $P_{t}$. Hence, we can take $c=12$ in Theorem 2.2. It then
follows that, for each $m>0$,
$\mathbb{P}\left(\left|r_{P_{t}}(G,\varphi^{\prime})-\mathbb{E}[r_{P_{t}}(G,\varphi^{\prime})]\right|\geq
m\right)\leq 2\exp\left(-m^{2}/(72n)\right)$. In particular, the probability
that $r_{P_{t}}(G,\varphi^{\prime})$ deviates from its expectation by more
than $\sqrt{n\log n}$ is at most $2n^{-1/72}=o(1)$.

The same argument holds for $b_{P_{t}}(G,\varphi^{\prime})$, and, by symmetry,
we have
$\mathbb{E}[r_{P_{t}}(G,\varphi^{\prime})]=\mathbb{E}[b_{P_{t}}(G,\varphi^{\prime})]$.
Hence, the probability that
$\left|r_{P_{t}}(G,\varphi^{\prime})-b_{P_{t}}(G,\varphi^{\prime})\right|\geq
2\sqrt{n\log n}$ is $o(1)$. Taking a union bound over all choices of $2\leq
t\leq 6$, we find that with high probability we have
$\left|r_{P_{t}}(G,\varphi^{\prime})-b_{P_{t}}(G,\varphi^{\prime})\right|\leq
2\sqrt{n\log n}$ for all $2\leq t\leq 6$.

We next turn our attention to (c). To start, we wish to select a sequence of
vertices whose pairwise distances are all at least $2d+1$. Observe that, since
$G$ is cubic, for each vertex $v$ we have $\left|B_{2d}(v)\right|\leq
1+\sum_{i=1}^{2d}3\cdot 2^{i}<3\cdot 2^{2d+1}$. We can then greedily select
our desired vertices. Indeed, after we add a vertex $v_{i}$ to our sequence,
we eliminate the vertices in $B_{2d}(v_{i})$ from our consideration. This
guarantees that we are now free to select any of the remaining vertices. This
results in a sequence of vertices $v_{1},v_{2},\ldots,v_{s^{\prime}}$ for some
$s^{\prime}\geq\tfrac{1}{3}2^{-2d-1}n$, with each pair at distance $2d+1$ or
more. In particular, the balls $B_{d}(v_{i})$ are pairwise disjoint.

Now consider the subgraphs induced by each ball $B_{d}(v_{i})$. These are
subcubic graphs on at most $3\cdot 2^{d+1}$ vertices, and hence there are a
finite number of possible isomorphism types. Furthermore, the subgraphs
inherit a vertex-colouring from $\varphi^{\prime}$. Since the number of
vertices in the ball is bounded, there can be at most $2^{3\cdot 2^{d+1}}$
different colourings. Therefore, considering the isomorphism type and
colouring of each ball, there is some finite number $\kappa=\kappa(d)$ of
different classes the balls can fall into.

For each $j\in[\kappa]$, we denote by $Y_{j}$ the random variable counting the
number of balls $B_{d}(v_{i})$, $i\in[s^{\prime}]$, that belong to the $j$th
class. Note that for each $i$, the distribution of the colouring of
$B_{d}(v_{i})$ depends on how the paths of $F_{1}$ appear in the ball.
However, by symmetry, opposite colourings of $B_{d}(v_{i})$ appear with equal
probabilities. It follows that if $j$ and $\bar{j}$ represent opposite
colourings of isomorphic balls, then
$\mathbb{E}[Y_{j}]=\mathbb{E}[Y_{\bar{j}}]$.

Since the balls are pairwise disjoint, changing the colour of a single vertex
can affect at most $1$ ball $B_{d}(v_{i})$. Hence, changing the colouring of a
path component of $F_{1}$ can affect at most $6$ balls. Applying Theorem 2.2
to the random variables $Y_{j}$, we can therefore take $c=6$. Setting
$m=\sqrt{n\log n}$, we find that with probability $1-o(1)$ we have
$\left|Y_{j}-\mathbb{E}[Y_{j}]\right|\leq\sqrt{n\log n}$ for each
$j\in[\kappa]$. It then follows that for opposite colourings $j$ and $\bar{j}$
we have $\left|Y_{j}-Y_{\bar{j}}\right|\leq 2\sqrt{n\log n}$. We can therefore
match the balls $B_{d}(v_{i})$ into isomorphic pairs with opposite colourings,
with at most $2\sqrt{n\log n}$ unmatched balls for each of the $\kappa$
isomorphism types. Provided $n$ is suitably large, this is a total of at most
$\tfrac{1}{2}s^{\prime}$ unmatched balls, leaving us with at least
$\tfrac{1}{4}s^{\prime}$ matched pairs of balls.

This shows that the random colouring $\varphi^{\prime}$ is very likely to
satisfy (a), (b) and (c). To finish the proof, we shall show that it is
typically also close to being a bisection, and we can make it one without
destroying the other properties.

Consider the random variable that is the difference between the numbers of red
and blue vertices. Since every path component in $F_{1}$ of odd length
contributes an equal number of red and blue vertices to the colouring, any
discrepancy in the colour class sizes must come from the paths of even length.
Furthermore, each such path contributes a difference in the colour class sizes
of exactly $1$, with equal probability in either direction. Thus, the expected
difference is $0$, and recolouring a path component can affect the difference
by at most $2$. We thus make a final appeal to Theorem 2.2, finding that with
probability $1-o(1)$, the difference in the two colour classes is of size at
most $\tfrac{1}{10}\sqrt{n\log n}$.

In summary, with positive probability it holds that the colouring
$\varphi^{\prime}$ satisfies properties (a), (b) and (c), and that the
difference $\Delta$ between the number of red and blue vertices is at most
$\tfrac{1}{10}\sqrt{n\log n}$. We can therefore obtain a bisection $\varphi$
by taking $\varphi^{\prime}$ and replacing the colouring of $\Delta$ even
paths in $F_{1}$ with their opposite colourings, thereby satisfying (d).

Note that $\varphi$ remains a proper colouring of $F_{1}$, and therefore
property (a) is preserved. Moreover, we are changing the colours of at most
$5\Delta$ vertices. As previously discussed, changing the colour of a vertex
can affect at most two monochromatic copies of $P_{t}$, and hence, for each
$2\leq t\leq 6$, the difference
$\left|r_{P_{t}}(G,\varphi)-b_{P_{t}}(G,\varphi)\right|$ deviates from
$\left|r_{P_{t}}(G,\varphi^{\prime})-b_{P_{t}}(G,\varphi^{\prime})\right|$ by
at most $\sqrt{n\log n}$. In particular, we have
$\left|r_{P_{t}}(G,\varphi)-b_{P_{t}}(G,\varphi)\right|\leq 3\sqrt{n\log n}$
for each $2\leq t\leq 6$, establishing (b).

Similarly, under $\varphi^{\prime}$ we had at least
$\tfrac{1}{4}s^{\prime}\geq\tfrac{1}{3}2^{-2d-3}n$ pairs of isomorphic balls
with opposite colourings. Since these balls are pairwise disjoint, each
recoloured vertex can affect at most one such pair. Hence, under $\varphi$ we
still have at least $\tfrac{1}{4}s^{\prime}-5\Delta$ such pairs which, if $n$
is large enough, is at least $2^{-2d-5}n$ pairs. Thus, (c) holds for $\varphi$
as well, completing the proof. ∎

###  2.2 Correcting the bisection

The colouring $\varphi$ from Proposition 2.1 is close to being the bisection
we need, but the number of short paths in the red and blue subgraphs can be a
little off. In the second stage of our argument, we will make local changes to
the colouring to correct these discrepancies. We do this via gadgets we call
_$P_{t}$ -reducers_. These are flexible subgraphs, in the sense that they
admit two different colourings which have the same monochromatic subgraph
counts, except for short paths. By choosing an appropriate colouring, then, we
can adjust the values of $r_{P_{t}}(G,\varphi)$ and $b_{P_{t}}(G,\varphi)$,
making them equal.

When doing so, though, we do need to take care that our changes do not leak
out and affect subgraph counts elsewhere. We thus insulate the $P_{t}$-reducer
by colouring its boundary with alternating colours, thus preventing any
monochromatic components from extending outwards.

######  Definition 2.3 ($P_{t}$-reducer).

Given some $t\geq 3$, an induced subgraph $R\subseteq G$ is a _$P_{t}$
-reducer_ if there are two vertex colourings $\psi_{1},\psi_{2}$ of
$B_{2}(R)=R\cup N(R)\cup N^{2}(R)$ such that:

  * (i)

the two colourings have the same number of red (and therefore also blue)
vertices,

  * (ii)

in both $\psi_{1}$ and $\psi_{2}$, all vertices of $N(R)$ are blue and all
vertices of $N^{2}(R)$ are red,

  * (iii)

$r_{H}(B_{2}(R),\psi_{1})=r_{H}(B_{2}(R),\psi_{2})$ and
$b_{H}(B_{2}(R),\psi_{1})=b_{H}(B_{2}(R),\psi_{2})$, unless $H=P_{\ell}$ for
some $2\leq\ell\leq t$, and

  * (iv)

$r_{P_{t}}(B_{2}(R),\psi_{2})=r_{P_{t}}(B_{2}(R),\psi_{1})-1$ and
$b_{P_{t}}(B_{2}(R),\psi_{1})=b_{P_{t}}(B_{2}(R),\psi_{2})$.

Of course, this definition is only useful if we can actually find
$P_{t}$-reducers in our graph. Fortunately, they happen to be ubiquitous in
cubic graphs.

######  Proposition 2.4.

Let $G$ be a connected cubic graph on more than $3\cdot 2^{50}$ vertices, and
let $v\in V(G)$ be arbitrary. Then, for every $3\leq t\leq 6$, there is a
$P_{t}$-reducer in $B_{50}(v)$.

We shall prove Proposition 2.4 in Section 3, but first we show how one can use
$P_{t}$-reducers to obtain the desired isomorphic bisection.

###### Proof of Theorem 1.3.

Given a sufficiently large connected cubic graph $G$, set $d=57$ and let
$\varphi_{0}$ be the bisection given by Proposition 2.1 with this $d$. We then
have $r_{H}(G,\varphi_{0})=b_{H}(G,\varphi_{0})$ for all $H$ except $H=P_{t}$,
$2\leq t\leq 6$. For these paths, we have
$\left|r_{P_{t}}(G,\varphi_{0})-b_{P_{t}}(G,\varphi_{0})\right|\leq
3\sqrt{n\log n}$, and we shall correct these imbalances one at a time, in
decreasing order of path length.

We start with $t=6$. Suppose, without loss of generality, that we have
$r_{P_{6}}(G,\varphi_{0})>b_{P_{6}}(G,\varphi_{0})$. Take the first pair of
isomorphic and oppositely-coloured balls, $B_{57}(u_{1})$ and $B_{57}(w_{1})$.
By Proposition 2.4, we can find some $P_{6}$-reducer $R\subseteq
G[B_{50}(u_{1})]$, and therefore we find a corresponding oppositely-coloured
copy $\bar{R}\subseteq G[B_{50}(w_{1})]$ as well. We then recolour $B_{2}(R)$
with $\psi_{2}$, and colour $B_{2}(\bar{R})$ with $\bar{\psi}_{1}$, the
opposite colouring of $\psi_{1}$.

Let $\varphi_{1}$ be the resulting colouring. Note that this is still a
bisection, since $\psi_{1}$ and $\psi_{2}$ have the same number of red
vertices, and we have made symmetric changes in $B_{2}(R)$ and
$B_{2}(\bar{R})$. We next claim that
$r_{H}(G,\varphi_{1})=b_{H}(G,\varphi_{1})$ for all graphs except $P_{t}$,
$2\leq t\leq 6$, and that
$r_{P_{6}}(G,\varphi_{1})-b_{P_{6}}(G,\varphi_{1})=r_{P_{6}}(G,\varphi_{0})-b_{P_{6}}(G,\varphi_{0})-1$;
that is, the difference in monochromatic copies of $P_{6}$ is reduced by $1$.

Observe that we only need to concern ourselves with monochromatic components
contained within $B_{57}(u_{1})$ and $B_{57}(w_{1})$. Indeed, in
$\varphi_{0}$, all monochromatic components were paths of length at most $5$.
As we only recoloured vertices in $B_{2}(R)$ and $B_{2}(\bar{R})$, which are
contained in $B_{50}(u_{1})$ and $B_{50}(w_{1})$ respectively, any affected
components do not reach outside the original balls $B_{57}(u_{1})$ and
$B_{57}(w_{1})$. Also note that, since these balls had the opposite colorings,
before the recoloring there was one to one correspondence between red
components in the first ball and blue components in the second ball and vice
versa.

First we consider components not fully contained within $B_{2}(R)$ or
$B_{2}(\bar{R})$. Recall that in $\psi_{2}$, the vertices in $N(R)$ and
$N^{2}(R)$ receive opposite colours, with the same being true of the colouring
$\bar{\psi}_{1}$ of $B_{2}(\bar{R})$. Thus, any such component in
$B_{57}(u_{1})$ can only contain (red) vertices from $N^{2}(R)$, together with
some vertices in $B_{57}(u_{1})\setminus B_{2}(R)$. However, since
$B_{57}(u_{1})$ and $B_{57}(w_{1})$ are isomorphic and oppositely-coloured,
these components are in bijection with isomorphic blue components in
$B_{57}(w_{1})$, and hence no additional discrepancy is introduced through
these components.

This leaves us with components fully within $B_{2}(R)$ and $B_{2}(\bar{R})$,
where the properties of the $P_{6}$-reducer come into play. For any component
$H$ that is not a path of length at most $6$, we have
$r_{H}(B_{2}(R),\psi_{2})=r_{H}(B_{2}(R),\psi_{1})=b_{H}(B_{2}(\bar{R}),\bar{\psi}_{1})$,
and similarly $b_{H}(B_{2}(R),\psi_{2})=r_{H}(B_{2}(\bar{R}),\bar{\psi}_{1})$.
Thus the monochromatic copies of these components remain balanced. As for
paths of length $6$, we have

$r_{P_{6}}(B_{2}(R),\psi_{2})=r_{P_{6}}(B_{2}(R),\psi_{1})-1=b_{P_{6}}(B_{2}(\bar{R}),\bar{\psi}_{1})-1,$

while $b_{P_{6}}(B_{2}(R),\psi_{2})=r_{P_{6}}(B_{2}(\bar{R}),\bar{\psi}_{1})$,
and so the difference between red and blue copies of $P_{6}$ is indeed reduced
by $1$ in $\varphi_{1}$.

Although this recolouring could create monochromatic components that are not
paths of length at most $6$, these must be fully contained within the balls
$B_{57}(u_{1})$ and $B_{57}(w_{1})$, which are disjoint from all the other
balls. We can thus repeat this process a further
$r_{P_{6}}(G,\varphi_{1})-b_{P_{6}}(G,\varphi_{1})$ times, using the next
pairs of balls $B_{57}(u_{i})$ and $B_{57}(w_{i})$ in the sequence. This gives
us a sequence of colourings, $\varphi_{1},\varphi_{2},\ldots,\varphi_{k}$, the
last of which will satisfy
$r_{P_{6}}(G,\varphi_{k})=b_{P_{6}}(G,\varphi_{k})$.

Furthermore, since each $P_{6}$-reducer is of constant size, every step of the
process can only have created a constant number of monochromatic
$P_{5}$-components. Thus, we still have
$\left|r_{P_{5}}(G,\varphi_{k})-r_{P_{5}}(G,\varphi_{k})\right|=O\left(\sqrt{n\log
n}\right)$. We can therefore use Proposition 2.4 to find $P_{5}$-reducers in
the next $O\left(\sqrt{n\log n}\right)$ pairs of balls and balance the
monochromatic $P_{5}$ counts. Once those are handled, we proceed to fixing the
$P_{4}$ counts, and then finally the $P_{3}$ counts. Observe that we require a
total of $O\left(\sqrt{n\log n}\right)$ steps, and since Proposition 2.1
guarantees us $\Omega(n)$ pairs of isomorphic balls, we can see this process
through to completion.

Let $\varphi$ be the final colouring obtained. Following our corrections with
the $P_{t}$-reducers, we know that for every $H\neq P_{2}$, we have
$r_{H}(G,\varphi)=b_{H}(G,\varphi)$. However, since $G$ is cubic and $\varphi$
is a bisection, double-counting the edges between the colour classes shows
that the total number of monochromatic red edges must equal the number of blue
edges. It therefore follows that $r_{P_{2}}(G,\varphi)=b_{P_{2}}(G,\varphi)$
as well, and hence the subgraphs induced by the red and the blue vertices are
isomorphic. ∎

##  3 Constructing $P_{t}$-reducers

To complete the proof of Theorem 1.3, we need to prove Proposition 2.4,
showing that we can find $P_{t}$-reducers in the local neighbourhoods of every
vertex. We will first show a very simple construction that works in graphs of
girth at least $7$, thereby providing a short proof of Conjecture 1.2 for
large cubic graphs without short cycles. The proof in the general case is a
little more involved, requiring analysis of a few different cases, and can be
found in Section 3.2.

###  3.1 Graphs of girth at least $7$

Our construction is based around geodesics — that is, shortest paths in the
graph between a pair of vertices. We start with a lemma about neighbourhoods
of geodesics.

######  Lemma 3.1.

Let $G$ be a cubic graph of girth at least $7$, and let $P$ be a geodesic in
$G$. Then $N(P)$, the set of external neighbours of vertices on $P$, is an
independent set.

###### Proof.

Let $u,w\in N(P)$ be arbitrary vertices in the neighbourhood of $P$, and
suppose for contradiction we have an edge $\\{u,w\\}$. Let
$u^{\prime},w^{\prime}\in P$ be neighbours of $u$ and $w$ respectively. If
$u^{\prime}$ and $w^{\prime}$ are at distance at most $3$ along the path $P$,
then, together with the edges $\\{u^{\prime},u\\},\\{u,w\\}$ and
$\\{w,w^{\prime}\\}$, we would obtain a cycle of length at most $6$,
contradicting our assumption on the girth of $G$.

On the other hand, if $u^{\prime}$ and $w^{\prime}$ are at distance at least
$4$ on the path $P$, then we could shorten the path by rerouting it between
$u^{\prime}$ and $w^{\prime}$ through $u$ and $w$ instead. This contradicts
$P$ being a geodesic.

Hence $u$ and $w$ cannot be adjacent, and thus it follows that $N(P)$ is an
independent set. ∎

This shows that the structure around a geodesic is particularly simple. As a
result, we can easily find $P_{t}$-reducers, as we now show.

###### Proof of Proposition 2.4 (girth $\geq 7$).

Since there are at most $3\cdot 2^{t+1}<3\cdot 2^{50}$ vertices at distance at
most $t$ from the vertex $v$, there must be a vertex $w$ at distance exactly
$t+1$ from $v$. Let $P$ be a geodesic from $v$ to $w$, with vertices
$v=v_{0},v_{1},v_{2},\ldots,v_{t},v_{t+1}=w$. We’ll show that $P$ is a
$P_{t}$-reducer.

We now define the colourings $\psi_{1}$ and $\psi_{2}$ of $B_{2}(P)=P\cup
N(P)\cup N^{2}(P)$. In both colourings, we colour all vertices in $N^{2}(P)$
red and all vertices in $N(P)$ blue. When colouring the path $P$, we make all
vertices red, except in $\psi_{1}$ the vertex $v_{t}$ is coloured blue, while
in $\psi_{2}$ the vertex $v_{t-1}$ is coloured blue instead.

Clearly both $\psi_{1}$ and $\psi_{2}$ have the same number of red vertices,
and thus property (i) is satisfied. Property (ii) is satisfied by the
definition of the colouring on $N(P)$ and $N^{2}(P)$.

Finally, we inspect the monochromatic components of $B_{2}(P)$ under
$\psi_{1}$ and $\psi_{2}$ to verify properties (iii) and (iv). Let us start
with the blue components. In the two colourings, the blue vertices are those
in $N(P)$, together with one of $v_{t-1}$ or $v_{t}$. By Lemma 3.1, the
vertices in $N(P)$ form an independent set. As $v_{t-1}$ and $v_{t}$ are
internal vertices on the path $P$, they have exactly one neighbour in $N(P)$.
Thus in both $\psi_{1}$ and $\psi_{2}$, the blue vertices induce one isolated
edge and $\left|N(P)\right|-1$ isolated vertices, and thus
$b_{H}(B_{2}(P),\psi_{1})=b_{H}(B_{2}(P),\psi_{2})$ for every $H$.

Since $N(P)$ is entirely blue, the red components of $B_{2}(P)$ are either
wholly contained in $N^{2}(P)$ or in $P$. In the former case, since all
vertices in $N^{2}(P)$ are red, both colourings have the same components. In
the latter case, the path $P$ is broken into two red paths by the sole blue
vertex, which is $v_{t}$ in $\psi_{1}$ and $v_{t-1}$ in $\psi_{2}$. Thus
$\psi_{1}$ has a red $P_{t}$ and a red $P_{1}$, while $\psi_{2}$ has a red
$P_{t-1}$ and a red $P_{2}$. This shows that (iii) and (iv) are indeed
satisfied, and so the colourings $\psi_{1}$ and $\psi_{2}$ bear witness to $P$
being a $P_{t}$-reducer. ∎

###  3.2 The general case

In general, we cannot expect such simple structure around geodesic paths.
However, induced paths will still play a key role in our construction of
$P_{t}$-reducers, as shown by the following lemma.

######  Lemma 3.2.

In a cubic graph $G$, let $Q$ be an induced path of length $t+1$ or $t+2$ with
vertices labelled as $Q=(u,x,z,q_{1},\dots,q_{t-1})$ or
$Q=(u,x,y,z,q_{1},\dots,q_{t-1})$ respectively. Let $v$ a vertex outside $Q$
with the edges $vx$ and $vz$ present. Then $B_{3}(Q)$ contains a
$P_{t}$-reducer.

###### Proof.

Depending on the length of $Q$, define $\psi_{1}$ and $\psi_{2}$ on
$R:=Q\cup\\{v\\}$ as follows:

Define both $\psi_{1}$ and $\psi_{2}$ to be blue on $N(R)$ and red on
$N^{2}(R)$. We claim that this makes $R$ a $P_{t}$-reducer. Properties (i) and
(ii) are immediate by construction. Notice that
$b_{H}(B_{2}(R),\psi_{1})=b_{H}(B_{2}(R),\psi_{2})$ for all $H$. Indeed the
only blue component that changes between the two colourings is the one that
contains $v$. However, since the graph is cubic, neither $x$ nor $z$ has any
neighbours in $N(R)$, and therefore it is easy to see that this component is
isomorphic between the two colourings. Finally notice that the only red
components that change between the two colourings are the two red subpaths of
$Q$. The colouring $\psi_{1}$ has a red $P_{t}$ and a red $P_{1}$, while
$\psi_{2}$ has a red $P_{t-1}$ and a red $P_{2}$. We also have
$r_{H}(B_{2}(R),\psi_{1})=r_{H}(B_{2}(R),\psi_{2})$ for all other $H$. This
completes the proof of (iii) and (iv) ∎

Recall that a geodesic path $Q$ is a shortest length path between its
endpoints, and note that a length $14$ geodesic path exists in $B_{14}(v)$ for
every vertex $v$ in a large connected cubic graph. An important consequence of
the above lemma is that it reduces us to the case when every vertex outside a
geodesic path $Q$ has at most one neighbour on $Q$. Using this we can prove
the following lemma.

######  Lemma 3.3.

Let $Q$ be a geodesic path of length $14$ in a cubic graph $G$. Then
$B_{3}(Q)$ either contains $P_{t}$-reducers for all $3\leq t\leq 6$ or it
contains, for each $3\leq t\leq 6$, an induced subgraph $R$ which has two
colourings $\psi_{1}$ and $\psi_{2}$ of $B_{2}(R)$ that satisfy (ii), (iii),
and (iv) of the definition of $P_{t}$-reducer and also:

  * (i’)

$\psi_{1}$ has one more red vertex than $\psi_{2}$.

###### Proof.

Let $Q=(q_{1},\dots,q_{15})$. For each $2\leq i\leq 14$, let $r_{i}$ be the
neighbour of $q_{i}$ outside $Q$. These are unique because the graph is cubic.
If $r_{i}=r_{j}$ for some $2\leq i<j\leq 14$, the fact that $Q$ is a geodesic
path forces $j=i+1$ or $j=i+2$. In either case, we find $P_{t}$-reducers for
all $3\leq t\leq 6$ using Lemma 3.2. Thus we can assume that
$r_{2},\dots,r_{14}$ are all distinct.

Next, suppose that $r_{i}r_{i+1}$ is an edge for all $3\leq i\leq 10$. Since
$G$ is cubic, this determines all the neighbours of $r_{i}$ for $4\leq i\leq
10$. It follows that for $t\in\\{3,4,5,6\\}$, the path
$Q^{\prime}=(q_{2},q_{3},q_{4},r_{4},r_{5},\dots,r_{t+4})$ is induced, has
length $t+3$, and the vertex $v:=r_{3}$ has neighbours $q_{3}$ and $r_{4}$.
Thus Lemma 3.2 applies to give us $P_{t}$-reducers for all $3\leq t\leq 6$.

Hence, we may assume that $r_{i}r_{i+1}$ is a non-edge for some $3\leq i\leq
10$. Fix $t\in\\{3,4,5,6\\}$. Define the subpath
$Q^{\prime}=(q_{i-1},\dots,q_{i+t-1})$ Define $\psi_{1}$ and $\psi_{2}$ on
$R:=Q^{\prime}\cup\\{r_{i},r_{i+1}\\}$ as follows:

Extend both $\psi_{1}$, and $\psi_{2}$ to be blue on $N(R)$ and red on
$N^{2}(R)$. We claim that then these colourings of $B_{2}(R)$ satisfy (i’),
(ii), (iii), and (iv). Properties (i’) and (ii) are immediate by construction.
For (iii) and (iv), notice that the only components that change between the
two colourings are the blue component containing $q_{i}$ (which, by virtue of
the fact that all neighbours of $q_{i}$ and $q_{i+1}$ lie within $R$, is a
$P_{1}$ in $\psi_{1}$ and a $P_{2}$ in $\psi_{2}$) and the red component
containing $q_{i+2}$ (which is a $P_{t}$ in $\psi_{1}$ and splits into a
$P_{1}$ and a $P_{t-2}$ in $\psi_{2}$). ∎

The above lemma implies Proposition 2.4 for $t\geq 4$.

###### Proof of Proposition 2.4 for $t\geq 4$.

Note that within $B_{45}(v)$, we can find two geodesic paths of length $14$,
which we call $Q$ and $R$, at distance $10$ from each other. Thus the balls
$B_{3}(Q)$ and $B_{3}(R)$ are disjoint. If either of these balls contains a
$P_{t}$-reducer, we are done. Otherwise, by Lemma 3.3, we can assume the
existence of some $S_{1}\subseteq B_{3}(Q)$ with colourings
$\psi_{1}^{S_{1},t}$ and $\psi_{2}^{S_{1},t}$ of $B_{2}(S_{1})$ satisfying
(ii), (iii), (iv) of the definition of a $P_{t}$-reducer and also (i’) from
Lemma 3.3. Similarly, we find $S_{2}\subseteq B_{3}(R)$ with colourings
$\psi_{1}^{S_{2},t-1},\psi_{2}^{S_{2},t-1}$ of $B_{2}(S_{2})$ satisfying (ii),
(iii), (iv) of the definition of a $P_{t-1}$-reducer and also (i’) above. We
now construct colourings $\psi_{1}$ and $\psi_{2}$ of $B_{50}(v)$ satisfying
the definition of a $P_{t}$-reducer.

  * •

On $B_{2}(S_{1})$, $\psi_{1}$ and $\psi_{2}$ agree with $\psi_{1}^{S_{1},t}$
and $\psi_{2}^{S_{1},t}$ respectively.

  * •

On $B_{2}(S_{2})$, $\psi_{1}$ and $\psi_{2}$ have the opposite colourings of
$\psi_{1}^{S_{2},t-1}$ and $\psi_{2}^{S_{2},t-1}$.

  * •

Outside $B_{2}(S_{1})$ and $B_{2}(S_{2})$, $\psi_{1}$ and $\psi_{2}$ are
entirely blue, except on $N^{50}(v)$, where they are red.

We check that these colourings do indeed result in a $P_{t}$-reducer
$B_{48}(v)$. Using property (i’) of the pairs
$\psi_{1}^{S_{1},t},\psi_{2}^{S_{1},t}$ and
$\psi_{1}^{S_{2},t-1},\psi_{2}^{S_{2},t-1}$, and the fact that we use the
opposite colourings on $S_{2}$, we see that $\psi_{1}$ and $\psi_{2}$ have an
equal number of red vertices in total, satisfying property (i) of a
$P_{t}$-reducer. Property (ii) holds by the third bullet point of the
construction. Property (iii) is immediate from it holding for the colourings
$\psi_{1}^{S_{1},t}$, $\psi_{2}^{S_{1},t}$, $\psi_{1}^{S_{2},t-1}$ and
$\psi_{2}^{S_{2},t-1}$, since the property (ii) for these colourings ensures
that the monochromatic components involving vertices whose colours change are
fully contained within $B_{2}(S_{1})$ and $B_{2}(S_{2})$ respectively. For
property (iv), note we lose exactly one red copy of $P_{t}$ when going from
$\psi_{1}^{S_{1},t}$ to $\psi_{2}^{S_{1},t}$ on $B_{2}(S_{1})$, while the
number of blue copies of $P_{t}$ stays the same. On the other hand, going from
$\psi_{1}^{S_{2},t-1}$ to $\psi_{2}^{S_{2},t-1}$ on $B_{2}(S_{2})$ does not
affect the number of the monochromatic copies of $P_{t}$ (by property (iii)).
Thus in total exactly one red $P_{t}$ is lost, as required. ∎

The above proof doesn’t work for $t=3$ because our proof of Lemma 3.3 doesn’t
work for $t=2$. Thus for $t=3$, we need a different proof of the proposition.

###### Proof of Proposition 2.4 for $t=3$.

Let $Q=(q_{0},\dots,q_{20})$ be a length $20$ geodesic within distance $20$ of
$v$. For each $1\leq i\leq 19$, let $r_{i}$ be the (unique) neighbor of
$q_{i}$. As in the proof of Lemma 3.3, if $r_{i}=r_{j}$ for some $1\leq
i<j\leq 19$, we must have $j=i+1$ or $j=i+2$, and then we find a
$P_{3}$-reducer using Lemma 3.2. Thus we may assume that $r_{1},\dots,r_{19}$
are all distinct.

######  Claim 3.4.

We have at least one of the following:

  1. (a)

For some $3\leq i\leq 9$, none of the edges $r_{i}r_{i+1},r_{i}r_{i+2}$ or
$r_{i+1}r_{i+2}$ are present.

  2. (b)

For some $3\leq i\leq 10$, the edge $r_{i}r_{i+1}$ is present and either

     * •

the edges $r_{i}r_{i+2}$ and $r_{i}r_{i+3}$ are absent, or

     * •

the edges $r_{i-1}r_{i+1}$ and $r_{i-2}r_{i+1}$ are absent.

  3. (c)

For some $3\leq i\leq 8$, the edge $r_{i}r_{i+1}$ is present, the edges
$r_{i+1}r_{i+2},r_{i+1}r_{i+3},r_{i-1}r_{i}$ and $r_{i-2}r_{i}$ are absent,
and either $r_{i}r_{i+3}$ or $r_{i-2}r_{i+1}$ is present.

###### Proof.

First observe that the three edges $r_{3}r_{5},r_{5}r_{7}$ and $r_{7}r_{9}$
cannot all be present, as that would contradict $Q$ being a geodesic. Hence,
if (a) does not hold, we must have the edge $r_{i}r_{i+1}$ for some $3\leq
i\leq 8$.

Next, suppose that $r_{i+1}r_{i+2}$ is also present. In this case,
$N(r_{i+1})=\\{q_{i+1},r_{i},r_{i+2}\\}$, which implies that $r_{i-1}r_{i+1}$
and $r_{i-2}r_{i+1}$ are both absent (since $r_{i-1},r_{i-2}$ are distinct
from $q_{i+1},r_{i},r_{i+1}$). This leaves us in case (b). The same argument
shows that we are in case (b) if any of the edges
$r_{i+1}r_{i+3},r_{i-1}r_{i}$ or $r_{i-2}r_{i}$ were present. Thus we can
assume that $r_{i+1}r_{i+2},r_{i+1}r_{i+3},r_{i-1}r_{i}$ and $r_{i-2}r_{i}$
are absent.

If (c) doesn’t hold, then both $r_{i}r_{i+3}$ and $r_{i-2}r_{i+1}$ must be
absent. Then, to avoid case (b), both $r_{i}r_{i+2}$ and $r_{i-1}r_{i+1}$ must
be present. Hence $N(r_{i})=\\{q_{i},r_{i+1},r_{i+2}\\}$ and
$N(r_{i+1})=\\{q_{i+1},r_{i-1},r_{i}\\}$. Recalling that $r_{i+1}r_{i+2}$ and
$r_{i+1}r_{i+3}$ are absent, note that $r_{i+2}r_{i+3}$ must be present, as
otherwise we would be in case (a) for $i^{\prime}=i+1$. However, as
$r_{i}r_{i+3}$ and $r_{i+1}r_{i+3}$ are both absent, we are then in case (b)
with $i^{\prime}=i+2$. ∎

We now find $P_{3}$-reducers in each of the above three cases.

  1. (a)

Set $R=\\{q_{i-1},q_{i},q_{i+1},q_{i+2},q_{i+3},r_{i},r_{i+1},r_{i+2}\\}$ and
define colourings $\psi_{1},\psi_{2}$ on $R$ as follows:

Define both $\psi_{1}$, and $\psi_{2}$ to be blue on $N(R)$ and red on
$N^{2}(R)$. It is immediate that this colouring satisfies the definition of
$P_{3}$-reducer.

  2. (b)

Without loss of generality, we may suppose that $r_{i}r_{i+1}$ is present and
the edges $r_{i}r_{i+2},r_{i}r_{i+3}$ are absent (the other case is symmetric
to this by reversing the order of the path $Q$). Let $u$ be the third
neighbour of $r_{i}$, i.e. $N(r_{i})=\\{q_{i},r_{i+1},u\\}.$ Consider the path
$Q^{\prime}=(u,r_{i},q_{i},q_{i+1},q_{i+2},q_{i+3})$. We claim that this is an
induced path. Indeed the edges $r_{i}q_{j}$ are all absent for $j\neq i$, so
the only way this could be non-induced is if $u=r_{i+1},r_{i+2}$ or $r_{i+3}$.
But $u$ was the third neighbour of $r_{i}$ so $u\neq r_{i+1}$ by definition,
and $r_{i+2},r_{i+3}\not\in N(r_{i})$ by the definition of case (b). Thus
$Q^{\prime}$ is indeed induced, and by Lemma 3.2 (applied with $v=r_{i+1}$)
there is a $P_{3}$-reducer in $B_{3}(Q^{\prime})$.

  3. (c)

Without loss of generality, we may suppose that $r_{i}r_{i+1}$ and
$r_{i}r_{i+3}$ are present and $r_{i+1}r_{i+2},$ $r_{i+1}r_{i+3},$
$r_{i-1}r_{i},$ $r_{i-2}r_{i}$ are absent (the other case is symmetric). Set
$R=\\{q_{i-1},q_{i},q_{i+1},q_{i+2},q_{i+3},r_{i},r_{i+1},r_{i+2},r_{i+3}\\}$
and define colourings $\psi_{1},\psi_{2}$ on $R$ as shown below. Extend both
$\psi_{1}$ and $\psi_{2}$ to be blue on $N(R)$ and red on $N^{2}(R)$. Since
$q_{i},r_{i},q_{i+1}$ have no neighbours in $N(R)$, it is easy to check that
this colouring satisfies the definition of $P_{3}$-reducer.

∎

##  4 Concluding remarks

In this paper we have proven Ando’s conjecture for all large connected cubic
graphs. While this only leaves a finite number of graphs to be checked, and
there is room to optimise the constants in our proof, there will still be too
many cases to be handled computationally. Hence, a complete resolution of
Conjecture 1.2 will likely require some additional ideas. In this section we
indicate some ways in which our proof could be modified, which might help make
progress towards the full conjecture, and close with some related open
problems.

#### A simpler starting block

While our proof is relatively short, one could argue that it is not fully
self-contained, as we use Thomassen’s theorem, which is already a very
significant result. However, it is not crucial in our proof that, in the
partition of the edges of $G$ into linear forests $F_{1}$ and $F_{2}$, the
paths have length at most five. We could therefore replace Theorem 1.1 with
one of its predecessors [5, 11], which have simpler proofs, but allow for
longer paths. Although this comes at the cost of requiring $P_{t}$-reducers
for larger values of $t$, our constructions readily generalise to longer
paths. This is especially easy when we assume $G$ has large girth, resulting
in a truly short proof of this special case.

#### Fewer reducers

Alternatively, one might seek to reduce the amount of work done in Section 3,
when constructing the $P_{t}$-reducers. A potential route to simplification
lies in the observation that, when using Theorem 1.1, it was not very
important that the paths in $F_{1}$ were so strongly bounded in length.
Indeed, we only used the lengths of the paths in $F_{1}$ to bound the
Lipschitz constant $c$ in our application of Theorem 2.2, and we can afford
for this to be as large as $n^{o(1)}$. On the other hand, if we can limit the
lengths of the paths in $F_{2}$ to some $\ell\leq 4$, then we would only need
to construct $P_{t}$-reducers for $2\leq t\leq\ell+1$.

######  Question 4.1.

What is the smallest $\ell$ for which the edges of any connected cubic graph
on $n$ vertices can be partitioned into two spanning linear forests $F_{1}$
and $F_{2}$, such that the paths in $F_{1}$ are of length $n^{o(1)}$, and the
paths in $F_{2}$ are of length at most $\ell$?

It is worth noting that, while the five in Theorem 1.1 is best possible, the
examples of tightness given in [15] are the two cubic graphs on six vertices.
It would be interesting to know if there are arbitrarily large tight
constructions, or if, when dealing with large connected graphs, one can
achieve $\ell=4$ even in the symmetric setting. Furthermore, we can weaken
Question 4.1, as in our application $F_{1}$ does not have to be a linear
forest, but rather a bipartite graph with bounded components.

#### Stronger conjectures

While Theorem 1.3 sheds light on the structure of large cubic graphs, showing
that they can be partitioned into isomorphic induced subgraphs, it does not
directly address the motivating question raised in Section 1, as there are no
guarantees that these subgraphs are simple. However, by analysing our proof,
one can obtain some further information about the subgraphs obtained. As
stated in Proposition 2.1, the only monochromatic components in the initial
random colouring are paths of length at most five. When we then use the
$P_{t}$-reducers to make the subgraphs isomorphic, we can introduce more
complicated monochromatic components. However, since the $P_{t}$-reducers are
all isolated within balls of bounded radius, it follows that the components in
the isomorphic subgraphs are of bounded size.

In particular, if we assume that our connected graph has large girth,111By
carefully considering the $P_{t}$-reducers from Section 3.1, it suffices to
assume girth at least $15$. it follows that the isomorphic subgraphs are
forests. Moreover, we need never have vertices of degree three in the
isomorphic subgraphs, as these can be recoloured (in pairs) to become isolated
vertices of the opposite colour. Thus, we in fact partition large connected
cubic graphs of large girth into isomorphic linear forests. It was conjectured
in [2] that every cubic graph should admit such a partition; the challenge
lies in removing the girth condition.

Ban and Linial [7] went even further, conjecturing that much more should be
true when we restrict our attention to two-edge-connected cubic graphs.

######  Conjecture 4.2.

The vertices of every bridgeless cubic graph, with the exception of the
Petersen graph, can be two-coloured such that the two colour classes induce
isomorphic matchings.

The conjecture has been proven for three-edge-colourable graphs [7] and for
claw-free graphs [1], but is otherwise open. It would be very interesting to
see to what extent our methods can be applied to this conjecture, as well as
to Wormald’s conjecture on partitioning the edges of cubic graphs into
isomorphic linear forests.

## References

  * [1] M. Abreu, J. Goedgebeur, D. Labbate and G. Mazzuoccolo,  A note on $2$-bisections of claw-free cubic graphs,  Discrete Appl. Math. 244 (2018), 214–217.
  * [2] M. Abreu, J. Goedgebeur, D. Labbate and G. Mazzuoccolo,  Colourings of cubic graphs inducing isomorphic monochromatic subgraphs,  J. Graph Theory 92 (2019), 415–444.
  * [3] J. Akiyama and V. Chvátal,  A short proof of the linear arboricity for cubic graphs,  Bull. Liber. Arts Sci. NMS 2 (1981).
  * [4] J. Akiyama, G. Exoo and F. Harary,  Covering and packing in graphs. II. Cyclic and acyclic invariants,  Math. Slovaca 30 (1980), 405–417.
  * [5] R. E. L. Aldred and N. C. Wormald,  More on the linear $k$-arboricity of regular graphs,  Australas. J. Combin. 18 (1998), 97–104.
  * [6] N. Alon, G. Ding, B. Oporowski and D. Vertigan,  Partitioning into graphs with only small components,  J. Combin. Theory Ser. B 87 (2003), 231–243.
  * [7] A. Ban and N. Linial,  Internal partitions of regular graphs,  J. Graph Theory 83 (2016), 5–18.
  * [8] J. C. Bermond, J. L. Fouquet, M. Habib and B. Péroche,  On linear $k$-arboricity,  Discrete Math. 52 (1984), 123–132.
  * [9] J.L. Fouquet, H. Thuillier, J.M. Vanherpe, and A.P. Wojda,  On isomorphic linear partitions in cubic graphs,  Discrete Math. 309 (2009), 6425–6433.
  * [10] P. Haxell, T. Szabó and G. Tardos,  Bounded size components — partitions and transversals,  J. Combin. Theory Ser. B 88 (2003), 281–297.
  * [11] B. Jackson and N. C. Wormald,  On the linear $k$-arboricity of cubic graphs,  Discrete Math. 162 (1996), 293–297.
  * [12] N. Linial, J. Matoušek, O. Sheffet and G. Tardos,  Graph coloring with no large monochromatic components,  Comb. Probab. Comput. 17 (2008), 577–589.
  * [13] L. Lovász,  On decomposition of graphs,  Studia Sci. Math. Hungarica 1 (1966), 237–238.
  * [14] C. McDiarmid,  On the method of bounded differences,  Surveys in Combinatorics, ed. J. Siemons, London Mathematical Society Lecture Note Series 141 (1989), 148–188.
  * [15] C. Thomassen,  Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most $5$,  J. Comb. Theory Ser. B 75 (1999), 100–109.
  * [16] D. Wood,  Defective and clustered graph colouring,  Electron. J. Combin. (2018), #DS23.
  * [17] N. C. Wormald,  Problem 13,  Ars Combinatorica 23 (1987), 332–334.


$\displaystyle\beta_{1}(M,\mathcal{H}_{i},X)=\begin{cases}q(1-X)\left(2\beta_{0}(M,0,X)+\sum_{\alpha\in(\mathcal{O}_{F_{0}}/(\pi_{0}))^{\times}}\beta_{0}(M,\langle-2\alpha\rangle,X)\right)&\text{
if $i=0$}\\\ q(q+1)(1-X)\beta_{0}(M,0,X)&\text{ if $i\geq 1$}.\end{cases}$

Here $\alpha(M,0,X)=\alpha(M,\mathcal{O}_{F}{\bf x},X)$ with $q({\bf x})=0$
and ${\bf x}\neq 0$. Now the proposition for $L=\mathcal{H}_{i}$ follows from
Corollary A.12.

Recall

$\displaystyle I(M_{k},L,d)=\\{\phi\in$
$\displaystyle\mathrm{Hom}_{\mathcal{O}_{F}}(L/\pi_{0}^{d}L,M_{k}/\pi_{0}^{d}M_{k})\mid$
$\displaystyle(\phi(x),\phi(y))=(x,y)\in\pi_{0}^{d}\cdot\mathrm{Herm}_{n}(\mathcal{O}_{F_{0}})^{\vee},\
\forall x,y\in L\\}.$

Let

$\displaystyle J(M_{k},L,d)$ $\displaystyle\coloneqq\\{\phi\in
I(M_{k},L,d)\mid\mathrm{dim}_{\mathbb{F}_{q}}\overline{\mathrm{Pr}_{\mathcal{H}^{k}}(\phi(L))}=\mathrm{dim}_{\mathbb{F}_{q}}\overline{\mathrm{Pr}_{M}(\phi(L))}=1\\}.$

Then

$\displaystyle\beta_{1}(M,L,X)=\lim_{d\to\infty}q^{-(4(2k+m)-4)d}|J(M_{k},L,d)|.$

Let $\\{l_{1},l_{2}\\}$ be a basis of $L$ with Gram matrix $\mathcal{H}_{i}$.
For $\phi\in J(M_{k},L,d)$, it will be determined by $w_{i}=\phi(l_{i})$. Let
$w_{i,\mathcal{H}}=\mathrm{Pr}_{\mathcal{H}^{k}}(w_{i})$, and
$w_{i,M}=\mathrm{Pr}_{M}(w_{i})$. Since
$\mathrm{rank}_{\mathbb{F}_{q}}\overline{\mathrm{Pr}_{\mathcal{H}^{k}}(\phi(L))}=1$,
$\mathrm{rank}_{\mathbb{F}_{q}}\overline{\mathrm{Pr}_{\mathcal{H}^{k}}(w_{i})}=1$
for $i=1$ or $2$.

Now we define a partition of $J(M_{k},L,d)$. Assume
$\alpha\in\mathcal{O}_{F_{0}}$. Let

$\displaystyle J_{\alpha}(M_{k},L,d)$ $\displaystyle\coloneqq\\{\phi\in
I(M_{k},L,d)\mid\mathrm{rank}_{\mathbb{F}_{q}}\overline{w}_{1,\mathcal{H}}=1,\
\overline{w}_{2,\mathcal{H}}=\alpha\overline{w}_{1,\mathcal{H}}\\},\text{ and
}$ $\displaystyle J_{\infty}(M_{k},L,d)$ $\displaystyle\coloneqq\\{\phi\in
I(M_{k},L,d)\mid\mathrm{rank}_{\mathbb{F}_{q}}\overline{w}_{2,\mathcal{H}}=1,\
\overline{w}_{1,\mathcal{H}}=0\\}.$

Then it is easy to verify

$\displaystyle
J(M_{k},L,d)=\bigcup_{\alpha\in\mathcal{O}_{F_{0}}/(\pi_{0})}J_{\alpha}(M_{k},L,d)\cup
J_{\infty}(M_{k},L,d).$

Now we compute $|J_{\alpha}(M_{k},L,d)|$. To determine a $\phi\in
J_{\alpha}(M_{k},L,d)$, we choose $w_{1}=\phi(l_{1})$ first. By definition, we
have

(A.6) $\displaystyle\lim_{d\to\infty}q^{(2(2k+m)-1)d}\\#\\{w_{1}\in
M_{k}/\pi_{0}^{d}M_{k}|\text{$w_{1}$ is primitive, and }q(w_{1})=0\text{ mod
}\pi_{0}^{d}\\}$ $\displaystyle=\beta_{1}(S_{k},0)=1-X.$

Given such a $w_{1}$, now we find the number of $w_{2}=\phi(l_{2})$ such that
$\phi$ lies in $J_{\alpha}(M_{k},L,d)$. By Lemma A.2, we may assume
$w_{1,S}=0$. Let $w_{2}=w_{2,M}+\alpha w_{1}+\pi w_{\mathcal{H}}$, where
$w_{\mathcal{H}}\in\mathcal{H}^{k}$. Then the corresponding $\phi$ lies in
$J_{\alpha}(M_{k},L,d)$ if and only if

$\displaystyle(w_{1},w_{2})=(w_{1},\pi
w_{\mathcal{H}})=\pi^{i}\mod\pi_{0}^{d}$

and

$\displaystyle 0=q(w_{2})$ $\displaystyle=\mathrm{tr}((\alpha w_{1},\pi
w_{\mathcal{H}}))-\pi_{0}q(w_{\mathcal{H}})+q(w_{2,M})$
$\displaystyle=\alpha\mathrm{tr}(\pi^{i})-\pi_{0}q(w_{\mathcal{H}})+q(w_{2,M})\mod\pi_{0}^{d}.$

First,

(A.7) $\displaystyle\lim_{d\to\infty}q^{-2d(2k-1)}\\#\\{\pi
w_{\mathcal{H}}\in\mathcal{H}^{k}/\pi_{0}^{d}\mathcal{H}^{k}|(w_{1},\pi
w_{\mathcal{H}})=\pi^{i}\mod\pi^{2d-1}\\}=q^{1-2k}.$

Second, for each fixed $\pi w_{\mathcal{H}}$ we have

(A.8) $\displaystyle\lim_{d\to\infty}q^{(-2m+1)d}\\#\\{w_{2,M}\in
M/\pi_{0}^{d}M\mid w_{2,M}\text{ primitive,
}q(w_{2,M})=-\alpha\mathrm{tr}(\pi^{i})+\pi_{0}q(w_{\mathcal{H}})\mod\pi_{0}^{d}\\}$
$\displaystyle=\beta(M,\langle-\alpha\mathrm{tr}(\pi^{i})+\pi_{0}q(w_{\mathcal{H}})\rangle),$
$\displaystyle=\begin{cases}\beta(M,\langle-2\alpha\rangle)&\hbox{if }i=0,\\\
\beta(M,0)&\hbox{if }i>0.\end{cases}$

By symmetry, $|J_{\infty}(M_{k},L,d)|=|J_{0}(M_{k},L,d)|$. Now a combination
of (A.6), (A.7) and (A.8) implies that

$\displaystyle\beta_{1}(M,\mathcal{H}_{i},X)$
$\displaystyle=\lim_{d\to\infty}q^{(-4(2k+m)+4)d}\left(\sum_{\alpha\in\mathcal{O}_{F_{0}}/(\pi_{0})}|J_{\alpha}(M_{k},L,d)|+|J_{\infty}(M_{k},L,d)|\right)$
$\displaystyle=\begin{cases}q(1-X)\left(2\beta_{0}(M,0,X)+\sum_{\alpha\in\mathcal{O}_{F_{0}}^{\times}/(\pi_{0})}\beta_{0}(M,-2\alpha,X)\right)&\text{
if $i=0$},\\\ q(q+1)(1-X)\beta_{0}(M,0,X)&\text{ if $i\geq 1$},\end{cases}$

as claimed.

Next, we assume $L$ has a basis $\\{l_{1},l_{2}\\}$ whose Gram matrix is
$\mathrm{Diag}(u_{1}(-\pi_{0})^{a},u_{2}(-\pi_{0})^{b})$ with $0\leq a\leq b$.
Let $w_{i}=\phi(l_{i})$ as before. Then the number of possible choices for
$w_{1}$ is given by

$q^{(2(2k+m)-1)d}\beta_{1}(M,\langle u_{1}(-\pi_{0})^{a}\rangle,X)$

for sufficiently large $d$. We may assume $w_{1}=w_{1,\mathcal{H}}$ without
loss of generality. Let $w_{2}=w_{2,M}+\alpha w_{1}+\pi w_{\mathcal{H}}$ as
before. Then $\phi$ lies in $J_{\alpha}(M_{k},L,d)$ if and only if

$\displaystyle(w_{1},w_{2})=(w_{1},\alpha w_{1})+(w_{1},\pi
w_{\mathcal{H}})=0\mod\pi_{0}^{d}$

and

$\displaystyle u_{2}(-\pi_{0})^{b}$ $\displaystyle=q(w_{2})=(w_{2,M}+\alpha
w_{1}+\pi w_{\mathcal{H}},w_{2})$
$\displaystyle=q(w_{2,M})+\alpha^{2}q(w_{1})-\pi_{0}q(w_{\mathcal{H}})\mod\pi_{0}^{d}.$

Now

$\lim_{d\to\infty}q^{(-4k+2)d}\\#\\{\pi
w_{\mathcal{H}}\in\mathcal{H}^{k}/\pi_{0}^{d}\mathcal{H}^{k}|(w_{1},\pi
w_{\mathcal{H}})=0\mod\pi^{2d-1}\\}=q^{1-2k},$

and for a fixed $\pi w_{\mathcal{H}}$ we have

$\displaystyle\lim_{d\to\infty}q^{(-2m+1)d}\\#\\{w_{2,M}\in
L_{S}/\pi_{0}^{d}L_{S}|w_{2,M}\text{ primitive, }$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad
q(w_{2,M})=u_{2}(-\pi_{0})^{b}-\alpha^{2}q(w_{1})+\pi_{0}q(w_{\mathcal{H}})\mod\pi_{0}^{d}\\}$
$\displaystyle=\beta(M,\langle
u_{2}(-\pi_{0})^{b}-\alpha^{2}q(w_{1})+\pi_{0}q(w_{\mathcal{H}})\rangle).$

Now this proposition follows from a similar argument as before, and we leave
the details to the reader. ∎

Finally, we record a lemma that we use frequently.

######  Lemma A.15.

[Kat99, Proposition 2.5 (1)] Suppose $M^{\prime}$ is a Hermtitian lattice
represented by $S^{\prime}$. Let $i(T)$ be the least integer $\ell$ such that
$\pi^{\ell}T^{-1}$ is integral. Assume that $\mathrm{v}(S^{\prime})>i(T)$.
Then we have

$\alpha(M\obot M^{\prime},L)=\alpha(M,L).$

###### Proof.

This follows from a similar argument as in the proof of Lemma A.8 and a
Hermitian analogue of [Kit99, Corollary 5.4.4]. We leave the details to the
reader. ∎

### References

  * [Bro89] Kenneth S Brown.  Buildings.  Springer, 1989.
  * [BY20] Jan Bruinier and Tonghai Yang.  Arithmetic degrees of special cycles and derivatives of siegel eisenstein series.  Journal of European Math. Soc, page pp60, 2020.
  * [Cho20] Sungyoon Cho.  Special cycles on unitary Shimura varieties with minuscule parahoric level structure.  arXiv preprint arXiv:2002.00172, 2020.
  * [CY20] Sungmun Cho and Takuya Yamauchi.  A reformulation of the siegel series and intersection numbers.  Mathematische Annalen, 377(3):1757–1826, 2020.
  * [Gil09] Henri Gillet.  Arithmetic intersection theory on deligne-mumford stacks.  arXiv preprint arXiv:0904.1424, 2009.
  * [Gro86] Benedict Gross.  On canonical and quasi-canonical liftings.  Inventiones mathematicae, 84(2):321–326, 1986.
  * [GS19] Luis E. Garcia and Siddarth Sankaran.  Green forms and the arithmetic Siegel-Weil formula.  Invent. Math., 215(3):863–975, 2019.
  * [GY00] Wee Teck Gan and Jiu-Kang Yu.  Group schemes and local densities.  Duke Mathematical Journal, 105(3):497–524, 2000.
  * [Har13] Robin Hartshorne.  Algebraic geometry, volume 52.  Springer Science & Business Media, 2013.
  * [How12] Benjamin Howard.  Complex multiplication cycles and Kudla-Rapoport divisors.  Annals of Mathematics, pages 1097–1171, 2012.
  * [How15] Benjamin Howard.  Complex multiplication cycles and kudla-rapoport divisors II.  American Journal of Mathematics, 137(3):639–698, 2015.
  * [How19] Benjamin Howard.  Linear invariance of intersections on unitary Rapoport–Zink spaces.  In Forum Mathematicum, volume 31, pages 1265–1281, 2019.
  * [HSY20] Qiao He, Yousheng Shi, and Tonghai Yang.  The Kudla-Rapoport conjecture at a ramified prime for $U(1,1)$.  Transactions of the AMS, to appear., 2020.
  * [Jac62] Ronald Jacobowitz.  Hermitian forms over local fields.  American Journal of Mathematics, 84(3):441–465, 1962.
  * [Kat99] Hidenori Katsurada.  An explicit formula for siegel series.  American Journal of Mathematics, 121(2):415–452, 1999.
  * [Kit83] Yoshiyuki Kitaoka.  A note on local densities of quadratic forms.  Nagoya Mathematical Journal, 92:145–152, 1983.
  * [Kit99] Yoshiyuki Kitaoka.  Arithmetic of quadratic forms, volume 106.  Cambridge University Press, 1999.
  * [KM90] Stephen S Kudla and John J Millson.  Intersection numbers of cycles on locally symmetric spaces and Fourier coefficients of holomorphic modular forms in several complex variables.  Publications Mathématiques de l’IHÉS, 71:121–172, 1990\.
  * [KR11] Stephen Kudla and Michael Rapoport.  Special cycles on unitary Shimura varieties I. unramified local theory.  Inventiones mathematicae, 184(3):629–682, 2011.
  * [KR14a] Stephen Kudla and Michael Rapoport.  An alternative description of the Drinfeld $p$-adic half-plane.  In Annales de l’Institut Fourier, volume 64, pages 1203–1228, 2014\.
  * [KR14b] Stephen Kudla and Michael Rapoport.  Special cycles on unitary Shimura varieties II: Global theory.  Journal für die reine und angewandte Mathematik (Crelles Journal), 2014(697):91–157, 2014.
  * [Krä03] Nicole Krämer.  Local models for ramified unitary groups.  In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 73, pages 67–80. Springer, 2003.
  * [Kud94] Stephen Kudla.  Splitting metaplectic covers of dual reductive pairs.  Israel Journal of Mathematics, 87(1-3):361–401, 1994.
  * [Kud96] Stephen Kudla.  Notes on the local theta correspondence.  unpublished notes, available online, 1996.
  * [Kud97] Stephen Kudla.  Central derivatives of eisenstein series and height pairings.  Annals of mathematics, 146(3):545–646, 1997.
  * [Kud03] Stephen S Kudla.  Special cycles and derivatives of eisenstein series.  arXiv preprint arXiv:math/0308295, 2003.
  * [Liu11] Yifeng Liu.  Arithmetic theta lifting and $L$-derivatives for unitary groups, I.  Algebra Number Theory, 5(7):849–921, 2011.
  * [LL21] Chao Li and Yifeng Liu.  Chow groups and $L$-derivatives of automorphic motives for unitary groups, II.  arXiv preprint arXiv:2101.09485, 2021.
  * [LZ19] Chao Li and Wei Zhang.  Kudla–Rapoport cycles and derivatives of local densities.  J. Amer. Math. Soc. to appear, 2019.
  * [LZ21] Chao Li and Wei Zhang.  On the arithmetic Siegel–Weil formula for GSpin Shimura varieties.  arXiv preprint arXiv:2106.15038, 2021.
  * [RSZ17] Michael Rapoport, Brian Smithling, and Wei Zhang.  On the arithmetic transfer conjecture for exotic smooth formal moduli spaces.  Duke Mathematical Journal, 166(12):2183–2336, 2017.
  * [RSZ18] Michael Rapoport, Brian Smithling, and Wei Zhang.  Regular formal moduli spaces and arithmetic transfer conjectures.  Mathematische Annalen, 370(3-4):1079–1175, 2018.
  * [RSZ20] M. Rapoport, B. Smithling, and W. Zhang.  Arithmetic diagonal cycles on unitary Shimura varieties.  Compositio Mathematica, 156(9):1745–1824, 2020.
  * [RSZ21] M Rapoport, B Smithling, and W Zhang.  On shimura varieties for unitary groups.  Pure and Applied Mathematics Quarterly, 17(2):773–837, 2021.
  * [RTW14] Michael Rapoport, Ulrich Terstiege, and Sean Wilson.  The supersingular locus of the Shimura variety for $\mathrm{GU}(1,n-1)$ over a ramified prime.  Mathematische Zeitschrift, 276(3-4):1165–1188, 2014.
  * [RZ96] M Rapoport and Thomas Zink.  Period spaces for p-divisible groups.  Number 141. Princeton University Press, 1996.
  * [SABK94] Christophe Soulé, Dan Abramovich, JF Burnol, and JK Kramer.  Lectures on Arakelov geometry.  Number 33 in Cambridge Studies in Advanced Mathematics. Cambridge university press, 1994.
  * [Shi18] Yousheng Shi.  Special cycles on unitary Shimura varieties at ramified primes I.  arXiv preprint arXiv:1811.11227, 2018.
  * [Shi20] Yousheng Shi.  Special cycles on unitary Shimura curves at ramified primes.  arXiv preprint arXiv:2004.07158, 2020.
  * [Tam63] Tsuneo Tamagawa.  On the $\zeta$-functions of a division algebra.  Annals of Mathematics, 77(2):387–405, 1963.
  * [Ter10] Ulrich Terstiege.  Intersections of special cycles on the Shimura variety for $\mathrm{GU}(1,2)$.  Journal fur die Reine und Angewandte Mathematik, 2013, 06 2010.
  * [Zha21] Wei Zhang.  Weil representation and arithmetic fundamental lemma.  Annals of Mathematics, 193(3):863–978, 2021.