Determine whether it's possible to cover a $K_{2012}$ with a) 1000 $K_{1006}$'s; b) 1000 $K_{1006,1006}$'s. David Yang.
Problem
Source: ELMO Shortlist 2012, C2
Tags: floor function, ceiling function, algorithm, logarithms, combinatorics proposed, combinatorics
06.07.2012 11:52
a) Let $A_1=\{1,2,\cdots,503\}$, $A_2=\{504,\cdots,1006\}$, $A_3=\{1007,\cdots,1509\}$, $A_4=\{1510,\cdots,2012\}$. Just consider $6$ complete graphs $A_1\cup A_2$, $A_1\cup A_3, \cdots A_3 \cup A_4$. Thus possible. b)Possible. Just consider $505$ divisions. $\{odd\},\{1,4,5,8,\ldots,2009,2012\},\{4k-3,4k-2,\ldots,4k+1002\}$. (Take modulo $2012$)
06.07.2012 19:35
Bigwood wrote: b)Possible. Just consider $505$ divisions. $\{odd\},\{1,4,5,8,\ldots,2009,2012\},\{4k-3,4k-2,\ldots,4k+1002\}$. (Take modulo $2012$) For a cleaner and more efficient construction, we can use recursion: letting $f(n)$ denote the minimum number of $K_{\lfloor{n/2}\rfloor,\lceil{n/2}\rceil}$'s needed to cover a $K_n$, we have $f(1)=0$ and \[f(n)\le 1+\max\{f(\lfloor{n/2}\rfloor),f(\lceil{n/2}\rceil)\}\]for $n\ge2$. Indeed, suppose $M=\max\{f(\lfloor{n/2}\rfloor),f(\lceil{n/2}\rceil)\}$ and consider the partition $G_1\cup G_2=K_n$, where $|G_1|=\lfloor{n/2}\rfloor$ and $|G_2|=\lceil{n/2}\rceil$. By definition, there exist covers of $G_1$ and $G_2$ by complete bipartite graphs $H_{1i}\cup H_{2i}$ and $H_{3i}\cup H_{4i}$ ($1\le i\le M$), respectively, such that $|H_{1i}|=\lfloor{|G_1|/2}\rfloor$, $|H_{2i}|=\lceil{|G_1|/2}\rceil$, $|H_{3i}|=|G_1|-\lfloor{|G_1|/2}\rfloor$, and $|H_{4i}|=|G_2|-\lceil{|G_1|/2}\rceil$, where it is easy to check that $\{|H_{3i}|,|H_{4i}|\}=\{\lfloor{|G_2|/2}\rfloor,\lceil{|G_2|/2}\rceil\}$. But then our $K_n$ is covered by $G_1\cup G_2$ and $(H_{1i}\cup H_{3i})\cup(H_{2i}\cup H_{4i})$ (we only have edges between $H_{ui},H_{vi}$ when $2\nmid u-v$) for $1\le i\le M$. This gives something like $f(2012)\le 11$. Note: In fact, for any fixed subgraph $H$, we can cover (using the greedy algorithm by covering the maximum possible number of previously uncovered edges at each step) $K_n$ using at most $cn^2\ln{n}/E(H)$ copies of $H$, where $c$ is some constant independent of $n,H$. (See, for instance, Proposition 1, and note that by the probabilistic method, $\mu(K_n)=\binom{n}{2}/E(H)$.)