Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors. I wonder if the following type of question has been studied before, where monochromatic is replaced by bichromatic (which now I use in the sense of having at most two colors).

How many colors do we need to color the edges of a given graph to avoid a certain bichromatic subgraph?

We could define the multicolor biRamsey number of $G$, denoted by $biR_k(G)$, as the least integer $n$ such that in any $k$-coloring of $K_n$ there is a bichromatic copy of $G$. Probably the simplest example is $biR_3(K_3)=5$, as a coloring of a complete graph has no bichromatic triangle if and only if every monochromatic component is a matching, and such a $3$-coloring exists for $K_n$ if and only if $n\le 4.$

Obviously, we have $biR_k(G)\le R_k(G)$, but I don't see any general lower bound for $biR_k$. Has this parameter ever been studied? (Possibly under a less brilliant name.)

Motivation: I would need something like in any $n$-coloring of a graph on $n$ vertices and $\Omega(n^2)$ edges there is a trichromatic $K_{3,3}$, or something similar, where I have other conditions, like every color class is a matching.

Update: As you can see from the answers of Ilya and Jan, the answer to the motivation is negative, but I can produce other similar conditions, so I am still interested whether the problem has been studied.

  • 1
    $\begingroup$ Suppose I have a $2k$ coloring of the edges of $K_n$. Partition the edge colors into $k$ pairs and consider each as a single color. If $n \ge R_k(G)$, then there is a monochromatic $G$ in this coloring and therefore a bichromatic $G$ in the original coloring. Therefore you can actually get that $biR_{2k}(G) \le R_k(G)$. This is still an upper bound of course, but I thought it was worth pointing out. $\endgroup$ – David Roberson Aug 31 '16 at 13:15
  • 2
    $\begingroup$ $biR_k(K_3)=k+2$ or $k+1$, depending on the parity of $k$. Indeed, a bichromatic $K_3$ exists iff there are two adjacent edges of the same color. $\endgroup$ – Ilya Bogdanov Aug 31 '16 at 13:25

Problems of this variety have been studied, beginning with a paper of Erdős and Gyárfás, 'A variant of the classical Ramsey problem'. In that paper, they define a function $f(n,p,q)$ to be the smallest number of colours $k$ needed to produce a $k$-colouring of the edges of $K_n$ such that every $K_p$ contains at least $q$ distinct colours. The study of this function and its variants (such as replacing $K_p$ with a general graph $H$) leads to a great number of interesting questions. For example, even the behaviour of $f(n,4,3)$ is poorly understood.

  • $\begingroup$ Thx, Abhishek Methuku just emailed me about the exact same paper... $\endgroup$ – domotorp Sep 1 '16 at 16:40

Regarding the question in "Motivation": a $1$-factorization of $K_{n,n}$ is essentially an $n\times n$ Latin square, and a $3$-chromatic $K_{3,3}$ would be a proper Latin subsqare.

This paper shows that there are Latin $n\times n$ squares with no proper Latin subsquares for $n=pq \neq 6$ where $p,q$ are distinct primes. The author claims that for $n$ prime it is well known that the multiplication table of the group of order $p$ is a Latin square with no proper Latin subsquares. Indeed, a proper Latin subsquare would correspond to a nontrivial proper subgroup.

Constructions of Latin $n\times n$ squares with no proper Latin subsquares are known for all odd $n$: http://www.sciencedirect.com/science/article/pii/S0195669805000909


As for $triR_k(K_{3,3})$, I would assume that the usual `averaging' approach should give an estimate not far from the optimal one. Take three colors with the maximal number of edges in them and estimate the number of triples of vertices having a common neighbour by these colors. If this number exceeds $2{n\choose 3}$, we are done. [EDIT] This seems to be covered by the Kővári–Sós–Turán theorem, see https://en.wikipedia.org/wiki/Zarankiewicz_problem. [END EDIT]

Exactly on the described situation, it seems that you have no chance for finding $K_{3,3}$ even in a complete graph with $n$ vertices and $n$-colored edges. Indeed, if we take a regular $(6k+1)$-gon and paint all parallel edges in one color, then the resulting graph would not contain a trichromatic $K_{3,3}$. Moreover, it seems that here we have some regularity which helps finding such $K_{3,3}$...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.