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$
4
  • $\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$ Nov 30, 2015 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$ Nov 30, 2015 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$ Nov 30, 2015 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$ Nov 30, 2015 at 19:35

1 Answer 1

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$
1
  • $\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$ Dec 8, 2015 at 5:38

You must log in to answer this question.

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