On the maximum number of tangencies among $1$-intersecting curves

This paper improves the known upper bounds on the maximum number of tangencies among $n$ 1-intersecting Jordan arcs from $O(n^{7/4})$ to $O(n^{5/3})$ for the general case and to $O(n^{3/2})$ for the strictly 1-intersecting case, while also establishing tighter bounds for specific variants involving $x$-monotone curves and proving a new graph-theoretic result.

The Gist

Imagine you are at a massive, chaotic dance floor filled with $n$ long, wiggly ribbons (we call these "Jordan arcs"). The rules of this dance are strict:

1. The "One-and-Done" Rule: Every pair of ribbons must touch or cross each other exactly once. They can't cross twice, and they can't avoid each other.
2. No Group Hugs: No single point on the floor can be touched by three ribbons at the same time.

Now, there are two ways ribbons can interact:

• Crossing: They slice through each other like an 'X'.
• Tangency (The "Kiss"): They gently brush against each other, touching at a single point without crossing, like two cars brushing bumpers in a parking lot.

The Big Question:
If you have $n$ ribbons dancing under these rules, what is the maximum number of "kisses" (tangencies) you can possibly have?

For a long time, mathematicians thought the answer was simple: just a few kisses, roughly proportional to the number of ribbons ($O(n)$). But proving this for any shape of ribbon was incredibly hard. The best previous guess was a bit messy, suggesting the number of kisses could be as high as $n^{1.75}$ (which is a lot more than $n$).

What This Paper Does:
The authors, Eyal Ackerman and Balázs Keszegh, act like master organizers. They tightened the rules and improved the math to show that the number of kisses is actually much lower than we thought.

Here is the breakdown of their findings, explained with some analogies:

1. The General Case (The Wild Dance Floor)

If the ribbons can wiggle anywhere (not necessarily straight or monotonic), the authors proved that the maximum number of kisses is roughly $n^{1.66}$ (or $n^{5/3}$).

• Analogy: Imagine trying to get 1,000 people to brush shoulders with each other in a crowd. You might think they could do it millions of times, but geometry limits them. You can't get more than about 100,000 kisses.

2. The "Precise" Case (The Strict Dance)

If the ribbons are even more disciplined and must cross or touch exactly once (no skipping), the limit drops further to $n^{1.5}$ (or $n^{3/2}$).

• Analogy: If you force the dancers to be perfectly synchronized, the chaos decreases, and the number of accidental shoulder brushes drops significantly.

3. The "Grounded" Case (The Wall of Ribbons)

The authors looked at a specific scenario: Imagine all ribbons start from a single vertical wall (like a curtain rod) and flow out to the right. They are also "x-monotone," meaning they never double back on themselves horizontally.

• The Result: In this specific setup, the number of kisses is exactly $n^{1.33}$ (or $n^{4/3}$).
• Analogy: Think of a row of water hoses all attached to a single wall. If you try to make them all touch each other as they spray out, there's a geometric limit to how many times they can kiss before they are forced to cross instead. This result is "tight," meaning you can actually build a setup that hits this limit, so you can't go any lower.

4. The "Infinite" Case (The Endless Highway)

They also looked at ribbons that go on forever in both directions (like an infinite highway).

• The Result: The number of kisses here is surprisingly small: just $n \log n$.
• Analogy: If you have infinite roads that only cross once, they can't "kiss" very often. It's almost a straight line relationship. If you have 100 roads, you get maybe 500 kisses. If you have 1,000 roads, you get maybe 7,000 kisses. It's very efficient.

The Secret Weapon: A Graph Theory Trick

To solve these problems, the authors didn't just look at ribbons; they looked at graphs (networks of dots and lines).

• They invented a new mathematical tool (Theorem 8) that acts like a "density detector."
• The Metaphor: Imagine a city where every neighborhood (a group of friends) is very sparse (not many people know each other). The authors proved that if every neighborhood is sparse, then the entire city cannot be too crowded.
• This tool is so powerful it improves old math theorems from the 1970s (Erdős and Simonovits) and helps solve problems about how many connections you can have in a network without creating specific "forbidden patterns."

Why Does This Matter?

You might ask, "Who cares about kissing ribbons?"

• Robotics: Robots need to move without crashing. Knowing how many times paths can touch helps plan safe routes.
• Computer Graphics: Rendering complex scenes requires knowing how many objects overlap or touch to calculate lighting and shadows efficiently.
• Data Structures: Algorithms that sort or search data often rely on understanding how lines and curves intersect.

In Summary:
This paper is like a master architect who looked at a chaotic construction site and said, "You thought you could build a tower this high, but actually, the laws of geometry only allow it to go this high." They tightened the bounds, proving that no matter how you twist and turn your lines, the number of times they can gently touch is strictly limited, and they provided the exact formulas for those limits.

Technical Summary

Here is a detailed technical summary of the paper "On the maximum number of tangencies among 1-intersecting curves" by Eyal Ackerman and Balázs Keszegh.

1. Problem Statement

The paper investigates the maximum number of tangency points (pairs of curves touching at exactly one point without crossing) in a family of $n$ planar Jordan arcs (curves). The study focuses on two specific classes of curve families:

1. 1-intersecting curves: Every pair of curves intersects in at most one point (either a crossing or a tangency).
2. Precisely 1-intersecting curves: Every pair of curves intersects in exactly one point.

The central question is to determine the asymptotic upper bound on the number of tangent pairs, denoted as $T(n)$, for these families. A long-standing conjecture by Pach posits that for precisely 1-intersecting curves, $T(n) = O(n)$. While this was proven for specific cases (e.g., $x$-monotone curves), the general case previously had a loose upper bound of $O(n^{7/4})$.

2. Methodology

The authors employ a combination of geometric decomposition, graph theory, and extremal combinatorics.

• Geometric Decomposition: For $x$-monotone curves, the authors utilize a Cutting Lemma (Theorem 10) to partition the plane into generalized trapezoids. This allows them to bound tangencies locally within "short" and "long" curve segments and sum the results.
• Graph-Theoretic Transformation: The problem of counting tangencies is transformed into an edge-counting problem in a tangency graph $G_C$, where vertices represent curves and edges represent tangencies.
• Sparse Sub-bineighborhoods: The core innovation is the introduction of a graph-theoretic property called $f$-sparse sub-bineighborhoods. Two vertices $u, v$ have $f$-sparse sub-bineighborhoods if the number of edges between any disjoint subsets of their neighbors is bounded by a function $f$.
• Extremal Graph Theory: The authors prove a new theorem (Theorem 8) extending results by Erdős and Simonovits. This theorem relates the sparsity of induced subgraphs within the open bineighborhoods of vertices to the total number of edges in the graph.
• Induction and Recursion: Several bounds are derived using recursive splitting of curve families (e.g., splitting grounded curves or $x$-monotone curves into subsets) and applying the Kővári-Sós-Turán theorem.

3. Key Contributions

A. Improved Upper Bounds for General Curves

The paper significantly tightens the known bounds for general 1-intersecting curves:

• Precisely 1-intersecting curves: The bound is improved from $O(n^{7/4})$ to $O(n^{3/2})$ (Theorem 3).
• 1-intersecting curves (at most one intersection): The bound is improved from $O(n^{7/4})$ to $O(n^{5/3})$ (Theorem 2).
• Method: These results rely on proving that the tangency graph satisfies the $f$-sparse sub-bineighborhood property with $f(x) = O(x^{3/2})$ and applying the new graph-theoretic theorem.

B. Bounds for $x$-Monotone Curves

The authors refine bounds for curves that are graphs of continuous functions:

• General $x$-monotone 1-intersecting: The bound is improved to $O(n^{4/3}(\log n)^{1/3})$ (Theorem 4), improving the previous $O(n^{4/3}(\log n)^{2/3})$ by Pach and Sharir.
• Grounded $x$-monotone 1-intersecting: For curves whose left endpoints lie on a common vertical line, the authors prove an asymptotically tight bound of $\Theta(n^{4/3})$ (Theorem 5). This matches the lower bound derived from the Erdős point-line incidence construction.
• Bi-infinite $x$-monotone 1-intersecting: The authors provide a simplified proof that the maximum number of tangencies is $\Theta(n \log n)$ (Theorem 6), and exactly $n-1$ for precisely 1-intersecting bi-infinite curves.

C. New Graph-Theoretic Theorem

The paper introduces Theorem 8, a generalization of the Erdős-Simonovits theorem:

• Statement: If a graph $G$ has the property that every pair of vertices has $f$-sparse sub-bineighborhoods (where $f(n) = O(n^{2-\alpha})$), then $|E(G)| = O(|V|^{2 - \frac{\alpha}{\alpha+1}})$.
• Significance: This extends previous results by requiring sparsity only in sub-bineighborhoods rather than the entire induced subgraph. The authors also prove a matching lower bound (Theorem 9) using random bipartite graphs, showing the bound is tight for $0 \le \alpha \le 1$.

4. Key Results Summary

Curve Type	Condition	Previous Best Bound	New Bound	Status
Precisely 1-intersecting	Arbitrary	$O(n^{7/4})$	$O(n^{3/2})$	Improved
1-intersecting	Arbitrary	$O(n^{7/4})$	$O(n^{5/3})$	Improved
1-intersecting	$x$-monotone	$O(n^{4/3}(\log n)^{2/3})$	$O(n^{4/3}(\log n)^{1/3})$	Improved
1-intersecting	Grounded $x$-monotone	$\Omega(n^{4/3})$	$\Theta(n^{4/3})$	Tight
1-intersecting	Bi-infinite $x$-monotone	$\Theta(n \log n)$	$\Theta(n \log n)$	Confirmed/Simplified

5. Significance and Impact

• Resolution of Open Problems: The paper makes significant progress toward Pach's conjecture (that precisely 1-intersecting curves have $O(n)$ tangencies) by reducing the gap from $n^{1.75}$ to $n^{1.5}$.
• Methodological Innovation: The introduction of the "sparse sub-bineighborhood" concept provides a powerful new tool for extremal graph theory, applicable beyond curve tangencies (e.g., to topological graphs and forbidden subgraphs like $K_{2,3}$).
• Tight Bounds: The establishment of $\Theta(n^{4/3})$ for grounded $x$-monotone curves settles the complexity for this specific geometric configuration, linking it directly to the classic point-line incidence problem.
• Simplification: The authors provide elementary proofs for results previously established using more complex machinery (e.g., the $O(n \log n)$ bound for bi-infinite curves), making the results more accessible.

The paper concludes by noting that while Pach's conjecture remains open for the general case, the new graph-theoretic framework offers a promising path for future improvements.