Search results for "Combinatorics"
showing 10 items of 1770 documents
On computing the degree of convexity of polyominoes
2015
In this paper we present an algorithm which has as input a convex polyomino $P$ and computes its degree of convexity, defined as the smallest integer $k$ such that any two cells of $P$ can be joined by a monotone path inside $P$ with at most $k$ changes of direction. The algorithm uses space $O(m + n)$ to represent a polyomino $P$ with $n$ rows and $m$ columns, and has a running time $O(min(m; r k))$, where $r$ is the number of corners of $P$. Moreover, the algorithm leads naturally to a decomposition of $P$ into simpler polyominoes.
Loop-free Gray code algorithm for the e-restricted growth functions
2011
The subject of Gray codes algorithms for the set partitions of {1,2,...,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of [email protected]?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,...,n}, Ruskey and Savage (1994) [9] generalized [email protected]?s results and give two Gray codes for the set of partitions of {1,2,...,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques. In this paper, we introduce the set of e-restricte…
DEFECT THEOREMS FOR TREES
2000
We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.
Weak regularity and consecutive topologizations and regularizations of pretopologies
2009
Abstract L. Foged proved that a weakly regular topology on a countable set is regular. In terms of convergence theory, this means that the topological reflection Tξ of a regular pretopology ξ on a countable set is regular. It is proved that this still holds if ξ is a regular σ -compact pretopology. On the other hand, it is proved that for each n ω there is a (regular) pretopology ρ (on a set of cardinality c ) such that ( RT ) k ρ > ( RT ) n ρ for each k n and ( RT ) n ρ is a Hausdorff compact topology, where R is the reflector to regular pretopologies. It is also shown that there exists a regular pretopology of Hausdorff RT -order ⩾ ω 0 . Moreover, all these pretopologies have the property…
Groups whose prime graph on conjugacy class sizes has few complete vertices
2012
Abstract Let G be a finite group, and let Γ ( G ) denote the prime graph built on the set of conjugacy class sizes of G. In this paper, we consider the situation when Γ ( G ) has “few complete vertices”, and our aim is to investigate the influence of this property on the group structure of G. More precisely, assuming that there exists at most one vertex of Γ ( G ) that is adjacent to all the other vertices, we show that G is solvable with Fitting height at most 3 (the bound being the best possible). Moreover, if Γ ( G ) has no complete vertices, then G is a semidirect product of two abelian groups having coprime orders. Finally, we completely characterize the case when Γ ( G ) is a regular …
A note on Sturmian words
2012
International audience; We describe an algorithm which, given a factor of a Sturmian word, computes the next factor of the same length in the lexicographic order in linear time. It is based on a combinatorial property of Sturmian words which is related with the Burrows-Wheeler transformation.
Highly irregular graphs with extreme numbers of edges
1997
Abstract A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the smallest number of edges of a highly irregular graph of given order.
Nilpotent Lie algebras with 2-dimensional commutator ideals
2011
Abstract We classify all (finitely dimensional) nilpotent Lie k -algebras h with 2-dimensional commutator ideals h ′ , extending a known result to the case where h ′ is non-central and k is an arbitrary field. It turns out that, while the structure of h depends on the field k if h ′ is central, it is independent of k if h ′ is non-central and is uniquely determined by the dimension of h . In the case where k is algebraically or real closed, we also list all nilpotent Lie k -algebras h with 2-dimensional central commutator ideals h ′ and dim k h ⩽ 11 .
Quasi-conformal mapping theorem and bifurcations
1998
LetH be a germ of holomorphic diffeomorphism at 0 ∈ ℂ. Using the existence theorem for quasi-conformal mappings, it is possible to prove that there exists a multivalued germS at 0, such thatS(ze 2πi )=H○S(z) (1). IfH λ is an unfolding of diffeomorphisms depending on λ ∈ (ℂ,0), withH 0=Id, one introduces its ideal $$\mathcal{I}_H$$ . It is the ideal generated by the germs of coefficients (a i (λ), 0) at 0 ∈ ℂ k , whereH λ(z)−z=Σa i (λ)z i . Then one can find a parameter solutionS λ (z) of (1) which has at each pointz 0 belonging to the domain of definition ofS 0, an expansion in seriesS λ(z)=z+Σb i (λ)(z−z 0) i with $$(b_i ,0) \in \mathcal{I}_H$$ , for alli. This result may be applied to the…
A characterization of the Schur property through the disk algebra
2017
[EN] In this paper we give a new characterization of when a Banach space E has the Schur property in terms of the disk algebra. We prove that E has the Schur property if and only if A(D, E) = A(D,E-w). (C) 2016 Elsevier Inc. All rights reserved.