Vol. 6 no. 2


1. Some lattices of closure systems on a finite set

Caspard, Nathalie ; Monjardet, Bernard.
In this paper we study two lattices of significant particular closure systems on a finite set, namely the union stable closure systems and the convex geometries. Using the notion of (admissible) quasi-closed set and of (deletable) closed set, we determine the covering relation \prec of these […]

2. Rare Events and Conditional Events on Random Strings

Régnier, Mireille ; Denise, Alain.
Some strings -the texts- are assumed to be randomly generated, according to a probability model that is either a Bernoulli model or a Markov model. A rare event is the over or under-representation of a word or a set of words. The aim of this paper is twofold. First, a single word is given. One […]

3. New Results on Generalized Graph Coloring

Alekseev, Vladimir E. ; Farrugia, Alastair ; Lozin, Vadim V..
For graph classes \wp_1,...,\wp_k, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given graph G can be partitioned into subsets V_1,...,V_k so that V_j induces a graph in the class \wp_j (j=1,2,...,k). If \wp_1=...=\wp_k is the class of edgeless graphs, then this […]

4. Coxeter-like complexes

Babson, Eric ; Reiner, Victor.
Motivated by the Coxeter complex associated to a Coxeter system (W,S), we introduce a simplicial regular cell complex Δ (G,S) with a G-action associated to any pair (G,S) where G is a group and S is a finite set of generators for G which is minimal with respect to inclusion. We examine the topology […]

5. The Summation Package Sigma: Underlying Principles and a Rhombus Tiling Application

Schneider, Carsten.
We give an overview of how a huge class of multisum identities can be proven and discovered with the summation package Sigma implemented in the computer algebra system Mathematica. General principles of symbolic summation are discussed. We illustrate the usage of Sigma by showing how one can find […]

6. Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs

Chen, Hon-Chan.
Let G be a graph. A component of G is a maximal connected subgraph in G. A vertex v is a cut vertex of G if k(G-v) > k(G), where k(G) is the number of components in G. Similarly, an edge e is a bridge of G if k(G-e) > k(G). In this paper, we will propose new O(n) algorithms for finding cut […]

7. Track Layouts of Graphs

Dujmović, Vida ; Pór, Attila ; Wood, David, .
A \emph(k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of […]

8. Improved Expansion of Random Cayley Graphs

Loh, Po-Shen ; Schulman, Leonard J..
In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite c(ε ) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley graph with […]

9. On Linear Layouts of Graphs

Dujmović, Vida ; Wood, David, .
In a total order of the vertices of a graph, two edges with no endpoint in common can be \emphcrossing, \emphnested, or \emphdisjoint. A \emphk-stack (respectively, \emphk-queue, \emphk-arch) \emphlayout of a graph consists of a total order of the vertices, and a partition of the edges into k sets […]

10. The distribution of m-ary search trees generated by van der Corput sequences

Steiner, Wolfgang.
We study the structure of $m$-ary search trees generated by the van der Corput sequences. The height of the tree is calculated and a generating function approach shows that the distribution of the depths of the nodes is asymptotically normal. Additionally a local limit theorem is derived.

11. On Cheating Immune Secret Sharing

Pieprzyk, Josef ; Zhang, Xian-Mo.
The paper addresses the cheating prevention in secret sharing. We consider secret sharing with binary shares. The secret also is binary. This model allows us to use results and constructions from the well developed theory of cryptographically strong boolean functions. In particular, we prove that […]

12. On Locating-Dominating Codes in Binary Hamming Spaces

Honkala, Iiro ; Laihonen, Tero ; Ranto, Sanna.
Locating faulty processors in a multiprocessor system gives the motivation for locating-dominating codes. We consider these codes in binary hypercubes and generalize the concept for the situation in which we want to locate more than one malfunctioning processor.

13. The Width of Galton-Watson Trees Conditioned by the Size

Drmota, Michael ; Gittenberger, Bernhard.
It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ ^2 are asymptotically given by (σ √n)^pm_p where m_p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and […]

14. Well-spread sequences and edge-labellings with constant Hamilton-weight

Kayll, Peter Mark.
A sequence (a_i) of integers is \emphwell-spread if the sums a_i+a_j, for i

15. Generating functions and the satisfiability threshold

Puyhaubert, Vincent.
The 3-SAT problem consists in determining if a boolean formula with 3 literals per clause is satisfiable. When the ratio between the number of clauses and the number of variables increases, a threshold phenomenon is observed: the probability of satisfiability appears to decrease sharply from 1 to 0 […]

16. Analysis of some statistics for increasing tree families

Panholzer, Alois ; Prodinger, Helmut.
This paper deals with statistics concerning distances between randomly chosen nodes in varieties of increasing trees. Increasing trees are labelled rooted trees where labels along any branch from the root go in increasing order. Many mportant tree families that have applications in computer science […]

17. On an open problem of Green and Losonczy: exact enumeration of freely braided permutations

Mansour, Toufik.
Recently, Green and Losonczy~GL1,GL2 introduced \emphfreely braided permutation as a special class of restricted permutations has arisen in representation theory. The freely braided permutations were introduced and studied as the upper bound for the number of commutation classes of reduced […]

18. Characterisations of Ideal Threshold Schemes

Pieprzyk, Josef ; Zhang, Xian-Mo.
We characterise ideal threshold schemes from different approaches. Since the characteristic properties are independent to particular descriptions of threshold schemes all ideal threshold schemes can be examined by new points of view and new results on ideal threshold schemes can be discovered.

19. Statistical properties of general Markov dynamical sources: applications to information theory

Chazal, Frédéric ; Maume-Deschamps, Véronique.
In \textitDynamical sources in information theory: fundamental intervals and word prefixes, B. Vallée studies statistical properties of words generated by dynamical sources. This is done using generalized Ruelle operators. The aim of this article is to generalize sources for which the results hold. […]

20. Efficient Algorithms on the Family Associated to an Implicational System

Bertet, Karell ; Nebut, Mirabelle.
An implication system (IS) on a finite set S is a set of rules called Σ -implications of the kind A →_Σ B, with A,B ⊆ S. A subset X ⊆ S satisfies A →_Σ B when ''A ⊆ X implies B ⊆ X'' holds, so ISs can be used to describe constraints on sets of elements, such as dependency or causality. ISs are […]

21. Towards automated proofs of observational properties

Berregeb, Narjes ; Robbana, Riadh ; Tiwari, Ashish.
Observational theories are a generalization of first-order theories where two objects are observationally equal if they cannot be distinguished by experiments with observable results. Such experiments, called contexts, are usually infinite. Therfore, we consider a special finite set of contexts, […]

22. A Note on t-designs with t Intersection Numbers

Pawale, Rajendra M..
We discuss Ray-Chaudhari and Wilson inequality for a 0-design and give simple proof of the result '\emphFor fixed block size k, there exist finitely many parametrically feasible t-designs with t intersection numbers and λ > 1'.