Sensitivity analysis in convex vector optimization

We consider a parametrized convex vector optimization problem with a parameter vectoru. LetY(u) be the objective space image of the parametrized feasible region. The perturbation mapW(u) is defined as the set of all minimal points of the setY(u) with respect to an ordering cone in the objective space. The purpose of this paper is to investigate the relationship between the contingent derivativeDW ofW and the contingent derivativeDY ofY. Sufficient conditions for MinDW=MinDY andDW=W minDY are obtained, respectively. Therefore, quantitative information on the behavior of the perturbation map is provided.The author would like to thank the anonymous referees for their helpful comments which improved the quality of this paper. The author would also like to thank Professor P. L. Yu for his encouragement.     

Time-optimal controls of the equation of evolution in a separable and reflexive Banach space

Let a variable, closed, bounded, and convex subset ofX, a separable and reflexive Banach space, be denoted byG(t). Suppose thatG(t) varies upper-semicontinuously with respect to inclusion ast varies in [0,T]. We say that the strongly measurable mapu from [0,T] toX is an admissible control if, for almost everyt in [0,T],u(t) is an element ofU, a closed, bounded, and convex subset ofX, and u _p M ^1p, where p>1 andM>0.Ifx ^u is the weak solution todx/dt+A(t)x=u(t), 0tT, whereA(t) is as defined by Tanabe in Ref. 1, we say that the responsex ^u to the controlu hits the target in timeT ^u ifx ^u (0)=0 andx ^u (T ^u ) is an element ofG(T ^u ). If there is a control with this property, then there is a time-optimal control.     

An unfeasible matching problem

LetG be a bipartite graph with natural edge weights, and letW be a function from the set of vertices ofG into natural numbers. AW-matching ofG is a subset of the set of edges ofG such that for each vertexv the total weight of edges in the subset incident tov does not exceedW(v). Letm be a natural number. We show that the problem of deciding whether there is aW-matching inG whose total weight is not less thanm is NP-complete even ifG is bipartite and its edge weights as well as theW(v)-constraints are constantly bounded.     

Bi-complement Reducible Graphs

We introduce a new family of bipartite graphs which is the bipartite analogue of the class ofcomplement reduciblegraphs orcographs. Abi-complement reduciblegraph orbi-cographis a bipartite graphG = (W ∪ B, E) that can be reduced to single vertices by recursively bi-complementing the edge set of all connected bipartite subgraphs. Thebi-complementedgraphofGis the graph having the same vertex setW ∪ BasG, while its edge set is equal toW × B − E. The aim of this paper is to show that there exists an equivalent definition of bi-cographs by three forbidden configurations. We also propose a tree representation for this class of graphs.     

Free subgroups of groups with a single defining relation

Summary This paper proves the following theorem. LetG be a group generated byA andB. LetW be a word inA andB which in cyclically reduced form contains bothA andB. IfG has the presentationG= ^u =I>, u =2, then there exists an integerv ₀ such thatA, B ^v generate a free subgroup ofG for allv =v ₀. A suitable value forv ₀ is easily calculated. The result can be generalized by replacingW ^u byWW whereW is obtained fromW by means of applying certain automorphisms of period 2 toW. Here it is required that the wordWW satisfies an easily verifiable extra condition.     

Embedding theorem ofZ-graded Lie superalgebras

The embedding theorem ofZ-graded Lie superalgebras is given and proved. As a subsidiary result it is proved that a transitiveZ-graded restricted lie superalgebm must be isomorphic toW(m,n, 1) if the dimension ofG _i satisfies a certain condition. Project supported by the National Natural Science Foundation of China and the Science of the University Doctoral Program of CNEC.     

A constrained matching problem

We show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graphG = (V,E) with edge weights and a digraphD = (V,A). AMaster/Slave-matching (MS-matching) ofG with respect toD is a matching ofG such that for each arc (u, v) A for which the nodeu is matched, the nodev is matched, too. TheMS-Matching Problem is the problem of finding a maximum-weight MS-matching. Letk(D) be the maximum size of a (weakly) connected component ofD. We prove that MS-matching is an NP-hard problem even ifG is bipartite andk(D) 3. Moreover, we show that in the relevant special case wherek(D) 2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.This research was supported by Grant 03-KL7PAS-6 of the German Federal Ministry of Research and Technology.     

Translation-invariant subspaces of functions on the group of linear transformations on the real line

The characterization of right translation-invariant subspaces ofL _∞(G ^*), where , is studied. We introduce the class of multiplier functions which, in the semisimple case, play a role similar to that played by the exponentials for the real line. However, it is proved that multiplier functions ofG ^* with respect toR fail to characterize right translation-invariant subspaces ofL _∞(G ^*). That is, we construct a right translation-invariant, w^*-closed subspace ofL _∞(G ^*) which contains no multiplier function. This paper is a part of the author's Ph.D. thesis prepared at the Hebrew University of Jerusalem under the supervision of Professor H. Furstenberg, to whom the author wishes to express his thanks for his helpful guidance, and valuable remarks.     

Hamiltonian Connected Claw-Free Graphs

A well-known result by O. Ore is that every graph of order n with d(u)+d(v)n+1 for any pair of nonadjacent vertices u and v is hamiltonian connected (i.e., for every pair of vertices, there is a hamiltonian path joining them). In this paper, we show that every 3-connected claw-free graph G on at most 5–8 vertices is hamiltonian connected, where denotes the minimum degree in G. This result generalizes several previous results.Acknowledgments. The author would like to thank the referee for his important suggestions and careful corrections.Final version received: March 12, 2003Supported by the project of Nature Science Funds of China     

W v cycles in plane graphs

A cycle in a plane graphG is called aW _v cycle if it has a connected (or empty) intersection with each face of the graph. We show that if the minimum degree (G)3 thenG has aW _v cycle and the lengthw(G) of a longestW _v cycle is bounded by the number,f(G), of faces ofG. The classW of graphsG withw(G)=f(G) is completely characterized by an characterized by an inductive construction from two graphs, namelyK ₄ and a face merging of two copies ofK ₄ on one hand, and in terms involving Halin graphs and face merging on the other hand. Longest cycles in members ofW are investigated. The shortness coefficient ofW is proved to be between one-half and three-quarters inclusively.     

Cycle reversals in oriented plane quadrangulations and orthogonal plane partitions

Aplane quadrangulation G is a simple plane graph such that each face ofG is quadrilateral. A (^*) -orientation D ^*(G) ofG is an orientation ofG such that the outdegree of each vertex on G is 1 and the outdegrees of other vertices are all 2, where G denotes the outer 4-cycle ofG. In this paper, we shall show that every plane quadrangulationG has at least one (^*)-orientation. We also show that any two (*)-orientations ofG can be transformed into one another by a sequence of 4-cycle reversals. Moreover, we apply this fact toorthogonal plane partitions, which are partitions of a square into rectangles by straight segments.A research fellow of the Japan Society for the Promotion of Science.     

On bandwidth sums of graphs

ＯＮＢＡＮＤＷＩＤＴＨＳＵＭＳＯＦＧＲＡＰＨＳＹＡＯＢＩＮＧ（姚兵）;ＷＡＮＧＪＩＡＮＦＡＮＧ（王建方）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｉｈｗｅｓｔｅｔｅｒｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ,Ｌａｎｚｈｏｕ７３００７０,Ｃｈｉ...     

Moduli of continuity of local times of strongly symmetric Markov processes via Gaussian processes

LetX be a strongly symmetric standard Markov process on a locally compact metric spaceS with 1-potential densityu ¹(x, y). Let {L _t ^y , (t, y)R ⁺×S} denote the local times ofX and letG={G(y), yS} be a mean zero Gaussian process with covarianceu ¹(x, y). In this paper results about the moduli of continuity ofG are carried over to give similar moduli of continuity results aboutL _t ^y considered as a function ofy. Several examples are given with particular attention paid to symmetric Lévy processes.The research of both authors was supported in part by a grant from the National Science Foundation. In addition the research of Professor Rosen was also supported in part by a PSC-CUNY research grant. Professor Rosen would like to thank the Israel Institute of Technology, where he spent the academic year 1989–90 and was supported, in part, by the United States-Israel Binational Science Foundation. Professor Marcus was a faculty member at Texas A&M University while some of this research was carried out.     

Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected

Let G be a graph. For u,vV(G) with dist_G(u,v)=2, denote J_G(u,v)={wN_G(u)∩N_G(v)|N_G(w)N_G(u)N_G(v){u,v}}. A graph G is called quasi claw-free if J_G(u,v)≠ for any u,vV(G) with dist_G(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected.     

Beurling's theorem and invariant subspaces for the shift on Hardy spaces

Let G be a bounded open subset in the complex plane and let H~2(G) denote the Hardy space on G. We call a bounded simply connected domain W perfectly connected if the boundary value function of the inverse of the Riemann map from W onto the unit disk D is almost 1-1 with respect to the Lebesgue measure on D and if the Riemann map belongs to the weak-star closure of the polynomials in H~∞(W). Our main theorem states: in order that for each M∈Lat (M_z), there exist u∈H~∞(G) such that M=∨{uH~2(G)}, it is necessary and sufficient that the following hold: (1) each component of G is a perfectly connected domain; (2) the harmonic measures of the components of G are mutually singular; (3) the set of polynomials is weak-star dense in H~∞(G). Moreover, if G satisfies these conditions, then every M∈Lat (M_z) is of the form uH~2(G), where u∈H~∞(G) and the restriction of u to each of the components of G is either an inner function or zero.     

On minimum metric dimension of honeycomb networks

A minimum metric basis is a minimum set W of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex wW with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. The honeycomb and hexagonal networks are popular mesh-derived parallel architectures. Using the duality of these networks we determine minimum metric bases for hexagonal and honeycomb networks.     

Zur Analytischen Darstellung des Randes Konvexer Körper Durch Stützhyperboloide

In this note, semiaxis-function and vertex-surface of a compact convex subsetK (with interior points) in (n+1)-dimensional Euclidean space are investigated. The semiaxisfunction ofK is defined by associating the half length a of the transverse axisv of any support hyperboloid ofK with the unit vectoru parallel tov, i.e. a is defined as function ofu. The end points of the vectors a(u)·u form the vertex-hypersurface ofK. Most significant result is the continuous differentiability of a (u(t)) as a function of t, where u (t)=1 andu (t) is a continuous differentiable vector function. Proof does not require further assumptions concerningK.     

Weakly symmetric spaces and bounded symmetric domains

LetG be a connected, simply-connected, real semisimple Lie group andK a maximal compactly embedded subgroup ofG such thatD=G/K is a hermitian symmetric space. Consider the principal fiber bundleM=G/K _s G/K, whereK _s is the semisimple part ofK=K _s ·Z _K ⁰ andZ _K ⁰ is the connected center ofK. The natural action ofG onM extends to an action ofG ¹=G×Z _K ⁰ . We prove as the main result thatM is weakly symmetric with respect toG ¹ and complex conjugation. In the case whereD is an irreducible classical bounded symmetric domain andG is a classical matrix Lie group under a suitable quotient, we provide an explicit construction ofM=D×S ¹ and determine a one-parameter family of Riemannian metrics onM invariant underG ¹. Furthermore,M is irreducible with respect to . As a result, this provides new examples of weakly symmetric spaces that are nonsymmetric, including those already discovered by Selberg (cf. [M]) for the symplectic case and Berndt and Vanhecke [BV1] for the rank-one case.Research partially supported by an NSF grant. The author wishes to thank the International Erwin Schroedinger Institute for its hospitality during the preparation of this paper.     

Quelques observations concernant les ensembles de Ditkin d'un groupe localement compact

We prove that every closed normal subgroupH of a locally compact amenable groupG is a Ditkin set with respect to the Herz-Figà-Talamanca algebraA _p (G) (p>1). Let be the canonical map ofG ontoG/H andF a closed subset ofG/H. We show thatF is a Ditkin set if and only if everyuA _p (G), which vanishes on ^–1, lies on the norm closure of the subspace ofA _p (G) generated by {u _h |hH, vA _p (G)C ₀₀(G)} whereu _h (x)=u(x h). As far as we know, this result seems to be new even forG abelian andp=2.     

Packing circuits in eulerian digraphs

LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK ₆ by –Y andY– operations.