The π-π-theorem for manifold pairs with boundaries

The surgery obstruction of a normal map to a simple Poincaré pair (X, Y) lies in the relative surgery obstruction group L _*(π ₁(Y) → π ₁(X)). A well-known result of Wall, the so-called π-π-theorem, states that in higher dimensions a normal map of a manifold with boundary to a simple Poincaré pair with π ₁(X) ? π ₁(Y) is normally bordant to a simple homotopy equivalence of pairs. In order to study normal maps to a manifold with a submanifold, Wall introduced the surgery obstruction groups LP _* for manifold pairs and splitting obstruction groups LS _*. In the present paper, we formulate and prove for manifold pairs with boundary results similar to the π-π-theorem. We give direct geometric proofs, which are based on the original statements of Wall’s results and apply obtained results to investigate surgery on filtered manifolds.     

n-bathycenters

Does there exist a polygon with the property that for a suitable point p in the plane every ray with endpoint p intersects the polygon in exactly n connected components? Does there exist a polygon with the property that there are two such points, or three, or a segment of such points? For polygon P call a point p with the property that every ray from p intersects P in exactly n connected components n-isobathic with respect to P. Define the n-bathycenter of a polygon P as the set of all points p that are n-isobathic with respect to P. Further define a set S to be an n-bathycenter if there exists a polygon P of which S is the n-bathycenter. This paper deals with the characterization of 2- and 3-bathycenters, together with some results on the general case.     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

On (0, 1)-matrices with prescribed row and column sum vectors

Given partitions R and S with the same weight, the Robinson-Schensted-Knuth correspondence establishes a bijection between the class A(R,S) of (0, 1)-matrices with row sum R and column sum S and pairs of Young tableaux of conjugate shapes λ and λ^∗, with S?λ?R^∗. An algorithm for constructing a matrix in A(R,S) whose insertion tableau has a prescribed shape λ, with S?λ?R^∗, is provided. We generalize some recent constructions due to R. Brualdi for the extremal cases λ=S and λ=R^∗.     

Counting singular plane curves via Hilbert schemes

We give a method of counting the number of curves with a given type of singularity in a suitably ample linear series on a smooth surface using punctual Hilbert schemes. The types of singularities for which our results suffice include the topological type with local equation x^a+y^b with ?a?3b. We work out the example of curves with the analytic type of singularity with local equation x²+yⁿ for 1<n<9.     

Robustness of optimal designs for correlated random variables

Suppose that Y = (Y_i) is a normal random vector with mean Xb and covariance σ²I_n, where b is a p-dimensional vector (b_j), X = (X_ij) is an n × p matrix with X_ij ∈ {−1, 1}; this corresponds to a factorial design with −1, 1 representing low or high level respectively, or corresponds to a weighing design with −1, 1 representing an object j with weight b_j placed on the left and right of a chemical balance respectively. E-optimal designs Z are chosen that are robust in the sense that they remain E-optimal when the covariance of Y_i, Y_i′ is ρ > 0 for i ≠ i′. Within a smaller class of designs similar results are obtained with respect to a general class of optimality criteria which include the A- and D-criteria.     

On the maximal eccentric connectivity indices of graphs

For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5).     

Sufficient conditions for a partially hyperbolic attractor to be a homoclinic class

We prove that a partially hyperbolic attractor with two-dimensional central direction Λ is a homoclinic class if it exhibits a hyperbolic periodic orbit O and a Lorenz-like singularity σ with Wu(σ)∩Ws(O)≠∅ such that Ws(σ) is dense in Λ.     

A family of orthonormal wavelet bases with dilation factor 4

In this paper, we study a method for the construction of orthonormal wavelet bases with dilation factor 4. More precisely, for any integer M>0, we construct an orthonormal scaling filter mM(ξ) that generates a mother scaling function ?M, associated with the dilation factor 4. The computation of the different coefficients of ²|mM(ξ)| is done by the use of a simple iterative method. Also, this work shows how this construction method provides us with a whole family of compactly supported orthonormal wavelet bases with arbitrary high regularity. A first estimate of α(M), the asymptotic regularity of ?M is given by α(M)∼0.25M. Examples are provided to illustrate the results of this work.     

Time-varying minimum cost flow problems

In this paper, we study a minimum cost flow problem on a time-varying network. Let N(V,A,l,b,c_r,c_w) be a network with an arc set A and a vertex set V. Each a∈A is associated with three integer parameters: a positive transit time b(a,t), an arbitrary transit cost c_r(a,t), and a positive capacity limit l(a,t). Each x∈V is associated with two integer parameters: a waiting cost c_w(x,t) and a vertex capacity l(x,t). All these parameters are functions of the discrete time t=0,1,2,… The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

Some well-posed functional equations which generate semigroups

Consider the abstract linear functional equation (FE) (Dx)(t) = f(t) (t ? 0), x(t) = ?(t) (t ? 0) in a Banach space B. A theorem is proven which contains the following result as a special case. Let Y(R; B; η) be a L^p-space or C₀-space on R = (?t8, ∞), with a suitable weight function η, and with values in B. Let D be a closed (unbounded) causal linear operator in Y(R; B; η), which commutes with translations. Suppose that D + λI has a continuous causal inverse for some complex λ, and that D restricted to those functions in Y(R;B;η) which vanish on R^? = (?∞, 0] has a continuous causal inverse. Then (FE) generates a strongly continuous semigroup of translation type on a Banach space, which is essentially the cross product of the restriction of the domain of D to R^? and Y(R⁺; B; η). Examples with B = Cⁿ on how the theory applies to a neutral functional differential equation, a difference equation, a Volterra integrodifferential equation (with nonintegrable kernel but integrable resolvent), and a fractional order functional differential equation are given. Also, an abstract neutral functional differential equation in a Hilbert space is studied and applications to an abstract Volterra integrodifferential equation in a Banach space are indicated.     

Extension of derivations in the algebra of compact operators

Let C(H) denote the C¹-algebra of all compact linear operators on a complex Hilbert space H. If δ is a closable ¹-derivation in C(H) which anti-commutes with an involutive ¹-antiautomorphism α and has finite spatial deficiency-indices, then there exists an infinitesimal generator δ₀ of a continuous action of R on C(H) which extends δ and anti-commutes with α. This is an analogue of the von Neumann's theorem which states that a symmetric operator commuting with a conjugation J has a self-adjoint extension which also commutes with J.     

Well-posedness of a class of perturbed optimization problems in Banach spaces

Let X be a Banach space and Z a nonempty subset of X. Let J:Z→R be a lower semicontinuous function bounded from below and p?1. This paper is concerned with the perturbed optimization problem of finding z₀∈Z such that ‖x−z₀p^‖+J(z₀)=infz∈Z{‖x−zp^‖+J(z)}, which is denoted by minJ(x,Z). The notions of the J-strictly convex with respect to Z and of the Kadec with respect to Z are introduced and used in the present paper. It is proved that if X is a Kadec Banach space with respect to Z and Z is a closed relatively boundedly weakly compact subset, then the set of all x∈X for which every minimizing sequence of the problem minJ(x,Z) has a converging subsequence is a dense Gδ-subset of X?Z₀, where Z₀ is the set of all points z∈Z such that z is a solution of the problem minJ(z,Z). If additionally p>1 and X is J-strictly convex with respect to Z, then the set of all x∈X for which the problem minJ(x,Z) is well-posed is a dense Gδ-subset of X?Z₀.     

Scheduling CCRR tournaments

In this paper, we construct CCRRS, complete coupling round robin schedules, for n teams each consisting of two pairs. The motivation for these schedules is a problem in scheduling bridge tournaments. We construct CCRRS(n) for n a positive integer, n?3, with the possible exceptions of n∈{54,62}. For n odd, we show that a CCRRS(n) can be constructed using a house with a special property. For n even, a CCRRS(n) can be constructed from a Howell design, H(2n-2,2n), with a special property called Property P. We use a combination of direct and recursive constructions to construct H(2n-2,2n) with Property P. In order to apply our main recursive construction, we need group divisible designs with odd group sizes and odd block sizes. One of our main results is the existence of these group divisible designs.     

A Sard theorem for tame set-valued mappings

If F is a set-valued mapping from Rn into Rm with closed graph, then y∈Rm is a critical value of F if for some x with y∈F(x), F is not metrically regular at (x,y). We prove that the set of critical values of a set-valued mapping whose graph is a definable (tame) set in an o-minimal structure containing additions and multiplications is a set of dimension not greater than m−1 (respectively a σ-porous set). As a corollary of this result we get that the collection of asymptotically critical values of a set-valued mapping with a semialgebraic graph has dimension not greater than m−1. We also give an independent proof of the fact that a definable continuous real-valued function is constant on components of the set of its subdifferentiably critical points.     

Constructing a covering triangulation by means of a nowhere-zero dual flow

Tutte conjectured that every graph with no isthmus can be provided with an integral nowhere-zero flow with no absolute value greater than k=5. As yet the result is established for k=6, and it is used for proving that the existence of a triangular imbedding of a graph G in a surface S implies the existence of a triangular imbedding of G_(m) in a surface $\text{S}\text{?}$ with the same orientability characteristic as S. G_(m) stands for the composition of G by an independent set of m vertices.     

Color-bounded hypergraphs, IV: Stable colorings of hypertrees

We consider vertex colorings of hypergraphs in which lower and upper bounds are prescribed for the largest cardinality of a monochromatic subset and/or of a polychromatic subset in each edge. One of the results states that for any integers s≥2 and a≥2 there exists an integer f(s,a) with the following property. If an interval hypergraph admits some coloring such that in each edge E_i at least a prescribed number s_i≤s of colors occur and also each E_i contains a monochromatic subset with a prescribed number a_i≤a of vertices, then a coloring with these properties exists with at most f(s,a) colors. Further results deal with estimates on the minimum and maximum possible numbers of colors and the time complexity of determining those numbers or testing colorability, for various combinations of the four color bounds prescribed. Many interesting problems remain open.     

Unitary multiplier and dilation of projective isometric representation

In this paper we study unitary operator-valued multiplier σ on a normal subsemigroup S of a group G with its extension to G. A dilation of a projective isometric σ-representations of S to a projective unitary Φ(σ)-representation of G is established for a suitable unitary operator-valued multiplier Φ(σ) associated with the multiplier σ which is explicitly constructed during the study.