Decomposing complete graphs into clique-free graphs of certain size
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 &lt; 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) &gt; k⋅2k/2/(e√2).  This means that if m is sufficiently large, then m &lt; R(k,k) for k = ⌈2 log2m⌉ = O(log m).  In other words, you can take a=1 with two sets.