skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Enumeration of Rooted Binary Unlabeled Galled Trees
Abstract 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 n - 1 2 . 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 - 3 2 , exceeding the growth$$0.3188(2.4833^n)n^{-\frac{3}{2}}$$ 0.3188 ( 2 . 4833 n ) n - 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.3910 n 1 2 compared to$$0.3188n^{-\frac{3}{2}}$$ 0.3188 n - 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 = n - 1 2 . We discuss implications in mathematical phylogenetics.  more » « less
Award ID(s):
2116322
PAR ID:
10496570
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Bulletin of Mathematical Biology
Volume:
86
Issue:
5
ISSN:
0092-8240
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We prove that there are$$\gg \frac{X^{\frac{1}{3}}}{(\log X)^2}$$ X 1 3 ( log X ) 2 imaginary quadratic fieldskwith discriminant$$|d_k|\le X$$ | d k | X and an ideal class group of 5-rank at least 2. This improves a result of Byeon, who proved the lower bound$$\gg X^{\frac{1}{4}}$$ X 1 4 in the same setting. We use a method of Howe, Leprévost, and Poonen to construct a genus 2 curveCover$$\mathbb {Q}$$ Q such thatChas a rational Weierstrass point and the Jacobian ofChas a rational torsion subgroup of 5-rank 2. We deduce the main result from the existence of the curveCand a quantitative result of Kulkarni and the second author. 
    more » « less
  2. Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ [ 0 , 1 ] k where$$k \ge 2$$ k 2 . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ x 1 , x 2 , , x n through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ i = 1 n | x i - x i + 1 | k 1 / k c k , where$$|x-y|$$ | x - y | is the Euclidean distance betweenxandy, and$$c_k$$ c k is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ x n + 1 x 1 . From the other direction, for every$$k \ge 2$$ k 2 and$$n \ge 2$$ n 2 , there existnpoints in$$[0,1]^k$$ [ 0 , 1 ] k , such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is$$c_2=2$$ c 2 = 2 and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 9 2 3 1 / k · k for every$$k \ge 3$$ k 3 and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ c k = 2 1 / k · k , for every$$k \ge 2$$ k 2 . Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 3 5 2 3 1 / k · k or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ c k = 2.91 k ( 1 + o k ( 1 ) ) . Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ c 3 2 7 / 6 , which disproves the conjecture for$$k=3$$ k = 3 . Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 
    more » « less
  3. Abstract Assuming the Riemann Hypothesis, we study negative moments of the Riemann zeta-function and obtain asymptotic formulas in certain ranges of the shift in ζ ( s ) {\zeta(s)}. For example, integrating | ζ ( 1 2 + α + i t ) | - 2 k {|\zeta(\frac{1}{2}+\alpha+it)|^{-2k}}with respect totfromTto 2 T {2T}, we obtain an asymptotic formula when the shift α is roughly bigger than 1 log T {\frac{1}{\log T}}and k < 1 2 {k<\frac{1}{2}}. We also obtain non-trivial upper bounds for much smaller shifts, as long as log 1 α log log T {\log\frac{1}{\alpha}\ll\log\log T}. This provides partial progress towards a conjecture of Gonek on negative moments of the Riemann zeta-function, and settles the conjecture in certain ranges. As an application, we also obtain an upper bound for the average of the generalized Möbius function. 
    more » « less
  4. A<sc>bstract</sc> We present a quantum M2 brane computation of the instanton prefactor in the leading non-perturbative contribution to the ABJM 3-sphere free energy at largeNand fixed levelk. Using supersymmetric localization, such instanton contribution was found earlier to take the form$$ {F}^{inst}\left(N,k\right)=-{\left({\sin}^2\frac{2\pi }{k}\right)}^{-1}\exp \left(-2\pi \sqrt{\frac{2N}{k}}\right)+.\dots $$ F inst N k = sin 2 2 π k 1 exp 2 π 2 N k + . The exponent comes from the action of an M2 brane instanton wrapped onS3/ℤk, which represents the M-theory uplift of the ℂP1instanton in type IIA string theory on AdS4× ℂP3. The IIA string computation of the leading largekterm in the instanton prefactor was recently performed in arXiv:2304.12340. Here we find that the exact value of the prefactor$$ {\left({\sin}^2\frac{2\pi }{k}\right)}^{-1} $$ sin 2 2 π k 1 is reproduced by the 1-loop term in the M2 brane partition function expanded near theS3/ℤkinstanton configuration. As in the Wilson loop example in arXiv:2303.15207, the quantum M2 brane computation is well defined and produces a finite result in exact agreement with localization. 
    more » « less
  5. Abstract In this paper we prove a higher dimensional analogue of Carleson’s$$\varepsilon ^{2}$$ ε 2 conjecture. Given two arbitrary disjoint Borel sets$$\Omega ^{+},\Omega ^{-}\subset \mathbb{R}^{n+1}$$ Ω + , Ω R n + 1 , and$$x\in \mathbb{R}^{n+1}$$ x R n + 1 ,$$r>0$$ r > 0 , we denote$$ \varepsilon _{n}(x,r) := \frac{1}{r^{n}}\, \inf _{H^{+}} \mathcal{H}^{n} \left ( ((\partial B(x,r)\cap H^{+}) \setminus \Omega ^{+}) \cup (( \partial B(x,r)\cap H^{-}) \setminus \Omega ^{-})\right ), $$ ε n ( x , r ) : = 1 r n inf H + H n ( ( ( B ( x , r ) H + ) Ω + ) ( ( B ( x , r ) H ) Ω ) ) , where the infimum is taken over all open affine half-spaces$$H^{+}$$ H + such that$$x \in \partial H^{+}$$ x H + and we define$$H^{-}= \mathbb{R}^{n+1} \setminus \overline{H^{+}}$$ H = R n + 1 H + . Our first main result asserts that the set of points$$x\in \mathbb{R}^{n+1}$$ x R n + 1 where$$ \int _{0}^{1} \varepsilon _{n}(x,r)^{2} \, \frac{dr}{r}< \infty $$ 0 1 ε n ( x , r ) 2 d r r < is$$n$$ n -rectifiable. For our second main result we assume that$$\Omega ^{+}$$ Ω + ,$$\Omega ^{-}$$ Ω are open and that$$\Omega ^{+}\cup \Omega ^{-}$$ Ω + Ω satisfies the capacity density condition. For each$$x \in \partial \Omega ^{+} \cup \partial \Omega ^{-}$$ x Ω + Ω and$$r>0$$ r > 0 , we denote by$$\alpha ^{\pm }(x,r)$$ α ± ( x , r ) the characteristic constant of the (spherical) open sets$$\Omega ^{\pm }\cap \partial B(x,r)$$ Ω ± B ( x , r ) . We show that, up to a set of$$\mathcal{H}^{n}$$ H n measure zero,$$x$$ x is a tangent point for both$$\partial \Omega ^{+}$$ Ω + and$$\partial \Omega ^{-}$$ Ω if and only if$$ \int _{0}^{1} \min (1,\alpha ^{+}(x,r) + \alpha ^{-}(x,r) -2) \frac{dr}{r} < \infty . $$ 0 1 min ( 1 , α + ( x , r ) + α ( x , r ) 2 ) d r r < . The first result is new even in the plane and the second one improves and extends to higher dimensions the$$\varepsilon ^{2}$$ ε 2 conjecture of Carleson. 
    more » « less