- Browse by Author

### Browsing by Author "Wagner, Stephan"

Now showing 1 - 10 of 10

###### Results Per Page

###### Sort Options

- ItemCanonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis(SIAM, 2015) Heuberger, Clemens; Krenn, Daniel; Wagner, Stephan
Show more 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).Show more - ItemDecomposing the hypercube Qn into n isomorphic edge-disjoint trees(Elsevier, 2012-02) Wagner, Stephan; Wild, Marcel
Show more 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.Show more - ItemHofstadter point spectrum trace and the almost Mathieu operator(AIP, 2018) Ouvry, Stephane; Wagner, Stephan; Wu, Shuang
Show more 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.Show more - ItemOn q-Quasiadditive and q-Quasimultiplicative Functions(Electronic Journal of Combinatorics, 2017) Kropf, Sara; Wagner, Stephan
Show more 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.Show more - ItemOn the centroid of increasing trees(Episciences.org, 2019) Durant, Kevin; Wagner, Stephan
Show more 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.Show more - ItemOn the distribution of subtree orders of a tree(University of Primorska, 2018) Ralaivaosaona, Dimbinaina; Wagner, Stephan
Show more 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.Show more - ItemOn the inducibility of small trees(Episciences, 2019) Dossou-Olory, Audace A. V.; Wagner, Stephan
Show more 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.Show more - ItemOn the minimal Hamming weight of a multi-base representation(Elsevier, 2020) Krenn, Daniel; Suppakitpaisarn, Vorapong; Wagner, Stephan
Show more 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.Show more - ItemPartitioning the hypercube Qn into n isomorphic edge-disjoint trees(TU Graz University of Technology, 2011) Wagner, Stephan; Wild, Marcel
Show more 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.Show more - ItemPaths vs. stars in the local prole of trees(Electronic Journal of Combinatorics, 2017) Czabarka, Eva; Szekely, Laszlo A.; Wagner, Stephan
Show more 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.Show more