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

<p>The <a href="http://mathworld.wolfram.com/RamseyNumber.html">Ramsey number</a> <i>R</i>(<i>k</i>,<i>k</i>) is the minimum integer <i>m</i> such that however you partition the edges of the complete graph K<sub><i>m</i></sub> into two sets, at least one of the sets contains K<sub><i>k</i></sub> as a subgraph.  This immediately implies that if <i>m</i> &lt; <i>R</i>(<i>k</i>,<i>k</i>), then the edges of the complete graph K<sub><i>m</i></sub> can be partitioned into two sets so that neither set contains K<sub><i>k</i></sub> as a subgraph.</p>

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

CC BY-SA 3.0
2011-07-19T05:00:13.347Z
any algorithms?
v s
CC BY-SA 3.0
2011-07-19T15:23:14.657Z
@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.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-19T15:57:24.660Z
!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!
v s
CC BY-SA 3.0
2011-07-22T15:17:45.167Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-19T00:13:47.087Z
2011-07-19T00:13:47.087Z
Tsuyoshi Ito
<p>Modified in accordance with Tsuyoshi's comment which seems to generalize.</p>

<p>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?</p>

<p>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?</p>

<graph-theory><co.combinatorics><graph-algorithms><clique><ramsey-theory>
Decomposing complete graphs into clique-free graphs of certain size
v s
# Decomposing complete graphs into clique-free graphs of certain size

(Asked by: username_0 on 2011-07-18)

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?

**Tags:** graph-theory, co.combinatorics, graph-algorithms, clique, ramsey-theory

---

## 1 answers

### Answer by username_1 on 2011-07-19. Score: 8 | Accepted answer

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](http://mathworld.wolfram.com/RamseyNumber.html) *R*(*k*,*k*) is the minimum integer *m* such that however you partition the edges of the complete graph K*m* into two sets, at least one of the sets contains K*k* as a subgraph. This immediately implies that if *m* < *R*(*k*,*k*), then the edges of the complete graph K*m* can be partitioned into two sets so that neither set contains K*k* as a subgraph.

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

> **Comments:**
> **username_0**: any algorithms?  
> **username_1**: @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.)  
> **username_0**: !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!  
> **username_1**: @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.  

---

