Asymptotic Analysis of Extremal Discrete Structures

Optimising structures or algorithms is a permanent goal in various branches of mathematics and their applications. Apart from the optimal solutions, we are interested also in their qualitative and quantitative behaviour for large values of the parameters in order to get a better understanding of their nature. Furthermore, we are then able to compare our solutions with other approaches and strategies. This leads to the quest for a precise asymptotic and probabilistic analysis of discrete structures and algorithms. In this vast field, we are especially interested in mathematical problems in graph theory and in applications in cryptography. In the past decades a variety of different graph theoretical indices were investigated intensively, some of them because molecules can be modelled as undirected graphs and certain physicochemical properties depend on the structure of these graphs, quantified by various graph theoretical indices. It is a natural question to determine the range of graph theoretical indices and to identify those graphs maximising or minimising the indices over a certain class of graphs, e.g. trees. Thus, it is our intention to determine extremal graphs for indices related to the Wiener index (sum of pairwise distances), the Merrifield-Simmons index (number of independent sets) and the Hosoya index (number of matchings) under various constraints. The description of those extremal graphs sometimes involves other concepts, one example being special digital expansions of the parameters, e.g. the order of the graph. On the other hand, digital expansions are also a key ingredient for our study of problems motivated by cryptography. Public-key (asymmetric) cryptography relies on the efficient computation of one-way functions, one common example being computing scalar multiples nP of an element P in some Abelian group. The classic procedure is to represent n by a digital expansion and to compute the scalar multiple nP by Horner`s scheme, resulting in the so-called double-and-add method. Apart from the multiplicative group of a finite field, the point group of an elliptic (or hyperelliptic) curve is widely used. The additional structure of these groups allows many variations of the basic double-and-add method. In particular, digital expansions to non-rational bases are of interest. We intend to derive optimal expansions in various contexts and perform precise asymptotic and probabilistic analyses of the resulting algorithms in the sense of D. E. Knuth.

While humans are used to the classical decimal digit system (in base ten with digits from 0 to 9), computers routinely use the binary digit system (base two) with digits 0 and 1. For specific applications, however, other digit systems turn out to be more useful. For instance, for encryption as it is used for secure communications over the internet, it is more efficient to use digit expansions in base two with digits -1, 0, and 1. The weight, i.e., the number of non-zero digits, then influences the running time of the encryption algorithm. As the introduction of the digit -1 leads to several possible expansions for the same integer, it is possible to choose an expansion which minimises the weight. It is known that the average weight when using digits 0 and 1 is one half of the number of digits whereas allowing the digit -1 decreases the average weight to one third of the number of digits. Using even more digits decreases the average weight further. It was one central aim of this project to determine the average weight as precisely as possible for a large class of digit expansions. It turned out that an adequate tool to describe such expansions are so-called transducer automata. These can be described by finitely many states and transitions between these states which transform the input (the standard binary expansion) to the desired expansion. The analysis of the average weight as well as its standard deviation can then be performed by considering appropriate properties of the underlying transducer. The results depend heavily on connectivity properties of the transducers. In the simplest case it turns out that the weight of a random expansion is approximately normally distributed. Such an analysis is typical for the scientific field of mathematical analysis of algorithms. Its aim is to analyse the running time of various algorithms as precisely as possible. It uses methods from many areas of mathematics. Another example of an algorithm studied in the frame of this project is the so-called dual- pivot quicksort algorithm. Sorting lists of values is a key ingredient in many applications and should be done as efficiently as possible. The performance of a sorting algorithm is usually measured by the number of comparisons which need to be made. By modelling the number of comparisons as a so-called lattice path endowed with a special probability distribution, we were able to prove that a particular variant of dual-pivot quicksort is indeed optimal in its class and to determine its performance with very high precision. Lattice paths can also be used to describe certain parameters of trees, i.e., graphs consisting of states and connections between these states which do not induce cycles. Here, we analysed various growth parameters associated with trees, for example the HortonStrahler number which is also used to describe river networks. In order to obtain our results, extensive computer calculations are required. This led to implementation of two modules for the open source computer algebra system SageMath, one for manipulations with transducer automata and the other for computations with asymptotic expressions. The aim when implementing these packages was to have versatile modules which can use the full power of SageMath while computing with transducer automata and asymptotic expansions, respectively.