$3$-colourings of a complete graph without monochromatic spanning trees

Question

It is not difficult to prove that for every $2$-colouring of the edges of a complete graph, there is a monochromatic spanning tree, based on the fact that a graph or its complement has to be connected. Then I was wondering:

Given a complete graph $K_n$, how many $3$-colourings of its edges ($f:E\to\{0,1,2\}$) are there such that no monochromatic spanning tree can be found?

Obviously, if there are three vertices $A,B,C$ such that no edge from $A$ has colour $0$, no edge from $B$ has colour $1$, no edge from $C$ has color $2$, we have a colouring with the wanted property. However I fear this gives just a weak lower bound.

I tried a probabilistic approach, based on the following fact: if we take a random subset of the edges of $K_n$, the associated graph is connected with probability $\frac{1}{2}$ (by the same lemma as above). So we may believe that the subgraph given by the edges with some colour is disconnected with probabability $\frac{1}{2}$, and the colourings with the previous property are roughly $\frac{1}{8}$ of the total. However, there is a fatal flaw in this argument, and I'll let you figure which one.

This configuration works for sure: let we assume to have a partition of the vertices in two subsets with $\geq 2$ vertices, and that every edge in a subset has colour $2$. Let we assume that both subsets are further partitioned in two subsets, say North and South. If we give colour $0$ to every S-S or N-N edge, colour $1$ to every S-N edge, we obviously cannot have monochromatic spanning trees. This argument shows that there are at least $4^n$ (roughly speaking) colourings with the wanted property. Maybe some tensor trick really works, since the situation just outlined comes from the following $3$-colouring of $K_4$:

Still another observation: if we start with a colouring of $K_n$ with our property, make a copy $v'$ of some vertex $v$, such that $c(v',w)=c(v,w)$, then give to the edge $v,v'$ any colour, we get a $3$-colouring of $K_{n+1}$ with the wanted property.

Answer 1

I don't think the lower bound that you get from proscribing one colour for each of three vertices is weak – I think it captures the asymptotics of the number you're interested in. The larger the components, the more edges between them that are restricted in their colour choices, so one-vertex components should be the leading contribution.

More semi-rigourously, there are $\binom nk$ subsets with $k$ vertices, and cutting them off from the rest of the graph restricts the colour choices of $k(n-k)$ edges, so the expected number of subsets with $k$ vertices not connected to the rest of the graph (which is an upper bound for the number of connected components with $k$ vertices) is

$$ \binom nk\left(\frac23\right)^{k(n-k)}\;. $$

The $k=1$ term exponentially dominates the $k=2$ term, and the remaining terms sum to

$$ \sum_{k=3}^{n/2}\binom nk\left(\frac23\right)^{k(n-k)}\le2^n\left(\frac23\right)^{3n}\sum_{k=0}^\infty\left(\frac23\right)^{kn/2}=\left(\frac23\right)^n\left(\frac89\right)^n\frac1{1-\left(\frac23\right)^{n/2}} $$

and are thus also exponentially dominated by the $k=1$ term.

I'll try to back this up with some computer simulations.

---

Edit: For the one-vertex contribution, we have $n!/(n-3)!$ choices for the isolated vertices, $3(n-3)$ edges that have only $2$ out of $3$ choices and $3$ edges that have only $1$ out of $3$ choices. Thus the probability for this (ignoring some overlaps) is

$$ \frac{729}{512}\frac{n!}{(n-3)!}\left(\frac8{27}\right)^n\;. $$

Here's code that generates random colourings and estimates the probability that there's no monochromatic spanning tree, and here's a plot of the ratio of the estimated probability to the one-vertex contribution for $3\le n\le16$ (the error bars show the standard deviation):

Convergence to unity looks likely.

Here's a logarithmic plot of the proportion of colourings without monochromatic spanning trees that don't have an isolated vertex for each colour:

The line is a linear fit to the last six data points, corresponding to $\log y=-0.272719x+0.532638$. The proportion is seen to go to zero exponentially, as expected.