Construct a graph $G=(V,E)$ where each $v\in V$ corresponds to a unit triangle, and each $uv\in E$ occurs if $u$ and $v$ share a side. We’re $3$-coloring $G$ and trying to maximize the number of occurences of a structure $uvw$ with $uv,vw\in E$. It is easy to see that $uw\notin E$. Call the color of $v$ as $f(v)$. We can hence write the number of these structures as $$\sum_{v\in V}\sum_{u,w\in V \mid f(u),f(w)\ne f(v), f(u)\ne f(w)}1\le \sum_{v\in V}\Big\lfloor \frac{d(v)}{2}\Big\rfloor \Big\lceil \frac{d(v)}{2}\Big\rceil.$$One can write this as $$\sum_{v\in V}\Big\lfloor \frac{d(v)^2}{4}\Big\rfloor.$$This sum is $18n^2-9n$ (thanks @below) after some trivial computations. To show the bound is achievable, we need to find a $3$-coloring such that the neighborhood of each $v\in V$ (W.L.O.G $f(v)$ is red) consists of half blue and half yellow vertices. It is not at all difficult to exhibit such a coloring, one can do it inductively.

It's actually $18n^2-9n$

yofro wrote: To show the bound is achievable, we need to find a $3$-coloring such that the neighborhood of each $v\in V$ (W.L.O.G $f(v)$ is red) consists of half blue and half yellow vertices. It is not at all difficult to exhibit such a coloring, one can do it inductively. @yofro Hi, would you please give a valid example for $n=2$, or just make the induction more clearly? I find that directly using the coloring pattern for $n=1$ doesn't work.

Anan_PZ wrote: yofro wrote: To show the bound is achievable, we need to find a $3$-coloring such that the neighborhood of each $v\in V$ (W.L.O.G $f(v)$ is red) consists of half blue and half yellow vertices. It is not at all difficult to exhibit such a coloring, one can do it inductively. @yofro Hi, would you please give a valid example for $n=2$, or just make the induction more clearly? I find that directly using the coloring pattern for $n=1$ doesn't work. I’ve attached an example for $n=2$ which should work (correct me if I’m wrong). I used R,G,B as the colors. The induction I had in mind wasn’t on $n$, it was inducting on the side length itself (we can do it for any side length, I think). The details are probably non-trivial, which is why my solution isn’t fully complete as is (I meant only to get the bound, don’t care too much about the construction), but the new graph is the old graph but with an added layer to the bottom. The idea is that very few vertices in this layer have fixed color, and most of the vertices directly connected to the layer above have two possible choices for color. Thus the strategy is to color whatever is fixed and then realize that we have enough freedom to color the rest. Again, the details are not obvious.

Attachments:

yofro wrote: Anan_PZ wrote: yofro wrote: To show the bound is achievable, we need to find a $3$-coloring such that the neighborhood of each $v\in V$ (W.L.O.G $f(v)$ is red) consists of half blue and half yellow vertices. It is not at all difficult to exhibit such a coloring, one can do it inductively. @yofro Hi, would you please give a valid example for $n=2$, or just make the induction more clearly? I find that directly using the coloring pattern for $n=1$ doesn't work. I’ve attached an example for $n=2$ which should work (correct me if I’m wrong). I used R,G,B as the colors. The induction I had in mind wasn’t on $n$, it was inducting on the side length itself (we can do it for any side length, I think). The details are probably non-trivial, which is why my solution isn’t fully complete as is (I meant only to get the bound, don’t care too much about the construction), but the new graph is the old graph but with an added layer to the bottom. The idea is that very few vertices in this layer have fixed color, and most of the vertices directly connected to the layer above have two possible choices for color. Thus the strategy is to color whatever is fixed and then realize that we have enough freedom to color the rest. Again, the details are not obvious. @yofro Thanks for you reply The problem states that each color appears $3n^2$ times, I feel not easy to verify this by induction on the side length. And in your example, the 2nd layer 2-degree R has 2 G's connected. The numbers of R,G,B are 13, 12, 11, respectively. I found the only valid example for $n=1$ has the similar pattern such as: R; RGB; GBGRB.

Thanks, I just completely missed that part of the problem statement! I hear the answer is still correct though, just the construction is harder to build.

Yes, I was quite confused that the condition that all colours appear the same number of times appears to be irrelevant to the problem (except making the construction slightly harder). For the upper bound, there is also a very short argument without any graphs: Each of the $9n^2-9n+3$ triangles not at the boundary is the center of exactly $3$ trapezoids, of which clearly at most two can be colorful. The $9n-6$ triangles at the boundary (without the vertices) are the center of exactly one trapezoid (and the vertices of none). Hence the number of colourful trapezoids is at most $2(9n^2-9n+3)+(9n-6)=18n^2-9n$.