Search results for "combinatoric"
showing 10 items of 1776 documents
Defining relations of minimal degree of the trace algebra of 3×3 matrices
2008
Abstract The trace algebra C n d over a field of characteristic 0 is generated by all traces of products of d generic n × n matrices, n , d ⩾ 2 . Minimal sets of generators of C n d are known for n = 2 and n = 3 for any d as well as for n = 4 and n = 5 and d = 2 . The defining relations between the generators are found for n = 2 and any d and for n = 3 , d = 2 only. Starting with the generating set of C 3 d given by Abeasis and Pittaluga in 1989, we have shown that the minimal degree of the set of defining relations of C 3 d is equal to 7 for any d ⩾ 3 . We have determined all relations of minimal degree. For d = 3 we have also found the defining relations of degree 8. The proofs are based …
Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics
2007
The original publication is available at www.springerlink.com ; ISBN 978-3-540-75519-7 ; ISSN 0302-9743 (Print) 1611-3349 (Online); International audience; We present a complete, exact and efficient implementation to compute the adjacency graph of an arrangement of quadrics, \ie surfaces of algebraic degree~2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the adjacency graph of the arrangement. Our implementation is {\em complete} in the sense that it can handle all kinds of…
Some remarks on the category SET(L), part III
2004
This paper considers the category SET(L) of L-subsets of sets with a fixed basis L and is a continuation of our previous investigation of this category. Here we study its general properties (e.g., we derive that the category is a topological construct) as well as some of its special objects and morphisms.
Dichotomies properties on computational complexity of S-packing coloring problems
2015
This work establishes the complexity class of several instances of the S -packing coloring problem: for a graph G , a positive integer k and a nondecreasing list of integers S = ( s 1 , ? , s k ) , G is S -colorable if its vertices can be partitioned into sets S i , i = 1 , ? , k , where each S i is an s i -packing (a set of vertices at pairwise distance greater than s i ). In particular we prove a dichotomy between NP-complete problems and polynomial-time solvable problems for lists of at most four integers.
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.