Characterization and representation problems for intersection betweennesses

For a set system M=(M_v)_v∈V indexed by the elements of a finite set V, the intersection betweenness B(M) induced by M consists of all triples (u,v,w)∈V³ with M_u∩M_w⊆M_v. Similarly, the strict intersection betweenness B_s(M) induced by M consists of all triples (u,v,w)∈B(M) such that u, v, and w are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 5-36]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Burigana’s notion of a partial tree representation can be solved efficiently using well-known algorithms.     

Algorithms for finding proper essential surfaces in 3-manifolds

In this paper, we present an algorithm which, for a given compact orientable irreducible boundary irreducible 3-manifold M, verifies whether M contains an essential orientable surface (possibly, with boundary), whose genus is at most N. The algorithm is based on Haken’s theory of normal surfaces, and on a trick suggested by Jaco and consisting in estimating the mean length of boundary curves in an unknown essential surface of a given genus in the given manifold.     

Remnant inequalities and doubly-twisted conjugacy in free groups

We give two results for computing doubly-twisted conjugacy relations in free groups with respect to homomorphisms φ and ψ such that certain remnant words from φ are longer than the images of generators under ψ.Our first result is a remnant inequality condition which implies that two words u and v are not doubly-twisted conjugate. Further we show that if ψ is given and φ, u, and v are chosen at random, then the asymptotic probability that u and v are not doubly-twisted conjugate is 1. In the particular case of singly-twisted conjugacy, this means that if φ, u, and v are chosen at random, then u and v are not in the same singly-twisted conjugacy class with asymptotic probability 1.Our second result generalizes Kim’s “bounded solution length”. We give an algorithm for deciding doubly-twisted conjugacy relations in the case where φ and ψ satisfy a similar remnant inequality. In the particular case of singly-twisted conjugacy, our algorithm suffices to decide any twisted conjugacy relation if φ has remnant words of length at least 2.As a consequence of our generic properties we give an elementary proof of a recent result of Martino, Turner, and Ventura, that computes the densities of the sets of injective and surjective homomorphisms from one free group to another. We further compute the expected value of the density of the image of a homomorphism.     

On Solvability of Finite Groups with Few Non-Normal Subgroups

For a finite group G, let v(G) denote the number of conjugacy classes of non-normal subgroups of G and vc(G) denote the number of conjugacy classes of non-normal noncyclic subgroups of G. In this paper, we show that every finite group G satisfying v(G) ≤2|π(G)| or vc(G) ≤ |π(G)| is solvable, and for a finite nonsolvable group G, v(G) = 2|π(G)| +1 if and only if G ? A ₅.     

Invariant fibrations of geodesic flows

Let (Σ,g) be a compact C² finslerian 3-manifold. If the geodesic flow of g is completely integrable, and the singular set is a tamely-embedded polyhedron, then π₁(Σ) is almost polycyclic. On the other hand, if Σ is a compact, irreducible 3-manifold and π₁(Σ) is infinite polycyclic while π₂(Σ) is trivial, then Σ admits an analytic riemannian metric whose geodesic flow is completely integrable and singular set is a real-analytic variety. Additional results in higher dimensions are proven.     

Finiteness of mapping degree sets for 3-manifolds

By constructing certain maps, this note completes the answer of the question: For which closed orientable 3-manifold N, is the set of mapping degrees D(M,N) finite for any closed orientable 3-manifold M?     

Diameter and connectivity of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a given graph G, X(G), is defined to have vertices the arcs of G. Two arcs uv,xy are adjacent in X(G) if and only if (v,u,x,y) is a 3-arc of G. This notion was introduced in recent studies of arc-transitive graphs. In this paper we study diameter and connectivity of 3-arc graphs. In particular, we obtain sharp bounds for the diameter and connectivity of X(G) in terms of the corresponding invariant of G.     

A convergent two-time method for periodic differential equations

Two timing, an ad hoc method for studying periodic evolution equations, can be given a rigorous justification when the problem is in standard form, u = ?f(t, u). First solve $\text{dw}\text{dσ}\text{= ?(I ? M) f(σ, w)}\text{for}\text{w(σ, v)}$, where M is the mean value operator and v is any initial value. Then w(σ, v) is periodic in σ but does not satisfy the original equation. Now, force a solution u(t), using nonlinear variation of constants, in the form w(σ, v(τ)), where σ = t is the fast time and τ = ?t is the slow time. With the resulting differential equation for v, one reads off from its nonconstant solutions thè approximate transient behavior of u(t) for times of order ?^?1. On the other hand, the equilibrium points (constant solutions) v₀ correspond to steady state (periodic solutions) of the original system. Interesting applications, such as to one-dimensional wave equations with cubic damping, can be given.     

Bipartite graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G^′ and G^″ of G by joining u∈V(G^′) and v∈V(G^″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. We prove that graphs without 5-cycles are not universal fixers, from which it follows that bipartite graphs are not universal fixers.     

Positive sectional curvature, symmetry and Chern's conjecture

Let M be a n-manifold of positive sectional curvature. Suppose that M admits an isometrical torus Tk-action with . The main results of the paper are: (1) the fundamental group π₁(M) contains no Zp⊕Zp subgroup with p prime and p≠3 (a partial positive answer to Chern's conjecture); (2) the 2-order element of π₁(M) belongs to the center of π₁(M).     

The twisted conjugacy problem for endomorphisms of metabelian groups

Let M be a finitely generated metabelian group explicitly presented in a variety of all metabelian groups. An algorithm is constructed which, for every endomorphism φ ∈ End(M) identical modulo an Abelian normal subgroup N containing the derived subgroup M′ and for any pair of elements u, v ∈ M, decides if an equation of the form (xφ)u = vx has a solution in M. Thus, it is shown that the title problem under the assumptions made is algorithmically decidable. Moreover, the twisted conjugacy problem in any polycyclic metabelian group M is decidable for an arbitrary endomorphism φ ∈ End(M). Supported by RFBR (project No. 07-01-00392). (V. A. Roman’kov) Translated from Algebra i Logika, Vol. 48, No. 2, pp. 157–173, March–April, 2009.     

Some paranormed sequence spaces of non-absolute type derived by weighted mean

The sequence spaces ?_∞(p), c(p) and c₀(p) were introduced and studied by Maddox [I.J. Maddox, Paranormed sequence spaces generated by infinite matrices, Proc. Cambridge Philos. Soc. 64 (1968) 335-340]. In the present paper, the sequence spaces λ(u,v;p) of non-absolute type which are derived by the generalized weighted mean are defined and proved that the spaces λ(u,v;p) and λ(p) are linearly isomorphic, where λ denotes the one of the sequence spaces ?_∞, c or c₀. Besides this, the β- and γ-duals of the spaces λ(u,v;p) are computed and the basis of the spaces c₀(u,v;p) and c(u,v;p) is constructed. Additionally, it is established that the sequence space c₀(u,v) has AD property and given the f-dual of the space c₀(u,v;p). Finally, the matrix mappings from the sequence spaces λ(u,v;p) to the sequence space μ and from the sequence space μ to the sequence spaces λ(u,v;p) are characterized.     

A distance-labelling problem for hypercubes

Let i₁≥i₂≥i₃≥1 be integers. An L(i₁,i₂,i₃)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…} such that |?(u)−?(v)|≥i_t for any u,v∈V with d(u,v)=t, t=1,2,3, where d(u,v) is the distance in G between u and v. The integer ?(v) is called the label assigned to v under ?, and the difference between the largest and the smallest labels is called the span of ?. The problem of finding the minimum span, λ_i1,i2,i3(G), over all L(i₁,i₂,i₃)-labellings of G arose from channel assignment in cellular communication systems, and the related problem of finding the minimum number of labels used in an L(i₁,i₂,i₃)-labelling was originated from recent studies on the scalability of optical networks. In this paper we study the L(i₁,i₂,i₃)-labelling problem for hypercubes Q_d (d≥3) and obtain upper and lower bounds on λ_i1,i2,i3(Q_d) for any (i₁,i₂,i₃).     

The asymptotic distribution of weighted empirical distribution functions

Let G_n denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between G_n(u) and u of the forms 6w_v(u)D_n(u)6 and 6w_v(G_n(u))D_n(u)6, where D_n(u) = G_n(u)?u, w_v(u) = (u(1?u))^?1+v and 0 ? v < $\text{1}\text{2}$ is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function w_v with $\text{1}\text{2}$ ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function w_v with 0 ? v < $\text{1}\text{2}$ are potentially applicable in the construction of confidence contours for the extreme tails of a distribution.     

Affine maps of state spaces and state spaces of K 0 groups

Let φ be a homomorphism from the partially ordered abelian group (S, v) to the partially ordered abelian group (G, u) with φ(v) = u, where v and u are order units of S and G respectively. Then φ induces an affine map φ* from the state space St(G, u) to the state space St(S, v). Firstly, in this paper, we give some suitable conditions under which φ* is injective, surjective or bijective. Let R be a semilocal ring with the Jacobson radical J(R) and let π: R → R/J(R) be a canonical map. We discuss the affine map (K ₀ π)*. Secondly, for a semiprime right Goldie ring R with the maximal right quotient ring Q, we consider the relations between St(R) and St(Q). Some results from [ALFARO, R.: State spaces, finite algebras, and skew group rings, J. Algebra 139 (1991), 134–154] and [GOODEARL, K. R.-WARFIELD, R. B., Jr.: State spaces of K ₀ of noetherian rings, J. Algebra 71 (1981), 322–378] are extended.     

Colorings at minimum cost

We define by min_c∑_{u,v}∈E(G)|c(u)−c(v)| the min-costMC(G) of a graph G, where the minimum is taken over all proper colorings c. The min-cost-chromatic numberχ_M(G) is then defined to be the (smallest) number of colors k for which there exists a proper k-coloring c attaining MC(G). We give constructions of graphs G where χ(G) is arbitrarily smaller than χ_M(G). On the other hand, we prove that for every 3-regular graph G^′, χ_M(G^′)≤4 and for every 4-regular line graph G^″, χ_M(G^″)≤5. Moreover, we show that the decision problem whether χ_M(G)=k is -hard for k≥3.     

Fundamental groups of asymptotic cones

We show that for any metric space M satisfying certain natural conditions, there is a finitely generated group G, an ultrafilter ω, and an isometric embedding ι of M to the asymptotic cone Cone_ω(G) such that the induced homomorphism ι^*:π₁(M)→π₁(Cone_ω(G)) is injective. In particular, we prove that any countable group can be embedded into a fundamental group of an asymptotic cone of a finitely generated group.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

Moves for standard skeleta of 3-manifolds with marked boundary

A 3-manifold with marked boundary is a pair (M, X), where M is a compact 3-manifold whose (possibly empty) boundary is made up of tori and Klein bottles, and X is a trivalent graph that is a spine of ?M. A standard skeleton of a 3-manifold with marked boundary (M, X) is a standard sub-polyhedron P of M such that P ?? ?M coincides with X and with ?P, and such that ${P \cup \partial M}$ is a spine of ${M\setminus B}$ (where B is a ball). In this paper, we will prove that the classical set of moves for standard spines of 3-manifolds (i.e. the MP-move and the V-move) does not suffice to relate to each other any two standard skeleta of a 3-manifold with marked boundary. We will also describe a condition on the 3-manifold with marked boundary that allows to establish whether the generalised set of moves, made up of the MP-move and the L-move, suffices to relate to each other any two standard skeleta of the 3-manifold with marked boundary. For the 3-manifolds with marked boundary that do not fulfil this condition, we give three other moves: the CR-move, the T₁-move and the T₂-move. The first one is local and, with the MP-move and the L-move, suffices to relate to each other any two standard skeleta of a 3-manifold with marked boundary fulfilling another condition. For the universal case, we will prove that the non-local T₁-move and T₂-move, with the MP-move and the L-move, suffice to relate to each other any two standard skeleta of a generic 3-manifold with marked boundary. As a corollary, we will get that disc-replacements suffice to relate to each other any two standard skeleta of a 3-manifold with marked boundary.