betaFeedback

WorksMathematics

Intersections of Odd Polygons Revisited

Abstract

It is shown that the maximum number of intersection points between the boundaries of a simple mm-gon and a simple nn-gon is mn−(m+n)+3mn-(m+n)+3 for any odd integers m,n≥3m,n \ge 3. The previous best upper bound was mn−(m+n)+Cmn-(m+n)+C, for some huge constant CC.

Introduction

Let PP and QQ be two simple polygons with mm and nn sides, respectively. We are interested in the very basic question of determining the maximum number of distinct intersection points between the boundaries of PP and QQ. We assume that no two sides of the polygons overlap, therefore, this number is finite and is upper-bounded by mnmn. It is easy to see that this bound can be attained when mm and nn are both even, see Figure 1(a) for an example. Observe also that if nn is odd, then every side of PP has at most n−1n-1 distinct intersection points with sides of QQ, therefore there are at most mn−mmn-m intersections between sides of PP and QQ. It is not hard to construct an mm-gon and an nn-gon admitting that many intersections for every even mm and odd nn, see Figure 1(b) for an example. In contrast, determining the maximum number of intersections between the boundaries of two odd size polygons is much more challenging.

Figure 1. (a) Optimal construction for m=n=8m=n=8, with 8⋅8=648\cdot8=64 intersections. (b) Optimal construction for m=8m=8, n=7n=7, with 8⋅7−8=488\cdot7-8=48 intersections. (c) Lower-bound construction for m=9m=9, n=7n=7, with 9⋅7−(9+7)+3=509\cdot7-(9+7)+3=50 intersections.

This problem was first studied by Dillencourt, Mount, and Saalfeld [3]. They showed a construction with mn−(m+n)+3mn-(m+n)+3 intersections (see Figure 1(c) for an example) and claimed that this bound is tight, however, their proof contained an unrecoverable error. A weaker upper bound of mn−(m+⌈n/6⌉)mn-(m+\lceil n/6\rceil) for m≥nm \ge n was proved by Černý, Kára, Král’, Podbrdský, Sotáková, and Šámal [2]. This was improved to mn−(m+n)+Cmn-(m+n)+C, where CC is a (huge) constant, in joint work Keszegh and Rote [1]. Recently, the author revisited this work with ChatGPT, asking it whether that proof is sound and whether the constant CC can be decreased, hopefully, down to 3. The outcome of the first question was a small gap revealed in a certain case-analysis in the proof of the main theorem where one subcase was overlooked (see Appendix § 6). Still, it seems that by a more careful and finer analysis this gap can be resolved. As for the second question, using tools from [1], ChatGPT indeed managed to decrease the constant CC: first, to 11 while also providing a simpler proof than the one in [1]. Then, with some extra effort and case-analysis, down to 3, thus determining the exact maximum possible number of intersections between two odd size simple polygons.

Theorem 1.1. For any odd integers m,n≥3m,n \ge3, the maximum number of intersection points between the boundaries of a simple mm-gon and a simple nn-gon is mn−(m+n)+3mn-(m+n)+3.

While preparing this manuscript the author was contacted by Ju Yong Seo who published a different proof of Theorem 1.1 obtained using a different LLM [4]. In fact, the result in [4] is stronger, since it states that the so-called disjointness graph of the two polygons has at most three connected components and this immediately implies Theorem 1.1 (see § 2). However, the proof in [4] is computer-assisted (in the pre-LLM era sense), as it boils down to verifying a few hundred cases using a SAT solver, whereas the proof presented here can be verified by hand. Furthermore, we present a simple proof (relying on [1]) of the slightly weaker bound mn−(m+n)+11mn-(m+n)+11.

Organization. We first establish terminology and some tools in Section 2. Using these tools we present a simple proof of the weaker bound in Section 3. Section 4 introduces further definitions and tools that are required for proving the optimal bound which is then proved in Section 5. The small gap in the proof in [1] is described in Appendix A.

AI Disclosure. ChatGPT-6 Astra was used for proving the new result and for preparing this manuscript. The author verified the proofs, simplified some of them, edited the paper considerably to improve the presentation, and takes full responsibility for its content.

Assumptions, terminology, and tools

Throughout this paper PP denotes a simple mm-gon and QQ denotes a simple nn-gon, where mm and nn are odd integers. We assume that each side of PP intersects each side of QQ in at most one point. Furthermore, it follows from [1] that we may assume, without loss of generality, that each intersection point of two sides lies in the interior of both sides (that is, it is a crossing point), no three vertices of PP and QQ combined are collinear, and that no two sides of PP and QQ combined are parallel. Denote by XX the number of intersection points between a side of PP and a side of QQ.

The disjointness graph GDG^{\mathrm{D}}. As in [1, 2], we define the disjointness graph of PP and QQ. It is a bipartite graph, GDG^{\mathrm{D}}, whose vertex set corresponds to the sides of PP and QQ and its edge set consists of pairs of disjoint sides, one from PP and the other from QQ. See Figure 4 for an example. By abuse of notation we interchange sides of the polygons with their corresponding vertices in GDG^{\mathrm{D}}.

Figure 4. Two heptagons PP and QQ, their disjointness graph GDG^{\mathrm{D}}, and their transitions graph HH. The edges of HH are associated with three gadgets: the PP-pure gadget (a,g,4,5)(a,g,4,5), the QQ-pure gadget (d,e,1,7)(d,e,1,7) and the double gadget (e,f,6,5)(e,f,6,5).

Let c(GD)c(G^{\mathrm{D}}) be the number of connected components of GDG^{\mathrm{D}}. Since every edge in GDG^{\mathrm{D}} corresponds to a non-intersecting pair of sides, it follows that X=mn−∣E(GD)∣X=mn-|E(G^{\mathrm{D}})|. Note that ∣V(GD)∣=m+n|V(G^{\mathrm{D}})|=m+n, and therefore ∣E(GD)∣≥m+n−c(GD)|E(G^{\mathrm{D}})|\ge m+n-c(G^{\mathrm{D}}). Thus, we have:

X≤mn−(m+n)+c(GD).(1)X \le mn-(m+n)+c(G^{\mathrm{D}}). \tag*{(1)}

The upper bound in [1] follows by showing that c(GD)<270c(G^{\mathrm{D}})<2^{70}. The current improvement of this bound is obtained by showing that many connected components imply many additional edges within connected components. Clearly, once the number of edges in a graph exceeds the number of vertices minus one, any additional edge within a connected component implies a new cycle. It is therefore convenient to consider the cycle rank of GDG^{D} and its connected components. For a graph GG the cycle rank of GG (also known as circuit rank or cyclomatic number) is the minimum number of edges one has to remove from GG to make it acyclic (that is, a forest). We recall the following facts about the cycle rank of a graph, which we denote here by μ(G)\mu(G).

Proposition 2.1. Let GG be a graph, possibly with parallel edges. Then μ(G)=∣E(G)∣−∣V(G)∣+c(G)\mu(G) = |E(G)| - |V(G)| + c(G), where c(G)c(G) is the number of connected components of GG. Furthermore, μ(G)\mu(G) is non-negative, does not decrease when adding vertices or edges, and remains the same when contracting a non-loop edge. If G1,G2G_1, G_2 have disjoint edge sets, then μ(G1∪G2)≥μ(G1)+μ(G2)\mu(G_1 \cup G_2) \ge\mu(G_1) + \mu(G_2).

Proof. If c(G)=1c(G) = 1, that is GG is connected, then clearly μ(G)=∣E(G)∣−∣V(G)∣+c(G)\mu(G) = |E(G)| - |V(G)| + c(G) since one has to remove ∣E(G)∣−(∣V(G)∣−1)|E(G)| - (|V(G)| - 1) edges to get a spanning tree with ∣V(G)∣−1|V(G)| - 1 edges. If c(G)>1c(G) > 1, then by applying this argument for every connected component and summing up we get the desired equality.

By definition μ(G)\mu(G) is non-negative and can only increase when adding vertices or edges. Contracting a non-loop edge ee decreases both the number of vertices and the number of edges by one while leaving the number of connected components unchanged, therefore μ(G/e)=μ(G)\mu(G/e) = \mu(G). It is also easy to see that μ(G1∪G2)≥μ(G1)+μ(G2)\mu(G_1 \cup G_2) \ge\mu(G_1) + \mu(G_2), since breaking every cycle in G1∪G2G_1 \cup G_2 requires in particular breaking every cycle in G1G_1 and every cycle in G2G_2.

Since μ(GD)=∣E(GD)∣−∣V(GD)∣+c(GD)\mu(G^{D}) = |E(G^{D})| - |V(G^{D})| + c(G^{D}), we have:

X=mn−(m+n)+c(GD)−μ(GD).(2)X = mn - (m+n) + c(G^{D}) - \mu(G^{D}). \tag*{(2)}

Therefore, we can get a better upper bound on XX by showing that GDG^{D} has few connected components or that its cycle rank is high. More precisely, Theorem 1.1 will follow once we show that c(GD)−μ(GD)≤3c(G^{D}) - \mu(G^{D}) \le3. In fact, it is enough to show that c(GD)−μ(GD)≤4c(G^{D}) - \mu(G^{D}) \le4 by the following observation.

Proposition 2.2. c(GD)−μ(GD)c(G^{D}) - \mu(G^{D}) is odd.

Proof. The number of crossings between two Jordan curves is even, thus XX is even. Since mnmn is odd and m+nm+n is even, it follows from (2) that c(GD)−μ(GD)c(G^{D}) - \mu(G^{D}) is odd.

We proceed with some other useful notions and lemmas from [1]. Let xx and yy be two consecutive polygon-sides sharing a common endpoint x∩yx \cap y. Denote by Cone⁡(x,y)\operatorname{Cone}(x,y) the convex cone which is bounded by the two rays emanating from x∩yx \cap y and containing xx and yy, respectively, and let Cone⁡‾(x,y)\overline{\operatorname{Cone}}(x,y) denote the opposite cone (see Figure 2).

Figure 2. The cones defined by two consecutive polygon-sides xx and yy.

Observation 2.3. Let xx and yy be two consecutive polygon-sides and let zz be a polygon-side that crosses both xx and yy. Then no endpoint of zz lies in Cone⁡(x,y)∪Cone⁡‾(x,y)\operatorname{Cone}(x,y) \cup\overline{\operatorname{Cone}}(x,y).

The following lemma gives rise to the main geometric structure used throughout the proof.

Lemma 2.4 ([1 Lemma 5]). Let xx and x′x' be two consecutive sides of one polygon such that there is no side of the other polygon which is disjoint from both of them. Then there are two consecutive sides of the other polygon, yy and y′y', such that (x,y),(x′,y′)∈E(GD)(x,y),(x',y') \in E(G^{\mathrm{D}}) and (x,y′),(x′,y)∉E(GD)(x,y'),(x',y) \notin E(G^{\mathrm{D}}). Furthermore, x∩x′∈Cone⁡(y,y′)x \cap x' \in\operatorname{Cone}(y,y') or y∩y′∈Cone⁡(x,x′)y \cap y' \in\operatorname{Cone}(x,x').

We remark that the original statement of this lemma in [1] assumes that xx and x′x' belong to different connected components of GDG^{\mathrm{D}}, however, its proof only uses the property stated here which is implied by the different components assumption.

Gadgets and hooking types

Let qq and q′q' be two consecutive sides of QQ and let pp and p′p' be two consecutive sides of PP such that (q,p),(q′,p′)∈E(GD)(q,p),(q',p') \in E(G^{\mathrm{D}}), (q,p′),(q′,p)∉E(GD)(q,p'),(q',p) \notin E(G^{\mathrm{D}}) and p∩p′∈Cone⁡(q,q′)p \cap p' \in\operatorname{Cone}(q,q') or q∩q′∈Cone⁡(p,p′)q \cap q' \in\operatorname{Cone}(p,p') (see Figure 3 for examples). The two pairs of consecutive edges are called associated pairs in [1]. Here we refer to them as a gadget and say that (p,q)(p,q) and (p′,q′)(p',q') are its base edges, or simply bases. As a convention, we denote a gadget by a 4-tuple (p,p′,q,q′)(p,p',q,q') such that p,p′p,p' are its PP-pair, q,q′q,q' are its QQ-pair, and (p,q),(p′,q′)∈E(GD)(p,q),(p',q') \in E(G^{\mathrm{D}}) are its base edges. Note that by definition we get the same set of gadgets if we interchange PP and QQ.

Figure 3. A gadget (p,p′,q,q′)(p,p',q,q'). (a) A pure QQ-hooking gadget. (b) A pure PP-hooking gadget. (c) A double gadget. (d) The base edges of the gadget. (e) Not a gadget since no hooking occurs.

If the common endpoint of the QQ-pair (resp., PP-pair) of a gadget lies in the cone of the PP-pair (resp., QQ-pair), then we say that the gadget is PP-hooking (resp., QQ-hooking). Note that a gadget may be both PP-hooking and QQ-hooking and that a pair of consecutive sides may participate in several gadgets (of similar or different hooking types). If exactly one hooking occurs in a gadget, then we say that this gadget is pure and otherwise if the two hookings occur the gadget is double. See Figure 3 for illustrations.

Observation 2.5. Let g=(p,p′,q,q′)g=(p,p',q,q') be a gadget.

If gg is pure QQ-hooking, then p∩p′∈Cone⁡(q,q′)p \cap p' \in\operatorname{Cone}(q,q') and q∩q′∈Cone⁡(p,p′)‾q \cap q' \in\overline{\operatorname{Cone}(p,p')}.

If gg is pure PP-hooking, then q∩q′∈Cone⁡(p,p′)q \cap q' \in\operatorname{Cone}(p,p') and p∩p′∈Cone⁡(q,q′)‾p \cap p' \in\overline{\operatorname{Cone}(q,q')}.

If gg is double hooking, then q∩q′∈Cone⁡(p,p′)q \cap q' \in\operatorname{Cone}(p,p') and p∩p′∈Cone⁡(q,q′)p \cap p' \in\operatorname{Cone}(q,q').

Corollary 2.6. GDG^{\mathrm{D}} contains no isolated vertices.

Proof. Suppose for contradiction that there is a polygon-side xx which is an isolated vertex in GDG^{\mathrm{D}}. Let x′x' be a side of the same polygon that is consecutive to xx. Then it follows from Lemma 2.4 that there is a side yy of the other polygon such that (x,y)∈E(GD)(x,y) \in E(G^{\mathrm{D}}), a contradiction.

The following lemma is crucial for the proof.

Lemma 2.7 ([1 Lemma 7]). Suppose that two gadgets use eight distinct sides and induce a subgraph of GDG^{\mathrm{D}} which is a matching consisting of their four base edges. Then both gadgets are pure and of different hooking types.

Remark. We note that the original statement of this lemma refers to the case where the four base edges belong to different connected components of GDG^{\mathrm{D}}, however, the proof actually uses the weaker assumption stated here.

A weaker upper bound X≤mn−(m+n)+11X \le mn-(m+n)+11

Recall that it is enough to show that c(GD)−μ(GD)≤11c(G^{\mathrm{D}})-\mu(G^{\mathrm{D}})\le11. In particular we may assume that c(GD)≥2c(G^{\mathrm{D}})\ge2.

The transitions graph HH. Define a graph HH as follows: the node2 set of HH consists of the connected components of GDG^{\mathrm{D}} and its edge set consists of pairs of distinct connected components UU and VV such that there are two consecutive QQ-sides qq and q′q' such that q∈Uq\in U and q′∈Vq'\in V. By Lemma 2.4 there is at least one gadget whose QQ-pair is q,q′q,q'. We say that any such gadget and UVUV are associated and note that the gadget has one of its base edges in UU and its other base edge in VV. See Figure 4 for an example.

Remarks. It easily follows from its definition that HH is connected. Observe that a gadget is associated with at most one edge of HH, but several gadgets may be associated with the same HH-edge. The fact that an HH-edge corresponds to a gadget and the symmetric roles that PP and

QQ play with respect to gadgets imply that defining the transitions graph according to PP would result in the same graph HH.

Lemma 3.1. There are no two node-disjoint edges of HH associated with two gadgets that are both QQ-hooking or both PP-hooking.

Proof. Suppose that HH has two disjoint edges associated with same-type gadgets g1g_1 and g2g_2. Then the four bases of g1g_1 and g2g_2 lie in four distinct connected components, thus, their eight vertices induce a matching in GDG^{\mathrm{D}}. But then by Lemma 2.7 the two gadgets must have different types.

Lemma 3.2. If two gadgets that join a component UU to two distinct other components are both QQ-hooking or both PP-hooking, then their bases in UU are connected by an edge of GDG^{\mathrm{D}} or share a vertex.

Proof. Suppose that there are two gadgets sharing the same type g1=(p1,p1′,q1,q1′)g_1=(p_1,p_1',q_1,q_1') and g2=(p2,p2′,q2,q2′)g_2=(p_2,p_2',q_2,q_2') and three distinct connected components U,L1,L2U,L_1,L_2 such that (pi,qi)(p_i,q_i) lies in UU and (pi′,qi′)(p_i',q_i') lies in LiL_i, for i=1,2i=1,2 (see Figure 5 for an illustration). It is enough to consider the case that p1≠p2p_1\ne p_2 and q1≠q2q_1\ne q_2, for otherwise the claim trivially holds. Consider the three subsets {p1,p2,q1,q2}⊆U\{p_1,p_2,q_1,q_2\}\subseteq U, {p1′,q1′}⊆L1\{p_1',q_1'\}\subseteq L_1 and {p2′,q2′}⊆L2\{p_2',q_2'\}\subseteq L_2, and observe that there cannot be edges in GDG^{\mathrm{D}} between vertices from different subsets, since they belong to different connected components. If (p1,q2),(p2,q1)∉E(GD)(p_1,q_2),(p_2,q_1)\notin E(G^{\mathrm{D}}), then the subgraph induced by those eight vertices is a matching and by Lemma 2.7 the two gadgets cannot share a hooking type, a contradiction.

Figure 5. An illustration for the proof of Lemma 3.2: the gadget gig_i consists of the QQ-pair qi,qi′q_i,q_i' and the PP-pair pi,pi′p_i,p_i', its base edges (pi,qi)(p_i,q_i) and (pi′,qi′)(p_i',q_i') are in UU and LiL_i, respectively. It follows that (p1,q1)(p_1,q_1) and (p2,q2)(p_2,q_2) share a vertex or are connected by an edge of GDG^{\mathrm{D}}.

The following is an important consequence of Lemma 3.2.

Corollary 3.3. Let UU be a connected component containing k≥1k\ge1 pairwise vertex-disjoint bases belonging to gadgets sharing the same hooking type where each of these gadgets is associated with an HH-edge connecting UU to a distinct connected component. Then the vertices of the kk bases induce a subgraph of UU with 2k2k vertices and at least k+(k2)k+\binom{k}{2} edges. In particular, μ(U)≥k+(k2)−(2k−1)=(k−12)\mu(U)\ge k+\binom{k}{2}-(2k-1)=\binom{k-1}{2}.

In order to use Corollary 3.3 we first consider a spanning tree TT of HH. Clearly, TT consists of exactly c(GD)−1c(G^{\mathrm{D}})-1 edges. For every edge UVUV of TT, we select one gadget associated with UVUV, and color UVUV with color QQ if this gadget is QQ-hooking, and with color PP otherwise (if it is PP-pure). Let TQT_Q and TPT_P be the subgraphs consisting of the edges colored QQ and PP, respectively. Recall that by Lemma 3.1 any two edges of HH associated with same-type gadgets share a common node of HH. It follows that apart from isolated nodes, each of TQT_Q and TPT_P is a star.3 Let UPU_P and UQU_Q be the centers of the stars TPT_P and TQT_Q, respectively (if one of these stars is empty, then we choose an arbitrary component as its center). Note that it may happen that UP=UQU_P = U_Q.

Obtaining disjoint base edges in UPU_P and UQU_Q. For each edge UQVU_QV of TQT_Q, we mark its base edge in UQU_Q that belongs to the gadget selected for UQVU_QV. Then we do the same for edges of TPT_P and their corresponding base edges in UPU_P. If a base edge belongs to two selected gadgets, then we mark it twice. Considering the subgraph of GDG^D that consists of these c(GD)−1c(G^D)-1 marked edges (possibly with parallel edges), note that its maximum degree is at most two. Indeed, suppose without loss of generality that a PP-side pp in UPU_P belongs to three marked bases (p,q1)(p,q_1), (p,q2)(p,q_2) and (p,q3)(p,q_3). Let (p,pi,qi,qi′)(p,p_i,q_i,q'_i) be the corresponding gadget and let UViUV_i be the associated HH-edge, for i=1,2,3i=1,2,3. Note that these are three distinct HH-edges, since we selected one gadget per tree edge. Then pip_i is a consecutive side of pp and belongs to ViV_i, for i=1,2,3i=1,2,3. But pp has only two consecutive sides.

It follows that the subgraph of marked bases consists of paths and even cycles (possibly 2-cycles). Therefore, its edge set can be partitioned into two matchings by picking every other edge in a path or a cycle. It follows that there is a matching M⊆E(GD)M \subseteq E(G^D) such that each of its (marked base) edges lies in UQU_Q or UPU_P and

∣M∣≥c(GD)−12.(3)|M| \ge\frac{c(G^D)-1}{2}. \tag*{(3)}

Finishing the proof. Let MQ⊆MM_Q \subseteq M (resp., MPM_P) denote the base edges in MM that belong to selected gadgets that are associated to edges of TQT_Q (resp., TPT_P). Set ∣MQ∣=k|M_Q| = k and ∣MP∣=t|M_P| = t. Considering the subgraph of UQU_Q that is induced by the endpoints of the edges in MQM_Q, it follows from Corollary 3.3 that its cycle rank is at least (k−12)≥2k−5\binom{k-1}{2} \ge2k - 5.4 Similarly, the cycle rank of the subgraph of UPU_P induced by the endpoints of the tt base edges in MPM_P is at least 2t−52t - 5. Since these two subgraphs are edge-disjoint and k+t=∣M∣k+t=|M|, it follows from Proposition 2.1 and (3) that μ(GD)≥2k−5+2t−5≥c(GD)−11\mu(G^D) \ge2k-5+2t-5 \ge c(G^D)-11 and by (2) we get that X≤mn−(m+n)+11X \le mn-(m+n)+11 as claimed.

More tools for proving the optimal bound

Before proving the optimal upper bound on XX in Section 5, we collect further useful claims.

Proposition 4.1. Let ℓ1,ℓ2,ℓ3\ell_1,\ell_2,\ell_3 be three lines in general position and let A\mathcal{A} denote their arrangement. Let Δ\Delta be the single (triangular) bounded face of A\mathcal{A} and let v1v2v_1v_2 be an edge of Δ\Delta. For i=1,2i=1,2, let sis_i be a straight-line segment with one endpoint in the unbounded face whose intersection with Δ\Delta is viv_i and its other endpoint lies in the unbounded face whose intersection with Δ\Delta is its edge opposite to viv_i.5 If each of s1s_1 and s2s_2 crosses v1v2v_1v_2, then s1s_1 and s2s_2 cross each other.

Proof. By applying an appropriate affine transformation we may assume without loss of generality that ℓ1\ell_1 is the xx-axis, ℓ2\ell_2 is the yy-axis, ℓ3\ell_3 is the line x+y=1x+y=1, v1=(0,0)v_1=(0,0) and v2=(1,0)v_2=(1,0). We denote the unbounded faces by F1,…,F6F_1,\ldots,F_6 in clockwise manner, such that F1F_1 shares the edge v1v2v_1v_2 with Δ\Delta. We may assume that the endpoints of s1s_1 lie in F2F_2 and F5F_5 and the endpoints of s2s_2 lie in F3F_3 and F6F_6. See Figure 6. Following s1s_1 from its endpoint in F2F_2 it enters Δ\Delta at a crossing point with v1v2v_1v_2, denote it by (α,0)(\alpha,0), 0<α<10<\alpha<1. Similarly, following s2s_2 from its endpoint in F6F_6 it enters Δ\Delta at a crossing point with v1v2v_1v_2, denote it by (β,0)(\beta,0), 0<β<10<\beta<1. If α=β\alpha=\beta, then s1s_1 and s2s_2 cross at (α,0)(\alpha,0). If β<α\beta<\alpha, then s1s_1 and s2s_2 must cross inside F1F_1, since their crossing points with its boundary alternate. Otherwise, if β>α\beta>\alpha, then s1s_1 and s2s_2 must cross inside Δ\Delta since their crossing points with its boundary alternate. □

Figure 6. An illustration for the proof of Proposition 4.1: If s1s_1 crosses v1v2v_1v_2 and its endpoints are in F2F_2 and F5F_5 and s2s_2 crosses v1v2v_1v_2 and its endpoints are in F3F_3 and F6F_6, then s1s_1 and s2s_2 cross.

Definition 4.2 (near edges). Let GG be a graph and let e1e_1 and e2e_2 be two distinct edges in GG. We say that e1e_1 and e2e_2 are near, if they share a vertex or there is an edge between an endpoint of e1e_1 and an endpoint of e2e_2.

Thus, Lemma 3.2 shows that there are near bases provided certain assumptions hold. The following will be useful later on.

Proposition 4.3. In a tree TT:

(a) For every non-empty set of pairwise near edges in TT, there is an edge (a,b)(a,b) such that every edge in the set has aa or bb as an endpoint. In particular TT has no three pairwise near edges that form a matching; and

(b) if e1e_1 and e2e_2 are two non-near edges, then a non-empty set of edges that are near each of e1e_1 and e2e_2 forms a star.

Proof. Let SS be a set of pairwise near edges in TT. If every pair of edges shares a vertex, then SS is a star (it cannot be a triangle), and we can pick any edge in SS as (a,b)(a,b). Otherwise, let e1e_1 and e2e_2 be vertex-disjoint edges and let (a,b)(a,b) be the edge connecting them. Suppose that there is an edge e3∈Se_3 \in S with no endpoint in {a,b}\{a,b\}. Considering the connected components of T∖{(a,b)}T \setminus\{(a,b)\}, e3e_3 belongs to one of them which does not contain at least one of e1e_1 and e2e_2, since they belong to different components. Assume without loss of generality that e3e_3 and e1e_1 belong to different components. Then a path connecting them in TT must go through (a,b)(a,b) but only one of them is incident to this edge. Therefore e1e_1 and e3e_3 are not near.

As for the second part of the claim, consider the unique path in TT connecting e1e_1 and e2e_2 and let vv be a vertex on this path which is not an endpoint of any of them (there must be such a vertex since e1e_1 and e2e_2 are not near). We claim that every edge which is near both e1e_1 and e2e_2 must have vv as an endpoint. Indeed, suppose that there is an edge ee which is near both e1e_1 and e2e_2 and vv is not one of its endpoints. Considering the connected components of T∖{v}T \setminus\{v\}, ee belongs to one of them which does not contain at least one of e1e_1 and e2e_2, since they belong to different components. Assume without loss of generality that ee and e1e_1 belong to different components. Then a path connecting them in TT must go through vv and therefore they are not near edges. □\square

By Lemma 3.2 two side-disjoint gadgets spanning three connected components must be of different pure types or force an edge between their base edges in their common connected component. The following claim complements this by showing that if the gadgets are both pure, then they do not share sides.

Proposition 4.4. Let g1=(p1,p1′,q1,q1′)g_1=(p_1,p'_1,q_1,q'_1) and g2=(p2,p2′,q2,q2′)g_2=(p_2,p'_2,q_2,q'_2) be two gadgets and let U,L1,L2U,L_1,L_2 be three distinct connected components of GDG^D such that (pi,qi)(p_i,q_i) lies in UU and (pi′,qi′)(p'_i,q'_i) lies in LiL_i, for i=1,2i=1,2. Then:

if p1=p2p_1=p_2, then both gadgets are QQ-hooking and at least one is also PP-hooking;

if q1=q2q_1=q_2, then both gadgets are PP-hooking and at least one is also QQ-hooking; and

if p1=p2p_1=p_2 and q1=q2q_1=q_2, then both are double.

Consequently, if g1g_1 and g2g_2 are pure, then their bases in UU are vertex-disjoint.

Proof. Suppose that p1=p2=pp_1=p_2=p. Apply an affine transformation of the plane such that the triangle whose vertices are p∩p1′p\cap p'_1, p∩q1′p\cap q'_1 and p1′∩q1p'_1\cap q_1 is mapped to the triangle whose vertices are (0,0)(0,0), (1,0)(1,0) and (0,1)(0,1), respectively. Note that if a point xx lies in a convex cone yy, then the image of yy is a convex cone and the image of xx lies in it. Therefore, intersections and hooking-types remain the same under this transformation.

We first claim that no gadget is PP-pure. Suppose without loss of generality that g1g_1 is PP-pure. Since g1g_1 is PP-hooking, q1∩q1′∈Cone⁡(p,p1′)q_1\cap q'_1\in\operatorname{Cone}(p,p'_1). Since g1g_1 is not QQ-hooking q1∩q1′q_1\cap q'_1 must lie inside the triangle whose corners are p∩p1′p\cap p'_1, p∩q1′p\cap q'_1 and p1′∩q1p'_1\cap q_1, see Figure 7. However, then p∩p2′∈Cone⁡(q1,q1′)p\cap p'_2\in\operatorname{Cone}(q_1,q'_1) which implies that p2′p'_2 cannot cross both q1q_1 and q1′q'_1 by Observation 2.3. Thus, p2′∈Up'_2\in U or p2′∈L1p'_2\in L_1, a contradiction.

Figure 7. An illustration for the proof of Proposition 4.4: If p1=p2=pp_1=p_2=p and g1g_1 is PP-pure, then p2′p'_2 cannot cross both q1q_1 and q1′q'_1.

Therefore, both gadgets are QQ-hooking and it remains to show that at least one of them is also PP-hooking. Suppose that both of them are QQ-pure. We proceed by considering whether p2′p'_2 lies above or below the xx-axis and whether it has a positive or negative slope. Consider the arrangement determined by the three lines through pp, p1′p'_1 and p2′p'_2: it contains one bounded triangular face, denote it by Δ\Delta, and six unbounded faces. Denote these unbounded faces by F1,…,F6F_1,\ldots,F_6 according to their clockwise order and such that F1F_1 has pp as one of its bounding edges.

  • Suppose that p2′p'_2 lies below the xx-axis and has a negative slope, see Figure 8a. Then Cone⁡(p,p1′)=F2\operatorname{Cone}(p,p'_1)=F_2 and q1∩q1′q_1\cap q'_1 must lie in this face by Observation 2.5 since g1g_1 is QQ-pure. However, then q1∩q1′∈Cone⁡(p,p2′)q_1\cap q'_1\in\operatorname{Cone}(p,p'_2) which implies by Observation 2.3 that q1′q'_1 cannot cross both pp and p2′p'_2, as it should.

Illustrations for the proof of Proposition 4.4: $p'_2$ lies below the $x$-axis

Figure 8. (a) If p2′p'_2 has a negative slope, then q1∩q1′∈Cone⁡(p,p2′)q_1 \cap q'_1 \in\operatorname{Cone}(p,p'_2) and therefore q1′q'_1 cannot cross both pp and p2′p'_2. (b) If p2′p'_2 has a positive slope, then q2∩q2′∈Cone⁡(p,p1′)q_2 \cap q'_2 \in\operatorname{Cone}(p,p'_1) and therefore q2′q'_2 cannot cross both pp and p1′p'_1. Figure 8: Illustrations for the proof of Proposition 4.4: p2′p'_2 lies below the xx-axis.

  • Suppose that p2′p'_2 lies below the xx-axis and has a positive slope, see Figure 8b. Then Cone⁡(p,p2′)=F2\operatorname{Cone}(p,p'_2)=F_2 and q2∩q2′q_2\cap q'_2 must lie in this face by Observation 2.5 since g2g_2 is QQ-pure. However, then q2∩q2′∈Cone⁡(p,p1′)q_2\cap q'_2\in\operatorname{Cone}(p,p'_1) which implies that q2′q'_2 cannot cross both pp and p1′p'_1, as it should.

  • Suppose that p2′p'_2 lies above the xx-axis and has a positive slope, see Figure 9a. Since g1g_1 is QQ-pure, q1∩q1′∈Cone⁡(p,p1′)=F4∪F5q_1\cap q'_1\in\operatorname{Cone}(p,p'_1)=F_4\cup F_5 by Observation 2.5. Because q1′q'_1 crosses pp and p2′p'_2, it follows that q1′q'_1 has one endpoint in F5F_5 and its other endpoint in F2F_2. Similarly, since g2g_2 is QQ-pure, q2∩q2′∈Cone⁡(p,p2′)=F4∪F3q_2\cap q'_2\in\operatorname{Cone}(p,p'_2)=F_4\cup F_3. Because q2′q'_2 crosses pp and p1′p'_1, it follows that q2′q'_2 has one endpoint in F3F_3 and its other endpoint in F6F_6. However, then q1′q'_1 and q2′q'_2 cross by Proposition 4.1, which is impossible.

Figure 9. (a) p2′p'_2 has a positive slope. (b) p2′p'_2 has a negative slope. Figure 9: Illustrations for the proof of Proposition 4.4: p2′p'_2 lies above the xx-axis.

  • Suppose that p2′p'_2 lies above the xx-axis and has a negative slope, see Figure 9b. Since g1g_1 is QQ-pure, q1∩q1′∈Cone⁡(p,p1′)=F2q_1 \cap q'_1 \in\operatorname{Cone}(p,p'_1) = F_2 by Observation 2.5. Because q1′q'_1 crosses pp and p2′p'_2, it follows that q1′q'_1 has its other endpoint in F5F_5. Similarly, since g2g_2 is QQ-pure, q2∩q2′∈Cone⁡(p,p2′)=F6q_2 \cap q'_2 \in\operatorname{Cone}(p,p'_2) = F_6. Because q2′q'_2 crosses pp and p1′p'_1, it follows that q2′q'_2 has its other endpoint in F3F_3. However, then q1′q'_1 and q2′q'_2 cross by Proposition 4.1, which is impossible.

This concludes the case that p1=p2p_1 = p_2. The case that q1=q2q_1 = q_2 is symmetric, and the case that p1=p2p_1 = p_2 and q1=q2q_1 = q_2 follows from the two previous cases. It also follows that if g1g_1 and g2g_2 are pure, then p1≠p2p_1 \ne p_2 and q1≠q2q_1 \ne q_2.

Next, we establish further properties of the transition graph HH.

Proposition 4.5. For every partition of the nodes of HH into two disjoint subsets AA and BB such that ∣A∣≥2|A| \ge2 and ∣B∣≥1|B| \ge1 there are two gadgets crossing the cut with vertex-disjoint bases in AA.

Proof. Observe first that there cannot be just one QQ-side in a component from AA that is part of every gadget crossing the cut. Indeed, suppose that there is such a side qq and let V1∈AV_1 \in A be the connected component of GDG^D that contains qq. By deleting qq from QQ, we get a path. Therefore, if we construct HH using this path instead of QQ, then we would still get a connected graph, apart from possibly V1V_1 which might be an isolated node. Since ∣A∣≥2|A| \ge2, it follows that there are a side in AA and a side in BB that are consecutive along the path and therefore by Lemma 2.4 belong to a gadget crossing the cut. Similarly, there cannot be just one PP-side in a component from AA that is part of every gadget crossing the cut, since constructing the transitions graph with respect to PP results in the same graph. Considering the HH-edges crossing the cut and base edges in components from AA that belong to corresponding gadgets, we have a bipartite graph such that each of its classes (sides of QQ and PP) contains at least two vertices and every vertex has degree at least one. Such a bipartite graph has a matching of size two, that is, two vertex-disjoint bases in AA.

Definition 4.6. Let UU be a node of HH and let SS be a set of gadgets associated with HH-edges E(S)⊆E(H)E(S) \subseteq E(H) adjacent to UU. We say that SS is admissible (with respect to UU) if each edge e∈E(S)e \in E(S) is associated with at most two gadgets in SS and if ee is associated with exactly two gadgets in SS, then their bases in UU are vertex-disjoint.

Proposition 4.7. Let UU be a node in HH and let SS be an admissible set of gadgets with respect to UU. Then ∣S∣≤2μ(U)+7|S| \leq2\mu(U) + 7. Furthermore, if all gadgets in SS are pure of the same type, then ∣S∣≤μ(U)+3|S| \leq\mu(U) + 3.

Proof. Suppose first that μ(U)=0\mu(U) = 0, that is, UU is a tree. Let SQS_Q denote the QQ-hooking gadgets in SS and let BQB_Q denote their bases in UU, where a base may appear with multiplicity in BQB_Q if it belongs to several gadgets in SQS_Q. Let dQd_Q denote the maximum vertex degree in the subgraph of UU consisting of the base edges in BQB_Q. Then dQ≤2d_Q \leq2: Firstly, by admissibility a vertex cannot belong to two bases of two gadgets on the same HH-edge. Secondly, if a vertex (polygon-side) belongs to three bases of gadgets on different HH-edges, then a polygon-side incident to it must belong to the other nodes (components) of these edges. But that is impossible since a polygon-side has just two incident sides. Now, if all the gadgets in SQS_Q are QQ-pure, then it follows from admissibility and Proposition 4.4 that BQB_Q is a matching, that is, dQ≤1d_Q \leq1. If the bases in BQB_Q are pairwise near, then by Proposition 4.3 there is an edge in UU that is incident to all of them. This implies that ∣SQ∣=∣BQ∣≤2dQ|S_Q| = |B_Q| \leq2d_Q, because at most dQd_Q bases are incident to each endpoint of that edge. Otherwise, if there is a pair of non-near bases in BQB_Q, then it follows from Lemma 3.2 that they must belong to two gadgets associated with the same HH-edge. Furthermore, by this lemma every other base in BQB_Q must be near each of these two bases. Therefore, by Proposition 4.3 all the other bases in BQB_Q must form a star which implies that there are at most dQd_Q such bases. Therefore, ∣SQ∣=∣BQ∣≤2+dQ|S_Q| = |B_Q| \leq2 + d_Q in this case. If all the gadgets in SQS_Q are QQ-pure, then recall that dQ≤1d_Q \leq1 and therefore ∣SQ∣=∣BQ∣≤max⁡{2dQ,2+dQ}=3|S_Q| = |B_Q| \leq\max\{2d_Q, 2 + d_Q\} = 3. Otherwise, if dQ=2d_Q = 2 then ∣SQ∣≤4|S_Q| \leq4.

Let SPS_P denote the PP-hooking gadgets in SS and let dPd_P denote the maximum vertex-degree is the subgraph of UU consisting of their corresponding base edges in UU. Clearly, the same arguments apply to SPS_P, therefore if all the gadgets in SS are pure of the same type, then ∣S∣≤3|S| \leq3.

It remains to consider the case that not all gadgets are pure of the same type. If there is at least one double gadget, then ∣S∣≤∣SQ∣+∣SP∣−1≤7|S| \leq|S_Q| + |S_P| - 1 \leq7. Otherwise, if all the gadgets are pure but not of the same type, then ∣S∣=∣SQ∣+∣SP∣≤3+3<7|S| = |S_Q| + |S_P| \leq3 + 3 < 7. This concludes the case that UU is a tree.

Suppose now that μ(U)>0\mu(U) > 0 and let TT be a spanning tree of UU. Clearly, UU contains μ(U)\mu(U) edges not in TT. For each such edge choose one of its endpoints and discard from SS any gadget that contains this endpoint. Denote by S′S' the set of remaining gadgets. Note that, as above, every vertex belongs to at most two gadgets in SS, thus, at most 2μ(U)2\mu(U) gadgets are discarded. Furthermore, if all the gadgets are pure, then every vertex belongs to at most one gadget in SS and therefore at most μ(U)\mu(U) gadgets are discarded. We would like to apply the above arguments to conclude that ∣S′∣≤7|S'| \leq7 (and ∣S′∣≤3|S'| \leq3, if all gadgets are pure of the same type). Clearly, S′S' is admissible. Note that S′S' also satisfies the nearness relations. Indeed, if the deleted edge (u,v)(u,v) was a witness of two near bases, then one of them is incident to uu, thus, the corresponding gadget and base were discarded.

It follows from the discussion above that ∣S′∣≤7|S'| \leq7 and therefore ∣S∣≤2μ(U)+7|S| \leq2\mu(U) + 7. If all the gadgets in SS are pure of the same type, then every vertex belongs to at most one gadget and therefore at most μ(U)\mu(U) gadgets are discarded and at most three survive. Thus, ∣S∣≤μ(U)+3|S| \le\mu(U) + 3 in this case.

Proposition 4.8. A connected component UU contains a cycle if:

(a) there are three pure same-type gadgets associated with three HH-edges connecting UU to three distinct components; or

(b) UU has two distinct neighbors V1V_1 and V2V_2 in HH, there are two gadgets associated with UV1UV_1 whose bases in UU are vertex-disjoint, there are two gadgets associated with UV2UV_2 whose bases in UU are vertex-disjoint, and these four gadgets are pure of the same type.

Proof. Suppose that (a) holds. Then by Proposition 4.4 those gadgets have three vertex-disjoint edge bases in UU. Therefore by Lemma 3.2 these base edges are pairwise near and it follows from Proposition 4.3 that UU is not a tree.

Suppose now that (b) holds. Considering the four corresponding bases in UU, it follows from the assumption and Proposition 4.4 that they are pairwise vertex-disjoint. By Lemma 3.2 there is an edge of GDG^{\mathrm{D}} between each of the two bases that corresponds to UV1UV_1 and each of the two bases that corresponds to UV2UV_2. Therefore, by contracting the four bases we obtain a copy of K2,2K_{2,2}. Thus, μ(U)≥1\mu(U) \ge1.

Summarizing the properties of HH. Before proceeding to the proof of the optimal bound, we summarize the main properties of the transitions graph HH for convenience and future reference. Recall that every node of HH corresponds to a bipartite graph. Every edge UVUV of HH is associated with at least one ‘gadget’: two pairs of adjacent vertices (‘bases’ of the gadget), one from UU and the other from VV. Each such gadget has at least one of the labels {Q,P}\{Q, P\}. If it has both labels, then we call it ‘double’ and otherwise it is ’pure’. The following summarizes Lemma 3.1, Lemma 3.2, Proposition 4.4 and Proposition 4.5.

HH satisfies the following properties:

  1. There are no two node-disjoint HH-edges associated with two gadgets sharing a label.

  1. Consequently, for each label the HH-edges associated with gadgets of this label form a star or a triangle.

  1. If two gadgets with the same label are associated with two HH-edges UVUV and UZUZ (V≠ZV \ne Z), then their bases in UU are near. If both gadgets are pure, then their bases are vertex-disjoint and therefore are connected by an edge of UU.

  1. For every partition of the nodes of HH into two disjoint subsets AA and BB such that ∣A∣≥2|A| \ge2 and ∣B∣≥1|B| \ge1 there are two gadgets crossing the cut with vertex-disjoint bases in AA.

The optimal bound X≤mn−(m+n)+3X \le mn - (m+n) + 3

Recall that it is enough to show that c(GD)−μ(GD)≤4c(G^{\mathrm{D}}) - \mu(G^{\mathrm{D}}) \le4. Therefore, we may assume that c(GD)−μ(GD)≥5c(G^{\mathrm{D}}) - \mu(G^{\mathrm{D}}) \ge5 and in particular c(GD)≥5c(G^{\mathrm{D}}) \ge5. We consider the transitions graph HH and denote by HQH_Q (resp., HPH_P) the subgraph of HH that consists of HH-edges associated with QQ-hooking (resp., PP-hooking) gadgets. Recall that it follows from Lemma 3.1 that each of these subgraphs is either a triangle or a star (ignoring isolated nodes). We proceed by considering the possible cases.

Case 1. At least one of HQH_Q and HPH_P is a star. Suppose without loss of generality that HQH_Q is a star whose center is UQU_Q. Then HPH_P is either a triangle or a star.

Subcase 1.1. HPH_P is a triangle. Since HH is connected, HQH_Q and HPH_P share at least one node. There are four possible cases: either UQU_Q is one node of the triangle HPH_P (see Figure 10(a)), or UQU_Q is not a node of the triangle HPH_P and there are exactly ii leaves in HQH_Q that belong to HPH_P, for i=1,2,3i = 1,2,3 (see Figure 10(b)–(Figure 10d)). In the first case, UQU_Q is connected to c(GD)−3c(G^D)-3 leaves that do not belong to HPH_P. For each such leaf LL we apply Proposition 4.5 on the cut (V(H)∖{L},{L})(V(H)\setminus\{L\},\{L\}) and obtain two QQ-pure gadgets with disjoint bases in UQU_Q. This results in an admissible set SS of 2(c(GD)−3)2(c(G^D)-3) QQ-pure gadgets that satisfies the properties in Proposition 4.7. Therefore, 2(c(GD)−3)=∣S∣≤μ(UQ)+3≤μ(GD)+3≤c(GD)−5+32(c(G^D)-3)=|S|\leq\mu(U_Q)+3\leq\mu(G^D)+3\leq c(G^D)-5+3. However, this implies that c(GD)≤4c(G^D)\leq4.

Figure 10. If HQH_Q is a star and HPH_P is a triangle then either (a) the center of the star UQU_Q belongs to HPH_P; or (b)–(d) exactly ii of its leaves in HQH_Q belong to HPH_P, for i=1,2,3i = 1,2,3.

Otherwise, suppose that UQU_Q does not belong to HPH_P (see Figure 10(b)–(Figure 10d)). Then by applying Proposition 4.5 on the cut (V(H)∖{L},{L})(V(H)\setminus\{L\},\{L\}) for each leaf LL from the c(GD)−4c(G^D)-4 leaves in HQH_Q that do not belong to HPH_P and also for the cut (V(H)∖V(HP),V(HP))(V(H)\setminus V(H_P),V(H_P)), we again obtain an admissible set of 2(c(GD)−3)2(c(G^D)-3) QQ-pure gadgets and conclude that c(GD)≤4c(G^D)\leq4 as above.

Subcase 1.2. HPH_P is a star whose center is UQU_Q. In this case HH is a star with center UQU_Q and c(GD)−1c(G^D)-1 leaves. For a leaf LL we apply Proposition 4.5 on the cut (V(H)∖{L},{L})(V(H)\setminus\{L\},\{L\}), and obtain two gadgets with disjoint bases in UQU_Q. By repeating this for each of the c(GD)−1c(G^D)-1 leaves, we obtain an admissible set SS of 2(c(GD)−1)2(c(G^D)-1) gadgets that satisfies the properties in Proposition 4.7. Note that these gadgets are not necessarily pure. Therefore, 2(c(GD)−1)=∣S∣≤2μ(UQ)+7≤2μ(GD)+7≤2(c(GD)−5)+7=2c(GD)−32(c(G^D)-1)=|S|\leq2\mu(U_Q)+7\leq2\mu(G^D)+7\leq2(c(G^D)-5)+7=2c(G^D)-3, which is impossible.

Subcase 1.3. HPH_P is a star with center UP≠UQU_P\ne U_Q. Each of the c(GD)−2c(G^D)-2 other components is adjacent to UQU_Q, UPU_P, or both. For each such component V≠UQ,UPV\ne U_Q,U_P we apply Proposition 4.5 on the cut (V(H)∖{V},{V})(V(H)\setminus\{V\},\{V\}) and obtain two gadgets with disjoint bases in UQ∪UPU_Q\cup U_P. Note that each of these gadgets is either QQ-pure or PP-pure. Denote by nQn_Q and nPn_P the number of those gadgets, respectively. Then nQ+nP=2(c(GD)−2)n_Q+n_P=2(c(G^D)-2). Applying Proposition 4.7 on UQU_Q and the subset of those QQ-pure gadgets, we get that nQ≤μ(UQ)+3n_Q\leq\mu(U_Q)+3. Similarly, we have nP≤μ(UP)+3n_P\leq\mu(U_P)+3. Thus we have,

2(c(GD)−2)=nQ+nP≤μ(UQ)+3+μ(UP)+3≤μ(GD)+6≤c(GD)−5+6,(4)2(c(G^D)-2)=n_Q+n_P\leq\mu(U_Q)+3+\mu(U_P)+3\leq\mu(G^D)+6\leq c(G^D)-5+6, \tag*{(4)}

which implies that c(GD)≤5c(G^D)\leq5. Since we assumed that c(GD)≥5c(G^D)\geq5, it remains to consider the case that GDG^D contains exactly five connected components.

Suppose that c(GD)=5c(G^D)=5 and let V1,V2,V3V_1,V_2,V_3 be the other connected components of GDG^D apart from UQU_Q and UPU_P. We may further assume that μ(UQ)=μ(UP)=μ(GD)=0\mu(U_Q)=\mu(U_P)=\mu(G^D)=0 and that (4) holds with equality, for otherwise we immediately get c(GD)−μ(GD)<5c(G^D)-\mu(G^D)<5 and we are done. Thus, nQ+nP=6n_Q+n_P=6 and therefore nQ=nP=3n_Q=n_P=3 (because nx≤μ(Ux)+3=3n_x\leq\mu(U_x)+3=3, for x∈{P,Q}x\in\{P,Q\}).

Recall that for every i=1,2,3i=1,2,3, exactly two of those six gadgets have one base in ViV_i, the other base in UQU_Q or UPU_P, and if both gadgets are associated with the same HH-edge, then their bases in the star-center are disjoint. Observe first that it follows from the first part of Proposition 4.8 that it is impossible to have three gadgets associated with the three edges UQV1,UQV2,UQV3U_QV_1,U_QV_2,U_QV_3, since this would imply that μ(UQ)≥1\mu(U_Q)\ge1. By the second part of Proposition 4.8 it is also impossible that two of these gadgets are over UQViU_QV_i and two others are over UQVjU_QV_j, for i≠ji\ne j. Applying the same arguments for UPU_P, we conclude that, without loss of generality, there are two gadgets over each of UQV1U_QV_1 and UPV3U_PV_3 and one gadget over each of UQV2U_QV_2 and UPV2U_PV_2 (see Figure 11).

Figure 11. An illustration for Subcase 1.3: c(GD)=5c(G^{\mathrm{D}})=5, UQU_Q is connected by two QQ-pure gadgets to V1V_1, by a QQ-pure gadget to V2V_2, and by a double gadget to UPU_P. UPU_P is also connected by two PP-pure gadgets to V3V_3 and by a PP-pure gadget to V2V_2.

By applying Proposition 4.5 on the cut {{UQ,V1,V2},{UP,V3}}\{ \{U_Q,V_1,V_2\},\{U_P,V_3\} \}, it follows that there must be another HH-edge crossing this cut except UPV2U_PV_2. Such an edge can only be UQUPU_QU_P (see Figure 11). Note that no gadget associated with this edge can be pure. Indeed, if it is QQ-pure, then considering pure gadgets between UQU_Q and each of V1V_1, V2V_2 and UPU_P, it follows that μ(UQ)≥1\mu(U_Q)\ge1 by the first part of Proposition 4.8. Similarly, UQUPU_QU_P cannot be associated with a PP-pure gadget. Let e1e_1 and e1′e'_1 be vertex-disjoint bases in UQU_Q from QQ-pure gadgets associated with UQV1U_QV_1, and let e2e_2 be a base in UQU_Q from a QQ-pure gadget associated with UQV2U_QV_2. Note that e2e_2 does not share vertices with e1e_1 and e1′e'_1 by Proposition 4.4, and that there are edges connecting e2e_2 to both of e1e_1 and e1′e'_1 by Lemma 3.2. Therefore e1e_1 and e1′e'_1 are not connected by an edge, for otherwise we could contract e1e_1, e1′e'_1 and e2e_2 and get a 3-cycle implying μ(UQ)≥1\mu(U_Q)\ge1.

Consider now the cut {{UQ,V1},{UP,V2,V3}}\{ \{U_Q,V_1\},\{U_P,V_2,V_3\} \}. Every gadget that crosses this cut is either a QQ-pure gadget associated with UQV2U_QV_2 or a double gadget associated with UQUPU_QU_P. By Lemma 3.2 the base edge in UQU_Q of such gadgets must be near each of e1e_1 and e1′e'_1. It follows from Proposition 4.3(b) that these base edges form a star. However, this contradicts Proposition 4.5 by which there should be two vertex-disjoint base edges in UQU_Q that belong to two gadgets crossing this cut.

Case 2. Both HQH_Q and HPH_P are triangles. Since H=HQ∪HPH=H_Q\cup H_P is connected, it follows that c(GD)≤5c(G^{\mathrm{D}})\le5. Recalling the assumption that c(GD)≥5c(G^{\mathrm{D}})\ge5, we may assume that the two triangles share exactly one node, denote it by UU. Let V1V_1 and V2V_2 be the other nodes of HQH_Q and let V3V_3 and V4V_4 be the other nodes of HPH_P. Note that since no HH-edge belongs to both HQH_Q and HPH_P, it follows that every gadget associated with the six edges of HH is pure. We may also assume that each of the five connected components of GDG^{\mathrm{D}} is a tree, for otherwise μ(GD)≥1\mu(G^{\mathrm{D}})\ge1 and we are done.

Let SiS_i be the set of endpoints of base edges in UU of gadgets that are associated with UViUV_i, for i=1,2,3,4i=1,2,3,4. It follows from Proposition 4.4 that Si∩Sj=∅S_i\cap S_j=\varnothing for i≠ji\ne j. By Lemma 3.2, each of the subgraphs of UU induced by S1∪S2S_1\cup S_2 and S3∪S4S_3\cup S_4 is connected. Recall that UU is a tree, hence there is a unique path connecting the subtrees U[S1∪S2]U[S_1\cup S_2] and U[S3∪S4]U[S_3\cup S_4]. Let q∗q^* be a QQ-side that corresponds to a vertex on this path. See Figure 12 for an illustration.

Figure 12. An illustration for Case 2: HQH_Q and HPH_P are two triangles sharing exactly one node UU.

Omitting q∗q^* from QQ, we obtain a sequence of n−1n-1 QQ-sides. Some of them belong to V1∪V2V_1\cup V_2 and some to V3∪V4V_3\cup V_4, as every connected component of GDG^{\mathrm{D}} contains sides of both polygons and we omitted a side from UU. Recall that transitions along this sequence between sides that belong to different connected components correspond to HH-edges. Since there are no transitions between {V1,V2}\{V_1,V_2\} and {V3,V4}\{V_3,V_4\}, it follows that there is a subsequence of consecutive QQ-sides q1′,…,qk′q'_1,\ldots,q'_k such that each of them belongs to UU, q1′∈S1∪S2q'_1 \in S_1 \cup S_2, qk′∈S3∪S4q'_k \in S_3 \cup S_4, the side before q1′q'_1 belongs to V1∪V2V_1 \cup V_2 and the side after qk′q'_k belongs to V3∪V4V_3 \cup V_4 (we may assume that this is the order without loss of generality, since we can reverse the sequence of sides if needed).

We claim that for every i=1,…,k−1i = 1,\ldots,k-1, there is a side of PP that is disjoint from both qi′q'_i and qi+1′q'_{i+1}. Indeed, suppose that there is no PP-side that is disjoint from both qi′q'_i and qi+1′q'_{i+1}. Then, it follows from Lemma 2.4 that qi′q'_i and qi+1′q'_{i+1} are part of a gadget gg. Because qi′,qi+1′∈Uq'_i,q'_{i+1} \in U, all the sides of gg belong to UU. Since there is a QQ-pure gadget associated with V1V2V_1V_2 and its sides are disjoint from those of gg, it follows from Lemma 2.7 that gg is not QQ-hooking. Similarly, since there is a PP-pure gadget associated with V3V4V_3V_4 it follows that gg is also not PP-hooking, a contradiction.

Therefore, for every i=1,…,k−1i = 1,\ldots,k-1, there is a PP-side pi′p'_i (in UU) such that (qi′,pi′),(qi+1′,pi′)∈E(GD)(q'_i,p'_i),(q'_{i+1},p'_i) \in E(G^D). Thus, there is a path between S1∪S2S_1 \cup S_2 and S3∪S4S_3 \cup S_4, which avoids qk∗q^*_k, a contradiction. Hence, UU is not a tree and we are done.

The gap in the proof of the upper bound X≤mn−(m+n)+CX \le mn-(m+n)+C in [1]

For the proof of the upper-bound in [1] one assumes that there are more than CC connected components in GDG^D, where C<2270C < 2^{2^{70}} is a huge constant. Using Ramsey theory and Lemma 2.7 it then follows that there are six pairwise side-disjoint QQ-hooking gadgets (Ai,Bi,ai,bi)(A_i, B_i, a_i, b_i), i=1,2,…,6i = 1, 2, \ldots, 6, with the following properties (some are implied by the other):

  • The lines ℓi\ell_i containing the sides aia_i form a 6-cap such that the slope of ℓi\ell_i is greater than the slope of ℓj\ell_j for every i<ji < j;

  • the sides aia_i are pairwise disjoint and ℓi∩ℓj\ell_i \cap\ell_j lies on aja_j, for every i<ji < j;

  • aia_i and bib_i belong to different connected components of GDG^D for every ii;

  • aia_i and aja_j belong to different connected components of GDG^D for every i≠ji \ne j;

  • bib_i and bjb_j belong to the same connected component of GDG^D for every ii and jj;

  • AiA_i crosses aja_j for every i≠ji \ne j;

  • AiA_i crosses bjb_j for every ii and jj; and

  • BiB_i crosses aja_j for every ii and jj.

The proof proceeds by a case-analysis resulting in a contradiction in every case. In Case 2, one assumes that for 1≤i≤41 \le i \le4 the side AiA_i does not cross ℓi\ell_i to the left of aia_i. Then one considers the four possible subcases depending on whether a3∩b3a_3 \cap b_3 is the left or right endpoint of a3a_3 and whether A3∩B3A_3 \cap B_3 is the left or right endpoint of A3A_3. In Subcase 2.2 a3∩b3a_3 \cap b_3 is the left endpoint of a3a_3 and A3∩B3A_3 \cap B_3 is the left endpoint of A3A_3. The side a1a_1 crosses both A3A_3 and B3B_3, which partition it into three parts. It is then claimed that if A2A_2 intersects the middle part of a1a_1 (between a1∩A3a_1 \cap A_3 and a1∩B3a_1 \cap B_3), then A2A_2 cannot cross both a3a_3 and b3b_3 in the wedge determined by a3a_3 and b3b_3. That is true if b3b_3 crosses A3A_3 between A3∩a1A_3 \cap a_1 and A3∩a4A_3 \cap a_4, as is assumed implicitly by the accompanying figure (see Figure 13a). However, it is possible that b3b_3 crosses A3A_3 between A3∩a2A_3 \cap a_2 and A3∩a1A_3 \cap a_1, and then A2A_2 may cross both a3a_3 and b3b_3 inside the above-mentioned wedge, see Figure 13b and Figure 14.

Figure 13. (a) b3b_3 is implicitly assumed to cross A3A_3 between A3∩a1A_3 \cap a_1 and A3∩a4A_3 \cap a_4. (b) the case that b3b_3 crosses A3A_3 between A3∩a2A_3 \cap a_2 and A3∩a1A_3 \cap a_1 is not handled. Figure 13: The gap in the proof of the upper bound in [1].

Figure 14. A realization of the omitted case in [1] by straight-line segments.

It seems that the gap in this case-analysis can be resolved by considering seven gadgets instead of six (thus taking a greater constant CC). However, since the current proof is simpler and gives a better upper bound, there is not much point in going into those technicalities.

References

  1. [1]Eyal Ackerman, Balázs Keszegh, and Günter Rote. An almost optimal bound on the number of intersections of two simple polygons. Discrete & Computational Geometry, 68(4):1049–1077, 2022. doi:10.1007/s00454-022-00438-0.DOI
  2. [2]J. Černý, J. Kára, D. Král’, P. Podbrdský, M. Sotáková, and R. Šámal. On the number of intersections of two polygons. Comment. Math. Univ. Carolinae, 44(2):217–228, 2003. URL: https://cmuc.karlin.mff.cuni.cz/cmuc0302/cmuc0302.htm.
  3. [3]Michael B. Dillencourt, David M. Mount, and Alan Saalfeld. On the maximum number of intersections of two polyhedra in 2 and 3 dimensions. In Proceedings of the 5th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, August 1993, pages 49–54. University of Waterloo, 1993.
  4. [4]Ju Yong Seo. The maximum number of intersections of two simple polygons with an odd number of sides: A computer-assisted proof of a conjecture of Ackerman, Keszegh and Rote, October 2026. Preprint. doi:10.5281/zenodo.23306693.

Paper details

vlnc:W_43xpjcct
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents