Search results for "Combinatorics"
showing 10 items of 1770 documents
Central Units, Class Sums and Characters of the Symmetric Group
2010
In the search for central units of a group algebra, we look at the class sums of the group algebra of the symmetric group S n in characteristic zero, and we show that they are units in very special instances.
On the decision problem for the guarded fragment with transitivity
2002
The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability pr…
On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
2005
We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.
Optical Routing of Uniform Instances in Cayley Graphs
2001
Abstract Abstract We consider the problem of routing uniform communication instances in Cayley graphs. Such instances consist of all pairs of nodes whose distance is included in a specified set U. We give bounds on the load induced by these instances on the links and for the wavelength assignment problem as well. For some classes of Cayley graphs that have special symmetry property (rotational graphs), we are able to construct routings for uniform instances such that the load is the same for each link of the graph.
On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric
2011
It is known that the d-dimensional Steiner Minimum Tree Problem in Hamming metric is NP-complete if d is considered to be a part of the input. On the other hand, it was an open question whether the problem is also NP-complete in fixed dimensions. In this paper we answer this question by showing that the problem is NP-complete for any dimension strictly greater than 2. We also show that the Steiner ratio is 2 - 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special cases d = 3 and d = 4.
Mappings of finite distortion: discreteness and openness for quasi-light mappings
2005
Abstract Let f ∈ W 1 , n ( Ω , R n ) be a continuous mapping so that the components of the preimage of each y ∈ R n are compact. We show that f is open and discrete if | D f ( x ) | n ⩽ K ( x ) J f ( x ) a.e. where K ( x ) ⩾ 1 and K n − 1 / Φ ( log ( e + K ) ) ∈ L 1 ( Ω ) for a function Φ that satisfies ∫ 1 ∞ 1 / Φ ( t ) d t = ∞ and some technical conditions. This divergence condition on Φ is shown to be sharp.
Old and New on the Quasihyperbolic Metric
1998
Let D be a proper subdomain of \( {\mathbb{R}^d}\). Following Gehring and Palka [GP] we define the quasihyperbolic distance between a pair x 1, x 2 of points in D as the infimum of \( {\smallint _\gamma }\frac{{ds}}{{D\left( {x,\partial D} \right)}}\) over all rectifiable curves γ joining x 1, x 2 in D. We denote the quasihyperbolic distance between x 1, x 2 by k D (x 1, x 2). As pointed out by Gehring and Osgood [GO], x 1 and x 2 can be joined by a quasihyperbolic geodesic; also see [Mr]. The quasihyperbolic metric is comparable to the usual hyperbolic metric in a simply connected plane domain by the Koebe distortion theorem. For a multiply connected plane domain D these two metrics are co…
The node-depth encoding
2008
The node-depth encoding has elements from direct and indirect encoding for trees which encodes trees by storing the depth of nodes in a list. Node-depth encoding applies specific search operators that is a typical characteristic for direct encodings. An investigation into the bias of the initialization process and the mutation operators of the node-depth encoding shows that the initialization process has a bias to solutions with small depths and diameters, and a bias towards stars. This investigation, also, shows that the mutation operators are unbiased. The performance of node-depth encoding is investigated for the bounded-diameter minimum spanning tree problem. The results are presented f…
Fractional master equations and fractal time random walks
1995
Fractional master equations containing fractional time derivatives of order 0\ensuremath{\le}1 are introduced on the basis of a recent classification of time generators in ergodic theory. It is shown that fractional master equations are contained as a special case within the traditional theory of continuous time random walks. The corresponding waiting time density \ensuremath{\psi}(t) is obtained exactly as \ensuremath{\psi}(t)=(${\mathit{t}}^{\mathrm{\ensuremath{\omega}}\mathrm{\ensuremath{-}}1}$/C)${\mathit{E}}_{\mathrm{\ensuremath{\omega}},\mathrm{\ensuremath{\omega}}}$(-${\mathit{t}}^{\mathrm{\ensuremath{\omega}}}$/C), where ${\mathit{E}}_{\mathrm{\ensuremath{\omega}},\mathrm{\ensuremat…
Elementarteiler von Inzidenzmatrizen symmetrischer Blockpläne
1986
By a study of the integral code generated by the rows of the incidence matrix and its extention the following results are obtained: Let d 1,...,d V(d 1|d 2,d 2|d 3...) be the elementary divisors of the incidence matrix of a symmetric (v,n+λ, λ) design. Then d v=(n+λ)n/g.c.d. (n, λ). Moreover, if p is a prime such that p|n, p∤λ and if x p denotes the p-part of x, then (d idv+2−i) p =n p for 2≤i≤v. For projective planes it can be shown that d 1=···=d 3n−2=1, hence $$d_{n^2 - 2n{\text{ }} + {\text{ }}5} {\text{ }} = \cdots = d_{n^2 + n} = n$$ and $$d_{n^2 - n{\text{ }} + {\text{ }}1} = (n + 1)n$$ . The paper also contains some results about elementary divisors of incidence matrices G satisfyin…