Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

Question

You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a function that maps each vertex to a subset of colors of size $\le m$.
We define the set of edges of the graph as: $E := \big\lbrace \small\{ \normalsize v_i, v_j, c_k \small\} \normalsize \mid c_k \in f(v_i) \cap f(v_j) \big\rbrace$, i.e. there is an edge colored with a given color between every pair of vertices that share that color. Note that a pair of vertices may have more than one edge if they share multiple colors.

It is guaranteed that every pair of vertices has at least one edge in common. i.e. $\forall v_i, v_j \in V$ there exists $c_k \in C$ such that $\{v_i, v_j, c_k\} \in E$.

Define $F(n,m) = s$ such that for any graph with $n$ vertices, each vertex colored with $\le m$ colors as above, there is a clique of order $s$ where each edge is colored with the same color. Another way of phrasing this is that there is a subset of size $s$, $S \subseteq V$, $|S| = s$, all vertices of which share a color. i.e. $\exists c_k \in C$ such that $\forall v_i \in S, c_k \in f(v_i)$.

So a few simple examples: $F(n,1)=n$, clearly because every vertex has to have the same color. It is easy to show that, $F(n,2)=n−1$ and $F(n,n-1)=2$.

One can show that $F(9,3)=5$ by applying the pigeonhole principle repeatedly.

What method can be used to solve this for general $n$ and $k$? Or how can this problem be represented as a known problem in graph-theory/combinatorics.

Note: This function can be represented as an inverse to resemble the Ramsey numbers as follows: $G(s, m) = n$, where $n$ is the smallest number where any graph with $n$ vertices, each vertex colored with at most $m$ colors as above contains a clique of order $s$. But that is harder since $F$ only gives us bounds on $G$.

Answer 1

It is possible to give pretty tight bounds. Namely, one can show that $1+\frac{n-1}{m} \leq F(n,m)$, and if there exists a projective plane of order $m-1$ then $F(n,m) \leq\lceil \frac{n} {m^2-m+1}\rceil m$.

For the first bound, we need to show that for any collection of vertex lists of size $m$ such that every two lists share a color, there are at least $1+\frac{n-1}{m}$ vertices that have a common color. Indeed, choose an arbitrary vertex $v$, and assume that its list is $\{1, ... ,m\}$. Since every vertex shares a color with $v$, we can divide the remaining vertices into $m$ types, depending on which color they share with $v$. Therefore there is a set of at least $\frac{n-1}{m}$ vertices that have the same color as $v$, and together with $v$ they form the desired clique.

On the other hand, we have to show that there is a way to choose $n$ lists such that there is no cliques whose size is greater than $\lceil\frac{n} {m^2-m+1}\rceil m$. To do this, we will use the notion of a finite projective plane.

https://en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes

This is basically a collection of lists such that each two lists have an item in common, and each item is contained in the same number of lists. If the list length is $m$, then the number of such lists is $m^2-m+1$, and each item is contained in $m$ lists.

Let's divide the vertices into $m^2-m+1$ types of size at most $\lceil\frac{n}{m^2-m+1}\rceil$, and associate each type with a different list from our projective plane. Now the largest clique size is $ \lceil\frac{n}{m^2-m+1}\rceil$, the number of vertices in a type, times $m$, the number of different lists a given item is contained in, giving the result.