More Like this

1. 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)

   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⩽\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
2. Counting imaginary quadratic fields with an ideal class group of 5-rank at least 2

   https://doi.org/10.1007/s11139-025-01184-6  

   Bartz, Kollin; Levin, Aaron; Thamminana, Aman_Dhruva (August 2025, The Ramanujan Journal)

   Abstract We prove that there are$$\gg \frac{X^{\frac{1}{3}}}{(\log X)^2}$$ $\gg \frac{X^{\frac{1}{3}}}{{(logX)}^2}$imaginary quadratic fieldskwith discriminant$$|d_k|\le X$$ $|d_k|\le 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}}$$ $\gg X^{\frac{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
3. Modified supersymmetric indices in AdS3/CFT2

   https://doi.org/10.1007/JHEP01(2024)099  

   Ardehali, Arash Arabi; Krishna, Hare (January 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> We consider the 𝒩 = (2, 2) AdS₃/CFT₂dualities proposed by Eberhardt, where the bulk geometry is AdS₃× (S³×T⁴)/ℤ_k, and the CFT is a deformation of the symmetric orbifold of the supersymmetric sigma modelT⁴/ℤ_k(withk= 2, 3, 4, 6). The elliptic genera of the two sides vanish due to fermionic zero modes, so for microstate counting applications one must consider modified supersymmetric indices. In an analysis similar to that of Maldacena, Moore, and Strominger for the standard 𝒩 = (4, 4) case ofT⁴, we study the appropriate helicity-trace index of the boundary CFTs. We encounter a strange phenomenon where a saddle-point analysis of our indices reproduces only a fraction (respectively$$ \frac{1}{2} $$ $\frac{1}{2}$,$$ \frac{2}{3} $$ $\frac{2}{3}$,$$ \frac{3}{4} $$ $\frac{3}{4}$,$$ \frac{5}{6} $$ $\frac{5}{6}$) of the Bekenstein-Hawking entropy of the associated macroscopic black branes. 

   more » « less
4. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

   more » « less
5. Probing supersymmetric black holes with surface defects

   https://doi.org/10.1007/JHEP10(2023)136  

   Chen, Yiming; Heydeman, Matthew; Wang, Yifan; Zhang, Mengyang (October 2023, Journal of High Energy Physics)

   A<sc>bstract</sc> It has long been conjectured that the largeNdeconfinement phase transition of$$ \mathcal{N} $$ $N$= 4 SU(N) super-Yang-Mills corresponds via AdS/CFT to the Hawking-Page transition in which black holes dominate the thermal ensemble, and quantitative evidence of this has come through the recent matching of the superconformal index of$$ \frac{1}{16} $$ $\frac{1}{16}$-BPS states to the supersymmetric black hole entropy. We introduce the half-BPS Gukov-Witten surface defect as a probe of the superconformal index, which also serves as an order parameter for the deconfinement transition. This can be studied directly in field theory as a modification of the usual unitary matrix model or in the dual description as a D3-brane probe in the background of a (complex) supersymmetric black hole. Using a saddle point approximation, we determine our defect index in the largeNlimit as a simple function of the chemical potentials and show independently that it is reproduced by the renormalized action of the brane in the black hole background. Along the way, we also comment on the Cardy limit and the thermodynamics of the D3-brane in the generalized ensemble. The defect index sharply distinguishes between the confining and the deconfining phases of the gauge theory and thus is a supersymmetric non-perturbative order parameter for these largeNphase transitions which deserves further investigation. Finally, our work provides an example where the properties of a black hole coupled to an external system can be analyzed precisely. 

   more » « less