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. 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
3. 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
4. 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
5. Tree Independence Number IV. Even-hole-free graphs

   https://doi.org/10.1137/1.9781611978322.151  

   Chudnovsky, Maria; Gartland, Peter; Hajebi, Sepehr; Lokshtanov, Daniel; Spirkl, Sophie (January 2025, Society for Industrial and Applied Mathematics - Symposium on Discrete Algorithms)

   We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most clog10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasipolynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible). 

   more » « less