An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

A New Pareto Optimal Solution in a Lagrange Decomposable Multi-Objective Optimization Problem

In this paper a committee decision-making process of a convex Lagrange decomposable multi-objective optimization problem, which has been decomposed into various subproblems, is studied. Each member of the committee controls only one subproblem and attempts to select the optimal solution of this subproblem most desirable to him, under the assumption that all the constraints of the total problem are satisfied. This procedure leads to a new solution concept of a Lagrange decomposable multi-objective optimization problem, called a preferred equilibrium set. A preferred equilibrium point of a problem, for a committee, may or may not be a Pareto optimal point of this problem. In some cases, a non-Pareto optimal preferred equilibrium point of a problem, for a committee, can be considered as a special type of Pareto optimal point of this problem. This fact leads to a generalization of the Pareto optimality concept in a problem.     

On farthest points of sets

For a convex closed bounded set in a Banach space, we study the existence and uniqueness problem for a point of this set that is the farthest point from a given point in space. In terms of the existence and uniqueness of the farthest point, as well as the Lipschitzian dependence of this point on a point in space, we obtain necessary and su.cient conditions for the strong convexity of a set in several infinite-dimensional spaces, in particular, in a Hilbert space. A set representable as the intersection of closed balls of a fixed radius is called a strongly convex set. We show that the condition “for each point in space that is sufficiently far from a set, there exists a unique farthest point of the set” is a criterion for the strong convexity of a set in a finite-dimensional normed space, where the norm ball is a strongly convex set and a generating set.     

Induction of Geometric Actions

We prove that, in some situations, an induced action from a normal subgroup preserves a geometric structure. Combined with known geometric rigidity results, this result implies certain rigidity statements concerning the full diffeomorphism group of a manifold. It also provides many examples of actions on Lorentz manifolds. Combining these with a small number of well-known actions, we get the full list of connected, simply connected Lie groups admitting a locally faithful, orbit nonproper action by isometries of a connected Lorentz manifold. We give an example of a connected nilpotent Lie group with no complicated action on a Lorentz manifold. We show that, if a connected Lie group has a normal closed subgroup isomorphic to a (two-dimensional) cylinder, then it admits a locally faithful, orbit nonproper action by isometries of a connected Lorentz manifold.     

Scalarization of Henig Proper Efficient Points in a Normed Space

In a general normed space equipped with the order induced by a closed convex cone with a base, using a family of continuous monotone Minkowski functionals and a family of continuous norms, we obtain scalar characterizations of Henig proper efficient points of a general set and a bounded set, respectively. Moreover, we give a scalar characterization of a superefficient point of a set in a normed space equipped with the order induced by a closed convex cone with a bounded base.     

Subgradient Projectors: Extensions,Theory, and Characterizations

Subgradient projectors play an important role in optimization and for solving convex feasibility problems. For every locally Lipschitz function, we can define a subgradient projector via generalized subgradients even if the function is not convex. The paper consists of three parts. In the first part, we study basic properties of subgradient projectors and give characterizations when a subgradient projector is a cutter, a local cutter, or a quasi-nonexpansive mapping. We present global and local convergence analyses of subgradent projectors. Many examples are provided to illustrate the theory. In the second part, we investigate the relationship between the subgradient projector of a prox-regular function and the subgradient projector of its Moreau envelope. We also characterize when a mapping is the subgradient projector of a convex function. In the third part, we focus on linearity properties of subgradient projectors. We show that, under appropriate conditions, a linear operator is a subgradient projector of a convex function if and only if it is a convex combination of the identity operator and a projection operator onto a subspace. In general, neither a convex combination nor a composition of subgradient projectors of convex functions is a subgradient projector of a convex function.     

Diads and their Application to Topoi

It is well known that the category of coalgebras for a finite-limit preserving comonad on a topos is again a topos, and the category of algebras for a finite-limit preserving monad is a topos if the monad is idempotent, but not in general. A generalisation of this result (Paré et al., Bull Aus Math Soc 39(3):421–431, 1989) is that the full subcategory of fixed points for any idempotent finite-limit preserving endofunctor is again a topos (and indeed a subquotient in the category of topoi and geometric morphisms). Here, we present a common generalisation of all the above results, based on a notion which we call a diad, which is a common generalisation of a monad and a comonad. Many of the constructions that can be applied to monads and comonads can be extended to all diads. In particular, the category of algebras or coalgebras can be generalised to a category of dialgebras for a diad. The generalisation we present here is that the category of dialgebras for a finite-limit preserving left diad (for example, the diad corresponding to a comonad, or any idempotent endofunctor) on a topos is again a topos.     

On the intersections of circuits and cocircuits in matroids

Seymour has shown that a matroid has a triad, that is, a 3-element set which is the intersection of a circuit and a cocircuit, if and only if it is non-binary. In this paper we determine precisely when a matroidM has a quad, a 4-element set which is the intersection of a circuit and a cocircuit. We also show that this will occur ifM has a circuit and a cocircuit meeting in more than four elements. In addition, we prove that if a 3-connected matroid has a quad, then every pair of elements is in a quad. The corresponding result for triads was proved by Seymour.     

A relaxed extragradient-like method for a generalized mixed equilibrium problem,a general system of generalized equilibria and a fixed point problem

Very recently, Takahashi and Takahashi [S. Takahashi, W. Takahashi, Strong convergence theorem for a generalized equilibrium problem and a nonexpansive mapping in a Hilbert space, Nonlinear Anal. 69 (2008) 1025–1033] suggested and analyzed an iterative method for finding a common solution of a generalized equilibrium problem and a fixed point problem of a nonexpansive mapping in a Hilbert space. In this paper, based on Takahashi–Takahashi’s iterative method and well-known extragradient method we introduce a relaxed extragradient-like method for finding a common solution of a generalized mixed equilibrium problem, a general system of generalized equilibria and a fixed point problem of a strictly pseudocontractive mapping in a Hilbert space and then obtain a strong convergence theorem. Utilizing this theorem, we establish some new strong convergence results in fixed point problems, variational inequalities, mixed equilibrium problems and systems of generalized equilibria.     

Iterative algorithms for variational inclusions,mixed equilibrium and fixed point problems with application to optimization problems

In this paper, we introduce an iterative algorithm for finding a common element of the set of solutions of a mixed equilibrium problem, the set of fixed points of a nonexpansive mapping, and the the set of solutions of a variational inclusion in a real Hilbert space. Furthermore, we prove that the proposed iterative algorithm converges strongly to a common element of the above three sets, which is a solution of a certain optimization problem related to a strongly positive bounded linear operator.     

U-标算子的结构分析

类似与标型谱算子,U-标算子是否拟仿射相似于自伴算子是一“公开问题”．尽管对具纯离散谱的U-标算子答案是肯定的,但一般情况下并不成立．本文继续探讨这一问题,证明了U-标算子在一强范数拓扑意义下是Hermite算子,或者说U-标算子拟仿射相似于Hermite算子,并给出U-标算子是标型谱算子的充要条件．     

The weighted complexity and the determinant functions of graphs

The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs.     

On a Mathematical Comparison between Hierarchy and Network with a Classification of Coordination Structures

This paper proposes a mathematical model to compare a network organization with a hierarchical organization. In order to formulate the model, we define a three-dimensional framework of the coordination structure of a network and of other typical coordination structures. In the framework, we can define a network structure by contrasting it with a hierarchy, in terms of the distribution of decision making, which is one of the main features of information processing. Based on this definition, we have developed a mathematical model for evaluating coordination structures. Using this model, we can derive two boundary conditions among the coordination structures with respect to the optimal coordination structure. The boundary conditions help us to understand why an organization changes its coordination structure from a hierarchy to a network and what factors cause this change. They enable us, for example, to find points of structural change where the optimal coordination structure shifts from a hierarchy to a hierarchy with delegation or from a hierarchy with delegation to a network, when the nature of the task changes from routine to non-routine. In conclusion, our framework and model may provide a basis for discussing the processes that occur when coordination structures change between a hierarchy and a network.     

Semisimple types for p-adic classical groups

We construct, for any symplectic, unitary or special orthogonal group over a locally compact nonarchimedean local field of odd residual characteristic, a type for each Bernstein component of the category of smooth representations, using Bushnell–Kutzko’s theory of covers. Moreover, for a component corresponding to a cuspidal representation of a maximal Levi subgroup, we prove that the Hecke algebra is either abelian, or a generic Hecke algebra on an infinite dihedral group, with parameters which are, at least in principle, computable via results of Lusztig. In an appendix, we make a correction to the proof of a result of the second author: that every irreducible cuspidal representation of a classical group as considered here is irreducibly compactly-induced from a type.     

Characterizations of g-frames and g-Riesz bases in Hilbert spaces

In this paper, we introduce the pre-frame operator Q for the g-frame in a complex Hilbert space, which will play a key role in studying g-frames and g-Riesz bases etc. Using the pre-frame operator Q, we give some necessary and sufficient conditions for a g-Bessel sequence, a g-frame, and a g-Riesz basis in a complex Hilbert space, which have properties similar to those of the Bessel sequence, frame, and Riesz basis respectively. We also obtain the relation between a g-frame and a g-Riesz basis, and the relation of bounds between a g-frame and a g-Riesz basis. Lastly, we consider the stability of a g-frame or a g-Riesz basis for a Hilbert space under perturbation.     

分次单环的结构

A characterization of gr-simple rings is given by using the notion of componentwise-dense subrings of a full matrix ring over a division ring. As a consequence, any G-graded full matrix ring over a division ring is isomorphic to a dense subring of a full matrix ring with a good G-grading. Some conditions for a grading of a full matrix ring to be isomorphic to a good one are given, which generalize some results in: Dascascu, S., Lon, B., Nastasescu, C. and Montes, J. R., Group gradings on full matrix rings, J. Algebra, 220(1999), 709-728.     

Weak Convergence Theorems for Nonexpansive Mappings and Monotone Mappings

In this paper, we introduce an iteration process of finding a common element of the set of fixed points of a nonexpansive mapping and the set of solutions of a variational inequality problem for an inverse strongly-monotone mapping, and then obtain a weak convergence theorem. Using this result, we obtain a weak convergence theorem for a pair of a nonexpansive mapping and a strictly pseudocontractive mapping. Further, we consider the problem of finding a common element of the set of fixed points of a nonexpansive mapping and the set of zeros of an inverse strongly-monotone mapping.     

A Decomposition of Markov Processes via Group Actions

We study a decomposition of a general Markov process in a manifold invariant under a Lie group action into a radial part (transversal to orbits) and an angular part (along an orbit). We show that given a radial path, the conditioned angular part is a nonhomogeneous Lévy process in a homogeneous space, we obtain a representation of such processes and, as a consequence, we extend the well-known skew-product of Euclidean Brownian motion to a general setting.      

Certificates of Primal or Dual Infeasibility in Linear Programming

In general if a linear program has an optimal solution, then a primal and dual optimal solution is a certificate of the solvable status. Furthermore, it is well known that in the solvable case, then the linear program always has an optimal basic solution. Similarly, when a linear program is primal or dual infeasible then by Farkas's Lemma a certificate of the infeasible status exists. However, in the primal or dual infeasible case then there is not an uniform definition of what a suitable basis certificate of the infeasible status is.In this work we present a definition of a basis certificate and develop a strongly polynomial algorithm which given a Farkas type certificate of infeasibility computes a basis certificate of infeasibility. This result is relevant for the recently developed interior-point methods because they do not compute a basis certificate of infeasibility in general. However, our result demonstrates that a basis certificate can be obtained at a moderate computational cost.