# Distributing a binary relation into bins such that each element is in a small number of bins

We are given pairs of objects (say, numbers). Each object appears in at most $q$ pairs. Our goal is to distribute the pairs into equal-size bins, such that each object occurs in as few as possible different bins.

More precisely, we are interested in a function $f$ with the property that for every binary relation with $m$ pairs with at most $q$ pairs per object, there is a distribution of the pairs to $p$ bins, such that each bin receives $m/p$ pairs ($p$ should divide $m$), and no object occurs in more than $f(m,q,p)$ bins.

This question came up in our research on parallel query evaluation. One would expect that $m$ is large compared to $p$. The "right" size of $q$ is less clear. An interesting size for $q$ could be, e.g., $\sqrt{\frac{m}{p}}$. A function that does not depend on $q$, but only works for a certain range of $q$ would also be useful (but not $q=O(1)$).

Actually, we are after bounds of the form $p^{1-\epsilon}$, with $\epsilon>0$ as large as possible...

• In graph terminology: given an integer $p$ and a graph $G=(V,E)$ with $m$ edges, with each vertex having degree at most $q$, find $p$ subgraphs $G_1, G_2, \ldots, G_p$ where $G_i=(V_i, E_i)$, such that $V=\bigcup_i V_i$, and $\{E_i\}_i$ is a partition of $E$ into $p$ parts each of size $m/p$, and each vertex $v\in V$ occurs in at most $k$ of the graphs $(\max_v |\{i : v\in V_i\}| \le k)$. Your goal is to minimize $k$. What's the best upper bound on $k$ you can show given $m$, $p$, and $q$? – Neal Young Jun 10 '17 at 5:40
• That's right. In terms of graphs. The answer to the question is: $p$. Indeed, as written above, we are interested in bounds of the form $p^{1-\epsilon}$ and do not have any such bound for $\epsilon>0$. – Thomas S Jun 10 '17 at 11:18
• A special case to get started: Let $n \ge 1$ be an odd integer. Can one partition the $n\choose 2$ edges of the complete graph $K_n$ into $n$ subsets of size $(n-1)/2$ such that, for each vertex, the number of subsets containing edges incident to that vertex is $O(n^{1-\epsilon})$, for some $\epsilon>0$? I bet yes for any $\epsilon<1/2$ --- take $n$ random vertex subsets of size $n^{1-\epsilon}$ each. Then with high probability each vertex is in about $n^{1-\epsilon}$ of the vertex subsets, and each pair $(i,j)$ is in about $n^{1-2\epsilon}$ of the subsets. Now assign the pairs to subsets... – Neal Young Jun 11 '17 at 17:24
• In this case, the nodes can be first distributed into $\sqrt{n}$ sets of size $\sqrt{n}$ (think of intervals). Then each bin gets the product $I\times J$ of two such sets (I am considering the complete directed graph, whic is easier to state and asymptotically not much different). Hence, each vertex occurs in $\sqrt{n}$ bins, that is, $\epsilon=\frac{1}{2}$ in this case. – Thomas S Jun 11 '17 at 17:46
• For the star graph ($n-1$ edges incident to one vertex $r$) the vertex $r$ has to be in each of the $p$ subgraphs, so for that case a bound less than $p$ is not possible. I guess that's why you restrict the max degree $q$? Maybe you could say something more definitive about that, since it seems to be a crucial assumption. Meanwhile, I left an observation (not an answer, but too big to fit as a comment!) as an answer below. – Neal Young Jun 12 '17 at 2:17

This is not an answer. It is just the somewhat trivial observation that WLOG you can relax the requirement that there be exactly $p$ edge subsets $\{E_i\}_i$ of exactly the same size, and instead just look for any number of edge subsets of of size $O(\textsf{the desired size})$. Maybe this helps think about the problem.
Fix any graph $G=(V,E)$ and integer $p\ge 1$. Let $s=\lceil |E|/p\rceil$
Lemma. Suppose there are subgraphs $\{G'_j=(V'_j,E'_j)\}_j$ such that $\{E'_j\}_j$ partitions $E$ into (any number of) parts of size $O(s)$. Let $$M = \max_{v\in V} |\{j : v\in V'_j\}|$$ be the maximum number of parts that any vertex is in.
Then there are $p$ subgraphs $\{G_i=(V_i,E_i)\}_i$ such that $\{E_i\}_i$ partitions $E$ into exactly $p$ parts each of size at most $s=\lceil |E|/p\rceil$, and $$\max_{v\in V} |\{i : v\in V_i\}| = O(M).$$
Proof. Starting with the sequence $E'_1, E'_2, \ldots, E'_{p'}$, replace each part $E'_j$ in the sequence by any ordered sequence of the edges contained in that part. Let $e_1, e_2, \ldots, e_m$ be the resulting sequence (a permutation of $E$ such that each part $E'_j$ is some "interval" $\{e_a, e_{a+1}, \ldots, e_b\}$ of edges in the sequence). Now partition this sequence into $p$ contiguous subsequences such that each except the last has size $s$, and let $E_i$ contain the edges in the $i$th contiguous subsequence. (So $E_i = \{e_{i\,s+1}, e_{i\,s+1}, \ldots, e_{(i+1)s}\}$ for $i<p$.)
By assumption each part $E'_j$ has size $O(s)$, and by design each part $E_j$ except the last part $E_p$ has size $s$, so (because of the way $\{E_i\}_i$ is defined) the edges in any given part $E'_j$ are split across $O(1)$ parts in $\{E_i\}_i$. This, and the assumption that each vertex occurs in at most $M$ of the parts in $\{E'_j\}_j$, imply that each vertex occurs in at most $O(M)$ of the parts in $\{E_i\}_i$. QED