Search results for "combinatoric"
showing 10 items of 1776 documents
Languages with mismatches and an application to approximate indexing
2005
In this paper we describe a factorial language, denoted by L(S, k,r), that contains all words that occur in a string 5 up to k mismatches every r symbols. Then we give some combinatorial properties of a parameter, called repetition index and denoted by R(S,k,r), defined as the smallest integer h ? 1 such that all strings of this length occur at most in a unique position of the text S up to k mismatches every r symbols. We prove that R(S, k, r) is a non-increasing function of r and a non-decreasing function of k and that the equation r = R(S, k, r) admits a unique solution. The repetition index plays an important role in the construction of an indexing data structure based on a trie that rep…
More restrictive Gray codes for some classes of pattern avoiding permutations
2009
In a recent article [W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length n; two consecutive objects differ in at most two or three posit…
Minimal change list for Lucas strings and some graph theoretic consequences
2005
AbstractWe give a minimal change list for the set of order p length-n Lucas strings, i.e., the set of length-n binary strings with no p consecutive 1's nor a 1ℓ prefix and a 1m suffix with ℓ+m⩾p. The construction of this list proves also that the order p n-dimensional Lucas cube has a Hamiltonian path if and only if n is not a multiple of p+1, and its second power always has a Hamiltonian path.
Algebras of pseudodifferential operators on complete manifolds
2003
In several influential works, Melrose has studied examples of non-compact manifolds M 0 M_0 whose large scale geometry is described by a Lie algebra of vector fields V ⊂ Γ ( M ; T M ) \mathcal V \subset \Gamma (M;TM) on a compactification of M 0 M_0 to a manifold with corners M M . The geometry of these manifolds—called “manifolds with a Lie structure at infinity”—was studied from an axiomatic point of view in a previous paper of ours. In this paper, we define and study an algebra Ψ 1 , 0 , V ∞ ( M 0 ) \Psi _{1,0,\mathcal V}^\infty (M_0) of pseudodifferential operators canonically associated to a manifold M 0 M_0 with a Lie structure at infinity V ⊂ Γ ( M ; T M ) \mathcal V \subset \Gamma (…
The graded identities of upper triangular matrices of size two
2002
AbstractLet UT2 be the algebra of 2×2 upper triangular matrices over a field F. We first classify all possible gradings on UT2 by a group G. It turns out that, up to isomorphism, there is only one non-trivial grading and we study all the graded polynomial identities for such algebra. In case F is of characteristic zero we give a complete description of the space of multilinear graded identities in the language of Young diagrams through the representation theory of the hyperoctahedral group. We finally establish a result concerning the rate of growth of the identities for such algebra by proving that its sequence of graded codimensions has almost polynomial growth.
On minimal non-PC-groups
2009
On dit qu'un groupe G est un PC-groupe, si pour tout x ∈ G, G/C G (x G ) est une extension d'un groupe polycyclique par un groupe fini. Un non-PC-groupe minimal est un groupe qui n'est pas un PC-groupe mais dont tous les sous-groupes propres sont des PC-groupes. Notre principal resultat est qu'un non-PC-groupe minimal ayant un groupe quotient fini non-trivial est une extension cyclique finie d'un groupe abelien divisible de rang fini.
The prime graph on class sizes of a finite group has a bipartite complement
2020
Abstract Let G be a finite group, and let cs ( G ) denote the set of sizes of the conjugacy classes of G. The prime graph built on cs ( G ) , that we denote by Δ ( G ) , is the (simple undirected) graph whose vertices are the prime divisors of the numbers in cs ( G ) , and two distinct vertices p, q are adjacent if and only if pq divides some number in cs ( G ) . A rephrasing of the main theorem in [8] is that the complement Δ ‾ ( G ) of the graph Δ ( G ) does not contain any cycle of length 3. In this paper we generalize this result, showing that Δ ‾ ( G ) does not contain any cycle of odd length, i.e., it is a bipartite graph. In other words, the vertex set V ( G ) of Δ ( G ) is covered b…
Groups with few $p'$-character degrees
2019
Abstract We prove a variation of Thompson's Theorem. Namely, if the first column of the character table of a finite group G contains only two distinct values not divisible by a given prime number p > 3 , then O p p ′ p p ′ ( G ) = 1 . This is done by using the classification of finite simple groups.
Bounding the number of vertices in the degree graph of a finite group
2020
Abstract Let G be a finite group, and let cd ( G ) denote the set of degrees of the irreducible complex characters of G . The degree graph Δ ( G ) of G is defined as the simple undirected graph whose vertex set V ( G ) consists of the prime divisors of the numbers in cd ( G ) , two distinct vertices p and q being adjacent if and only if pq divides some number in cd ( G ) . In this note, we provide an upper bound on the size of V ( G ) in terms of the clique number ω ( G ) (i.e., the maximum size of a subset of V ( G ) inducing a complete subgraph) of Δ ( G ) . Namely, we show that | V ( G ) | ≤ max { 2 ω ( G ) + 1 , 3 ω ( G ) − 4 } . Examples are given in order to show that the bound is bes…
Characterizing normal Sylow p-subgroups by character degrees
2012
Abstract Suppose that G is a finite group, let p be a prime and let P ∈ Syl p ( G ) . We prove that P is normal in G if and only if all the irreducible constituents of the permutation character ( 1 P ) G have degree not divisible by p.