Search results for "Combinatorics"
showing 10 items of 1770 documents
Countable connected spaces and bunches of arcs in R3
2006
Abstract We investigate the images (also called quotients) of countable connected bunches of arcs in R 3 , obtained by shrinking the arcs to points (see Section 2 for definitions of new terms). First, we give an intrinsic description of such images among T 1 -spaces: they are precisely countable and weakly first countable spaces. Moreover, an image is first countable if and only if it can be represented as a quotient of another bunch with its projection hereditarily quotient (Theorem 2.7). Applying this result we see, for instance, that two classical countable connected T 2 -spaces—the Bing space [R.H. Bing, A connected countable Hausdorff space, Proc. Amer. Math. Soc. 4 (1953) 474], and th…
Some local properties defining $\mathcal T_0$-groups and related classes of groups
2016
We call $G$ a $\operatorname{Hall}_{\mathcal X}$-group if there exists a normal nilpotent subgroup $N$ of $G$ for which $G/N'$ is an ${\mathcal X}$-group. We call $G$ a ${\mathcal T}_0$-group provided $G/\Phi(G)$ is a ${\mathcal T}$-group, that is, one in which normality is a transitive relation. We present several new local classes of groups which locally define $\operatorname{Hall}_{\mathcal X}$-groups and ${\mathcal T}_0$-groups where ${\mathcal X}\in\{ {\mathcal T},\mathcal {PT},\mathcal {PST}\}$; the classes $\mathcal {PT}$ and $\mathcal {PST}$ denote, respectively, the classes of groups in which permutability and S-permutability are transitive relations.
Equations on trees
1996
We introduce the notion of equation on trees, generalizing the corresponding notion for words, and we develop the first steps of a theory of tree equations. The main result of the paper states that, if a pair of trees is the solution of a tree equation with two indeterminates, then the two trees are both powers of the same tree. As an application, we show that a tree can be expressed in a unique way as a power of a primitive tree. This extends a basic result of combinatorics on words to trees. Some open problems are finally proposed.
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes
2005
The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…
Graph Connectivity, Monadic NP and built-in relations of moderate degree
1995
It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.
Automorphism groups of some affine and finite type Artin groups
2004
We observe that, for fixed n ≥ 3, each of the Artin groups of finite type An, Bn = Cn, and affine type ˜ An−1 and ˜ Cn−1 is a central extension of a finite index subgroup of the mapping class group of the (n + 2)-punctured sphere. (The centre is trivial in the affine case and infinite cyclic in the finite type cases). Using results of Ivanov and Korkmaz on abstract commensurators of surface mapping class groups we are able to determine the automorphism groups of each member of these four infinite families of Artin groups. A rank n Coxeter matrix is a symmetric n × n matrix M with integer entries mij ∈ N ∪ {∞} where mij ≥ 2 for ij, and mii = 1 for all 1 ≤ i ≤ n. Given any rank n Coxeter matr…
Three-page encoding and complexity theory for spatial graphs
2004
We construct a series of finitely presented semigroups. The centers of these semigroups encode uniquely up to rigid ambient isotopy in 3-space all non-oriented spatial graphs. This encoding is obtained by using three-page embeddings of graphs into the product of the line with the cone on three points. By exploiting three-page embeddings we introduce the notion of the three-page complexity for spatial graphs. This complexity satisfies the properties of finiteness and additivity under natural operations.
Three cyclic branched covers suffice to determine hyperbolic knots.
2005
Let n > m > 2 be two fixed coprime integers. We prove that two Conway reducible, hyperbolic knots sharing the 2-fold, m-fold and n-fold cyclic branched covers are equivalent. Using previous results by Zimmermann we prove that this implies that a hyperbolic knot is determined by any three of its cyclic branched covers.
New Encodings of Pseudo-Boolean Constraints into CNF
2009
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
Elements with square roots in compact groups
2010
The probability that a randomly chosen element has a square root is studied in [1, 2, 8] in the finite case. Here we deal with the infinite case.