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 $$ . 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}}$$ , exceeding the growth$$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}}$$ compared to$$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$$ and the maximum of$$g=\lfloor \frac{n-1}{2} \rfloor $$ . We discuss implications in mathematical phylogenetics.
more »
« less
GHz Ultrasonic Chip-Scale Device Induces Ion Channel Stimulation in Human Neural Cells
Abstract Emergent trends in the device development for neural prosthetics have focused on establishing stimulus localization, improving longevity through immune compatibility, reducing energy re-quirements, and embedding active control in the devices. Ultrasound stimulation can single-handedly address several of these challenges. Ultrasonic stimulus of neurons has been studied extensively from 100 kHz to 10 MHz, with high penetration but less localization. In this paper, a chip-scale device consisting of piezoelectric Aluminum Nitride ultrasonic transducers was engineered to deliver gigahertz (GHz) ultrasonic stimulus to the human neural cells. These devices provide a path towards complementary metal oxide semiconductor (CMOS) integration towards fully controllable neural devices. At GHz frequencies, ultrasonic wavelengths in water are a few microns and have an absorption depth of 10–20 µm. This confinement of energy can be used to control stimulation volume within a single neuron. This paper is the first proof-of-concept study to demonstrate that GHz ultrasound can stimulate neuronsin vitro. By utilizing optical calcium imaging, which records calcium ion flux indicating occurrence of an action potential, this paper demonstrates that an application of a nontoxic dosage of GHz ultrasonic waves$$(\ge 0.05\frac{W}{c{m}^{2}})$$ caused an average normalized fluorescence intensity recordings >1.40 for the calcium transients. Electrical effects due to chip-scale ultrasound delivery was discounted as the sole mechanism in stimulation, with effects tested atα = 0.01 statistical significance amongst all intensities and con-trol groups. Ionic transients recorded optically were confirmed to be mediated by ion channels and experimental data suggests an insignificant thermal contributions to stimulation, with a predicted increase of 0.03oCfor$$1.2\frac{W}{c{m}^{2}}\cdot $$ This paper paves the experimental framework to further explore chip-scale axon and neuron specific neural stimulation, with future applications in neural prosthetics, chip scale neural engineering, and extensions to different tissue and cell types.
more »
« less
- Award ID(s):
- 1744271
- PAR ID:
- 10154066
- Publisher / Repository:
- Nature Publishing Group
- Date Published:
- Journal Name:
- Scientific Reports
- Volume:
- 10
- Issue:
- 1
- ISSN:
- 2045-2322
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let$$\mathbb {F}_q^d$$ be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ and a fixed nonzero$$t\in \mathbb {F}_q$$ , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ , where$$h_y:E\rightarrow \{0,1\}$$ is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ that if$$|E|\ge Cq^{\frac{11}{4}}$$ andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ isdwhenever$$E\subseteq \mathbb {F}_q^d$$ with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ .more » « less
-
Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ where$$k \ge 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$$ through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ , where$$|x-y|$$ is the Euclidean distance betweenxandy, and$$c_k$$ is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ . From the other direction, for every$$k \ge 2$$ and$$n \ge 2$$ , there existnpoints in$$[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}$$ . For the plane, the best constant is$$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}$$ for every$$k \ge 3$$ and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ , for every$$k \ge 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}$$ or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ . Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ , which disproves the conjecture for$$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
-
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 {\zeta(s)}. For example, integrating {|\zeta(\frac{1}{2}+\alpha+it)|^{-2k}}with respect totfromTto {2T}, we obtain an asymptotic formula when the shift α is roughly bigger than {\frac{1}{\log T}}and {k<\frac{1}{2}}. We also obtain non-trivial upper bounds for much smaller shifts, as long as {\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
-
Abstract In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization withnon-Lipschitzianvalue functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a$$(T+1)$$ -stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$ -optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ , and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$ -optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization.more » « less