Shared triangular sides in pseudoline arrangements

Introduction

An affine pseudoline arrangement is a finite family of proper embedded copies of $\mathbb{R}$ in the plane, any two meeting exactly once and crossing at their intersection. At a multiple crossing the participating pseudolines have the local order of distinct straight lines. Throughout the paper, every crossing has multiplicity two or three.

An edge is a segment of a pseudoline between consecutive crossings. A triangle is a bounded face with exactly three edges. In particular, triangles containing further portions of the arrangement are not counted. An edge is shared if both incident faces are triangles, and it is a boundary edge if exactly one incident face is a triangle. Write $d$ for the number of shared edges and $t_3$ for the number of triple crossings.

Parpalak and Utkin [1 §5.2, (5.5)] ask whether $d \le3t_3$. Their discharging argument proves the weaker estimate $d \le\frac{9}{2}t_3$. We establish the proposed inequality.

The proof has two parts. First, charge from triple crossings pays for all shared-edge incidences on the normalized boundary of the triangular faces. Second, a four-pseudoline restriction supplies the remaining charge needed at double crossings surrounded by four triangles. Keeping the boundary-edge incidences distinct prevents any charge from being used twice. No assumption of stretchability is required.

In the notation of [1], for $n \ge2$ pseudolines let $a_3$ count triangles, let $u$ count bounded edges incident to no triangle, and put $w = n(n - 2) - 3a_3$. The edge-incidence identity $w = 3t_3 + u - d$ shows that Theorem 1.1 is equivalently the assertion $w \ge u$.

Local restrictions on shared edges

We recall two elementary observations from [1 Appendix C]. Their proofs are included for completeness.

Proof. Suppose that a shared edge $PQ$ lies on a pseudoline $\ell$ and that both endpoints are double. Let $a$ and $b$ be the other pseudolines through $P$ and $Q$, respectively. Each triangular face on $PQ$ must have its remaining sides on $a$ and $b$, and thus its third vertex at their unique intersection. The compact arcs between these three vertices are unique. They cannot bound two triangular faces on opposite sides of $PQ$, a contradiction. □

Proof. Let $P$ be the triple crossing, with incident edges $h_0,\ldots,h_5$ in cyclic order. Suppose that $h_0=PQ_0$ and $h_1=PQ_1$ are shared and that $Q_0,Q_1$ are double. Writing $Q_i$ for the other endpoint of $h_i$ when needed, the three consecutive triangular sectors are

Let $a$ contain $Q_0Q_1$. At the double crossing $Q_0$, the edges $Q_5Q_0$ and $Q_0Q_1$ both lie on the pseudoline other than the one containing $PQ_0$. Thus $Q_5\in a$. Similarly $Q_2\in a$. But $Q_5$ and $Q_2$ also lie on the pseudoline $b$ containing the opposite edges $h_5,h_2$, on opposite sides of $P$. The pseudolines $a$ and $b$ are distinct: the pseudoline containing $PQ_0$ meets $a$ at $Q_0$ and $b$ at $P$. Consequently $a$ and $b$ have two distinct intersections, which is impossible. □

Double crossings surrounded by four triangles

Proof. Let $P_0,P_1,P_2,P_3$ be the consecutive neighbors of $S$, with indices taken modulo four. The four triangular faces are $SP_iP_{i+1}$. All four spokes $SP_i$ are shared, so each $P_i$ is triple by Lemma 2.1. These neighbors are distinct: opposite ones lie on opposite sides of $S$ along a pseudoline, whereas adjacent ones cannot coincide because the two pseudolines through $S$ meet only at $S$.

Let $c_i$ be the pseudoline containing the opposite side $e_i=P_iP_{i+1}$. Adjacent $c_i$ are distinct, since at their common endpoint they are the two different pseudolines on either side of the spoke. Opposite $c_i$ cannot coincide, since that would make a single pseudoline intersect a pseudoline through $S$ at two opposite neighbors. The four $c_i$ are therefore distinct. None is a pseudoline through $S$.

Consider the subarrangement consisting of these four pseudolines. It is simple. Indeed, any three of them contain an adjacent pair, whose intersection is one of the $P_i$. At that point the spoke and the two adjacent outer pseudolines already account for three pseudolines. A further outer pseudoline through the point would contradict the bound on multiplicity.

Suppose that $e_i$ is shared, and consider its triangular face other than $SP_iP_{i+1}$. The six rays at a triple crossing occur in the order $a,b,c,a,b,c$. At $P_i$, the ray adjacent to $e_i$ on the first triangle’s side is the spoke. The ray adjacent on the other side therefore belongs to $c_{i-1}$. Likewise, the remaining side at $P_{i+1}$ belongs to $c_{i+1}$. Thus the additional triangle is bounded by precisely $c_{i-1},c_i,c_{i+1}$.

Deleting all other pseudolines preserves this triangle as a bounded triangular face: its interior was empty, and its three boundary segments had no intervening crossings. The additional triangles obtained from different $e_i$ are distinct, because their sets of three supporting pseudolines are distinct.

A simple arrangement of four affine pseudolines has eight bounded edges, two on each pseudoline. By Lemma 2.1, no edge of this subarrangement is shared by two triangles. It therefore has at most $\lfloor8/3\rfloor=2$ bounded triangular faces. At most two of the $e_i$ can be shared. Since all four already border triangles, the remaining at least two are boundary edges. □

:::

Vector (PDF)

The normalized triangular boundary

Glue the closures of all triangular faces along their shared edges. At any original crossing where different maximal consecutive fans of triangular sectors meet only at that crossing, separate the fans. This produces a finite union of compact surfaces with boundary. Holes are permitted and will not affect the argument.

A boundary occurrence of a crossing is a maximal fan of $i \ge1$ consecutive triangular sectors. It has two incident boundary edges and $i-1$ incident shared edges within the fan. An original crossing can give several boundary occurrences; these are always kept distinct. At a double boundary occurrence, $i \le3$. An interior crossing has all its incident sectors triangular: four at a double crossing and six at a triple crossing.

Proof. Call a double occurrence active if $i \ge2$. Two active double occurrences cannot be consecutive along the boundary. Otherwise, consider the triangle incident to their common boundary edge. Its other two sides are shared, since the fan at either active endpoint continues across the corresponding side. Its third vertex cannot be double by Lemma 2.1. If it is triple, the two sides violate Lemma 2.2.

A double occurrence with $i=1$ cannot have two double boundary neighbors unless its triangular component is a single isolated triangle. Indeed, its only triangle would have three double vertices, so none of its sides could be shared by Lemma 2.1. It would consequently be an entire component, after separating meetings at vertices.

A run between triple occurrences thus contains at most one active occurrence: two such occurrences would either be consecutive or have between them an inactive occurrence with two double neighbors. The only possible nonzero summand in (2) is therefore $i-1 \le2$.

If a whole boundary circuit consists of double occurrences, an inactive occurrence forces the isolated triangle just described. If there is no inactive occurrence, every occurrence is active, contrary to the first paragraph. In either case the stated conclusion follows.

Discharging and completion of the proof

Proof of Theorem 1.1. Give initial charge 6 to every triple crossing and charge 0 to every double crossing. We assign cost 1 to each endpoint incidence of a shared edge. The total cost is $2d$.

At an interior triple crossing, all six incident edges are shared, so its initial charge pays its cost exactly. At a boundary occurrence of a triple crossing with $i$ triangular sectors, allocate charge $i+1$. This allocation respects the original crossing’s budget. Indeed, if its triangular sectors form $r$ maximal fans containing $k$ sectors altogether, at least $r$ nontriangular sectors separate the fans. Hence

The shared edges within such a fan have total endpoint cost $i-1$. After paying this cost, exactly two units remain. Orient each normalized boundary circuit, and associate both remaining units with the outgoing boundary edge at the occurrence. Every boundary edge has a unique initial occurrence, so these edge charges are kept distinct.

A double boundary occurrence has cost $i-1$. For each run of double occurrences between successive triple occurrences, let $D=\sum(i-1)$. Lemma 4.1 gives $D\le2$. Pay this cost from the two units on the boundary edge entering the run from its preceding triple occurrence. Different runs use different entering edges. Circuits containing only double occurrences have zero cost.

All shared-edge costs at boundary occurrences have now been paid. Moreover, the two units on a boundary edge joining two triple occurrences remain unused: such an edge does not enter a nonempty run of double occurrences.

It remains to pay the interior double crossings. Each is incident to four triangles and has cost four. By Lemma 3.1, choose two outer boundary edges of its four-triangle configuration. Both endpoints of each chosen edge are triple. The two units on each edge are still available, so the two edges together pay the cost of the interior double crossing.

These final transfers do not overlap. A boundary edge has exactly one incident triangular face. If it is an outer edge for an interior double crossing $S$, the third vertex of that face is $S$. Thus the same boundary edge cannot be selected for a different interior double crossing. Charges on different boundary edges are distinct, even when some of their original vertices coincide.

Every endpoint cost has therefore been paid, and no triple crossing has supplied more than six units by (3). Consequently

which is equivalent to (1).

Acknowledgment

OpenAI Codex assisted with mathematical exploration, development of the argument, and preparation of the manuscript.

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]