Search

We prove a conjectured asymptotic formula of Kuperberg from the representation theory of the Lie algebra \(G_2\). Given two non-negative integer sequences \((a_n)_{n\geq 0}\) and \((b_n)_{n\geq 0}\), with \(a_0=b_0=1\), it is well-known that if the identity \(B(x)=A(xB(x))\) holds for the generating functions \(A(x)=1+\sum_{n\geq 1} a_n x^n\) and \(B(x)=1+\sum_{n\geq 1} b_n x^n\), then \(b_n\) is the number of rooted planar trees with \(n+1\) vertices such that each vertex having \(i\) children may be colored with any one of \(a_i\) distinct colors. Kuperberg proved a specific case when this identity holds, namely when \(b_n=\dim \operatorname{Inv}_{G_2} (V(\lambda_1)^{\otimes n})\), where \(V(\lambda_1)\) is the 7-dimensional fundamental representation of \(G_2\), and \(a_n\) is the number of triangulations of a regular \(n\)-gon such that each internal vertex has degree at least \(6\). He also observed that \(\limsup_{n\to\infty}\sqrt[n]{a_n}\leq 7/B(1/7)\) and conjectured that this estimate is sharp, or, in terms of power series, that the radius of convergence of \(A(x)\) is exactly \(B(1/7)/7\). We prove this conjecture by introducing a new criterion for sharpness in the analogous estimate for general power series \(A(x)\) and \(B(x)\) satisfying \(B(x)=A(xB(x))\). Moreover, by way of singularity analysis performed on a recently discovered generating function for \(B(x)\), we significantly refine the conjecture by deriving an asymptotic formula for the sequence \((a_n)\).Mathematics Subject Classifications: 05A16, 05E10Keywords: Analytic combinatorics

Although regular expressions do not correspond univocally to regular languages, it is still worthwhile to study their properties and algorithms. For the average case analysis one often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward that asymptotic estimates obtained by considering the whole set of regular expressions are different from those obtained using a more refined set that avoids some large class of equivalent expressions. In this paper we study a set of expressions that avoid a given absorbing pattern. It is shown that, although this set is significantly smaller than the standard one, the asymptotic average estimates for the size of the Glushkov automaton for these expressions does not differ from the standard case. Furthermore, for this set the asymptotic density of 휀-accepting expressions is also the same as for the set of all standard regular expressions. [ABSTRACT FROM AUTHOR]

The Gödel–Dummett logic and Łukasiewicz one are two main many-valued logics used by the fuzzy logic community. Our goal is a quantitative comparison of these two. In this paper, we will mostly consider the 3-valued Gödel–Dummett logic as well as the 3-valued Łukasiewicz one. We shall concentrate on their implicational-negation fragments which are limited to formulas formed with a fixed finite number of variables. First, we investigate the proportion of the number of true formulas of a certain length n to the number of all formulas of such length built with exactly one variable. Then, we investigate such proportion for satisfiable formulas. Second, we generalise our investigation on formulas written with $ k\ge 1 $ k ≥ 1 variables. The primary goal of the paper is the research on the asymptotic behaviour of these fractions when the length n tends to infinity. If such limits exists, they are real numbers between 0 and 1, which are called the density of truth or the density of SAT. To compare the density of truth and the density of satisfiable formulas for both fragments of 3-valued Gödel–Dummett's and Łukasiewicz's logics we use the powerful theory of analytic combinatorics. This paper is a natural continuation of the previous brief conference note by Kostrzycka and Zaionc (2020) as well as enriched with some previous results from Kostrzycka and Zaionc (2003). In the conference note we computed analytically the density of truth and the density of SAT (with a determined precision) for 3-valued Łukasiewicz's logic restricted to a language with only one variable. In Kostrzycka and Zaionc (2003) we computed the same values for exactly the same fragment of the 3-valued Gödel–Dummett logic. This paper answers the more general questions of the existence of density of truth and density of SAT for both many-valued logics with an arbitrary finite number of variables. Therefore this paper gives an an interesting picture of two main families of finite-valued fuzzy logics problems treated quantitatively. This picture is taken from the perspective of classical logic. It shows that unexpectedly there is quantitatively a little distance between these two approaches. [ABSTRACT FROM AUTHOR]

We prove solution uniqueness for the genus one Canham variational problem arising in the shape prediction of biomembranes. The proof builds on a result of Yu and Chen that reduces the variational problem to proving positivity of a sequence defined by a linear recurrence relation with polynomial coefficients. We combine rigorous numeric analytic continuation of D-finite functions with classic bounds from singularity analysis to derive an effective index where the asymptotic behaviour of the sequence, which is positive, dominates the sequence behaviour. Positivity of the finite number of remaining terms is then checked separately.Mathematics Subject Classifications: 05A16, 68Q40, 30B40Keywords: Analytic combinatorics, D-finite, P-recursive, positivity, Canham model

We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence Ψ, in the language of two total orders, the probability pn,Ψ that a uniform random 231-avoiding permutation of size n satisfies Ψ admits a limit as n is large. Moreover, we establish two further results about the behavior and value of pn,Ψ: (i) it is either bounded away from 0, or decays exponentially fast; (ii) the set of possible limits is dense in [0, 1]. Our tools come mainly from analytic combinatorics and singularity analysis. [ABSTRACT FROM AUTHOR]

In this paper, we give a simple criterion to verify that functions of the form e g are in the Hayman class when g is a power series with nonnegative coefficients. Thus, using the Hayman and Báez-Duarte formulas, we obtain asymptotics for the coefficients of generating functions that arise in many examples of set construction in analytic combinatorics. This new criterion greatly simplifies the one obtained previously by the authors. [ABSTRACT FROM AUTHOR]

We study classes of musical scales obtained from shift spaces in symbolic dynamics through the first symbol rule, which yields scales in any n-TET tuning system. The modes are thought as elements of orbit equivalence classes of cyclic shift actions on languages, and we study their orbitals and transversals. We present explicit formulations of the generating functions that allow us to deduce the orbital and transversal dimensions of classes of musical scales generated by vertex shifts, for all n, in particular for the 12-TET tuning system. [ABSTRACT FROM AUTHOR]

On complex algebraic varieties, height functions arising in combinatorial applications fail to be proper. This complicates both the description and computation via Morse theory of key topological invariants. Here we establish checkable conditions under which the behavior at infinity may be ignored, and the usual theorems of classical and stratified Morse theory may be applied. This allows for simplified arguments in the field of analytic combinatorics in several variables, and forms the basis for new methods applying to problems beyond the reach of previous techniques. [ABSTRACT FROM AUTHOR]

Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called Pólya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results. [ABSTRACT FROM AUTHOR]

We are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing trees. These families are typical representatives of tree models with a small depth. Once a tree of size n is compacted by keeping only one occurrence of all fringe subtrees appearing in the tree the resulting graph contains only O(n/lnn) nodes. This result must be compared to classical results of compaction in the families of simply generated trees, where the analogous result states that the compacted structure is of size of order n/lnn. The result about the plane binary increasing trees has already been proved, but we propose a new and generic approach to get the result. Finally, an experimental study is presented, based on a prototype implementation of compacted binary search trees that are modeled by plane binary increasing trees. [ABSTRACT FROM AUTHOR]

In this paper, we focus on shape partitions. We show that for any fixed k, one can symbolically characterize the shape partition on a k × n rectangular grid by a context-free grammar. We explicitly give this grammar for k = 2 and k = 3 (for k = 1, this corresponds to compositions of integers). From these grammars, we deduce the number of shape partitions for the k × n rectangular grids for k ∈ {1, 2, 3} and every n, as well as the limiting Gaussian distribution of the number of connected components. This also enables us to randomly and uniformly generate shape partitions of large size. [ABSTRACT FROM AUTHOR]

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion— $q$ -ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated. [ABSTRACT FROM AUTHOR]

The relationship between a stable multivariable polynomial p(z) and the Fourier coefficients of its spectral density function 1 / | p (z) | 2 , is further investigated. In this paper we focus on the radial asymptotics of the Fourier coefficients for a specific choice of a two variable polynomial. Hypergeometric functions appear in the analysis, and new results are derived for these as well. [ABSTRACT FROM AUTHOR]

In this article, we study the impact of applying simple reduction rules to random syntactic formulas encoded as trees. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with n nodes, then the expected size of the result is bounded by a constant. The same holds for higher moments, establishing the lack of expressivity of uniform random expressions. Our framework is quite general as we consider expressions defined by systems of combinatorial equations. For our proofs, we rely on Drmota's multidimensional theorem for systems of generating functions. [ABSTRACT FROM AUTHOR]

In this article, we study some properties of random regular expressions of size n , when the cardinality of the alphabet also depends on n. For this, we revisit and improve the classical Transfer Theorem from the field of analytic combinatorics. This provides precise estimations for the number of regular expressions, the probability of recognizing the empty word and the expected number of Kleene stars in a random expression. For all these statistics, we show that there is a threshold when the size of the alphabet approaches n 2 , at which point the leading term in the asymptotics starts oscillating. [ABSTRACT FROM AUTHOR]

In this article, we consider random expressions produced as BST-like trees (from the term BST, binary search trees), and study the effect of simple semantic reductions on them. These random trees are fast to produce and can be parametrized; that is why they are often used in benchmarks for model-checking tools. We assume the existence of an operator ⊛ that has an absorbing pattern and study the effect of the induced bottom-up reduction, which produces a semantically equivalent (and smaller) tree. Our main result concerns the expected size of a random tree, of given input size n → ∞ , after reduction. We show that there are two different thresholds, leading to a total of five regimes, ranging from no significant reduction at all, to almost complete reduction. We characterize these regimes completely in terms of the probability of picking the absorbing operator. Our study shows that the parameters of random BST-like trees must be considered carefully, yet, contrarily to uniform random trees, they might offer a relevant way to sample interesting random expressions in practice. [ABSTRACT FROM AUTHOR]

Many biochemical reaction networks are inherently multiscale in time and in the counts of participating molecular species. A standard technique to treat different time scales in the stochastic kinetics framework is averaging or quasi-steady-state analysis: it is assumed that the fast dynamics reaches its equilibrium (stationary) distribution on a time scale where the slowly varying molecular counts are unlikely to have changed. We derive analytic equilibrium distributions for various simple biochemical systems, such as enzymatic reactions and gene regulation models. These can be directly inserted into simulations of the slow time-scale dynamics. They also provide insight into the stimulus-response of these systems. An important model for which we derive the analytic equilibrium distribution is the binding of dimer transcription factors (TFs) that first have to form from monomers. This gene regulation mechanism is compared to the cases of the binding of simple monomer TFs to one gene or to multiple copies of a gene, and to the cases of the cooperative binding of two or multiple TFs to a gene. The results apply equally to ligands binding to enzyme molecules.

The increasing throughput of DNA sequencing technologies creates a need for faster algorithms. The fate of most reads is to be mapped to a reference sequence, typically a genome. Modern mappers rely on heuristics to gain speed at a reasonable cost for accuracy. In the seeding heuristic, short matches between the reads and the genome are used to narrow the search to a set of candidate locations. Several seeding variants used in modern mappers show good empirical performance but they are difficult to calibrate or to optimize for lack of theoretical results. Here we develop a theory to estimate the probability that the correct location of a read is filtered out during seeding, resulting in mapping errors. We describe the properties of simple exact seeds, skip seeds and MEM seeds (Maximal Exact Match seeds). The main innovation of this work is to use concepts from analytic combinatorics to represent reads as abstract sequences, and to specify their generative function to estimate the probabilities of interest. We provide several algorithms, which together give a workable solution for the problem of calibrating seeding heuristics for short reads. We also provide a C implementation of these algorithms in a library called Sesame. These results can improve current mapping algorithms and lay the foundation of a general strategy to tackle sequence alignment problems. The Sesame library is open source and available for download at https://github.com/gui11aume/sesame.

A multiple target tracking filter is developed for merged measurement problems that arise with finite resolution sensors. The resulting combinatorial problem is incorporated directly in the joint likelihood function using analytic combinatorics techniques. The Bayesian filter is a sum of several terms that correspond one-to-one to the set of all feasible hypotheses about measurements and targets, i.e., resolved/unresolved, detected/undetected. Performance is demonstrated for two targets in both crossing and parallel target motion scenarios. [ABSTRACT FROM AUTHOR]

The increasing throughput of DNA sequencing technologies creates a need for faster algorithms. The fate of most reads is to be mapped to a reference sequence, typically a genome. Modern mappers rely on heuristics to gain speed at a reasonable cost for accuracy. In the seeding heuristic, short matches between the reads and the genome are used to narrow the search to a set of candidate locations. Several seeding variants used in modern mappers show good empirical performance but they are difficult to calibrate or to optimize for lack of theoretical results. Here we develop a theory to estimate the probability that the correct location of a read is filtered out during seeding, resulting in mapping errors. We describe the properties of simple exact seeds, skip seeds and MEM seeds (Maximal Exact Match seeds). The main innovation of this work is to use concepts from analytic combinatorics to represent reads as abstract sequences, and to specify their generative function to estimate the probabilities of interest. We provide several algorithms, which together give a workable solution for the problem of calibrating seeding heuristics for short reads. We also provide a C implementation of these algorithms in a library called Sesame. These results can improve current mapping algorithms and lay the foundation of a general strategy to tackle sequence alignment problems. The Sesame library is open source and available for download at https://github.com/gui11aume/sesame. [ABSTRACT FROM AUTHOR]

We provide precise asymptotic estimates for the number of several classes of labeled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky and coworkers. We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps. [ABSTRACT FROM AUTHOR]

As an increasing amount of data is gathered nowadays and stored in databases, the question arises of how to protect the privacy of individual records in a database even while providing accurate answers to queries on the database. Differential Privacy (DP) has gained acceptance as a framework to quantify vulnerability of algorithms to privacy breaches. We consider the problem of how to sanitize an entire database via a DP mechanism, on which unlimited further querying is performed. While protecting privacy, it is important that the sanitized database still provide accurate responses to queries. The central contribution of this work is to characterize the amount of information preserved in an optimal DP database sanitizing mechanism (DSM). We precisely characterize the utility-privacy trade-off of mechanisms that sanitize databases in the asymptotic regime of large databases. We study this in an information-theoretic framework by modeling a generic distribution on the data, and a measure of fidelity between the histograms of the original and sanitized databases. We consider the popular $\mathbb {L}_{1}-$ distortion metric, i.e., the total variation norm that leads to the formulation as a linear program (LP). This optimization problem is prohibitive in complexity with the number of constraints growing exponentially in the parameters of the problem. Our focus on the asymptotic regime enables us characterize precisely, the limit of the sequence of solutions to this optimization problem. Leveraging tools from discrete geometry, analytic combinatorics, and duality theorems of optimization, we fully characterize this limit in terms of a power series whose coefficients are the number of integer points on a multidimensional convex cross-polytope studied by Ehrhart in 1967. Employing Ehrhart theory, we determine a simple closed form computable expression for the asymptotic growth of the optimal privacy-fidelity trade-off to infinite precision. At the heart of the findings is a deep connection between the minimum expected distortion and a fundamental construct in Ehrhart theory - Ehrhart series of an integral convex polytope. [ABSTRACT FROM AUTHOR]

We consider the enumeration of walks on the nonnegative lattice Nd; with steps defined by a set S = f-1; 0; 1gdnf0g. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps S is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions having nonsmooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of ACSV. One application is a closed form for asymptotics of models defined by step sets that are symmetric over all but one axis. As a special case, we apply our results when d = 2 to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given. [ABSTRACT FROM AUTHOR]

For regular expressions in (strong) star normal form a large set of efficient algorithms is known, from conversions into finite automata to characterisations of unambiguity. In this paper we study the average complexity of this class of expressions using analytic combinatorics. As it is not always feasible to obtain explicit expressions for the generating functions involved, here we show how to get the required information for the asymptotic estimates with an indirect use of the existence of Puiseux expansions at singularities. We study, asymptotically and on average, the alphabetic size, the size of the 𝜀 -follow automaton and of the position automaton, as well as the ratio and the size of these expressions to standard regular expressions. [ABSTRACT FROM AUTHOR]

We enumerate the connected graphs that contain a number of edges growing linearly with respect to the number of vertices. So far, only the first term of the asymptotics and a bound on the error were known. Using analytic combinatorics, that is, generating function manipulations, we derive a formula for the coefficients of the complete asymptotic expansion. The same result is derived for connected multigraphs. [ABSTRACT FROM AUTHOR]

Given a gene-tree labeled topology G and a species tree S , the ancestral configurations at an internal node k of S represent the combinatorially different sets of gene lineages that can be present at k when all possible realizations of G in S are considered. Ancestral configurations have been introduced as a data structure for evaluating the conditional probability of a gene-tree labeled topology given a species tree, and their enumeration assists in describing the complexity of this computation. In the case that the gene-tree labeled topology G = t matches that of the species tree S , by techniques of analytic combinatorics, we study distributional properties of the total number of ancestral configurations measured across the different nodes of a random labeled topology t selected under the uniform and the Yule probability models. Under both of these probabilistic scenarios, we show that the total number T n of ancestral configurations of a random labeled topology of n taxa asymptotically follows a lognormal distribution. Over uniformly distributed labeled topologies, the asymptotic growth of the mean and the variance of T n are found to satisfy E U [ T n ] ∼ 2.449 ⋅ 1.333 n and V U [ T n ] ∼ 5.050 ⋅ 1.822 n , respectively. Under the Yule model, which assigns higher probabilities to more balanced labeled topologies, we obtain the mean E Y [ T n ] ∼ 1.425 n and the variance V Y [ T n ] ∼ 2.045 n. [ABSTRACT FROM AUTHOR]

Abstract Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation. [ABSTRACT FROM AUTHOR]