0
$\begingroup$

Let $n$ and $k$ be positive integers and fix a vertex $A$ in the complete graph $K_n$ on $n$ vertices. In how many ways can we colour the edges of $K_n$, each with one out of $k$ colours, so that $A$ is not in a monochromatic triangle?

I tried some inclusion-exclusion ideas but things get messy. Any help appreciated! (Bonus: Can we easily generalize to monochromatic $K_r$, where $r\geq 3$ is an integer? Maybe at least do something for $r=4$? The main question concerns $r=3$.)

$\endgroup$
2
  • 1
    $\begingroup$ I believe there's no easy closed-form expression. Are you expecting one? $\endgroup$
    – abacaba
    Commented May 14, 2022 at 20:23
  • $\begingroup$ @ShengtongZhang If not closed form, maybe something asymptotic? $\endgroup$ Commented May 15, 2022 at 0:25

1 Answer 1

2
+100
$\begingroup$

There is a "straightforward" multinomial summation $$ k^{\binom{n-1}{2}} \sum_{n_1, \dots, n_k} \binom{n-1}{n_1,\dots,n_k}\left(1-\frac1k\right)^{\binom{n_1}{2} + \dots + \binom{n_k}{2}} $$ where the sum is over all $n_1, \dots, n_k$ with $n_1 + n_2 + \dots + n_k = n-1$: these are the degrees of vertex $A$ in each of the $k$ colors. This summation accounts for all the ways we can color the edges incident on $A$.

For the other $\binom{n-1}{2}$ edges, we have two options:

  • A typical edge has all $k$ options, and so we prematurely have a factor of $k^{\binom{n-1}{2}}$ to count those.
  • An edge between two of the $n_i$ neighbors of $A$ in color $i$ has only $k-1$ objects; it can't also use color $i$, or we'd get a monochromatic triangle containing $A$. We adjust by $(1 - \frac1k)^{\binom{n_i}{2}}$ for such edges, for each $i$.

When $k=2$, the number of such colorings is in OEIS sequence A047863 with an offset by $1$. This has a different interpretation there: the description reads

Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

The idea is that "black nodes" are vertices whose edge to $A$ is the first color, "white nodes" are vertices whose edge to $A$ is the second color, and the color of edges between two black nodes or two white nodes are forced, so we may pretend they're not there. There are two color options for an edge between a black node and a white node, which is equivalent to choosing if there's an edge between them.

Notably, even the $k=2$ case has no closed form in the OEIS.

Sequence A047863 is a row of an array given by OEIS sequence A322280, but this is a different generalization, and not relevant to us. For $k=3$, the sequence counting the colorings begins $$1, 3, 24, 510, 28704, 4270152, \dots$$ and this does not appear in the OEIS (even if we delete the first few entries, which are a bit silly).


Here is an asymptotic approach when $n$ is large compared to $k$; in fact, for simplicity I will assume $k$ is constant as $n \to \infty$.

Then consider a random $k$-coloring of $K_n$. The expected number of monochromatic triangles containing $A$ is $\binom{n-1}2 \cdot \frac{1}{k^2}$. Though these are not quite independent events, they are mostly independent. Specifically, the $i^{\text{th}}$ moment for any constant $i$ is asymptotically dominated by triangles that share no edges, because sharing edges loses us factors of $n$ (in the number of cases) and wins us only factors of $k$ (in the probability).

Therefore the number of monochromatic triangles is asymptotically Poisson with mean $\frac{(n-1)(n-2)}{2k^2}$, and so a good estimate for the probability that there are none is $e^{-(n-1)(n-2)/(2k^2)}$. The number of colorings, then, is about $k^{\binom n2}e^{-(n-1)(n-2)/(2k^2)}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .