Search

We consider the sum-of-digits functions $s_2$ and $s_3$ in bases $2$ and $3$. These functions just return the minimal numbers of powers of two (resp. three) needed in order to represent a nonnegative integer as their sum. A result of the second author states that there are infinitely many \emph{collisions} of $s_2$ and $s_3$, that is, positive integers $n$ such that \[s_2(n)=s_3(n).\] This resolved a long-standing folklore conjecture. In the present paper, we prove a strong generalization of this statement, stating that $(s_2(n),s_3(n))$ attains almost all values in $\mathbb N^2$, in the sense of asymptotic density. In particular, this yields \emph{generalized collisions}: for any pair $(a,b)$ of positive integers, the equation \[as_2(n)=bs_3(n)\] admits infinitely many solutions in $n$., Comment: 24 pages

The purpose of this paper is to study the limiting distribution of special {\it additive functionals} on random planar maps, namely the number of occurrences of a given {\it pattern}. The main result is a central limit theorem for these pattern counts in the case of pattern with a simple boundary. The proof relies on a combination of analytic and combinatorial methods together with a moment method due to Gao and Wormald~\cite{GaoWormald}. It is an important issue to handle the overlap structure of two pattern which is the main difficulty in the proof., Comment: 47 pages

Thresholded hybrid systems are restricted dynamical systems, where the current mode, and hence the ODE system describing its behavior, is solely determined by externally supplied digital input signals and where the only output signals are digital ones generated by comparing an internal state variable to a threshold value. An attractive feature of such systems is easy composition, which is facilitated by their purely digital interface. A particularly promising application domain of thresholded hybrid systems is digital integrated circuits: Modern digital circuit design considers them as a composition of Millions and even Billions of elementary logic gates, like inverters, GOR and Gand. Since every such logic gate is eventually implemented as an electronic circuit, however, which exhibits a behavior that is governed by some ODE system, thresholded hybrid systems are ideally suited for making the transition from the analog to the digital world rigorous. In this paper, we prove that the mapping from digital input signals to digital output signals is continuous for a large class of thresholded hybrid systems. Moreover, we show that, under some mild conditions regarding causality, this continuity also continues to hold for arbitrary compositions, which in turn guarantees that the composition faithfully captures the analog reality. By applying our generic results to some recently developed thresholded hybrid gate models, both for single-input single-output gates like inverters and for a two-input CMOS NOR gate, we show that they are continuous. Moreover, we provide a novel thresholded hybrid model for the two-input NOR gate, which is not only continuous but also, unlike the existing one, faithfully models all multi-input switching effects., Comment: There was a missing author from the last submission. arXiv admin note: substantial text overlap with arXiv:2303.14048

Given $t\geq 2$ and $0\leq k\leq t$, we prove that the number of labelled $k$-connected chordal graphs with $n$ vertices and tree-width at most $t$ is asymptotically $c n^{-5/2} \gamma^n n!$, as $n\to\infty$, for some constants $c,\gamma >0$ depending on $t$ and $k$. Additionally, we show that the number of $i$-cliques ($2\leq i\leq t$) in a uniform random $k$-connected chordal graph with tree-width at most $t$ is normally distributed as $n\to\infty$. The asymptotic enumeration of graphs of tree-width at most $t$ is wide open for $t\geq 3$. To the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width where the asymptotic counting problem is solved. Our starting point is the work of Wormald [Counting Labelled Chordal Graphs, Graphs and Combinatorics (1985)], were an algorithm is developed to obtain the exact number of labelled chordal graphs on $n$ vertices., Comment: 23 pages, 5 figures

Functional equations with one catalytic appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that under certain positivity assumptions the dominant singularity of the solutions have a universal behavior. We have to distinguish between linear catalytic equations, where a dominating square root singularity appears, and non-linear catalytic equations, where we - usually - have a singularity of type 3/2.

The purpose of this paper is to study subsequences of synchronizing $k$-automatic sequences $a(n)$ along Piatetski-Shapiro sequences $\lfloor n^c \rfloor$ with non-integer $c>1$. In particular, we show that $a(\lfloor n^c \rfloor)$ satisfies a prime number theorem of the form $\sum_{n\le x} \Lambda(n)a(\lfloor n^c \rfloor) \sim C\, x$, and, furthermore, that it is deterministic for $c \in \mathbb R\setminus \mathbb Z$. As an interesting additional result, we show that the sequence $\lfloor n^c\rfloor \bmod m$ has polynomial subword complexity., Comment: 32 pages

We analyse uniform random cubic rooted planar maps and obtain limiting distributions for several parameters of interest. From the enumerative point of view, we present a unified approach for the enumeration of several classes of cubic planar maps, which allow us to recover known results in a more general and transparent way. This approach allows us to obtain new enumerative results. Concerning random maps, we first obtain the distribution of the degree of the root face, which has an exponential tail as for other classes of random maps. Our main result is a limiting map-Airy distribution law for the size of the largest block $L$, whose expectation is asymptotically $n/\sqrt{3}$ in a random cubic map with $n+2$ faces. We prove analogous results for the size of the largest cubic block, obtained from $L$ by erasing all vertices of degree two, and for the size of the largest 3-connected component, whose expected values are respectively $n/2$ and $n/4$. To obtain these results we need to analyse a new type of composition scheme which has not been treated by Banderier et al. [Random Structures Algorithms 2001]., Comment: 32 pages