Bounds on the number of numerical semigroups of a given genus

Lower and upper bounds are given for the number n_g of numerical semigroups of genus g. The lower bound is the first known lower bound while the upper bound significantly improves the only known bound given by the Catalan numbers. In a previous work the sequence n_g is conjectured to behave asymptotically as the Fibonacci numbers. The lower bound proved in this work is related to the Fibonacci numbers and so the result seems to be in the direction to prove the conjecture. The method used is based on an accurate analysis of the tree of numerical semigroups and of the number of descendants of the descendants of each node depending on the number of descendants of the node itself.     

Constructing numerical semigroups of a given genus

Let n _g denote the number of numerical semigroups of genus g. Bras-Amorós conjectured that n _g possesses certain Fibonacci-like properties. Almost all previous attempts at proving this conjecture were based on analyzing the semigroup tree. We offer a new, simpler approach to counting numerical semigroups of a given genus. Our method gives direct constructions of families of numerical semigroups, without referring to the generators or the semigroup tree. In particular, we give an improved asymptotic lower bound for n _g .     

Weighted and roughly weighted simple games

In this paper we give necessary and sufficient conditions for a simple game to have rough weights. We define two functions f(n) and g(n) that measure the deviation of a simple game from a weighted majority game and roughly weighted majority game, respectively. We formulate known results in terms of lower and upper bounds for these functions and improve those bounds. We also investigate rough weightedness of simple games with a small number of players.     

Fibonacci-like growth of numerical semigroups of a given genus

We give an asymptotic estimate of the number of numerical semigroups of a given genus. In particular, if n _g is the number of numerical semigroups of genus g, we prove that $$\lim_{g \rightarrow \infty} n_g \varphi^{-g} = S $$ where $\varphi = \frac{1 + \sqrt{5}}{2}$ is the golden ratio and S is a constant, resolving several related conjectures concerning the growth of n _g . In addition, we show that the proportion of numerical semigroups of genus g satisfying f<3m approaches 1 as g→∞, where m is the multiplicity and f is the Frobenius number.     

Comportement des noyaux de la chaleur des opérateurs de Schrödinger et applications à certaines équations paraboliques semi-linéaires

We consider general Schrödinger operators on domains of Riemannian manifolds with possibly exponential volume growth. We prove sharp large time Gaussian upper bounds. These bounds are then used to prove new Lp-Lp estimates for the corresponding semigroups. Applications to semi-linear parabolic equations are given.     

KP hierarchy for Hodge integrals

Starting from the ELSV formula, we derive a number of new equations on the generating functions for Hodge integrals over the moduli space of complex curves. This gives a new simple and uniform treatment of certain known results on Hodge integrals like Witten's conjecture, Virasoro constrains, Faber's λg-conjecture, etc. Among other results we show that a properly arranged generating function for Hodge integrals satisfies the equations of the KP hierarchy.     

Limit laws for embedded trees: Applications to the integrated superBrownian excursion

We study three families of labeled plane trees. In all these trees, the root is labeled 0 and the labels of two adjacent nodes differ by 0,1, or ?1. One part of the paper is devoted to enumerative results. For each family, and for all j ∈ ?, we obtain closed form expressions for the following three generating functions: the generating function of trees having no label larger than j; the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled j; and finally the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled at least, j. Strangely enough, all these series turn out to be algebraic, but we have no combinatorial intuition for this algebraicity. The other part of the paper is devoted to deriving limit laws from these enumerative results. In each of our families of trees, we endow the trees of size n with the uniform distribution and study the following random variables: M_n, the largest label occurring in a (random) tree; X_n(j), the number of nodes labeled j; and X(j), the number of nodes labeled j or more. We obtain limit laws for scaled versions of these random variables. Finally, we translate the above limit results into statements dealing with the integrated superBrownian excursion. In particular, we describe the law of the supremum of its support (thus recovering some earlier results obtained by Delmas) and the law of its distribution function at a given point. We also conjecture the law of its density (at a given point). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A generalization of Chernoff's product formula for time-dependent operators

In this article we provide a set of sufficient conditions that allow a natural extension of Chernoff's product formula to the case of certain one-parameter family of functions taking values in the algebra L(B) of all bounded linear operators defined on a complex Banach space B. Those functions need not be contraction-valued and are intimately related to certain evolution operators U(t,s)_0?s?t?T on B. The most direct consequences of our main result are new formulae of the Trotter-Kato type which involve either semigroups with time-dependent generators, or the resolvent operators associated with these generators. In the general case we can apply such formulae to evolution problems of parabolic type, as well as to Schrödinger evolution equations albeit in some very special cases. The formulae we prove may also be relevant to the numerical analysis of non-autonomous ordinary and partial differential equations.     

Degree asymptotics of the numerical semigroup tree

A numerical semigroup is a subset Λ of the nonnegative integers that is closed under addition, contains 0, and omits only finitely many nonnegative integers (called the gaps of Λ). The collection of all numerical semigroups may be visually represented by a tree of element removals, in which the children of a semigroup Λ are formed by removing one element of Λ that exceeds all existing gaps of Λ. In general, a semigroup may have many children or none at all, making it difficult to understand the number of semigroups at a given depth on the tree. We investigate the problem of estimating the number of semigroups at depth g with h children, showing that as g becomes large, it tends to a proportion φ ^?h?2 of all numerical semigroups, where φ is the golden ratio.     

Conjugate transforms for τT semigroups of probability distribution functions

This paper introduces the use of conjugate transforms in the study of τ_T semigroups of probability distribution functions. If Δ⁺ denotes the space of one-dimensional distribution functions concentrated on [0, ∞) and T is a t-norm, i.e., a suitable binary operation on [0, 1], then the operation τ_T is defined for F, G in Δ⁺by τ_T(F, G)(x) = sup_{u+v = x}T(F(u), G(v)) for all x. The pair (Δ⁺, τ_T) is then a semigroup. For any Archimedean t-norm T, a conjugate transform C_T is defined on (Δ⁺, τ_T). These transforms are shown to play a role similar to that played by the Laplace transform on the convolution semigroup. Thus a theory of “characteristic functions” for τ_T semigroups is developed. In addition to establishing their basic algebraic properties, we also use conjugate transforms to study the algebraic questions of the cancellation law, infinitely divisible elements, and solutions of equations in τ_T semigroups.     

How to minimize the cost of iterative methods in the presence of perturbations

We consider iterative methods for approximating solutions of nonlinear equations, where the iteration cannot be computed exactly, but is corrupted by additive perturbations. The cost of computing each iteration depends on the size of the perturbation. For a class of cost functions, we show that the total cost of producing an ε-approximation can be made proportional to the cost c(ε) of one single iterative step performed with the accuracy proportional to ε. We also demonstrate that for some cost functions the total cost is proportional to c(ε)². In both cases matching lower bounds are shown. The results find natural application to establishing the complexity of nonlinear boundary-value problems, where they yield an improvement over the known upper bounds, and remove the existing gap between the upper and lower bounds.     

On the graph labellings arising from phylogenetics

We study semigroups of labellings associated to a graph. These generalise the Jukes-Cantor model and phylogenetic toric varieties defined in [Buczynska W., Phylogenetic toric varieties on graphs, J. Algebraic Combin., 2012, 35(3), 421–460]. Our main theorem bounds the degree of the generators of the semigroup by g + 1 when the graph has first Betti number g. Also, we provide a series of examples where the bound is sharp.     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

Rigidity and stability of the Leibniz and the chain rule

We study rigidity and stability properties of the Leibniz and chain rule operator equations. We describe which non-degenerate operators V, T ₁, T ₂,A: C ^k (?) → C(?) satisfy equations of the generalized Leibniz and chain rule type for f, g ∈ C ^k (?), namely, V (f · g) = (T ₁ f) · g + f · (T ₂ g) for k = 1, V (f · g) = (T ₁ f) · g + f · (T ₂ g) + (Af) · (Ag) for k = 2, and V (f ○ g) = (T ₁ f) ○ g · (T ₂ g) for k = 1. Moreover, for multiplicative maps A, we consider a more general version of the first equation, V (f · g) = (T ₁ f) · (Ag) + (Af) · (T ₂ g) for k = 1. In all these cases, we completely determine all solutions. It turns out that, in any of the equations, the operators V, T ₁ and T ₂ must be essentially equal. We also consider perturbations of the chain and the Leibniz rule, T (f ○ g) = Tf ○ g · Tg + B(f ○ g, g) and T (f · g) = Tf · g + f · Tg + B(f, g), and show under suitable conditions on B in the first case that B = 0 and in the second case that the solution is a perturbation of the solution of the standard Leibniz rule equation.     

Integral trees of diameter 6

A graph G is called integral if all eigenvalues of its adjacency matrix A(G) are integers. In this paper, the trees T(p,q)•T(r,m,t) and K_1,s•T(p,q)•T(r,m,t) of diameter 6 are defined. We determine their characteristic polynomials. We also obtain for the first time sufficient and conditions for them to be integral. To do so, we use number theory and apply a computer search. New families of integral trees of diameter 6 are presented. Some of these classes are infinite. They are different from those in the existing literature. We also prove that the problem of finding integral trees of diameter 6 is equivalent to the problem of solving some Diophantine equations. We give a positive answer to a question of Wang et al. [Families of integral trees with diameters 4, 6 and 8, Discrete Appl. Math. 136 (2004) 349-362].     

On Some Functions That Send Each Generator of a C0-Semigroup to the Generator of a Holomorphic Semigroup

We give some conditions on functions of the Schoenberg class T for them to send the generators of uniformly bounded semigroup of class C ₀ to the generators of holomorphic semigroups. This generalizes Yosida, Balakrishnan, and Kato's result relating to fractional powers of operators. The functional calculus of generators of C ₀-semigroups which uses the class T was constructed in the preceding articles of the author.     

Two-side estimates of the number of fixed points of a discrete logarithm

Lower and upper bounds are obtained for an average number of solutions to the congruence g _x ?? x (mod p) in nonnegative integer numbers x ?? p ? 1, where g is a primitive root modulo p.     

Monomial Gorenstein ideals

The paper concerns itself with generating sets for monomial Gorenstein ideals in polynomial rings k[x₁,..., x_r], k an arbitrary field. For r=5 it is shown that for a certain class of these ideals, the number of generators is bounded by 13. To establish the sharpness of this bound an algorithm is established, to obtain all numerical symmetric semigroups with a fixed odd integer 2n+1 as last integer unattained. Finally, a short proof of the known fact is given, that for r=4 the number of elements in a generating set is 3 or 5.