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&gt;0$ as large as possible...
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&lt;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