Source-linked AI summary
$k$-arrangements of pseudolines and pseudocircles
Jan Kynčl, Carolina Medina, Gelasio Salazar
TL;DR
The paper asks how many unavoidable k-arrangements there are, against the challenge of fully classifying them. It uses combinatorial codes and Ramsey arguments to establish exponential bounds for pseudolines and, for even k, pseudocircles.
Problem
The paper asks how the number of unavoidable k-arrangements grows, while noting that fully classifying them appears beyond reach.
Source: §1.2 · pp. 2–3, §5.3 · p. 17Method
The upper-bound argument encodes arrangements and applies Ramsey’s theorem to their size-3 subcodes.
Source: §4.2 · p. 12, §4.3 · p. 13Results
For absolute constants a,b with a>1 and sufficiently large k, a^k < |Lk,m| < b^k for m≥3, with the same bounds for |Ck,m| when k is even.
Source: §1.4 · p. 3Takeaways & Limitations
The number of unavoidable arrangements has exponential growth in k independently of m, for pseudolines and for pseudocircles when k is even.
Source: §1.2 · p. 3, §1.4 · p. 3A full classification is not attempted because packable k-arrangements are at least as complicated as the open-meander classification problem.
Source: §5.3 · p. 17
Abstract
from arXiv · showhide
A $k$-arrangement of pseudolines is a set of bi-infinite curves in the plane such that any two of them intersect each other in exactly $k$ points, at which they cross, and it is simple if no three curves meet at a common point. Cyclic arrangements are the only simple $1$-arrangements of pseudolines that are unavoidable, in the Ramsey spirit: for each fixed $m\ge 1$, every sufficiently large simple $1$-arrangement of pseudolines has a cyclic subarrangement of size $m$. We show that, for every $m\ge 3$, the number of unavoidable simple $k$-arrangements of pseudolines of size $m$ grows exponentially with $k$, independently of $m$. For even $k$, we prove an analogous result for $k$-arrangements of pseudocircles.
1. Introduction
The paper studies unavoidable subarrangements in simple k-arrangements, characterizing them through packability and proving exponential bounds on their number. It also situates the result against earlier unavoidable-arrangement results and explains why a full classification is difficult.
1. Introduction
- Simple arrangements model uniform oriented matroids of rank 3, and the paper assumes throughout that no three curves meet at a common point.Pseudolines are bi-infinite curves crossing pairwise once, while pseudocircles are simple closed curves crossing pairwise twice.Source: §1 · p. 1
1.1. Unavoidable arrangements.
- Cyclic pseudoline arrangements are unavoidable for every size, while three unavoidable pseudocircle arrangements exist for each size m≥3.The cyclic-arrangement result is attributed to Ramírez-Alfonsín, and the pseudocircle result to Medina, Ramírez-Alfonsín and Salazar.Source: §1.1 · p. 2
1.2. k-arrangements and the motivation behind this work.
- The paper focuses on counting unavoidable k-arrangements after noting that a full classification appears beyond reach.Its motivating questions concern which k-arrangements are unavoidable and how their number grows.Source: §1.2 · pp. 2–3
1.3. Unavoidable k-arrangements and packable k-arrangements.
- The unique minimal unavoidable collection consists exactly of the packable size-m arrangements, with the pseudocircle statement applying when k is even.An arrangement is packable when arbitrarily large arrangements exist whose size-m subarrangements are all isomorphic to it.Source: §1.3 · p. 3
1.4. The main result.
- For absolute constants a,b with a>1 and all sufficiently large k, a^k < |Lk,m| < b^k for every m≥3; for even k, the same bounds hold for |Ck,m|.The lower bounds are proved by an elementary argument, while the upper bounds use preliminary code results and are proved in Sections 3 and 4.Source: §1.4 · pp. 3–4
1.5. Previous work on k-arrangements.
- Earlier work considered arrangements whose curves cross at most k times and constructions allowing each pseudoline pair to cross finitely many times.The cited work includes Chan and Bokowski, Kovič, Pisanski, and Žitnik.Source: §1.5 · p. 4
1.6. Proof of Proposition 1.
- Packable arrangements belong to every collection satisfying (U1), and a Ramsey coloring argument shows that the packable collection itself satisfies (U1).The proof uses a finite threshold for non-packable arrangements and colors m-subsets by isomorphism class.Source: §1.6 · pp. 4–5
2. Proof of the lower bounds in Theorem 2
The proof builds packable arrangements by concatenating sections indexed by words, then counts non-isomorphic arrangements after accounting for word symmetries. This yields exponential lower bounds for pseudolines and, for even k, pseudocircles.
2. Proof of the lower bounds in Theorem 2
- For m≥3, |L_k,m| ≥ 2^k/4 and, for even k, |C_k,m| ≥ 2^k/(4k).These lower bounds establish exponential growth in k for both types of arrangements.Source: §2 · pp. 5–7
- Concatenating k sections S_r or T_r from a word and extending the result in both directions constructs k-arrangements of pseudolines.S_r is a bounded section of the cyclic arrangement, while T_r is its reflection across a horizontal line.Source: §2 · p. 5, Figure 2 · p. 6
- For every n≥m, every m-subarrangement of A_n(W) is isomorphic to A_m(W), so A_m(W) is packable.The count of 2^k words, with at most four equivalent words per isomorphism class, gives at least 2^k/4 non-isomorphic pseudoline arrangements.Source: §2 · p. 6
- For pseudolines, two words yield isomorphic arrangements exactly when one is the other, its complement, its reversal, or the complement of its reversal.Thus at most four words represent each isomorphism class.Source: §2 · p. 6
- For pseudocircles, joining the loose ends of the concatenated S_r and T_r sections produces B_r(W), with every m-subarrangement of B_n(W) isomorphic to B_m(W).This makes B_m(W) packable.Source: §2 · p. 6
- For pseudocircles, complementing, reversing, and cyclically translating a word preserve isomorphism, and each word has at most 4k equivalents.Since there are 2^k words, this yields at least 2^k/(4k) non-isomorphic packable pseudocircle arrangements.Source: §2 · pp. 6–7
3. Codes of k-arrangements of pseudocircles
The section encodes pseudocircle k-arrangements as sequences that retain crossing order and identity, then defines subcodes for restricted arrangements. It proves that a code is determined by its 3-subcodes, enabling larger codes to be reconstructed from triple restrictions.
3.1. Codes of k-arrangements.
- Traversing each labelled pseudocircle from a chosen startpoint records crossings in order, identifying the other curve and whether the traversal enters or leaves its disk.The resulting keys, ordered by curve label, form the arrangement's code.Source: §3.1 · p. 7, §3 · p. 7
- A code need not be unique: changing curve labels, startpoints, or the outer face can produce different codes for the same arrangement.The encoding therefore permits multiple representations of one arrangement.Source: §3.1 · p. 8
- A shared code for two same-size pseudocircle k-arrangements implies that the arrangements are isomorphic.The code determines the embedded graph and rotation system, which determine its embedding in the sphere up to homeomorphism.Source: §3.1 · p. 8
3.2. Subcodes.
- A subcode retains the keys for selected curves, removes symbols for other curves, and relabels the retained curves in inherited order.It represents the corresponding subarrangement with the same startpoints; deleting curves in stages gives the same result as deleting them at once.Source: §3.2 · pp. 8–9
3.3. Reconstruction from triple subcodes.
- A code of size at least 3 is determined by its 3-subcodes, so equal triple subcodes imply equal codes.For a fixed 3-code and size m, at most one code has all its 3-subcodes equal to that 3-code.Source: §3.3 · p. 9
4. Proof of the upper bounds in Theorem 2
The upper-bound proofs count arrangements of two curves via meanders, then use exponential bounds on size-three codes and Ramsey’s theorem to bound larger arrangements. For pseudocircles, a size-three code bound is explicit; the pseudoline proof uses the analogous linear-code argument.
4.1. Meanders and k-arrangements of size two
- For every k ≥1, |L(k,2)| < D^k, and for even k ≥2, |C(k,2)| < D^k, by bounding these classes with open and closed meanders.Straightening one pseudoline gives an open meander of order k; opening a pseudocircle at a noncrossing point gives a closed meander of order k/2.Source: §4.1 · pp. 10–11
4.2. Proof of the upper bound in Theorem 2 for Ck,m
- For even k, |Ξk,3| < 4096k^6(64D^3)^k, providing the size-three pseudocircle code bound used in the upper-bound proof.Since the polynomial factor is eventually dominated by b^k for any b > 64D^3, this supports the claimed exponential upper bound.Source: §4.2 · pp. 11–12
- For pseudocircles, the proof bounds size-two codes by counting choices of sides, orientation, labels, and startpoints, then counts size-three keys by order-preserving merges.Each isomorphism class of two pseudocircles yields at most 16k² codes.Source: §4.2 · p. 11
4. Proof of the upper bounds in Theorem 2
- For m ≥3, Ramsey’s theorem turns a common size-three subcode into an injective encoding of each arrangement by a code in Ξk,3.The proof uses the fact that a code is determined by its size-three subcodes; the pseudoline argument uses the analogous property for linear codes.Source: §4.2 · p. 12, §4.3 · p. 13
4.3. Proof of the upper bound in Theorem 2 for Lk,m
- For pseudolines, the analogous Ramsey proof uses linear codes, which determine arrangements up to isomorphism and are determined by their size-three subcodes.A direction is chosen on each pseudoline, and crossings are recorded in order in each key.Source: §4.3 · pp. 12–13
5. Concluding remarks
The concluding remarks relate packable arrangements to regular path systems, planar maps, and meanders. They give a sharper pseudocircle upper-bound constant while noting that meander classification remains a barrier to classifying packable arrangements.
5.1. Regular path systems and x-monotone k-arrangements
- The characterization of regular path systems identifies packable x-monotone k-arrangements and yields a lower bound slightly better than the paper’s earlier bound, but still far below its upper bound.The signature determines the order in which each path meets the others, and thus the system up to isomorphism.Source: §5.1 · pp. 14–15
5.2. Arrangements of pseudocircles and 4-regular planar maps
- For pseudocircles, planar-map enumeration improves the upper-bound base to any b > (196/27)^3 ≈ 382.54, below the earlier 64D^3 constant.The authors retain the elementary proof because it is self-contained and treats pseudolines and pseudocircles uniformly; the map argument does not immediately apply to pseudolines.Source: §5.2 · p. 15
5.3. Packable arrangements and meanders
- For odd k and m ≥2, replacing each crossing of the cyclic arrangement with a two-pseudoline k-arrangement yields a packable arrangement, and the construction is injective.Each pair of pseudolines in the result recovers the substituted arrangement.Source: §5.3 · pp. 16–17
- Classifying packable k-arrangements of m pseudolines for odd k would also classify open meanders of order k, a classical difficult problem.The corresponding relation to closed meanders suggests a similar obstruction for pseudocircles and for even-k pseudoline arrangements.Source: §5.3 · p. 17
- For sufficiently large odd k, the open-meander-based lower bound exceeds both the Section 2 construction and the estimate from the regular-path-system characterization.The passage states that the number of open meanders grows exponentially with base strictly larger than 3.Source: §5.3 · p. 17
- The upper bounds count all arrangements of three curves and use packability little, so the authors expect substantial room to improve bounds for packable arrangements.Even the improved lower bound remains far from the upper bounds.Source: §5.3 · p. 17