More Like this

1. Interpolation for Curves in Projective Space with Bounded Error

   https://doi.org/10.1093/imrn/rnz136  

   Larson, Eric ( July 2019 , International Mathematics Research Notices)

   Abstract Given $n$ general points $p_1, p_2, \ldots , p_n \in{\mathbb{P}}^r$ it is natural to ask whether there is a curve of given degree $d$ and genus $g$ passing through them; by counting dimensions a natural conjecture is that such a curve exists if and only if $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor.\end{equation*}$$The case of curves with nonspecial hyperplane section was recently studied in [2], where the above conjecture was shown to hold with exactly three exceptions. In this paper, we prove a “bounded-error analog” for special linear series on general curves; more precisely we show that existence of such a curve subject to the stronger inequality $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor - 3.\end{equation*}$$Note that the $-3$ cannot be replaced with $-2$ without introducing exceptions (as a canonical curve in ${\mathbb{P}}^3$ can only pass through nine general points, while a naive dimension count predicts twelve). We also use the same technique to prove that the twist of the normal bundle $N_C(-1)$ satisfies interpolation for curves whose degree is sufficiently large relative to their genus, and deduce from this that the number of general points contained in the hyperplane section of a general curve is at least $$\begin{equation*}\min\left(d, \frac{(r - 1)^2 d - (r - 2)^2 g - (2r^2 - 5r + 12)}{(r - 2)^2}\right).\end{equation*}$$ As explained in [7], these results play a key role in the author’s proof of the maximal rank conjecture [9]. 

   more » « less
2. Enumeration of Rooted Binary Unlabeled Galled Trees

   https://doi.org/10.1007/s11538-024-01270-8  

   Agranat-Tamir, Lily ; Mathur, Shaili ; Rosenberg, Noah A. ( March 2024 , Bulletin of Mathematical Biology)

   Rooted binarygalledtrees generalize rooted binary trees to allow a restricted class of cycles, known asgalls. We build upon the Wedderburn-Etherington enumeration of rooted binary unlabeled trees withnleaves to enumerate rooted binary unlabeled galled trees withnleaves, also enumerating rooted binary unlabeled galled trees withnleaves andggalls,$$0 \leqslant g \leqslant \lfloor \frac{n-1}{2} \rfloor $$$0⩽g⩽\lfloor \frac{n-1}{2}\rfloor$. The enumerations rely on a recursive decomposition that considers subtrees descended from the nodes of a gall, adopting a restriction on galls that amounts to considering only the rooted binarynormalunlabeled galled trees in our enumeration. We write an implicit expression for the generating function encoding the numbers of trees for alln. We show that the number of rooted binary unlabeled galled trees grows with$$0.0779(4.8230^n)n^{-\frac{3}{2}}$$$0.0779(4.{8230}^n)n^{-\frac{3}{2}}$, exceeding the growth$$0.3188(2.4833^n)n^{-\frac{3}{2}}$$$0.3188(2.{4833}^n)n^{-\frac{3}{2}}$of the number of rooted binary unlabeled trees without galls. However, the growth of the number of galled trees with only one gall has the same exponential order 2.4833 as the number with no galls, exceeding it only in the subexponential term,$$0.3910n^{\frac{1}{2}}$$$0.3910n^{\frac{1}{2}}$compared to$$0.3188n^{-\frac{3}{2}}$$$0.3188n^{-\frac{3}{2}}$. For a fixed number of leavesn, the number of gallsgthat produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of$$g=0$$$g=0$and the maximum of$$g=\lfloor \frac{n-1}{2} \rfloor $$$g=\lfloor \frac{n-1}{2}\rfloor$. We discuss implications in mathematical phylogenetics.

    

   more » « less
3. A Graph Theoretic Additive Approximation of Optimal Transport

   Lahn, Nathaniel ; Mulchandani, Deepika ; Raghvendra, Sharath ( December 2019 , Advances in neural information processing systems)

   Transportation cost is an attractive similarity measure between probability distributions due to its many useful theoretical properties. However, solving optimal transport exactly can be prohibitively expensive. Therefore, there has been significant effort towards the design of scalable approximation algorithms. Previous combinatorial results [Sharathkumar, Agarwal STOC '12, Agarwal, Sharathkumar STOC '14] have focused primarily on the design of near-linear time multiplicative approximation algorithms. There has also been an effort to design approximate solutions with additive errors [Cuturi NIPS '13, Altschuler \etal\ NIPS '17, Dvurechensky \etal\, ICML '18, Quanrud, SOSA '19] within a time bound that is linear in the size of the cost matrix and polynomial in C/\delta; here C is the largest value in the cost matrix and \delta is the additive error. We present an adaptation of the classical graph algorithm of Gabow and Tarjan and provide a novel analysis of this algorithm that bounds its execution time by \BigO(\frac{n^2 C}{\delta}+ \frac{nC^2}{\delta^2}). Our algorithm is extremely simple and executes, for an arbitrarily small constant \eps, only \lfloor \frac{2C}{(1-\eps)\delta}\rfloor + 1 iterations, where each iteration consists only of a Dijkstra-type search followed by a depth-first search. We also provide empirical results that suggest our algorithm is competitive with respect to a sequential implementation of the Sinkhorn algorithm in execution time. Moreover, our algorithm quickly computes a solution for very small values of \delta whereas Sinkhorn algorithm slows down due to numerical instability. 

   more » « less
4. Minimum number of non-zero-entries in a stable matrix exhibiting Turing instability

   https://doi.org/10.3934/dcdss.2021128  

   Hambric, Christopher Logan ; Li, Chi-Kwong ; Pelejo, Diane Christine ; Shi, Junping ( January 2022 , Discrete and Continuous Dynamical Systems - S)

   It is shown that for any positive integer \begin{document}$ n \ge 3 $\end{document}, there is a stable irreducible \begin{document}$ n\times n $\end{document} matrix \begin{document}$ A $\end{document} with \begin{document}$ 2n+1-\lfloor\frac{n}{3}\rfloor $\end{document} nonzero entries exhibiting Turing instability. Moreover, when \begin{document}$ n = 3 $\end{document}, the result is best possible, i.e., every \begin{document}$ 3\times 3 $\end{document} stable matrix with five or fewer nonzero entries will not exhibit Turing instability. Furthermore, we determine all possible \begin{document}$ 3\times 3 $\end{document} irreducible sign pattern matrices with 6 nonzero entries which can be realized by a matrix \begin{document}$ A $\end{document} that exhibits Turing instability.

    

   more » « less
5. High-Dimensional Holeyominoes

   https://doi.org/10.37236/10515  

   Malen, Greg ; Manin, Fedor ; Roldán, Érika ( July 2022 , The Electronic Journal of Combinatorics)

   What is the maximum number of holes enclosed by a $d$-dimensional polyomino built of $n$ tiles? Represent this number by $f_d(n)$. Recent results show that $f_2(n)/n$ converges to $1/2$. We prove that for all $d \geq 2$ we have $f_d(n)/n \to (d-1)/d$ as $n$ goes to infinity. We also construct polyominoes in $d$-dimensional tori with the maximal possible number of holes per tile. In our proofs, we use metaphors from error-correcting codes and dynamical systems. 

   more » « less