A NOTE ON JUDICIOUS BISECTIONS OF GRAPHS

Abstract

Let G be a graph with m edges, minimum degree $\delta $ and containing no cycle of length 4. Answering a question of Bollobás and Scott, Fan et al. [‘Bisections of graphs without short cycles’, Combinatorics, Probability and Computing 27(1) (2018), 44–59] showed that if (i) G is $2$-connected, or (ii) $\delta \ge 3$, or (iii) $\delta \ge 2$ and the girth of G is at least 5, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$, where $e(V_i)$ denotes the number of edges of G with both ends in $V_i$. Let $s\ge 2$ be an integer. In this note, we prove that if $\delta \ge 2s-1$ and G contains no $K_{2,s}$ as a subgraph, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$.

1. Introduction

Many classical partitioning problems in combinatorics seek a partition of a combinatorial object (for example, a graph, directed graph, hypergraph and so on) which optimises a single quantity. For example, the well-known max-cut problem asks for a bipartition $(V_1, V_2)$ of G which maximises the size of the cut $e(V_1,V_2)$ , the number of edges with one end in $V_1$ and the other in $V_2$ . It is easy to see that every graph with m edges has a cut of size at least $m/2$ . Edwards [5, 6] proved the best possible result that the max-cut of graphs with m edges is at least

(1.1) $$ \begin{align} \frac{m}{2}+\frac{1}{4}\bigg(\sqrt{2m+\frac{1}{4}}-\frac{1}{2}\bigg). \end{align} $$

Judicious partitioning problems ask for partitions of graphs that maximise or minimise several quantities simultaneously. Bollobás and Scott initiated a systematic study of such problems. It was proved in [2] that every graph with m edges has a bipartition satisfying (1.1) in which each vertex class contains at most

$$ \begin{align*}\frac{m}{4}+\sqrt{\frac{m}{32}+\frac{1}{256}}-\frac{1}{16}\end{align*} $$

edges. The extremal graphs are the complete graphs of odd order. For more such results and problems, we refer the reader to [3, 11, 12].

In this paper, we focus on bisections of graphs. Let G be a graph. A bisection of G is a bipartition $(V_1, V_2)$ of its vertex set $V(G)$ with $||V_1|-|V_2||\leq 1$ , and judicious bisection problems usually ask for bisections in which both parts induce few edges. Considering $K_{1,n-1}$ shows that we cannot in general demand a bisection with fewer than $\lfloor m/2\rfloor $ edges in each part. To circumvent this issue, a natural idea is to add a minimum degree condition for the graphs under consideration. Specifically, Bollobás and Scott conjectured in [3] that every graph with m edges and minimum degree at least 2 admits a bisection such that the number of edges in each part is at most $m/3$ . This problem was studied by several authors [4, 9, 13, 14], and the conjecture was finally confirmed by Xu and Yu [15].

In [9], Lee et al. studied how the bound changes as the minimum degree condition imposed on the graph grows. They proved that if $\delta $ is even, then every graph G with m edges and minimum degree $\delta $ admits a bisection such that each part induces at most ${({(\delta +2)}/{4(\delta +1)}+o(1)) m}$ edges. One of their main contributions for analysing bisections is the introduction of the notion of tight component in a graph. Let T be a connected graph. We say that T is $tight$ if it has the following properties:

1. (i) for every vertex $v\in V(T)$ , $T-v$ contains a perfect matching; and

2. (ii) for every vertex $v\in V(T)$ and every perfect matching M of $T-v$ , no edge in M has exactly one end adjacent to v.

If G is disconnected, the components which are tight are called tight components of G. Answering a question of Lee et al. [9], Lu et al. [10] gave the following characterisation of tight graphs.

Lemma 1.1 (Lu et al. [10]).

A connected graph G is tight if and only if every block of G is an odd clique.

Remark 1.2. Each tight graph has an odd number of vertices and the degree of each vertex is even. Obviously, $K_1$ is tight and we call it trivial.

Note that by taking a random bisection $(V_1, V_2)$ , one expects $m/4$ edges in each part. However, $e(V_1)$ and $e(V_1)$ are dependent and the extremal graphs for the result of Lee et al. [9] indicate that, in general, both $V_1$ and $V_2$ cannot simultaneously induce at most $(1/4+o(1))m$ edges. This leads to the following problem, which was posed by Bollobás and Scott [3].

Problem 1.3. Under what conditions can we guarantee a bisection $(V_1, V_2)$ of a graph G of m edges such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$ ?

This problem was studied by Fan et al. [7]. They proved the following result. Let G be a graph with m edges, minimum degree $\delta $ and containing no cycle of length 4. If (i) G is 2-connected, or (ii) $\delta \geq 3$ , or (iii) $\delta \geq 2$ and the girth of G is at least 5, then G admits a bisection $(V_1, V_2)$ such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$ . For a set $\mathcal {H}$ of graphs, we say G is $\mathcal {H}$ -free if G contains no member of $\mathcal {H}$ as a subgraph. If $\mathcal {H}=\{H\}$ , we simply write H-free instead of $\mathcal {H}$ -free. In [8], Hou and Wu improved property (iii) by considering $\{K_{3}, K_{\delta , l}\}$ -free graphs with minimum degree $\delta $ . In this note, we improve property (ii).

Theorem 1.4. For any fixed integer $s\ge 2$ , if G is $K_{2,s}$ -free and $\delta (G)\ge 2s-1$ , then G admits a bisection $(V_1, V_2)$ such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$ .

We end this section with some notation and definitions. All graphs considered here are finite, undirected, and have no loops and no parallel edges. Let G be a graph with edge set $E(G)$ and vertex set $V(G)$ . The set of neighbours of a vertex $v\in V(G)$ is denoted by $N_G(v)$ and $d(v)= |N_G(v)|$ is the degree of v in G. Let $\Delta (G)$ and $\delta (G)$ be the maximum and minimum degree of G, respectively. For disjoint subsets $X, Y$ of $V(G)$ , we denote by $E(X)$ the set of edges of G with both ends in X, and by $E(X,Y)$ the set of edges of G with one end in X and the other end in Y. The cardinalities of $E(X)$ and $E(X,Y)$ are $e(X)$ and $e(X,Y)$ , respectively. When $X=\{v\}$ , we write $e(v,Y)$ instead of $e(\{v\},Y)$ for simplicity. Let $N_Y(v)$ denote the set of neighbours of v in Y and $d_Y(v)=|N_Y(v)|$ the Y-degree of v in G. Clearly, $d_Y(v)=e(v,Y)$ .

2. Proof of Theorem 1.4

In this section, we give a proof of Theorem 1.4. Let G be a $K_{2,s}$ -free graph with n vertices, m edges and $\delta (G)\ge 2s-1$ . It suffices to show that for any small real $\varepsilon> 0$ , there exists an integer $n_0> 0$ such that if $n\ge n_0$ , then G has a bisection $(V_1,V_2)$ such that $e(V_i)\le (1/4+\varepsilon )m$ for $i = 1,2$ . Throughout the proof, we tacitly assume that the number of vertices n is large enough. Since $\delta (G)\ge 2s-1$ , we have $m\ge (2s-1)n/2$ , which indicates that m is also large enough.

As a starting point for Problem 1.3, Bollobás and Scott [3] (see also [11]) suggested that one of $\Delta (G)=o(n)$ or $\delta (G)\rightarrow \infty $ might suffice. This was confirmed independently by several authors [9, 14, 16]. We use the following result of Lee et al. [9].

Lemma 2.1 (Lee et al. [9]).

Let $\varepsilon $ be a fixed positive constant and let G be a graph with n vertices and m edges such that (i) $m\ge n/\varepsilon ^{2}$ or (ii) $\Delta (G)\le \varepsilon ^2 n/2$ . If n is sufficiently large, then G admits a bisection $(V_1,V_2)$ such that $\max \{e(V_1),e(V_2)\}\le (1/4+ \varepsilon )m$ .

It follows from Lemma 2.1 that to prove Theorem 1.4, we need only consider sparse graphs with large maximum degree. More formally, we may assume that

$$ \begin{align*}m< \frac n {\varepsilon^{2}} \quad\text{and}\quad \Delta(G)> \frac{\varepsilon^2 n}2.\end{align*} $$

In fact, for sparse graphs with small maximum degree, Lee et al. [9] gave the following strengthening of Lemma 2.1. The key benefit is its parametrisation in terms of the number of tight components.

Lemma 2.2 (Lee et al. [9]).

Given any real constants $C, \varepsilon> 0$ , there exist $\gamma , n_0>0$ for which the following holds. Every graph G with $n\ge n_0$ vertices, $m\le Cn$ edges, maximum degree at most $\gamma n$ and $\tau $ tight components admits a bisection $(V_1,V_2)$ such that $\max \{e(V_1),e(V_2)\}\le m/4 -(n-\tau )/8 + \varepsilon n$ .

Combining Lemmas 2.1 and 2.2, we see that the main obstacle for Problem 1.3 is the maximum degree condition. To work around this, we use the natural idea of Lee et al. [9], which was first used by Bollobás and Scott [1] and then by several others. First, partition $V(G)$ into A and $\overline {A}$ , where A consists of certain high degree vertices; then partition A into $A_1$ and $A_2$ with certain properties and partition $\overline {A}$ by Lemma 2.2; finally appropriately combine the vertex subsets of the two partitions. This leads to the following result.

Lemma 2.3 (Lee et al. [9]).

Given any real constants $C, \varepsilon> 0$ , there exist $\gamma ,n_0> 0$ for which the following holds. Let G be a given graph with $n\ge n_0$ vertices and at most $Cn$ edges, and let $A\subseteq V(G)$ be a set of $\leq \gamma n$ vertices which has already been partitioned into $A_1$ and $A_2$ . Let $\overline {A} =V(G)\setminus A$ , and suppose that every vertex in $\overline {A}$ has degree at most $\gamma n$ (with respect to the full G). Let $\tau $ be the number of tight components in $G[\overline {A}]$ . Then there is a bisection $(V_1,V_2)$ with $A_1\subseteq V_1$ and $A_2\subseteq V_2$ , such that for $i = 1,2$ ,

$$ \begin{align*}e(V_i )\le e(A_i )+\frac{e(A_i,\overline{A})}2+\frac{e(\overline{A})}4-\frac{n-\tau}8+\varepsilon n.\end{align*} $$

Now we use Lemma 2.3 and some additional ideas to prove Theorem 1.4. Let

$$ \begin{align*}A = \{v \in V(G) : d_G (v)\ge n^{3/4} \} \quad\text{and}\quad \overline{A} =V(G)\setminus A.\end{align*} $$

Suppose $A\neq \emptyset $ , otherwise we are already done by Lemma 2.2. Note that

$$ \begin{align*}2m =\sum_{v\in V(G)}d(v)\ge \sum_{v\in A}d(v)\ge |A|n^{3/4},\end{align*} $$

which, together with $m< n/\varepsilon ^{2}$ , yields

(2.1) $$ \begin{align} |A|< \frac{2 n^{1/4}}{\varepsilon^{2}}, \end{align} $$

and hence

$$ \begin{align*}e(A)\le{{|A|}\choose{2}}= O(n^{1/2}).\end{align*} $$

Partition A into $(A_1,A_2)$ such that $e(A_1 ,\overline {A})\ge e(A_2 ,\overline {A})$ and, subject to this,

(2.2) $$ \begin{align} \theta: = e(A_1 ,\overline{A})-e(A_2 ,\overline{A}) \end{align} $$

is minimised. Since $e(A_1,\overline {A})+e(A_2,\overline {A})=e(A,\overline {A})$ , from (2.2), we see that

$$ \begin{align*}e(A_2 ,\overline{A})\le e(A_1 ,\overline{A}) = \frac{e(A,\overline{A})+\theta}2.\end{align*} $$

By (2.1), $|A| =O(n^{1/4})$ . For each $v\in \overline {A}$ , we have $d_G (v)< n^{3/4}$ . Since n is sufficiently large (by choosing $n_0$ large), it follows from Lemma 2.3 (with $C=1/\varepsilon ^2$ ) that G has a bisection $(V_1,V_2)$ with $A_1\subseteq V_1$ and $A_2\subseteq V_2$ , such that for $i = 1,2$ ,

$$ \begin{align*} e(V_i )\le e(A_i )+\frac{e(A,\overline{A})+\theta}4+\frac{e(\overline{A})}4-\frac{n-\tau}8+\varepsilon n \le\frac14\bigg(\theta+\frac{\tau}2-\frac n2\bigg)+\frac{m}{4}+\frac{3\varepsilon}{4} m, \end{align*} $$

where $\tau $ is the number of tight components in $G[\overline {A}]$ . The last inequality holds as ${e(A_i ) = O(n^{1/2} )}$ and $m\ge (2s-1)n/2$ . Then, to prove $e(V_i)\leq (1/4+\varepsilon )m$ , it suffices to show

(2.3) $$ \begin{align} \theta+\frac \tau 2\leq\frac {n} 2+\varepsilon m. \end{align} $$

Now we prove (2.3) through carefully bounding $\theta $ and $\tau $ . Consider the partition $(T,K)$ of $\overline {A}$ , where T consists of all vertices of the tight components in $G[\overline {A}]$ and $K:=\overline {A}\setminus T$ . Let $T_0$ be the set of isolated vertices in $G[\overline {A}]$ and denote $T_1=T\setminus T_0$ . By Lemma 1.1, each component of $G[T_1]$ has at least three vertices. Therefore,

$$ \begin{align*}\tau\le |T_0|+\frac{|T_1|}{3}.\end{align*} $$

Let

$$ \begin{align*}S = \{v\in \overline{A }: d_A(v)\ge2\}.\end{align*} $$

Then $T_0\subset S$ since $\delta (G)\ge 2s-1\ge 3$ . To give a reasonable bound for $\tau $ , we bound $|S|$ by using the condition that G is $K_{2,s}$ -free.

Claim 1. $|S|=O(n^{1/2})$ and thus $\tau \le \tfrac 13|T_1|+O(n^{1/2})$ .

Since G is $K_{2,s}$ -free, any pair of vertices in A has at most $s-1$ common neighbours in G (and thus in S). Through (double) counting the number of $K_{1,2}$ with the 2-degree vertex in S and the two pendent vertices in A, we have

$$ \begin{align*}(s-1){{|A|}\choose{2}}\ge\sum_{v\in S}{{d_A(v)}\choose{2}}\ge |S|.\end{align*} $$

Since $|A|= O(n^{1/4})$ by (2.1), we see that $|S| = O(n^{1/2})$ . This proves Claim 1.

For $s\ge 3$ , we give a better bound for $\tau $ .

Claim 2. For $s\ge 3$ , $\tau \le |S|=O(n^{1/2})$ .

Clearly, each vertex in S falls in at most one tight component in $G[\overline {A}]$ . Now we show that each tight component in $G[\overline {A}]$ has a vertex in S, which implies that $\tau \le |S|= O(n^{1/2})$ . Suppose in contrast that $T'$ is a tight component in $G[\overline {A}]$ which does not contain a vertex of S. This means each vertex of $T'$ has at most one neighbour in A. Considering one of the endblocks of $T'$ , by Lemma 1.1, it is an odd clique with minimum degree at least $2s-2$ , and hence contains a $K_{2s-1}$ . Since $s\ge 3$ , it also contains a $K_{2,s}$ , which gives a contradiction. This proves Claim 2.

Now we bound $\theta $ . In the partition $(A_1,A_2)$ of A, since $A\neq \emptyset $ , we have $A_1\neq \emptyset $ .

Claim 3. For any $v\in A_1$ , we have $d_{\overline {A}}(v)\ge \theta $ .

For otherwise, through moving v from $A_1$ to $A_2$ ,

$$ \begin{align*} \theta'&=e(A_1\setminus \{v\},\overline{A})-e(A_2\cup \{v\},\overline{A}) \\ &=e(A_1,\overline{A})-d_{\overline{A}}(v)-e(A_2,\overline{A})-d_{\overline{A}}(v) \\ &=\theta-2d_{\overline{A}}(v) \\ &>-\theta. \end{align*} $$

However, $\theta '=\theta -2d_{\overline {A}}(v)<\theta $ . This implies that $|\theta '|<\theta $ , which is a contradiction to the optimality of the partition $(A_1,A_2)$ . This proves Claim 3.

For some fixed $v_0\in A_1$ , by Claim 3, $\theta \le d_{\overline {A}}(v_0)$ . We give a bound for $d_{\overline {A}}(v_0)$ .

Claim 4. $d_{\overline {A}}(v_0)\le \tfrac 12|\overline {A}|+|S|.$ Moreover, if $s=2$ , then $d_{\overline {A}}(v_0)\le |T_0|+\tfrac 13|T_1|+\tfrac 12|K|+|S|$ .

Denote $X=N_{\overline {A}}(v_0)\setminus S$ and $Y=\overline {A}\setminus X$ . We show that

$$ \begin{align*}|X|\le |Y|.\end{align*} $$

Then the claim follows immediately.

For any connected component B of $G[\overline {A}]$ , no matter whether it belongs to $G[T]$ or $G[K]$ , let $B\cap X=C$ and $B\cap Y=D$ . To prove $|X|\le |Y|$ , it suffices to show $|C|\le |D|.$

Summing up the degrees of all vertices in C,

$$ \begin{align*}\sum_{v\in C}{d(v)}=2e(C)+e(C,A)+e(C,D).\end{align*} $$

Since G contains no $K_{2,s}$ , the maximum degree of $G[C]$ is no more than $s-1$ , which implies

$$ \begin{align*}e(C)\le \frac{(s-1)|C|}{2}.\end{align*} $$

Note that $(C\cap S)\subset (X\cap S)=\emptyset $ , so that $e(C,A)\le |C|$ . Therefore, on the one hand,

$$ \begin{align*} e(C,D) & = \sum_{v\in C}{d(v)}-2e(C)-e(C,A) \\ & \ge (2s-1)|C|-(s-1)|C|-|C| \\ & \ge (s-1)|C|. \end{align*} $$

On the other hand, for any vertex y of D, if $d_C(y)\ge s$ , then a $K_{2,s}$ can be found easily in $G[{v_0\cup y\cup N_C(y)}]$ . Hence, y has at most $s-1$ neighbours in C, which implies

$$ \begin{align*}e(C,D)\le (s-1)|D|.\end{align*} $$

We conclude that

$$ \begin{align*}|C|\le |D|.\end{align*} $$

For the second inequality, by Lemma 1.1, if G is $K_{2,2}$ -free, each block of a tight component in $G[\overline {A}]$ has three vertices. Therefore, $v_0$ has at most one neighbour in each such block. It is easy to see $d_{T}(v_0)\le |T_0|+\tfrac 13|T_1|$ . Through considering nontight components B (restrict B in $G[K]$ ), our proof above implies that ${d_{K}(v_0)\le \tfrac 12|K|+|S|}$ . Thus, $d_{\overline {A}}(v_0)=d_{T}(v_0)+d_{K}(v_0)\le |T_0|+\tfrac 13|T_1|+\tfrac 12|K|+|S|$ when $s=2$ . This proves Claim 4.

When $s\ge 3$ , combining Claims 2–4,

$$ \begin{align*}\theta+\frac {\tau}2\le \frac{|\overline{A}|}2+|S|+\frac{|S|}2\le \frac n2+\varepsilon m.\end{align*} $$

When $s=2$ , by Claims 1 and 3 and the second inequality of Claim 4,

$$ \begin{align*}\theta+\frac {\tau}2\le |T_0|+\frac{|T_1|}{3}+\frac{|K|}2+|S|+\frac{|T_1|/3+O(n^{1/2})}2\le \frac n2+\varepsilon m,\end{align*} $$

where the final inequality follows as $T_0\subset S$ . This completes the proof of (2.3).