Here, we suppose that we are given several graphs on the same vertex set and we want to find a bipartition which maximizes the sizes of the cuts for all these graphs simultaneously. This problem was posed by Bollobás and Scott [5] . More precisely, they asked the following question: What is the largest integer $f\left(m\right)$  such that whenever $G_1$  and $G_2$  are two graphs with $m$  edges on the same vertex set $V$  , there exists a bipartition of $V$  in which for both $i=1,2$  at least $f\left(m\right)$  edges of $G_i$  go across (i.e. their endvertices lie in different partition classes).

They suggested that perhaps even $f\left(m\right)=(1-o(1\left)\right)m/2$  , i.e. that we can almost do as well as in the case where we only have a single graph. Theorem  1 shows that this is indeed the case.

Given a graph $G$  and disjoint subsets $A,B$  of its vertex set, let $e_G(A,B)$  denote the number of edges between $A$  and $B$  .

Theorem 1 Consider graphs $G_1,...,G_{\ell }$  on the same vertex set $V$  and suppose that $G_i$  has $m_i$  edges. Then there is a bipartition of $V$  into two classes $A$  and $B$  so that for all $i=1,...,\ell$  we have $$e_{G_i}(A,B)\ge \frac{m_i}{2}-\sqrt{\ell m_i/2}.$$ 

Rautenbach and Szigeti [14] observed that even for $\ell =2$  we cannot guarantee that $e_{G_i}(A,B)\ge m_i/2$  for all $i$  . Indeed, let $G_1$  and $G_2$  be two edge-disjoint cycles of length 5 on the same vertex set. (So $G_1\cup G_2=K_5$  .) They also proved that $f\left(m\right)\ge m/2-{\Delta }^3$  if $\Delta \left(G_i\right)\le \Delta$  for $i=1,2$  . (This answers the problem of Bollobás and Scott if $(\Delta (G_i){)}^3=o(m)$  for $i=1,2$  .) The following result for partitions of graphs into more than two parts shows that simultaneously for all graphs we can ensure that the number of crossing edges is almost as large as one would expect in a random partition (and almost the value one can ensure if one partitions only a single graph).

Theorem 2 Let $k\ge 2$  . Consider graphs $G_1,...,G_{\ell }$  on the same vertex set $V$  and suppose that $G_i$  has $m_i$  edges. Then there is a partition of $V$  into $k$  classes $V_1,...,V_k$  so that for all $i=1,...,\ell$  the number of edges spanned by the $k$  -partite subgraph of $G_i$  induced by $V_1,...,V_k$  is at least $$\frac{(k-1)m_i}{k}-\sqrt{2\ell m_i}.$$ 

In fact, if $\Delta \left(G_i\right)=o\left(m_i\right)$  for each $i$  , then we can strengthen the conclusion:

The next theorem shows that there is a partition of $V$  into $k$  classes where each of the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$  bipartite graphs spanned by two of the partition classes contains almost $2m_i/k^2$  edges for all $i=1,...,\ell$  simultaneously. Again, this is about the number of edges which one would expect in a random partition.

Theorem 3 Let $k\ge 2$  and $0<\varepsilon \le 1/\left(9{\ell }^2{k}^4\right)$  . Consider graphs $G_1,...,G_{\ell }$  on the same vertex set $V$  . Suppose that $G_i$  has $m_i$  edges and that $\Delta \left(G_i\right)\le \varepsilon m_i$  for all $i=1,...,\ell$  . Then there is a partition of $V$  into $k$  classes $V_1,...,V_k$  so that for all $i=1,...,\ell$  and for all $s,t$  with $1\le s<t\le k$  we have $$e_{G_i}(V_s,V_t)\ge \frac{2m_i}{k^2}-{\varepsilon }^{1/4}{m}_i$$  and $$e_{G_i}\left(V_s\right)\ge \frac{m_i}{k^2}-{\varepsilon }^{1/4}{m}_i.$$ 

Note that even for $\ell =1$  the condition that $\Delta \left(G_i\right)\le \varepsilon m_i$  cannot be omitted completely. For example, the result is obviously false if $G$  is a star. On the other hand, a result of Bollobás and Scott [5,Thm. 3.2] implies that in the case when the maximum degree of each $G_i$  is bounded by a constant $\Delta$  , the bound on $e_{G_i}(V_s,V_t)$  in Theorem  3 can be improved to $2m_i/k^2-C$  where $C=C(\ell ,\Delta )$  (and similarly for $e_{G_i}\left(V_s\right)$  ). Note that this implies that if $G$  has bounded maximum degree, then one can achieve a bounded error term in Theorems  1 and  2 as well.

The proofs of Theorems  1 – 3 can be derandomized to yield polynomial time algorithms which find the desired partitions (see Section  4 ).

2 An open problem

Consider an $r$  -uniform hypergraph $\mathcal{\mathscr{H}}$  with $m$  hyperedges. It is easy to see that there is a partition $V_1,...,V_r$  of the vertex set of $\mathcal{\mathscr{H}}$  such that at least $r!m/r^r$  hyperedges of $\mathcal{\mathscr{H}}$  meet every $V_i$  (in other words, each $r$  -uniform hypergraph contains an $r$  -partite subhypergraph with at least $r!m/r^r$  hyperedges).

To verify this, consider the expected number of hyperedges which meet every $V_i$  in a random partition of the vertices. We believe that one does not loose much if one considers several hypergraphs simultaneously:

Conjecture 4 Suppose that ${\mathcal{\mathscr{H}}}_1,...,{\mathcal{\mathscr{H}}}_{\ell }$  are $r$  -uniform hypergraphs on the same vertex set $V$  such that ${\mathcal{\mathscr{H}}}_i$  has $m_i$  hyperedges. Then there exists a partition of $V$  into $r$  classes $V_1,...,V_r$  such that for all $i=1,...,\ell$  at least $r!m_i/r^r-o\left(m_i\right)$  hyperedges of ${\mathcal{\mathscr{H}}}_i$  meet each of the classes $V_1,...,V_r$  .

Given an $r$  -uniform hypergraph $\mathcal{\mathscr{H}}$  and distinct vertices $x,y\in \mathcal{\mathscr{H}}$  , denote by $N_{\mathcal{\mathscr{H}}}(x,y)$  the number of hyperedges which contain both $x$  and $y$  . Let ${\Delta }_2(\mathcal{\mathscr{H}})$  denote the maximum of $\left|N_{\mathcal{\mathscr{H}}}\right(x,y\left)\right|$  over all pairs $x\ne y$  . One can adapt our proof of Theorem  3 to show that Conjecture  4 holds in the case when ${\Delta }_2\left({\mathcal{\mathscr{H}}}_i\right)=o\left(m_i\right)$  for each $i$  . We omit the details.

3 Proofs

The proofs all proceed by considering a random partition and analyzing this using the second moment method.

Lemma 5 Let $c\in \mathbb{R}$  with $c>1/2$  . Suppose that $G$  is a graph with $m$  edges whose vertex set is $V$  . Consider a random bipartition of $V$  into two classes $A$  and $B$  which is obtained by including each $v\in V$  into $A$  with probability $1/2$  independently of all other vertices in $V$  . Then with probability at least $1-1/\left(2c\right)$  we have $$e_G(A,B)\ge \frac{m}{2}-\sqrt{cm/2}.$$ 

If we apply the above result with $c=\ell$  (say) to the graphs in Theorem  1 , the failure probability for each of them is less than $1/(2\ell )$  . Summing up all these failure probabilities immediately implies Theorem  1 .

Proof of Lemma  5 . For every edge $e$  of the graph $G$  , define an indicator variable $X_e$  as follows: if one endvertex of $e$  is in $A$  and the other one is in $B$  , then let $X_e:=1$  , otherwise let $X_e:=0$  . Clearly, $\mathbb{P}[X_e=1]=1/2$  . Also, for $e,e^{\prime }\in E\left(G\right)$  with $e\ne e^{\prime }$  , we have $$\mathbb{E}[X_e\cdot X_{e^{\prime }}]=\mathbb{P}[X_e=1,X_{e^{\prime }}=1]=\frac{1}{2}\mathbb{P}[X_e=1|X_{e^{\prime }}=1]=\frac{1}{4}.$$  Note that the final equality holds regardless of whether $e$  and $e^{\prime }$  have an endvertex in common or not. Now let $X:={\sum }_{e\in E\left(G\right)}{X}_e$  . Thus $X$  counts the number of edges between $A$  and $B$  and $\mathbb{E}X=m/2$  . Let ${\sum }_{\genfrac{}{}{0ex}{}{e,e^{\prime }\in E\left(G\right)}{e\ne e^{\prime }}}$  denote the sum over all ordered pairs $e,e^{\prime }$  of distinct edges in $G$  . Then, using the fact that $\mathbb{E}\left[X_e^2\right]=\mathbb{E}\left[X_e\right]$  , we have

$$\begin{array}{cc}\mathbb{E}\left[X^2\right]& ={\sum }_{e\in E\left(G\right)}\mathbb{E}\left[X_e\right]+{\sum }_{\genfrac{}{}{0ex}{}{e,e^{\prime }\in E\left(G\right)}{e\ne e^{\prime }}}\mathbb{E}[X_e\cdot X_{e^{\prime }}]\end{array}$$

$$\begin{array}{cc}& =\mathbb{E}\left[X\right]+{\sum }_{\genfrac{}{}{0ex}{}{e,e^{\prime }\in E\left(G\right)}{e\ne e^{\prime }}}\frac{1}{4}=\frac{m}{2}+\frac{m(m-1)}{4}=\frac{m(m+1)}{4}.\end{array}$$

This in turn implies that the variance of $X$  satisfies $VarX=\mathbb{E}\left[X^2\right]-(\mathbb{E}X{)}^2=m/4$  . The result now follows from a straightforward application of Chebyshev's inequality:

$$\mathbb{P}[X\le m/2-\sqrt{cm/2}]\le \mathbb{P}\left[\right|X-\mathbb{E}X|\ge \sqrt{cm/2}]\le \frac{2VarX}{cm}=\frac{1}{2c}.$$  $\square$  Proof of Theorem  2 . As in Lemma  5 , we first consider a single graph $G$  with $m$  edges and vertex set $V$  . Consider a random partition of $V$  into $k$  disjoint sets $V_j$  which is obtained by including each $v\in V$  into $V_j$  with probability $1/k$  independently of all other vertices. Let $X_e:=0$  if the edge $e$  has both its endpoints in some $V_j$  and let $X_e:=1$  otherwise. So $\mathbb{P}[X_e=1]=(k-1)/k$  .

Also, it is easy to check that $\mathbb{E}[X_e\cdot X_{e^{\prime }}]=(k-1{)}^2/k^2$  . Again, this holds regardless of whether $e$  and $e^{\prime }$  have an endvertex in common or not. Let $X$  denote the number of edges whose endvertices lie in different vertex classes.

Thus $\mathbb{E}X=\frac{k-1}{k}m$  and

$$\begin{array}{cc}\mathbb{E}\left[X^2\right]& ={\sum }_{e\in E\left(G\right)}\mathbb{E}\left[X_e\right]+{\sum }_{\genfrac{}{}{0ex}{}{e,e^{\prime }\in E\left(G\right)}{e\ne e^{\prime }}}\mathbb{E}[X_e\cdot X_{e^{\prime }}]\end{array}$$

$$\begin{array}{cc}& =\frac{k-1}{k}m+m(m-1)\frac{(k-1{)}^2}{k^2}\le m+(\mathbb{E}[X]{)}^2.\end{array}$$

Therefore $VarX\le m$  and so Chebyshev's inequality implies that $$\mathbb{P}[X\le \frac{k-1}{k}m-\sqrt{2\ell m}]\le \mathbb{P}\left[\right|X-\mathbb{E}X|\ge \sqrt{2\ell m}]\le \frac{VarX}{2\ell m}\le \frac{1}{2\ell }.$$  Theorem  2 now follows by summing up this bound on the failure probability for each of the graphs $G_i$  . $\square$  Proof of Theorem  3 . Let $\varepsilon$  be as in the statement of the theorem. As in the previous proof, we first consider a single graph $G$  , this time with $m$  edges and maximum degree $\Delta \le \varepsilon m$  . Consider a random partition of $V:=V\left(G\right)$  into $k$  disjoint sets $V_j$  which is obtained by including each vertex $v\in V$  into $V_j$  with probability $1/k$  independently of all other vertices. Fix some $s$  and $t$  with $1\le s<t\le k$  . This time let $X_e:=1$  if one endvertex of $e$  is contained in $X_s$  and the other in $X_t$  . Put $X_e:=0$  otherwise. So $\mathbb{P}[X_e=1]=2/k^2=:\alpha$  .

Now the value of $\mathbb{E}[X_e\cdot X_{e^{\prime }}]$  depends on whether $e$  and $e^{\prime }$  have an endvertex in common or not: If they do have an endvertex in common, we will use the trivial bound $\mathbb{E}[X_e\cdot X_{e^{\prime }}]\le 1<1+{\alpha }^2$  . Note that the number of ordered pairs $e,e^{\prime }$  of distinct edges for which this can happen is trivially at most $2\Delta m$  . If $e$  and $e^{\prime }$  have no vertex in common, then it is easy to see that $$\mathbb{E}[X_e\cdot X_{e^{\prime }}]=\mathbb{P}[X_e=1]\mathbb{P}[X_{e^{\prime }}=1]={\alpha }^2.$$  Let $X:={\sum }_{e\in E\left(G\right)}{X}_e$  . Thus $\mathbb{E}\left[X\right]=2m/k^2=\alpha m$  . Moreover

$$\begin{array}{cc}\mathbb{E}\left[X^2\right]& ={\sum }_{e\in E\left(G\right)}\mathbb{E}\left[X_e\right]+{\sum }_{\genfrac{}{}{0ex}{}{e,e^{\prime }\in E\left(G\right)}{e\ne e^{\prime }}}\mathbb{E}[X_e\cdot X_{e^{\prime }}]\end{array}$$

$$\begin{array}{cc}& <\mathbb{E}\left[X\right]+2\Delta m+{\sum }_{\genfrac{}{}{0ex}{}{e,e^{\prime }\in E\left(G\right)}{e\ne e^{\prime }}}{\alpha }^2\end{array}$$

$$\begin{array}{cc}& \le \alpha m+2\Delta m+{\alpha }^2{m}^2\le 3\Delta m+(\mathbb{E}[X]{)}^2.\end{array}$$

Thus $VarX\le 3\Delta m\le 3\varepsilon m^2$  . So we can conclude that $$\mathbb{P}[X\le \alpha m-{\varepsilon }^{1/4}m]\le \mathbb{P}\left[\right|X-\mathbb{E}X|\ge {\varepsilon }^{1/4}m]\le \frac{VarX}{\sqrt{\varepsilon }{m}^2}\le 3\sqrt{\varepsilon }\le \frac{1}{\ell k^2}.$$  In exactly the same way one can show that $\mathbb{P}\left[e_G\right(V_s)\le m/k^2-{\varepsilon }^{1/4}m]\le 1/(\ell k^2)$  . (This time $\alpha :=1/k^2$  .) Now sum up these failure probabilities for all the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$  pairs $s,t$  and all the $k$  values of $s$  to see that the probability that a random partition does not have the required properties for $G$  is at most $3/(4\ell )$  .

Again, Theorem  3 follows from summing up this probability for all $G_i$  . $\square$  We remark that at the expense of increasing the error terms the partition classes in Theorems  1 – 3 can be chosen to have almost equal sizes. Indeed, Chernoff 's inequality implies that in a random partition of the vertex set as considered in the proofs with high probability the vertex classes have almost equal sizes.

4 Algorithmic aspects

Papadimitriou and Yannakakis [10] showed that the Max-Cut problem is APX-complete. On the other hand, as mentioned in the introduction, the obvious greedy algorithm always guarantees a cut whose size is at least $m/2$  .

Moreover, the proofs described in the previous section can be derandomized to yield polynomial algorithms which construct partitions satisfying the bounds in Theorems  1 – 3 . As the derandomization argument is similar for all three results, we only only describe it for Theorem  1 . More background information on derandomization can be found for instance in the books [1, 9] and in Fundia [8] (in particular, the framework described in the latter applies to our situation).

For simplicity, we consider Theorem  1 only for $\ell =2$  , i.e. in the case of two graphs.

So let $G_1$  and $G_2$  be two graphs whose vertex set is $V$  with $e\left(G_i\right)=m_i$  .

Consider a random partition of $V$  into sets $A$  and $B$  as described in the proof of Theorem  1 (cf. Lemma  5 ). For $i=1,2$  define random variables $X_i:=e_{G_i}(A,B)$  and put ${\mu }_i:=m_i/2=\mathbb{E}\left[X_i\right]$  . Set $$Z_i:=\frac{{\mu }_i^2-2{\mu }_i{X}_i+X_i^2}{m_i}$$  for $i=1,2$  and $Z:=Z_1+Z_2$  . The proof of Theorem  1 shows that for each $i$  $$\mathbb{P}[X_i<{\mu }_i-\sqrt{m_i}]\le \frac{Var{X}_i}{m_i}<1/2.$$  But $\mathbb{E}\left[Z_i\right]=Var{X}_i/m_i$  and so $\mathbb{E}\left[Z\right]=\mathbb{E}\left[Z_1\right]+\mathbb{E}\left[Z_2\right]<1$  . Let $v_1,...,v_n$  be an enumeration of the vertices in $V$  . Let $A_i$  denote the event that the vertex $v_i$  is contained in $A$  . Then $$1>\mathbb{E}\left[Z\right]=(\mathbb{E}[Z\left|A_1\right]+\mathbb{E}\left[Z\right|A_1^c\left]\right)/2\ge min\{\mathbb{E}[Z\left|A_1\right],\mathbb{E}\left[Z\right|A_1^c\left]\right\}.$$  Thus at least one of $\mathbb{E}\left[Z\right|A_1]$  , $\mathbb{E}\left[Z\right|A_1^c]$  has to be less than 1. Let $C_1\in \{A_1,A_1^c\}$  be such that $\mathbb{E}\left[Z\right|C_1]<1$  . Note that both $\mathbb{E}\left[Z\right|A_1]$  and $\mathbb{E}\left[Z\right|A_1^c]$  can be computed in polynomial time and so also $C_1$  can be determined in polynomial time. Now $$1>\mathbb{E}\left[Z\right|C_1]=(\mathbb{E}\left[Z\right|C_1\cap A_2]+\mathbb{E}[Z|C_1\cap A_2^c])/2.$$  So similarly as before there exists $C_2\in \{A_2,A_2^c\}$  such that $\mathbb{E}\left[Z\right|C_1\cap C_2]<1$  and $C_2$  can be determined in polynomial time. We continue in this fashion until we have obtained events $C_k\in \{A_k,A_k^c\}$  for all $k=1,...,n$  such that $$\mathbb{E}\left[Z\right|C_1\cap \cdot \cdot \cdot \cap C_n]<1.$$  The proof of Chebyshev's inequality shows that for each $i=1,2$  and for any event $U$  which has positive probability, we have $$\mathbb{P}[X_i<{\mu }_i-\sqrt{m_i}|U]\le \frac{{\mu }_i^2-2{\mu }_i\mathbb{E}\left[X_i\right|U]+\mathbb{E}[X_i^2\left|U\right]}{m_i}=\mathbb{E}[Z_i\left|U\right]$$  (the above also follows from Corollary 4 in [8] ). Taking $U:=C_1\cap \cdot \cdot \cdot \cap C_n$  this implies that

$$\begin{array}{cc}{\sum }_{i=1,2}\mathbb{P}[X_i<{\mu }_i-\sqrt{m_i}|U]\le {\sum }_{i=1,2}\mathbb{E}[Z_i\left|U\right]=\mathbb{E}\left[Z\right|U]<1.& \end{array}$$

(1)

But $U:=C_1\cap \cdot \cdot \cdot \cap C_n$  means that for each vertex $v_k\in V$  we have decided whether $v_k\in A$  or $v_k\in B$  . So the left hand side of ( 1 ) is either $0$  or $1$  , i.e. it has to be 0. This means that the unique partition corresponding to $C_1\cap \cdot \cdot \cdot \cap C_n$  is as desired in Theorem  1 . Since each $C_k$  can be determined in polynomial time this gives us a polynomial algorithm.

Acknowledgement We are grateful to Dieter Rautenbach for telling us about the problem.

References

1. N. Alon and J. Spencer, The Probabilistic Method (2nd edition), Wiley-Interscience 2000.
2. B. Bollobás and A.D. Scott, Judicious partitions of graphs, Periodica Math. Hungar. 26 (1993), 127–139.
3. B. Bollobás and A.D. Scott, Exact bounds for judicious partitions, Combinatorica 19 (1999), 473–486.
4. B. Bollobás and A.D. Scott, Problems and results on judicious partitions, Random Struct. Alg. 21 (2002), 414–430.
5. B. Bollobás and A.D. Scott, Judicious partitions of bounded-degree graphs, J. Graph Theory 46 (2004) 131–143.
6. C.S. Edwards, Some extremal properties of bipartite subgraphs, Canadian J. Math. 25 (1973), 475–485.
7. C.S. Edwards, An improved lower bound on the number of edges in a largest bipartite subgraph, in Proc. 2nd Czech. Symposium on Graph Theory, Prague 1975, 167–181.
8. A.D. Fundia, Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs, Random Struct. Alg. 8 (1996), 131–147.
9. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
10. C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43 (1991), 425–440.
11. T.D. Porter, On a bottleneck conjecture of Erdős, Combinatorica 12 (1992), 317–321.
12. T.D. Porter, Graph partitions, J. Combin. Math. Combin. Comp. 15 (1994), 111-118.
13. T.D. Porter, Minimal partitions of a graph, Ars Combinatorica 53 (1999), 181–186.
14. D. Rautenbach and Z. Szigeti, Simultaneous large cuts, manuscript 2004.

Daniela Kühn & Deryk Osthus School of Mathematics Birmingham University Edgbaston Birmingham B15 2TT UK E-mail addresses: {kuehn,osthus}@maths.bham.ac.uk