Browsing by Author "Wagner, Stephan"

Now showing 1 - 13 of 13
  • Thumbnail Image
    Item
    Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis
    (SIAM, 2015) Heuberger, Clemens; Krenn, Daniel; Wagner, Stephan
    For fixed t ≥ 2, we consider the class of representations of 1 as a sum of unit fractions whose denominators are powers of t, or equivalently the class of canonical compact t-ary Huffman codes, or equivalently rooted t-ary plane “canonical” trees. We study the probabilistic behavior of the height (limit distribution is shown to be normal), the number of distinct summands (normal distribution), the path length (normal distribution), the width (main term of the expectation and concentration property), and the number of leaves at maximum distance from the root (discrete distribution).
  • No Thumbnail Available
    Item
    Decomposing the hypercube Qn into n isomorphic edge-disjoint trees
    (Elsevier, 2012-02) Wagner, Stephan; Wild, Marcel
    The problem of finding edge-disjoint trees in a hypercube arises for example in the context of parallel computing [3]. Independently of applications it is of high aesthetic appeal. The hypercube of dimension n, denoted by Qn, comprises 2n vertices each corresponding to a distinct binary string of length n. Two vertices are adjacent if and only if their corresponding binary strings differ in exactly one position. Since each vertex of Qn has degree n, the number of edges is n2n−1. A variety of decomposability options derive from this fact. In the remainder of the introduction we focus on three of them. The first two have been dealt with before in the literature; the third is the topic of this article.
  • Thumbnail Image
    Item
    Hofstadter point spectrum trace and the almost Mathieu operator
    (AIP, 2018) Ouvry, Stephane; Wagner, Stephan; Wu, Shuang
    We consider point spectrum traces in the Hofstadter model. We show how to recover the full quantum Hofstadter trace by integrating these point spectrum traces with the appropriate free density of states on the lattice. This construction is then generalized to the almost Mathieu operator and its nth moments which can be expressed in terms of generalized Kreft coefficients.
  • Thumbnail Image
    Item
    Inducibility of d-ary trees
    (Elsevier, 2020) Czabarka, Eva; Dossou-Olory, Audace A. V.; Szekely, Laszlo A.; Wagner, Stephan
    Imitating the binary inducibility, a recently introduced invariant of binary trees (Cz- abarka et al., 2017), we initiate the study of the inducibility of d-ary trees (rooted trees whose vertex outdegrees are bounded from above by d ≥ 2). We determine the exact inducibility for stars and binary caterpillars. For T in the family of strictly d-ary trees (every vertex has 0 or d children), we prove that the difference between the maximum density of a d-ary tree D in T and the inducibility of D is of order O(|T |−1/2) compared to the general case where it is shown that the difference is O(|T |−1) which, in particular, responds positively to a conjecture on the inducibility in binary trees. We also discover that the inducibility of a binary tree in d-ary trees is independent of d. Furthermore, we establish a general lower bound on the inducibility and also provide a bound for some special trees. Moreover, we find that the maximum inducibility is attained for binary caterpillars for every d.
  • Thumbnail Image
    Item
    The number of distinct adjacent pairs in geometrically distributed words
    (Episciences.org, 2021-01-28) Archibald, Margaret; Blecher, Aubrey; Brennan, Charlotte; Knopfmacher, Arnold; Wagner, Stephan; Ward, Mark Daniel
    A sequence of geometric random variables of length n is a sequence of n independent and identically distributed geometric random variables (Γ1,Γ2,…,Γn) where P(Γj=i)=pqi−1 for 1 ≤ j ≤ n with p+q=1. We study the number of distinct adjacent two letter patterns in such sequences. Initially we directly count the number of distinct pairs in words of short length. Because of the rapid growth of the number of word patterns we change our approach to this problem by obtaining an expression for the expected number of distinct pairs in words of length n. We also obtain the asymptotics for the expected number as n→∞.
  • Thumbnail Image
    Item
    On q-Quasiadditive and q-Quasimultiplicative Functions
    (Electronic Journal of Combinatorics, 2017) Kropf, Sara; Wagner, Stephan
    In this paper, we introduce the notion of q-quasiadditivity of arithmetic functions, as well as the related concept of q-quasimultiplicativity, which generalise strong q-additivity and -multiplicativity, respectively. We show that there are many natural examples for these concepts, which are characterised by functional equations of the form f(qk+ra+b) = f(a)+f(b) or f(qk+ra+b) = f(a)f(b) for all b < qk and a fixed parameter r. In addition to some elementary properties of q-quasiadditive and q-quasimultiplicative functions, we prove characterisations of q-quasiadditivity and q-quasimultiplicativity for the special class of q-regular functions. The final main result provides a general central limit theorem that includes both classical and new examples as corollaries.
  • Thumbnail Image
    Item
    On the centroid of increasing trees
    (Episciences.org, 2019) Durant, Kevin; Wagner, Stephan
    A centroid node in a tree is a node for which the sum of the distances to all other nodes attains its minimum, or equivalently a node with the property that none of its branches contains more than half of the other nodes. We generalise some known results regarding the behaviour of centroid nodes in random recursive trees (due to Moon) to the class of very simple increasing trees, which also includes the families of plane-oriented and d-ary increasing trees. In particular, we derive limits of distributions and moments for the depth and label of the centroid node nearest to the root, as well as for the size of the subtree rooted at this node.
  • Thumbnail Image
    Item
    On the distribution of subtree orders of a tree
    (University of Primorska, 2018) Ralaivaosaona, Dimbinaina; Wagner, Stephan
    We investigate the distribution of the number of vertices of a randomly chosen subtree of a tree. Specifically, it is proven that this distribution is close to a Gaussian distribution in an explicitly quantifiable way if the tree has sufficiently many leaves and no long branchless paths. We also show that the conditions are satisfied asymptotically almost surely for random trees. If the conditions are violated, however, we exhibit by means of explicit counterexamples that many other (non-Gaussian) distributions can occur in the limit. These examples also show that our conditions are essentially best possible.
  • Thumbnail Image
    Item
    On the inducibility of small trees
    (Episciences, 2019) Dossou-Olory, Audace A. V.; Wagner, Stephan
    The quantity that captures the asymptotic value of the maximum number of appearances of a given topological tree (a rooted tree with no vertices of outdegree 1) S with k leaves in an arbitrary tree with sufficiently large number of leaves is called the inducibility of S. Its precise value is known only for some specific families of trees, most of them exhibiting a symmetrical configuration. In an attempt to answer a recent question posed by Czabarka, Sz´ekely, and the second author of this article, we provide bounds for the inducibility J(A5) of the 5-leaf binary tree A5 whose branches are a single leaf and the complete binary tree of height 2. It was indicated before that J(A5) appears to be ‘close’ to 1/4. We can make this precise by showing that 0.24707 . . . ≤ J(A5) ≤ 0.24745 . . .. Furthermore, we also consider the problem of determining the inducibility of the tree Q4, which is the only tree among 4-leaf topological trees for which the inducibility is unknown.
  • Thumbnail Image
    Item
    On the minimal Hamming weight of a multi-base representation
    (Elsevier, 2020) Krenn, Daniel; Suppakitpaisarn, Vorapong; Wagner, Stephan
    Given a finite set of bases b1, b2, ..., br (integers greater than 1), a multi-base representation of an integer n is a sum with summands dbα1 1 b α2 2 ··· bαr r , where the αj are nonnegative integers and the digits d are taken from a fixed finite set. We consider multi-base representations with at least two bases that are multiplicatively independent. Our main result states that the order of magnitude of the minimal Hamming weight of an integer n, i.e., the minimal number of nonzero summands in a representation of n, is log n/(log log n). This is independent of the number of bases, the bases themselves, and the digit set. For the proof, the existing upper bound for prime bases is generalized to multiplicatively independent bases; for the required analysis of the natural greedy algorithm, an auxiliary result in Diophantine approximation is derived. The lower bound follows by a counting argument and alternatively by using communication complexity; thereby improving the existing bounds and closing the gap in the order of magnitude.
  • Thumbnail Image
    Item
    On the number of increasing trees with label repetitions
    (Elsevier, 2019) Bodini, Olivier; Genitrini, Antoine; Gittenberger, Bernhard; Wagner, Stephan
    We study the asymptotic number of certain monotonically labeled increasing trees arising from a generalized evolution process. The main difference between the presented model and the classical model of binary increasing trees is that the same label can appear in distinct branches of the tree. In the course of the analysis we develop a method to extract asymptotic information on the coefficients of purely formal power series. The method is based on an approximate Borel transform (or, more generally, Mittag-Leffler transform) which enables us to quickly guess the exponential growth rate. With this guess the sequence is then rescaled and a singularity analysis of the generating function of the scaled counting sequence yields accurate asymptotics. The actual analysis is based on differential equations and a Tauberian argument. The counting problem for trees of size n exhibits interesting asymptotics involving powers of n with irrational exponents.
  • Thumbnail Image
    Item
    Partitioning the hypercube Qn into n isomorphic edge-disjoint trees
    (TU Graz University of Technology, 2011) Wagner, Stephan; Wild, Marcel
    ENGLISH ABSTRACT: The problem of finding edge-disjoint trees in a hypercube e.g. arises in the context of parallel computing. Independent of applications it is of high aesthetic appeal.
  • Thumbnail Image
    Item
    Paths vs. stars in the local prole of trees
    (Electronic Journal of Combinatorics, 2017) Czabarka, Eva; Szekely, Laszlo A.; Wagner, Stephan
    The aim of this paper is to provide an affirmative answer to a recent question by Bubeck and Linial on the local profile of trees.