 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 12 no. 3
1. On the Number of Balanced Words of Given Length and Height over a Two-Letter Alphabet
We exhibit a recurrence on the number of discrete line segments joining two integer points in the plane using an encoding of such segments as balanced words of given length and height over the two-letter alphabet $\{0,1\}$. We give generating functions and study the asymptotic behaviour. As a particular case, we focus on the symmetrical discrete segments which are encoded by balanced palindromes.
2. Covering codes in Sierpinski graphs
For a graph G and integers a and b, an (a, b)-code of G is a set C of vertices such that any vertex from C has exactly a neighbors in C and any vertex not in C has exactly b neighbors in C. In this paper we classify integers a and b for which there exist (a, b)-codes in Sierpinski graphs.
Section:
Graph and Algorithms
3. On the asymptotic enumeration of accessible automata
We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.
Section:
Automata, Logic and Semantics
4. Cubefree words with many squares
We construct infinite cubefree binary words containing exponentially many distinct squares of length n. We also show that for every positive integer n, there is a cubefree binary square of length 2n.
Section:
Automata, Logic and Semantics
5. The Laplacian spread of Cactuses
Connected graphs in which any two of its cycles have at most one common vertex are called cactuses. In this paper, we continue the work on Laplacian spread of graphs, and determine the graph with maximal Laplacian spread in all cactuses with n vertices.
Section:
Combinatorics
6. A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r
Cuckoo hashing is a hash table data structure offering constant access time, even in the worst case. As a drawback, the construction fails with small, but practically significant probability. However, Kirsch et al. (2008) showed that a constant-sized additional memory, the so called stash, is sufficient to reduce the failure rate drastically. But so far, using a modified insertion procedure that demands additional running time to look for an admissible key is required. As a major contribution of this paper, we show that the same bounds on the failure probability hold even without this search process and thus, the performance increases. Second, we extend the analysis to simplified cuckoo hashing, a variant of the original algorithm offering increased performance. Further, we derive some explicit asymptotic approximations concerning the number of usual resp. bipartite graphs related to the data structures. Using these results, we obtain much more precise asymptotic expansions of the success rate. These calculations are based on a generating function approach and applying the saddle point method. Finally, we provide numerical results to support the theoretical analysis.
Section:
Analysis of Algorithms
7. Coloring Geographical Threshold Graphs
We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. The motivation for analyzing this model is that many real networks (e. g., wireless networks, the Internet, etc.) need to be studied by using a ''richer'' stochastic model (which in this case includes both a distance between nodes and weights on the nodes). Here, we analyze the GTG coloring algorithm together with the graph's clique number, showing formally that in spite of the differences in structure between GTG and RGG, the asymptotic behavior of the chromatic number is identical: chi = ln n/ln ln n(1 +o(1)). Finally, we consider the leading corrections to this expression, again using the coloring algorithm and clique number to provide bounds on the chromatic number. We show that the gap between the lower and upper bound is within C ln n/(ln ln n)(2), and specify the constant C.
Section:
Graph and Algorithms
8. On the support of the free Lie algebra: the Schutzenberger problems
M.-P. Schutzenberger asked to determine the support of the free Lie algebra L(Zm) (A) on a finite alphabet A over the ring Z(m) of integers mod m and all pairs of twin and anti-twin words, i.e., words that appear with equal (resp. opposite) coefficients in each Lie polynomial. We characterize the complement of the support of L(Zm) (A) in A* as the set of all words w such that m divides all the coefficients appearing in the monomials of l* (w), where l* is the adjoint endomorphism of the left normed Lie bracketing l of the free Lie ring. Calculating l* (w) via the shuffle product, we recover the well known result of Duchamp and Thibon (Discrete Math. 76 (1989) 123-132) for the support of the free Lie ring in a much more natural way. We conjecture that two words u and v of common length n, which lie in the support of the free Lie ring, are twin (resp. anti-twin) if and only if either u = v or n is odd and u = (v) over tilde (resp. if n is even and u = (v) over tilde), where (v) over tilde denotes the reversal of v and we prove that it suffices to show this for a two-lettered alphabet. These problems can be rephrased, for words of length n, in terms of the action of the Dynkin operator l(n) on lambda-tabloids, where lambda is a partition of n. Representing a word w in two letters by the subset I of [n] = \1, 2, ... , n\ that consists of all positions that one of the letters occurs in w, the computation of l* (w) leads us to the notion of the Pascal descent polynomial p(n)(I), a […]
Section:
Combinatorics
9. Binary Labelings for Plane Quadrangulations and their Relatives
Motivated by the bijection between Schnyder labelings of a plane triangulation and partitions of its inner edges into three trees, we look for binary labelings for quadrangulations (whose edges can be partitioned into two trees). Our labeling resembles many of the properties of Schnyder's one for triangulations: Apart from being in bijection with tree decompositions, paths in these trees allow to define the regions of a vertex such that counting faces in them yields an algorithm for embedding the quadrangulation, in this case on a 2-book. Furthermore, as Schnyder labelings have been extended to 3-connected plane graphs, we are able to extend our labeling from quadrangulations to a larger class of 2-connected bipartite graphs.
Section:
Graph and Algorithms
10. Structure of spanning trees on the two-dimensional Sierpinski gasket
Consider spanning trees on the two-dimensional Sierpinski gasket SG(n) where stage n is a non-negative integer. For any given vertex x of SG(n), we derive rigorously the probability distribution of the degree j ∈{1,2,3,4} at the vertex and its value in the infinite n limit. Adding up such probabilities of all the vertices divided by the number of vertices, we obtain the average probability distribution of the degree j. The corresponding limiting distribution φj gives the average probability that a vertex is connected by 1, 2, 3 or 4 bond(s) among all the spanning tree configurations. They are rational numbers given as φ1=10957/40464, φ2=6626035/13636368, φ3=2943139/13636368, φ4=124895/4545456.
Section:
Combinatorics
11. q-Enumeration of words by their total variation
In recent work, Mansour [Discrete Math. Theoret. Computer Science 11, 2009, 173--186] considers the problem of enumerating all words of length n over {1,2,...,k} (where k is a given integer), that have the total variation equal to a given integer m. In the present paper we study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities. We are interested in the probabilities of words of given type to have a given total variation.
Section:
Combinatorics