% Faithful TeX transcription of the authors' supplied November 8, 2026 PDF.
% The figure is preserved as a vector extract from that PDF.
\documentclass[11pt]{amsart}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,graphicx}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\numberwithin{equation}{section}
\title{Shared triangular sides in pseudoline arrangements}
\author{Will Howe}
\email{howew@purdue.edu}
\author{Grant Huffman}
\email{huffma97@purdue.edu}
\author{Jensen Kohlmeyer}
\email{jenwin@purdue.edu}
\author{Liam Kruer}
\email{kruerl@purdue.edu}
\date{November 8, 2026}
\subjclass[2020]{52C30}
\keywords{pseudoline arrangement, triangular face, multiple crossing, discharging}
\begin{document}
\begin{abstract}
Let $d$ be the number of edges incident to two bounded triangular faces in a finite affine arrangement of pseudolines, with each pair crossing exactly once and with only double and triple crossings. If $t_3$ is the number of triple crossings, we prove $d\leq 3t_3$, answering the compensation question of Parpalak and Utkin. The proof distributes charge along the normalized boundary of the union of triangular faces. A double crossing incident to four triangles is treated by restricting the arrangement to the four pseudolines supporting their opposite sides. This restriction provides two boundary edges whose unused endpoint charges pay for the crossing.
\end{abstract}
\maketitle

\section{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 \emph{edge} is a segment of a pseudoline between consecutive crossings. A \emph{triangle} is a bounded face with exactly three edges. In particular, triangles containing further portions of the arrangement are not counted. An edge is \emph{shared} if both incident faces are triangles, and it is a \emph{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~\cite[\S5.2, (5.5)]{PU} ask whether $d\leq 3t_3$. Their discharging argument proves the weaker estimate $d\leq \frac92t_3$. We establish the proposed inequality.

\begin{theorem}\label{thm:main}
For every finite affine pseudoline arrangement with only double and triple crossings,
\begin{equation}\label{eq:main}d\leq 3t_3.\end{equation}
\end{theorem}

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~\cite{PU}, for $n\geq 2$ 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~\ref{thm:main} is equivalently the assertion $w\geq u$.

\clearpage
\section{Local restrictions on shared edges}
We recall two elementary observations from~\cite[Appendix C]{PU}. Their proofs are included for completeness.

\begin{lemma}\label{lem:triple}
A shared edge has at least one triple endpoint.
\end{lemma}
\begin{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.
\end{proof}

\begin{lemma}\label{lem:consecutive}
At a triple crossing, two consecutive incident edges cannot both be shared edges whose other endpoints are double crossings.
\end{lemma}
\begin{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
\[
PQ_5Q_0,\quad PQ_0Q_1,\quad PQ_1Q_2.
\]
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.
\end{proof}

\section{Double crossings surrounded by four triangles}
\begin{lemma}\label{lem:four}
Suppose that a double crossing $S$ is incident to four triangular faces. Their four sides opposite $S$ have triple endpoints, and at least two of these sides are boundary edges.
\end{lemma}
\begin{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~\ref{lem:triple}. 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~\ref{lem:triple}, 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.
\end{proof}

\clearpage
\begin{figure}[t]
\centering
\includegraphics[width=2.85in]{triangular-configuration.pdf}
\caption{Four triangular faces incident to a double crossing. In this example the dashed outer sides $e_1,e_2$ are boundary edges. Lemma~\ref{lem:four} guarantees at least two such outer boundary sides in every arrangement. Each carries two unused units in the discharging argument.}
\label{fig:four}
\end{figure}

\section{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 \emph{boundary occurrence} of a crossing is a maximal fan of $i\geq 1$ 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\leq 3$. An interior crossing has all its incident sectors triangular: four at a double crossing and six at a triple crossing.

\begin{lemma}\label{lem:run}
On a normalized boundary circuit, a run of double occurrences between successive triple occurrences satisfies
\begin{equation}\label{eq:run}\sum(i-1)\leq 2.\end{equation}
A circuit consisting entirely of double occurrences has $i=1$ at every occurrence.
\end{lemma}
\begin{proof}
Call a double occurrence \emph{active} if $i\geq 2$. 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~\ref{lem:triple}. If it is triple, the two sides violate Lemma~\ref{lem:consecutive}.

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~\ref{lem:triple}. 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~\eqref{eq:run} is therefore $i-1\leq 2$.

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.
\end{proof}

\clearpage
\section{Discharging and completion of the proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
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
\begin{equation}\label{eq:budget}\sum_{\text{fans}}(i+1)=k+r\leq 6.\end{equation}
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~\ref{lem:run} gives $D\leq 2$. 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~\ref{lem:four}, 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~\eqref{eq:budget}. Consequently
\[
2d\leq 6t_3,
\]
which is equivalent to~\eqref{eq:main}.
\end{proof}

\section*{Acknowledgment}
OpenAI Codex assisted with mathematical exploration, development of the argument, and preparation of the manuscript.

\begin{thebibliography}{1}
\bibitem{PU} R. Parpalak and D. Utkin, \emph{Non-simple arrangements of lines and pseudolines with many triangles}, arXiv:2611.03096v1 (2026), \url{https://arxiv.org/abs/2611.03096}.
\end{thebibliography}
\end{document}