Search results for "Mathematics::Combinatorics"
showing 10 items of 81 documents
A Local Approach to Certain Classes of Finite Groups
2003
Abstract We develop several local approaches for the three classes of finite groups: T-groups (normality is a transitive relation) and PT-groups (permutability is a transitive relation) and PST-groups (S-permutability is a transitive relation). Here a subgroup of a finite group G is S-permutable if it permutes with all the Sylow subgroup of G.
Quantum Queries on Permutations
2015
K. Iwama and R. Freivalds considered query algorithms where the black box contains a permutation. Since then several authors have compared quantum and deterministic query algorithms for permutations. It turns out that the case of \(n\)-permutations where \(n\) is an odd number is difficult. There was no example of a permutation problem where quantization can save half of the queries for \((2m+1)\)-permutations if \(m\ge 2\). Even for \((2m)\)-permutations with \(m\ge 2\), the best proved advantage of quantum query algorithms is the result by Iwama/Freivalds where the quantum query complexity is \(m\) but the deterministic query complexity is \((2m-1)\). We present a group of \(5\)-permutati…
The absolute center of a unicyclic network
1989
Abstract A unicyclic network is one generalization of a tree network. In this paper we examine the problem of finding an absolute center of a unicyclic network. We show that this problem can be solved in linear time with respect to the number of vertices in the network.
Some subgroup embeddings in finite groups: A mini review
2015
[EN] In this survey paper several subgroup embedding properties related to some types of permutability are introduced and studied. ª 2014 Production and hosting by Elsevier B.V. on behalf of Cairo University
An Efficient Algorithm for the Generation of Z-Convex Polyominoes
2014
We present a characterization of Z-convex polyominoes in terms of pairs of suitable integer vectors. This lets us design an algorithm which generates all Z-convex polyominoes of size n in constant amortized time.
A bijection between words and multisets of necklaces
2012
Two of the present authors have given in 1993 a bijection Phi between words on a totally ordered alphabet and multisets of primitive necklaces. At the same time and independently, Burrows and Wheeler gave a data compression algorithm which turns out to be a particular case of the inverse of Phi. In the present article, we show that if one replaces in Phi the standard permutation of a word by the co-standard one (reading the word from right to left), then the inverse bijection is computed using the alternate lexicographic order (which is the order of real numbers given by continued fractions) on necklaces, instead of the lexicographic order as for Phi(-1). The image of the new bijection, ins…
Total and fractional total colourings of circulant graphs
2008
International audience; In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases.
Combinatorial aspects of L-convex polyominoes
2007
We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an ''L'' shaped path in one of its four cyclic orientations. The paper proves bijectively that the number f"n of L-convex polyominoes with perimeter 2(n+2) satisfies the linear recurrence relation f"n"+"2=4f"n"+"1-2f"n, by first establishing a recurrence of the same form for the cardinality of the ''2-compositions'' of a natural number n, a simple generalization of the ordinary compositions of n. Then, such 2-compositions are studied and bijectively related to certain words of a regular language over four letters which is in turn bijectively related to L-convex polyominoes. In …
Enumerable classes of total recursive functions: Complexity of inductive inference
1994
This paper includes some results on complexity of inductive inference for enumerable classes of total recursive functions, where enumeration is considered in more general meaning than usual recursive enumeration. The complexity is measured as the worst-case mindchange (error) number for the first n functions of the given class. Three generalizations are considered.
Lehmer code transforms and Mahonian statistics on permutations
2012
Abstract In 2000 Babson and Steingrimsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006. In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections…