Chain of $3$-cells bounded by $x$-monotone curves.

Question

Assume that we have collection of $x$-monotone curves in the plane such that the following is true for these curves:

1. Each pair of the curves intersects exactly once.

2. Each curve is monotone increasing.

A $3$-cell is defined as an empty cell bounded by three arcs of the curves and three intersection points of the curves (so cells must be empty i.e. no other line passes through any of the cells). Two cells form a $2$-chain when they share at least one $x$-monotone curve.

I am trying to show that in a collection of any intersecting $x$-monotone curves the $3$-cells form a chain such that every $x$-monotone curve has at least one arc in this chain.

Perhaps we could assume that this is true for $n-1$ monotone curves in the plane, and by adding curve to this collection we would have to show that this curve would have to be adjacent with at least one $3$-cell in the pre-existing chain of $3$-cells?

Answer 1

Here is a sketch, and I don't know if I'll have time to improve it. I publish it on the hope that someone may complete it. The proof principle seems sounds, but there are gaps, and it would also require more case splitting to be complete. Or a more powerful argument (some invariant?).

So we have $n$ $x$-monotone curves, and we want to prove that any curve bounds a 3-cell.

Let's call 3-room the closed space made by 3 curves. As pairs of curves have exactly one intersection, any 3 curves define exactly one 3-room. If this 3-room is not crossed by another curve, it is a 3-cell.

Let's take $A$, any of the $n$ curves. We order the other curves according to the place where they intersect $A$. Let's call two curves adjacent if their intersection points with $A$ are one next to the other (i.e. there is no other intersection point between them). We'll only look at 3-rooms $(A, B, C)$ where $B$ and $C$ are adjacent, and cross $A$ in that order (by growing $x$).

Lemma: if a curve $C$ crosses a 3-room $(A, D, E)$ on $D$ and $E$ (where $D$ and $E$ are adjacent and in that order), then the intersection of $C$ with $D$ cannot be a crossing of the 3-room $(A, B, C)$ by $D$. This seems obvious but the proof is missing.

Main proof

We study pairs $(B, C)$ of adjacent curves (there are $n-2$ such pairs). We define a relation "$<$" between pairs: $(B, C) < (D, E) \iff$ $B$ or $C$ crosses the 3-room $(A, D, E)$. Properties:

Antireflexive: a curve does not cross a 3-room to which it participates.

Asymetric: if $(B, C) < (D, E)$, then not $(D, E) < (B, C)$. Proof: let's suppose $C$ crosses 3-room $(A, D, E)$ (same demonstration with $B$).

• $C$ cannot intersect $A$ between the intersection points of $D$ and $E$ with $A$, because $D$ and $E$ are adjacent. So $C$ intersects $D$ and $E$ in the 3-room $(A, D, E)$.
• Hence $D$ and $E$ cannot cross the 3-room $(A, B, C)$:
• they cannot intersect $A$ between $B$ and $C$ because $B$ and $C$ are adjacent;
• they cannot intersect $C$ because there is already an intersection point with $C$, and it cannot be the same, cf. lemma.

Transitivity does not hold, but a weaker property holds: the relation is acyclic. I.e. if $(B_0, C_0) < (B_1, C_1)$ and ... and $(B_{n-1}, C_{n-1}) < (B_n, C_n)$, then not $(B_n, C_n) < (B_0, C_0)$. The proof is missing.

These properties are sufficient to prove that there are pairs that have no inferior pair: if there was none, we could either build an infinite sequence of different pairs, or a cycle.

So $\exists (A, B, C)$ a 3-room where $(B,C)$ is never $<$ to any other pair. This means it is not crossed, hence it is a 3-cell. We have found a 3-cell bounded by $A$.