<p><strong>This is not an answer.</strong>  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.</p>

<p>Fix any graph $G=(V,E)$ and integer $p\ge 1$.  Let $s=\lceil |E|/p\rceil$</p>

<p><strong>Lemma.</strong> <em>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.</em></p>

<p><em>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).$$</em></p>

<p><em>Proof.</em>  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$.)</p>

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

CC BY-SA 3.0
2017-06-12T02:20:26.627Z
2017-06-12T02:20:26.627Z
Neal Young
<p>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.</p>

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

<p>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)$). </p>

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

CC BY-SA 3.0
2017-06-10T05:40:28.820Z
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
CC BY-SA 3.0
2017-06-10T11:18:33.297Z
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
CC BY-SA 3.0
2017-06-11T17:24:36.710Z
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
CC BY-SA 3.0
2017-06-11T17:46:16.953Z
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
CC BY-SA 3.0
2017-06-12T02:17:36.223Z
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
CC BY-SA 3.0
2017-06-12T17:50:56.930Z
Yes, that's true. If all edges contain the same vertex, there is no hope. Furthermore, we can handle vertices of very high degree somehow separately in our application and can then assume that the remaining tuples are not too bad. One of the insights that I hoped for by posting the question was to get insights about the influence of $q$. 
I agree with the observation stated in the "answer", we are also thinking in terms of O(.).
Thomas S
<combinatorics>
Distributing a binary relation into bins such that each element is in a small number of bins
Thomas S
# Distributing a binary relation into bins such that each element is in a small number of bins

(Asked by: username_0 on 2017-06-01)

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...

**Tags:** combinatorics
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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$.  
> **username_1**: 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...  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Yes, that's true. If all edges contain the same vertex, there is no hope. Furthermore, we can handle vertices of very high degree somehow separately in our application and can then assume that the remaining tuples are not too bad. One of the insights that I hoped for by posting the question was to get insights about the influence of $q$.  I agree with the observation stated in the "answer", we are also thinking in terms of O(.).  

---

## 1 answers

### Answer by username_1 on 2017-06-12. Score: 2

**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

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


---

