1 Introduction↩︎

For many graph theory problems, there are some classes of graphs in which it is easy to obtain an optimum solution. As such, there are many situations in which we may want to know how far a graph is from one of these ‘easy’ classes, and hence there are numerous ‘width’ parameters to define this distance. Some well-established parameters include tree-width, path-width, and clique-width, each a measure of how structurally distant a graph is from being a tree, path, or clique, respectively.

The usefulness of width parameters cannot be understated, as they allow us to describe the structure of a graph, characterize its complexity with respect to computational problems, and choose or design suitable algorithms to run on it (see, for example, [1]). Choosing the right parameter depends on the problem and all parameters have limitations. Tree-width, for example, is bounded in a smaller range of classes, requiring the graph to be sparse, but can yield more efficient algorithms while clique-width (or, similarly, rank-width) is more general, covering dense families of graphs on top of all those with bounded tree-width.

Recently, twin-width has emerged as being in some sense among the most general of the width parameters. It was introduced by Bonnet, Kim, Thomassé, and Watrigant in [2] as a generalization of an earlier permutations parameter from Guillemot and Marx [3]. Twin-width is more powerful than both tree-width and clique-width (see Figure 2a in [4] for a detailed picture of the comparability of common width parameters) since all graphs with bounded tree-width or clique-width also have bounded twin-width. Unlike tree-width and clique-width which are best suited to sparse or dense graphs respectively, graphs of bounded twin-width seem to “stop at the right place" between the two realms in terms of balancing efficiency with generality [5], so twin-width is useful for a broader range of graphs.

Informally, twin-width measures how structurally different a family of graphs is from the class of cographs (see Section 2 for a formal definition). Cographs, the class of graphs which can be built from a single-vertex graph by repeatedly taking complements and disjoint unions, have nice computational properties and naturally arise in many areas, including recognition algorithms, parallel computing, and biology [6]. Quantifying the structural distance between a graph and this class is therefore both practical and natural. However, being a relatively new parameter, much is still unknown about its behaviour, especially in large hereditary classes.

Twin-width is particularly well-suited to problems related to induced subgraphs of graphs. For one, cographs are exactly the class of \(P_4\)-free graphs and are one of the more significant classes of hereditary graphs [7]. Twin-width is also closed under taking induced subgraphs and complements [2], which makes it a natural candidate for the study of hereditary graph classes in general. Bonnet, Geniet, Kim, Thomassé, and Watrigant initially conjectured that every small hereditary class has bounded twin-width [5]. This was later disproven in general [8], but is true of small hereditary classes of ordered graphs [9].

Bounded twin-width is closed under taking FO interpretations and transductions [2]. The original algorithmic application of twin-width is in first-order (FO) model-checking, which is FPT-solvable when twin-width is bounded [2]. In hereditary classes of ordered graphs, FO-model-checking is FPT-solvable if and only if the class has bounded twin-width [9], [10]. In fact, many algorithmic and structural questions have nice answers in classes of graphs with bounded twin-width, including enumeration [5], colouring [11], [12] and \(\chi\)-boundedness [13], and finding minimum or partial dominating sets [11], [14]. As mentioned, bounded twin-width encompasses many important graph classes, including graphs with bounded tree-width, bounded clique-width or rank-width, planar graphs, proper minor-closed graph classes, and proper subclasses of permutation graphs [2].

However, there are limitations to considering only families of graphs with bounded twin-width, as we will see. While graphs of twin-width zero or one can be recognized in linear time [15], little is known even about graphs of twin-width two or three, and deciding if a graph has twin-width four or five is already NP-complete [16]. Most notable to the work presented here, many natural classes of graphs do not have bounded twin-width at all. In fact, some graphs can have linear twin-width relative to the number of vertices, as evidenced by taking an Erdös-Rényi random graph or a conference graph [17], for example. Extending the latter, one can similarly show that each of the three classes of split, bipartite, and co-bipartite graphs have linear twin-width (see Appendix 6 for proof).

This raises a natural question of the relationship between twin-width and Vapnik-Chervonenkis (VC) dimension [18], a parameter measuring the complexity of vertex neighbourhoods (see Section 2 for a formal definition). A hereditary class of graphs has bounded VC-dimension if and only if it excludes a bipartite graph, a co-bipartite graph, and a split graph [19], [20]. Since all three classes of bipartite, co-bipartite, and split graphs can have linear twin-width (in the number of vertices), we know that a hereditary class of unbounded VC-dimension contains arbitrarily large graphs of linear twin-width.

In the opposite direction, Bonnet, Foucaud, Lehtilä, and Parreau [21] showed that bounded twin-width implies bounded VC-dimension by arguing about neighbourhood complexity and restrictions on the number of distinct neighbourhoods between fixed-size sets of vertices. For an \(n\)-vertex graph with twin-width at most \(d\), they obtain an essentially tight upper bound of \(2^{d+\log d+\Theta(1)}k\) on the VC-dimension.

However, it is known that graphs with bounded VC-dimension can have unbounded twin-width in general: Every bounded twin-width class \(\mathcal{C}\) is small in the sense that \(\mathcal{C}\) does not contain more than \(n!c^n\) graphs with \(n\) vertices, for some constant \(c\) [5]. The class of graphs with VC-dimension at most two contains the class of interval graphs [19] and these already have unbounded twin-width by the counting argument on the size of the class [5]. However, this argument provides little information with respect to precisely how large the twin-width can be for either of these classes. Can it be linear or can we do better? This question is the focus of the current work.

We provide separate answers for both bounded VC-dimension graphs and interval graphs, despite the former containing the latter. We do this for two reasons. First, we can obtain better bounds for interval graphs than for general graphs with bounded VC-dimension, including establishing a lower bound alongside the upper bound. Second, we note the importance of interval graphs in their own right [22], justifying this distinction.

Interval graphs have unbounded twin-width but some subclasses, including unit interval graphs, do have bounded twin-width. This was one of the arguments in [5] for twin-width seeming to strike the balance between sparse and dense classes. Moreover, interval graphs are delineated by twin-width [23]. Despite these notable aspects of the class and their consistent use as a prime example of graphs with unbounded twin-width, to the best of our knowledge no efforts have been made to sufficiently characterize the behaviour of their twin-width. As such, we devote some attention to obtaining better bounds for this class that improve upon those obtained for general graphs with bounded VC-dimension.

1.1 Main Results↩︎

We obtain four main results: a general tool for obtaining twin-width bounds, a sub-linear upper bound on the twin-width of graphs with bounded VC-dimension, and both a sub-linear upper bound and a super-logarithmic lower bound on the twin-width of interval graphs.

In Section 3, we first establish a tool that takes as input a graph that is vertex-partitioned into a bounded number of parts, each of which have high similarity between their neighbourhoods, and outputs a contraction sequence witnessing sub-linear twin-width dependent on both the number of parts and the symmetric difference between their neighbourhoods. This is the technique we will use to obtain upper bounds on the twin-width.

Then, in Section 4, we find a suitable partition for graphs with bounded VC-dimension to use as input to the aforementioned tool. Feeding this partition into the twin-width tool we designed, we obtain our first result.

Theorem 6 The class of n-vertex graphs with VC-dimension at most \(k\) has twin-width in \(O(n^{1-\frac{1}{2k+1}})\).

In particular, Theorem 6 implies that a hereditary class \(\mathcal{C}\) of graphs admits a sub-linear bound (\(o(n)\) in terms of the number of vertices \(n\)) on twin-width if and only if \(\mathcal{C}\) has bounded VC-dimension. The first direction comes from the above, while the second comes from the fact that split, bipartite, and cobipartite graphs are all hereditary classes with linear twin-width (see Appendix 12 for proof) and any class with unbounded VC-dimension contains at least one of these classes, as previously mentioned.

In Section 5, we expand on our previous results to give explicit bounds on the twin-width of interval graphs. We find a partition distinct from that for general graphs with bounded VC-dimension which improves the upper bound on the twin-width. We obtain our second result.

Theorem 7 Any \(n\)-vertex interval graph has twin-width at most \(2\lceil\sqrt{2n}\rceil \in O(\sqrt{n})\).

We then give a construction for graphs that belong to the intersection of the class of interval graphs and the class of split graphs (graphs whose vertex-set can be partitioned into a clique and a stable set). This construction gives a lower bound on the twin-width of interval graphs.

Theorem 8 The class of \(n\)-vertex interval graphs has twin-width in \(\Omega(n^{1/4})\).

2 Preliminaries↩︎

In this paper, all logarithms are taken base \(e\) unless otherwise stated and all graphs are simple and undirected.

2.1 Graph Theory↩︎

For a graph \(G\), let \(V(G)\) denote its vertex-set, \(E(G)\) its edge-set, and \(uv \in E(G)\) the edge between vertices \(u,v \in V(G)\). We denote by \(N(v)\) the neighbourhood of a vertex \(v\) and by \(\Delta(G)\) the maximum degree of a vertex in \(G\). For a subset of vertices \(X \subseteq V(G)\), we denote by \(G[X]\) the subgraph induced by \(X\) in \(G\) and let \(|X|\) be the cardinality of \(X\). A stable set is a set \(X\) of vertices where \(G[X]\) has no edges. The following lemma is well-known, for example, as a consequence of Brooks’ Theorem [24].

Twin-width will require working with the differences in vertex neighbourhoods, so we define some related basic language here. For two vertices \(u,v \in V(G)\), let \(N(u) \Delta N(v)\) denote the symmetric difference \((N(u) \cup N(v)) \setminus (N(u) \cap N(v))\) between their neighbourhoods. Consider a vertex-set \(S\) and a vertex \(v\) (possibly in \(S\)). We call \(v\) complete to \(S\) if it is adjacent to all vertices of \(S\), anticomplete to \(S\) if it is adjacent to none of \(S\), and mixed on \(S\) otherwise (it has both a neighbour and a non-neighbour, possibly \(v\) itself, in \(S\)).

2.2 Twin-Width↩︎

We use the following standard definitions from [2].

A trigraph is a graph \(G\) along with a partition \((B,R)\) of its edge-set; we usually refer to edges in \(B\) as black edges and edges in \(R\) as red edges. We think of red edges as recording ‘errors’ that will arise from ‘merging’ edges and non-edges. A (vertex) contraction is an identification of two vertices \(u,v\) into a single vertex \(w\) where we keep previously black or red edges from \(w\) to \(N(u) \cap N(v)\) and add red edges from \(w\) to \(N(u) \Delta N(v)\) (or turn previously black edges red, avoiding multi-edges). In a trigraph, the red degree of a vertex \(v\) is the number of red edges incident with \(v\).

A contraction sequence of an \(n\)-vertex graph \(G\) is a sequence of trigraphs \(G = G_n,\dots,G_1 = K_1\) such that \(G_t\) is obtained from \(G_{t+1}\) by performing a single vertex contraction. We call such a sequence a d-sequence if all trigraphs in the sequence have maximum red degree at most \(d\). We may also say that a \(d\)-sequence is a contraction sequence with width \(d\). The twin-width of a graph \(G\), denoted \(\mathop{\mathrm{\textrm{tww}}}(G)\), is the minimum integer \(d\) such that \(G\) has a \(d\)-sequence.

For a trigraph \(G_t\) in a contraction sequence, let \(\mathcal{P}_t\) denote the set of parts of \(G_t\), where a part is a maximal set of vertices that have been contracted to one vertex in \(G_t\). For example, if the vertices \(u,v \in G_{t+1}\) are contracted together in \(G_t\) and neither had previously been contracted with any other vertex, then they will appear in the same part \(\{u,v\} \in \mathcal{P}_t\). Hence the trigraph \(G_t\) has one vertex for each set in \(\mathcal{P}_t\). We refer to parts of size exactly one as singletons or uncontracted vertices: they have not yet been involved in a contraction with any other vertex. All other vertices of a trigraph \(G_t\) are called contracted vertices: they represent two or more vertices of \(G\).

2.3 VC-Dimension↩︎

Originally defined for set systems, VC-dimension essentially characterizes how complex a system is.

Extended to graphs, the VC-dimension of a graph characterizes the complexity of its sets of vertex neighbourhoods.

Computing the VC-dimension is LOGNP-Complete [25], [26]. Therefore, in this work, we assume that it is given as input along with the graph. We will need a result due to Haussler [27].

For our use, we apply Lemma 2 to graphs, as follows.

This follows from applying Lemma 2 to the set system \(\{N(b) \cap A : b \in B\}\) with ground set \(A\) (hence \(N=a\)) and \(c=z\).

This tells us that given a graph with bounded VC-dimension, for any two subsets \(A\) and \(B\) of \(G\), either \(B\) is small or there exists a pair of vertices in \(B\) with neighbourhoods in \(A\) that are not substantially different from each other. This is the main tool we will use to help us find vertices with small symmetric difference between their neighbourhoods in Section 4, so that we may partition our graph into sets of vertices that make good candidates for contraction while maintaining bounded red degree over the contraction sequence.

2.4 Interval Graphs↩︎

For an interval \(I = [a,b]\) with \(a < b\), we say that \(I\) has left endpoint \(a\) and right endpoint \(b\). Without loss of generality, we may assume that all endpoints are integers. In fact, if \(G\) is an \(n\)-vertex interval graph, we may assume that \(G\) corresponds to a family \(\mathcal{I}\) of intervals such that all intervals in \(\mathcal{I}\) have distinct endpoints in \(\{1, \dots, 2n\}\).

3 The Twin-Width Tool↩︎

Our first result is a tool for obtaining twin-width bounds in general.

Theorem 4 below tells us that to show that an input graph \(G\) has sub-linear twin-width in the size of \(G\), we need only find a partition of \(G\) into a bounded number of sets in a sequence such that each but at most one is mixed on a bounded number of vertices later in the sequence, and the one that may be mixed on more has bounded size. The tool gives a contraction sequence witnessing the twin-width as a function of the number of sets, the number of vertices they are mixed on, and the size of the single set that may be mixed on more. This is the technique we will use to obtain upper bounds on the twin-width of graphs of bounded VC-dimension in Section 4 and of interval graphs in Section 5.

4 Graphs of Bounded VC-Dimension↩︎

We first need to structure graphs with bounded VC-dimension into a vertex-partition satisfying the constraints of Theorem 4 above. Building on Lemma 3 from Section 2.3, we show that there always exists some reasonably-sized set of vertices such that the cumulative difference between their neighbourhoods is not too large. Some of this is similar to the ideas of Theorem 3 in [28], which uses bounded VC-dimension to partition the graph into a bounded number of sets while controlling edge densities between sets. With the tool of Lemma 5 in place, we will then be able to partition the graph into the sets needed to apply the technique of Theorem 4 and obtain an upper bound on the twin-width.

We now have all of the necessary tools to show that bounded VC-dimension implies sub-linear twin-width. We will use the previous result to obtain the partition that will serve as input to Theorem 4, which will then give us a bound on the twin-width.

The above result gives us that all graphs with small VC-dimension have twin-width at most sub-linear. As a corollary, in Table ¿tbl:table:vc-tww? we list a few select classes of graphs with bounded VC-dimension that we find interesting and state explicitly the bound obtained from Theorem 6. While planar graphs are known to have twin-width at most 8 [29], we list them here to provide a frame of reference.

5 Interval Graphs↩︎

We now proceed to give better upper bounds on the twin-width of interval graphs than those obtained from Theorem 6, and then also give lower bounds. The lower bound is constructive, while the upper bound leverages the ordering of neighbourhoods to find a suitable partition for Theorem 4 from Section 3.

Proof. We construct an interval graph \(G_\mathcal{I}\) on a family \(\mathcal{I}\) of \(n\) intervals. We refer to the intervals in \(\mathcal{I}\) and the vertices in \(G_\mathcal{I}\) interchangeably throughout this proof, and we will drop \(G_\mathcal{I}\) as subscript of the neighbourhood \(N_{G_\mathcal{I}}(v)\) of a vertex since we will study no other graph. The idea is to make \(G_\mathcal{I}\) a split graph such that any clique-vertex is adjacent to many stable-set vertices, yet for any two clique-vertices, their neighbourhoods are quite different.

Figure 1 illustrates the following construction. First, create a clique \(\cal K\) of size \(k = r^2\). The key idea here is that any two vertices in \(\cal K\) whose left endpoints are close together will have right endpoints that are far apart. Formally, for all indices \(i,j \in \{0,\dots,r-1\}\), we define the interval \(K_{i,j} = [ri+j, k+rj+i]\) and let \(\mathcal{K} = \{K_{i,j} : i,j \in \{0,\dots, r-1\}\}\). Observe that all intervals in \(\cal K\) intersect the point \(k-\frac{1}{2}\), so they indeed form a clique.

Now construct a stable set \(\mathcal{S}\) on \(2k-2\) vertices as follows. For each index \(i \in \{0, \dots,2k-2\}\), define the interval \(S_i = [i+\frac{1}{3}, i+\frac{2}{3}]\). Let \({\cal S} = \{S_i : i \in \{0,\dots,2k-2\}\) and \(i \neq k-1\}\) and let \({\cal S}_L = \{S_i : i \in \{0,\dots,k-2\}\}\) and \({\cal S}_R = S \setminus S_L\). Note that \(|\mathcal{S}| = 2k-2\) as desired.

This completes the construction of \(G_\mathcal{I}\). We first prove two useful properties of \(G_\mathcal{I}\). Our first claim concerns the neighbourhood of any clique-vertex.

Claim 9. Each interval \(K_{i,j}\) in \(\mathcal{K}\) satisfies \(|N(K_{i,j})\cap S| \geq 2r-2\).

Proof. There are three cases. In the first case, interval \(K_{i,j}\) starts far enough to the left such that it intersects the rightmost \(2r-2\) intervals of \(\mathcal{S}_L\), i.e., \(S_{k-2}\) and the \(2r-3\) intervals of \(\mathcal{S}_L\) to its left. This holds if \(ri+j\leq k-2r+3=r^2-2r+1\), which is the case if either \(i\leq r-3\) or \(i=r-2\) and \(j\leq 1\). Similarly, if \(j \geq 2\) or both \(j=1\) and \(i\geq r-2\), then \(K_{i,j}\) intersects the leftmost \(2r-2\) intervals of \(\mathcal{S}_R\). This leaves the case where \(i=r-1\) and \(j=0\). Here \(K_{i,j}\) intersects the \(r-1\) rightmost intervals of \(\mathcal{S}_L\) and the \(r-1\) leftmost intervals of \(\mathcal{S}_R\), i.e., \(S_{(r-1)r},\dots, S_{(r-1)r+r-2}\) and \(S_k, \dots, S_{k+r-2}\). In all three cases, \(K_{i,j}\) intersects at least \(2r-2\) intervals as desired. ◻

The next claim formalizes the earlier statement that for any two clique-vertices the neighbourhoods are quite distinct.

Claim 10. For any two intervals \(K_{i,j},K_{i',j'}\in \mathcal{K}\), we have \(|N(K_{i,j}) \Delta N(K_{i',j'})| \geq r\).

Proof. Write \(L=ir+j, L'=i'r+j', R=jr+i\) and \(R'=j'r+i'\) for the left and right endpoints of these intervals. We are done if \(|L'-L|\geq r\) or \(|R'-R|\geq r\), because then the (at least \(r\)) intervals of \(\mathcal{S}\) that fall into the gap between the endpoints belong to one of the neighbourhoods, but not the other. We now show that this is nearly always the case, and the one exception can be handled as well.

\(|i-i'|\geq 2\) or \(|j-j'|\geq 2\). Let us assume that \(|i-i'|\geq 2\), the other case is done similarly by considering \(R,R'\). Up to renaming of the two intervals, we have \(i'\geq i+2\), and therefore \(L'= i'r+j'\geq (i+2)r > ir+r+j=L+r\).

\(i=i'\) or \(j=j'\). Let us assume that \(j=j'\), the other case is done similarly by considering \(R,R'\). Since the intervals are distinct, we have \(i\neq i'\), hence up to renaming of the two intervals we have \(i'\geq i+1\) and \(L' = i'r+j' \geq (i+1)r+j = L+r\).

\(|i-i'|=1\) and \(|j-j'|=1\). Up to renaming we have \(i'=i+1\). If furthermore \(j'=j+1\), then we are done since \(L'= i'r+j'=(i+1)r + j+1= L+r+1\). This leaves as final case \(j'=j-1\), where similar computations show \(L'=L+r-1\) and \(R=R'+r-1\). Hence in each of \(\mathcal{S}_L\) and \(\mathcal{S}_R\) there are \(r-1\) intervals in the symmetric difference, and in total there are \(2r-2\geq r\). ◻

We now show the lower bound on the twin-width of \(G_\mathcal{I}\). Consider a contraction sequence \(G_\mathcal{I} = G_n, \dots, G_1\) of width \(w\). We will show that \(w+1\geq \sqrt{r/2}\), which with \(r=\sqrt{k}=\sqrt{\tfrac{n+2}{3}}\) gives the result after appropriate reformulations.

Let \(q\) be maximal such that \(G_q\) has a part \(P\) that is not a singleton and contains a clique-vertex \(K_{i,j}\). Note that \(q < n\), since all parts of \(G_n\) are singletons. Also in \(G_{q+1}\) vertex \(K_{i,j}\) was a singleton by choice of \(q\), so we obtained part \(P\) of \(G_q\) by merging some part \(P'\) of \(G_{q+1}\) with \(K_{i,j}\). We claim that no part of \(G_{q+1}\) can have been very big.

Claim 11. Any part \(Q\) of \(G_{q+1}\) has size \(|Q| \leq 2w+2\).

Proof. We may assume that \(Q \subseteq \mathcal{S}\), for otherwise \(Q \cap K \neq \emptyset\) and \(|Q|= 1 \leq 2w-2\) by choice of \(q\). Up to symmetry between \(\mathcal{S}_L\) and \(\mathcal{S}_R\), we may assume that \(|Q \cap \mathcal{S}_L| \geq \frac{|Q|}{2}\). Let \(l = \min\{l':S_{l'} \in Q \cap \mathcal{S}_L\}\) and \(m = \max\{l':S_{l'} \in Q \cap \mathcal{S}_L\}\) so that \(S_l\) and \(S_m\) are the leftmost and rightmost intervals of \(\mathcal{S}_L\) in \(Q\), respectively. Since \(S_l\) has right endpoint \(l + \frac{2}{3}\) and \(S_m\) has left endpoint \(m + \frac{1}{3}\), both of which are less than \(k\), it follows that all intervals in \(\mathcal{K}\) with left endpoint between \(l+1\) and \(m\) are mixed on \(Q\). Since \(Q\subseteq \mathcal{S}\), therefore \(Q\) has red edges to every vertex in the set \(\{I^x:x \in \{l+1,\dots,m\}\}\), where \(I^x\) is the interval of \(\mathcal{K}\) whose left endpoint is \(x\). (Note that this exists for all \(x\in \{0,\dots,k-1\}\).) Then \(Q\) has red degree at least \(m-l \geq |Q\cap \mathcal{S}_L|-1 \geq \frac{|Q|}{2}-1\). Since the red degree of \(Q\) is at most \(w\), the claim follows. ◻

Now we study the part \(P'=P\setminus K_{i,j}\) of \(G_{q+1}\) to argue a lower bound on \(w\). As first case, assume that \(P'\) contains vertices of \(\mathcal{S}\). Let \(\mathcal{S}' = (N(K_{i,j})\cap \mathcal{S})\setminus P'\). By Claims [eq:k-nbrs] and [eq:part-size], we have \(|\mathcal{S}'|\geq 2r-2-(2w+2)\). Again by Claim [eq:part-size], at least \(\tfrac{|\mathcal{S}'|}{2w+2}\geq \frac{2r-2}{2w+2}-1\) parts in \(G_q\) contain a vertex in \(\mathcal{S}'\). Let \(\hat{P}\) be one such part, say it contains \(\hat{S}\in \mathcal{S}'\). By definition of \(\mathcal{S}'\) we have \(\hat{P}\neq P'\). Therefore \(\hat{P}\) is mixed on \(P\), because \(\hat{S}\) is adjacent to \(K_{i,j}\) by definition of \(\mathcal{S}'\), and \(\hat{S}\) is not adjacent to the vertices of \(\mathcal{S}\) in \(P'\). It follows that, in \(G_q\), part \(P\) has red edges to at least \(\tfrac{2r-2}{2w+2}-1\) other parts, hence \(w \geq \frac{r-1}{w+1}-1\), or \((w+1)^2\geq r-1 \geq \tfrac{r}{2}\) as desired.

Now we consider the other case where \(P'\subseteq K\), which by our choice of \(q\) means that \(P'\) is a singleton, say \(P' = \{K_{i',j'}\}\). Consider the symmetric difference \(X=N(K_{i,j}) \Delta N(K_{i',j'})\), which by Claim [eq:x-size] has size \(|X|\geq r\). In \(G_q\), part \(P=\{K_{i,j},K_{i',j'}\}\) has a red edge to every part of \(G_q\) containing a vertex of the set \(X\), which is at least \(\frac{r}{2w+2}\) parts by Claim [eq:part-size]. Hence \(w\geq \frac{r}{2w+2}\), which implies \(\tfrac{r}{2}\leq w(w+1)<(w+1)^2\) as desired. ◻

References↩︎