More Like this

1. Enumeration of Intersection Graphs of x-Monotone Curves

   https://doi.org/10.4230/LIPIcs.GD.2024.4  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Felsner, Stefan; Klein, Karsten (Ed.)

   A curve in the plane is x-monotone if every vertical line intersects it at most once. A family of curves are called pseudo-segments if every pair of them have at most one point in common. We construct 2^Ω(n^{4/3}) families, each consisting of n labelled x-monotone pseudo-segments such that their intersection graphs are different. On the other hand, we show that the number of such intersection graphs is at most 2^O(n^{3/2-ε}), where ε > 0 is a suitable constant. Our proof uses an upper bound on the number of set systems of size m on a ground set of size n, with VC-dimension at most d. Much better upper bounds are obtained if we only count bipartite intersection graphs, or, in general, intersection graphs with bounded chromatic number. 

   more » « less
2. Positive braids minimize ascending number

   https://doi.org/10.1142/S0218216525500725  

   Davis, Lowell; Meier, Jeffrey (January 2026, Journal of Knot Theory and Its Ramifications)

   A well-known algorithm for unknotting knots involves traversing a knot diagram and changing each crossing that is first encountered from below. The minimal number of crossings changed in this way across all diagrams for a knot is called the ascending number of the knot. The ascending number is bounded below by the unknotting number. We show that for knots obtained as the closure of a positive braid, the ascending number equals the unknotting number. We also present data indicating that a similar result may hold for positive knots. We use this data to examine which low-crossing knots have the property that their ascending number is realized in a minimal crossing diagram, showing that there are at most 5 hyperbolic, alternating knots with at most 12 crossings with this property. 

   more » « less
3. Singmaster’s Conjecture In The Interior Of Pascal’s Triangle

   https://doi.org/10.1093/qmath/haac006  

   Matomäki, Kaisa; Radziwiłł, Maksym; Shao, Xuancheng; Tao, Terence; Teräväinen, Joni (April 2022, The Quarterly Journal of Mathematics)

   Abstract Singmaster’s conjecture asserts that every natural number greater than one occurs at most a bounded number of times in Pascal’s triangle; that is, for any natural number $$t \geq 2$$, the number of solutions to the equation $$\binom{n}{m} = t$$ for natural numbers $$1 \leq m \lt n$$ is bounded. In this paper we establish this result in the interior region $$\exp(\log^{2/3+\varepsilon} n) \leq m \leq n - \exp(\log^{2/3+\varepsilon} n)$$ for any fixed ɛ > 0. Indeed, when t is sufficiently large depending on ɛ, we show that there are at most four solutions (or at most two in either half of Pascal’s triangle) in this region. We also establish analogous results for the equation $$(n)_m = t$$, where $$(n)_m := n(n-1) \dots (n-m+1)$$ denotes the falling factorial. 

   more » « less
4. Counting conjugacy classes of fully irreducibles: double exponential growth

   https://doi.org/10.1007/s10711-024-00885-4  

   Kapovich, Ilya; Pfaff, Catherine (April 2024, Geometriae Dedicata)

   Inspired by results of Eskin and Mirzakhani (J Mod Dyn 5(1):71–105, 2011) counting closed geodesics of length at most L in the moduli space of a fixed closed surface, we consider a similar question in the Out(Fr) setting. The Eskin-Mirzakhani result can be equivalently stated in terms of counting the number of conjugacy classes (within the mapping class group) of pseudo-Anosovs whose dilatations have natural logarithm at most L. Let N(L) denote the number of Out(Fr)-conjugacy classes of fully irreducibles satisfying that the natural logarithm of their dilatation is at most L. We prove for r>2 that as L goes to infinity, the number N(L) has double exponential (in L) lower and upper bounds. These bounds reveal behavior not present in the surface setting or in classical hyperbolic dynamical systems. 

   more » « less
5. On the number of edges of separated multigraphs

   https://doi.org/10.1002/jgt.23030  

   Fox, Jacob; Pach, János; Suk, Andrew (September 2023, Journal of Graph Theory)

   Abstract We prove that the number of edges of a multigraph with vertices is at most , provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi, and Leighton, if has edges, in any drawing of with the above property, the number of crossings is . This answers a question of Kaufmann et al. and is tight up to the logarithmic factor. 

   more » « less