Search results for "Combinatorics"
showing 10 items of 1770 documents
Functional calculi for convolution operators on a discrete, periodic, solvable group
2009
Suppose T is a bounded self-adjoint operator on the Hilbert space L2(X,μ) and let T=∫SpL2TλdE(λ) be its spectral resolution. Let F be a Borel bounded function on [−a,a], SpL2T⊂[−a,a]. We say that F is a spectral Lp-multiplier for T, if F(T)=∫SpL2TF(λ)dE(λ) is a bounded operator on Lp(X,μ). The paper deals with l1-multipliers, where X=G is a discrete (countable) solvable group with ∀x∈G, x4=1, μ is the counting measure and TΦ:l2(G)∋ξ↦ξ∗Φ∈l2(G), where Φ=Φ∗ is a l1(G) function, suppΦ generates G. The main result of the paper states that there exists a Ψ on G such that all l1-multipliers for TΨ are real analytic at every interior point of Spl2(G)TΨ. We also exhibit self-adjoint Φ′s in l1(G) suc…
Strongly invertible links and divides
2008
Abstract To a proper generic immersion of a finite number of copies of the unit interval in a 2-disc, called a divide, A’Campo associates a link in S 3 . From the more general notion of ordered Morse signed divides, one obtains a braid presentation of links of divides. In this paper, we prove that every strongly invertible link is isotopic to the link of an ordered Morse signed divide. We give fundamental moves for ordered Morse signed divides and show that strongly invertible links are equivalent if and only if we can pass from one ordered Morse signed divide to the other by a sequence of such moves. Then we associate a polynomial to an ordered Morse signed divide, invariant for these move…
Universal Lyndon Words
2014
A word w over an alphabet Σ is a Lyndon word if there exists an order defined on Σ for which w is lexicographically smaller than all of its conjugates (other than itself). We introduce and study universal Lyndon words, which are words over an n-letter alphabet that have length n! and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every n and exhibit combinatorial and structural properties of these words. We then define particular prefix codes, which we call Hamiltonian lex-codes, and show that every Hamiltonian lex-code is in bijection with the set of the shortest unrepeated prefixes of the conjugates of a universal Lyndon word. This allows us t…
On Packing Colorings of Distance Graphs
2014
International audience; The {\em packing chromatic number} $\chi_{\rho}(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\ldots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. This paper studies the packing chromatic number of infinite distance graphs $G(\mathbb{Z},D)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being adjacent if and only if $|i-j|\in D$. We present lower and upper bounds for $\chi_{\rho}(G(\mathbb{Z},D))$, showing that for finite $D$, the packing chromatic number is finite. Our main result concerns distance graphs with $D=…
Polyhedral results for a vehicle routing problem
1991
Abstract The Vehicle Routing Problem is a well known, and hard, combinatorial problem, whose polyhedral structure has deserved little attention. In this paper we consider the particular case in which all the demands are equal (since in the general case the associated polytope may be empty). From a known formulation of the problem we obtain the dimension of the corresponding polytope and we study the facetial properties of every inequality in it.
Minimal forbidden words and symbolic dynamics
1996
We introduce a new complexity measure of a factorial formal language L: the growth rate of the set of minimal forbidden words. We prove some combinatorial properties of minimal forbidden words. As main result we prove that the growth rate of the set of minimal forbidden words for L is a topological invariant of the dynamical system defined by L.
Classical sequences revisited with permutations avoiding dotted pattern
2011
International audience; Inspired by the definition of the barred pattern-avoiding permutation, we introduce the new concept of dotted pattern for permutations. We investigate permutations classes avoiding dotted patterns of length at most 3, possibly along with other classical patterns. We deduce some enumerating results which allow us to exhibit new families of permutations counted by the classical sequences: 2^n, Catalan, Motzkin, Pell, Fibonacci, Fine, Riordan, Padovan, Eulerian.
Character sums and double cosets
2008
Abstract If G is a p-solvable finite group, P is a self-normalizing Sylow p-subgroup of G with derived subgroup P ′ , and Ψ is the sum of all the irreducible characters of G of degree not divisible by p, then we prove that the integer Ψ ( P ′ z P ′ ) is divisible by | P | for all z ∈ G . This answers a question of J. Alperin.
McKay natural correspondences on characters
2014
Let [math] be a finite group, let [math] be an odd prime, and let [math] . If [math] , then there is a canonical correspondence between the irreducible complex characters of [math] of degree not divisible by [math] belonging to the principal block of [math] and the linear characters of [math] . As a consequence, we give a characterization of finite groups that possess a self-normalizing Sylow [math] -subgroup or a [math] -decomposable Sylow normalizer.
Quadratic rational solvable groups
2012
Abstract A finite group G is quadratic rational if all its irreducible characters are either rational or quadratic. If G is a quadratic rational solvable group, we show that the prime divisors of | G | lie in { 2 , 3 , 5 , 7 , 13 } , and no prime can be removed from this list. More generally, if G is solvable and the field Q ( χ ) generated by the values of χ over Q satisfies | Q ( χ ) : Q | ⩽ k , for all χ ∈ Irr ( G ) , then the set of prime divisors of | G | is bounded in terms of k . Also, we prove that the degree of the field generated by the values of all characters of a semi-rational solvable group (see Chillag and Dolfi, 2010 [1] ) or a quadratic rational solvable group over Q is bou…