 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 6 no. 1
1. Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees
We study numerically a non-linear integral equation that arises in the study of binary search trees. If the tree is constructed from n elements, this integral equation describes the asymptotic (as n→∞) distribution of the height of the tree. This supplements some asymptotic results we recently obtained for the tails of the distribution. The asymptotic height distribution is shown to be unimodal with highly asymmetric tails.
2. Counting occurrences of some subword patterns
We find generating functions the number of strings (words) containing a specified number of occurrences of certain types of order-isomorphic classes of substrings called subword patterns. In particular, we find generating functions for the number of strings containing a specified number of occurrences of a given 3-letter subword pattern.
3. The b-chromatic number of power graphs
The b-chromatic number of a graph G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i≤ k, has at least one representant x_i adjacent to a vertex of every color j, 1 ≤ j ≠ i ≤ k. In this paper, we discuss the b-chromatic number of some power graphs. We give the exact value of the b-chromatic number of power paths and power complete binary trees, and we bound the b-chromatic number of power cycles.
4. Some Algebraic Aspects of Morse Code Sequences
Morse code sequences are very useful to give combinatorial interpretations of various properties of Fibonacci numbers. In this note we study some algebraic and combinatorial aspects of Morse code sequences and obtain several q-analogues of Fibonacci numbers and Fibonacci polynomials and their generalizations.
5. A new two-variable generalization of the chromatic polynomial
We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of a graph. This new polynomial satisfies both an edge decomposition formula and a vertex decomposition formula. We establish two general expressions for this new polynomial: one in terms of the broken circuit complex and one in terms of the lattice of forbidden colorings. We show that the new polynomial may be considered as a specialization of Stanley's chromatic symmetric function. We finally give explicit expressions for the generalized chromatic polynomial of complete graphs, complete bipartite graphs, paths, and cycles, and show that it can be computed in polynomial time for trees and graphs of restricted pathwidth.
6. Fountains, histograms, and q-identities
We solve the recursion S_n=S_n-1-q^nS_n-p, both, explicitly, and in the limit for n→∞, proving in this way a formula due to Merlini and Sprugnoli. It is also discussed how computer algebra could be applied.
7. Efficient maxima-finding algorithms for random planar samples
We collect major known algorithms in the literature for finding the maxima of multi-dimensional points and provide a simple classification. Several new algorithms are proposed. In particular, we give a new maxima-finding algorithm with expected complexity n+O(√n\log n) when the input is a sequence of points uniformly chosen at random from general planar regions. We also give a sequential algorithm, very efficient for practical purposes.
8. Minimum survivable graphs with bounded distance increase
We study in graphs properties related to fault-tolerance in case a node fails. A graph G is k-self-repairing, where k is a non-negative integer, if after the removal of any vertex no distance in the surviving graph increases by more than k. In the design of interconnection networks such graphs guarantee good fault-tolerance properties. We give upper and lower bounds on the minimum number of edges of a k-self-repairing graph for prescribed k and n, where n is the order of the graph. We prove that the problem of finding, in a k-self-repairing graph, a spanning k-self-repairing subgraph of minimum size is NP-Hard.
9. An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions
The Ackermann function is a fascinating and well studied paradigm for a function which eventually dominates all primitive recursive functions. By a classical result from the theory of recursive functions it is known that the Ackermann function can be defined by an unnested or descent recursion along the segment of ordinals below ω ^ω (or equivalently along the order type of the polynomials under eventual domination). In this article we give a fine structure analysis of such a Ackermann type descent recursion in the case that the ordinals below ω ^ω are represented via a Hardy Ramanujan style coding. This paper combines number-theoretic results by Hardy and Ramanujan, Karamata's celebrated Tauberian theorem and techniques from the theory of computability in a perhaps surprising way.
10. A bijection between planar constellations and some colored Lagrangian trees
Constellations are colored planar maps that generalize different families of maps (planar maps, bipartite planar maps, bi-Eulerian planar maps, planar cacti, ...) and are strongly related to factorizations of permutations. They were recently studied by Bousquet-Mélou and Schaeffer who describe a correspondence between these maps and a family of trees, called Eulerian trees. In this paper, we derive from their result a relationship between planar constellations and another family of trees, called stellar trees. This correspondence generalizes a well known result for planar cacti, and shows that planar constellations are colored Lagrangian objects (that is objects that can be enumerated by the Good-Lagrange formula). We then deduce from this result a new formula for the number of planar constellations having a given face distribution, different from the formula one can derive from the results of Bousquet-Mélou and Schaeffer, along with systems of functional equations for the generating functions of bipartite and bi-Eulerian planar maps enumerated according to the partition of faces and vertices.
11. A Note on Set Systems with no Union of Cardinality 0 modulo m
\emphAlon, Kleitman, Lipton, Meshulam, Rabin and \emphSpencer (Graphs. Combin. 7 (1991), no. 2, 97-99) proved, that for any hypergraph \textbf\textitF=\F_1,F_2,\ldots, F_d(q-1)+1\, where q is a prime-power, and d denotes the maximal degree of the hypergraph, there exists an \textbf\textitF_0⊂ \textbf\textitF, such that |\bigcup_F∈\textbf\textitF_0F| ≡ 0 (q). We give a direct, alternative proof for this theorem, and we also show that an explicit construction exists for a hypergraph of degree d and size Ω (d^2) which does not contain a non-empty sub-hypergraph with a union of size 0 modulo 6, consequently, the theorem does not generalize for non-prime-power moduli.