4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ How $F(n,m)$ does not depend on $|C|$? E.g., it is unclear why $F(n,1)=n$ if we can color each vertex in its own color? $\endgroup$ – Max Alekseyev Nov 30 '15 at 15:46
  • $\begingroup$ @MaxAlekseyev That is because every pair of vertices needs to have at least one edge. So for $F(n, 1)$ all vertices have to have the same color and hence $F(n, 1) = n$. $\endgroup$ – Kostub Deshmukh Nov 30 '15 at 18:53
  • $\begingroup$ This is still obscure. E.g., if $|C|=1$, then $F(n,m)$ should be equal to $n$, no matter what is $m$. $\endgroup$ – Max Alekseyev Nov 30 '15 at 19:09
  • $\begingroup$ Oh, I see. The size of $|C|$ doesn't really matter and is not relevant to the question. Assume there are infinitely many colors. I clarified in the statement above. $\endgroup$ – Kostub Deshmukh Nov 30 '15 at 19:35
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. The upper bound looks interesting. I was looking for a stronger lower bound than just applying the pigeon hole principle once. To calculate $F(9,3) =5$, I had to apply it repeatedly and am trying to generalize that proof. $\endgroup$ – Kostub Deshmukh Dec 8 '15 at 5:38

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.