2
$\begingroup$

Modified in accordance with Tsuyoshi's comment which seems to generalize.

Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no cliques of size $k$ for some $k \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

How about the case when $K_{n}$ is replaced by a bipartite $K_{m,n}$ where one seeks a partition such that there is no $K_{k,l}$ for some $k,l \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

This question is about Ramsey theory. In the case of the complete graphs, you can take a=1 by considering partitioning into only two sets.

The Ramsey number R(k,k) is the minimum integer m such that however you partition the edges of the complete graph Km into two sets, at least one of the sets contains Kk as a subgraph. This immediately implies that if m < R(k,k), then the edges of the complete graph Km can be partitioned into two sets so that neither set contains Kk as a subgraph.

Erdős proved that R(k,k) grows exponentially: R(k,k) > k⋅2k/2/(e√2). This means that if m is sufficiently large, then m < R(k,k) for k = ⌈2 log2m⌉ = O(log m). In other words, you can take a=1 with two sets.

Improve this answer
$\endgroup$
4
  • $\begingroup$ any algorithms? $\endgroup$
    – v s
    Commented Jul 19, 2011 at 5:00
  • $\begingroup$ @vs: I suggest you to check the literature in Ramsey theory (both for algorithms and for your modified question). Note that many lower bounds on Ramsey numbers, including Erdős’s lower bound which I mentioned in the answer, are proved by using probabilistic method and do not automatically produce efficient algorithms to find an actual partition. (By the way, this result of Erdős’s is well-known for being one of the first uses of probabilistic method.) $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 19, 2011 at 15:23
  • $\begingroup$ !Tsuyoshi Thank you. I think the number $2$ is right in my case. I checked my problem. For me, $m = O(c\log{n})$ where $c \le 3$ and $k = O(\log{n})$. Any decent algorithm should be good for benchmarking! $\endgroup$
    – v s
    Commented Jul 19, 2011 at 15:57
  • $\begingroup$ @vs: Just a few quick updates: (1) The bipartite case seems to be also studied, so again check the literature in Ramsey theory. (2) When I wrote “do not automatically produce efficient algorithms” in my previous comment, I meant efficient deterministic algorithms. Probabilistic method usually gives efficient randomized algorithms, so you may be in luck if that is what you want. $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 22, 2011 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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