On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

On an interpolatory product rule for evaluating Cauchy principal value integrals

Convergence results for interpolatory product rules for evaluating Cauchy principal value integrals of the form f _?1 ¹ v(x)f(x)/x ? λ dx wherev is an admissible weight function have been extended to integrals of the form f _?1 ¹ k(x)f(x)/x ? λ dx wherek is an arbitrary integrable function subject to certain conditions. Further, whereas the above convergence results were shown when the interpolation points were the Gauss points with respect to some admissible weight functionw, they are now shown to hold when the interpolation points are Radau or Lobatto points with respect tow.     

A new upper bound for the complex Grothendieck constant

Let ? denote the real function $$\varphi (k) = k\smallint _0^{\pi /2} \frac{{cos^2 t}}{{\sqrt {1 - k^2 sin ^2 t} }}dt, - 1 \leqq k \leqq 1$$ and letK _G ^C be the complex Grothendieck constant. It is proved thatK _G ^C ≦8/π(k ₀+1), wherek ₀ is the (unique) solution to the equation?(k)=1/8π(k+1) in the interval [0,1]. One has 8/π(k ₀+1) ≈ 1.40491. The previously known upper bound isK _G ^C ≦e ^1?y ≈ 1.52621 obtained by Pisier in 1976.     

An initial value problem for a singular parabolic equation of even order

At first Cauchy-problem for the equation: \(L[u(X,t)] \equiv \sum\limits_{i = 1}^n {\frac{{\partial ^2 u}}{{\partial x_1^2 }} + \frac{{2v}}{{\left| X \right|^2 }}} \sum\limits_{i = 1}^n {x_i \frac{{\partial u}}{{\partial x_i }} - \frac{{\partial u}}{{\partial t}} = 0} \) wheren≥1,v—an arbitrary constant,t>0,X=(x ₁, …, x_n)∈E ⁿ/{0}, |X|= =(x ₁ ² +…+x _n ² )^1/2, with 0 being a centre of coordinate system, is studied. Basing on the above, the solution of Cauchy-Nicolescu problem is given which consist in finding a solution of the equationL ^p [u (X, t)]=0, withp∈N subject the initial conditions \(\mathop {\lim }\limits_{t \to \infty } L^k [u(X,t)] = \varphi _k (X)\) ,k=0, 1,…,p?1 and ?_k(X) are given functions.     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Global convergence of a modified BFGS-type method for unconstrained non-convex minimization

To the unconstrained programme of non-convex function, this article give a modified BFGS algorithm associated with the general line search model. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the new quasi-Newton iteration equationB _k +1s _k =y _k ^* ,, wherey _k ^* is the sum ofy _k andA _k s _k , andA _k is some matrix. The global convergence properties of the algorithm associating with the general form of line search is proved.     

Functional equations for vector products and quaternions

In our paper we find all functions ${f : \mathbb {R} \times \mathbb {R}^{3} \rightarrow \mathbb {H}}$ and ${g : \mathbb {R}^{3} \rightarrow \mathbb {H}}$ satisfying ${f (r, {\bf v}) f (s, {\bf w}) = -\langle{\bf v},{\bf w}\rangle + f (rs, s{\bf v} + r{\bf w} + {\bf v} \times {\bf w})}$ ${(r, s \in \mathbb {R}, {\bf v},{\bf w} \in \mathbb {R}^{3})}$ , and ${g({\bf v})g({\bf w}) = -\langle{\bf v}, {\bf w}\rangle + g({\bf v} \times {\bf w})}$ $({{\bf v},{\bf w} \in \mathbb {R}^{3}})$ . These functional equations were motivated by the well-known identities for vector products and quaternions, which can be obtained from the solutions f (r, (v ₁, v ₂, v ₃)) = r + v ₁ i + v ₂ j + v ₃ k and g((v ₁ ,v ₂, v ₃)) = v ₁ i + v ₂ j + v ₃ k.     

k-Quasihyponormal operators are subscalar

In this paper we shall prove that if an operatorT∈L(⊕ ₁ ² H) is an operator matrix of the form $$T = \left( {\begin{array}{*{20}c} {T_1 } & {T_2 } \\ 0 & {T_3 } \\ \end{array} } \right)$$ whereT ₁ is hyponormal andT ₃ ^k =0, thenT is subscalar of order 2(k+1). Hence non-trivial invariant subspaces are known to exist if the spectrum ofT has interior in the plane as a result of a theorem of Eschmeier and Prunaru (see [EP]). As a corollary we get that anyk-quasihyponormal operators are subscalar.     

On the power of the zeros of Bessel functions

For ν≥0 let c_νk be the k-th positive zero of the cylinder functionC _v(t)=J _v(t)cosα-Y _v(t)sinα, 0≤α>π whereJ _ν(t) andY _ν(t) denote the Bessel functions of the first and the second kind, respectively. We prove thatC _v,k ^1+H(x) is convex as a function of ν, ifc _νk≥x>0 and ν≥0, whereH(x) is specified in Theorem 1.1.     

Lucas's criterion for the primality of numbers of the form N = h2n−1

The following theorem is proved. Let N = h2ⁿ-1, where n ≥ 2, h is odd, 1 <-h < 2ⁿ, and suppose that v is a positive integer, v ≥ 3,α is a root of the equation $$(v^2 - 4,N) = 1,\left( {\frac{{v - 2}}{N}} \right) = 1,\left( {\frac{{v + 2}}{N}} \right) = - 1$$ . Then for N to be prime, it is necessary and sufficient that s_n?2≡0(modN), where S_k+1=S _k ² ? 2 (k = 0, 1...), s_o=a^h+ a^?h. For given N, an algorithm is described for the construction of the smallest v satisfying the conditions of this theorem.     

Grassmann and Weyl embeddings of orthogonal grassmannians

Given a non-singular quadratic form q of maximal Witt index on $V := V(2n+1,\mathbb{F})$ , let Δ be the building of type B _n formed by the subspaces of V totally singular for q and, for 1≤k≤n, let Δ _k be the k-grassmannian of Δ. Let ε _k be the embedding of Δ _k into PG(? ^k V) mapping every point 〈v ₁,v ₂,…,v _k 〉 of Δ _k to the point 〈v ₁∧v ₂∧?∧v _k 〉 of PG(? ^k V). It is known that if $\mathrm{char}(\mathbb{F})\neq2$ then $\mathrm{dim}(\varepsilon_{k})={{2n+1}\choose k}$ . In this paper we give a new very easy proof of this fact. We also prove that if $\mathrm{char}(\mathbb{F}) = 2$ then $\mathrm{dim}(\varepsilon_{k})={{2n+1}\choose k}-{{2n+1}\choose{k-2}}$ . As a consequence, when 1<k<n and $\mathrm{char}(\mathbb{F}) = 2$ the embedding ε _k is not universal. Finally, we prove that if $\mathbb{F}$ is a perfect field of characteristic p>2 or a number field, n>k and k=2 or 3, then ε _k is universal.     

On symmetric and nonsymmetric blowup for a weakly quasilinear heat equation

We construct blow-up patterns for the quasilinear heat equation (QHE) $$u_t = \nabla \cdot (k(u)\nabla u) + Q(u)$$ in Ω×(0,T), Ω being a bounded open convex set in ? ^N with smooth boundary, with zero Dirichet boundary condition and nonnegative initial data. The nonlinear coefficients of the equation are assumed to be smooth and positive functions and moreoverk(u) andQ(u)/u ^p with a fixedp>1 are of slow variation asu→∞, so that (QHE) can be treated as a quasilinear perturbation of the well-known semilinear heat equation (SHE) $$u_t = \nabla u) + u^p .$$ We prove that the blow-up patterns for the (QHE) and the (SHE) coincide in a structural sense under the extra assumption $$\smallint ^\infty k(f(e^s ))ds = \infty ,$$ wheref(v) is a monotone solution of the ODEf′(v)=Q(f(v))/v ^p defined for allv?1. If the integral is finite then the (QHE) is shown to admit an infinite number of different blow-up patterns.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

Signed total (k, k)-domatic number of digraphs

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ^?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f ₁, f ₂, . . . , f _d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d _st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006).     

Binary codes and partial permutation decoding sets from the odd graphs

For k ≥ 1, the odd graph denoted by O(k), is the graph with the vertex-set Ω^{k}, the set of all k-subsets of Ω = {1, 2, …, 2k +1}, and any two of its vertices u and v constitute an edge [u, v] if and only if u ∩ v = /0. In this paper the binary code generated by the adjacency matrix of O(k) is studied. The automorphism group of the code is determined, and by identifying a suitable information set, a 2-PD-set of the order of k ⁴ is determined. Lastly, the relationship between the dual code from O(k) and the code from its graph-theoretical complement $\overline {O(k)} $ , is investigated.     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

D’Atri Spaces of Type k and Related Classes of Geometries Concerning Jacobi Operators

In this article, we continue the study of the geometry of k-D’Atri spaces, 1≤k ≤n?1 (n denotes the dimension of the manifold), begun by the second author. It is known that k-D’Atri spaces, k≥1, are related to properties of Jacobi operators R _v along geodesics, since she has shown that ${\operatorname{tr}}R_{v}$ , ${\operatorname{tr}}R_{v}^{2}$ are invariant under the geodesic flow for any unit tangent vector v. Here, assuming that the Riemannian manifold is a D’Atri space, we prove in our main result that ${ \operatorname{tr}}R_{v}^{3}$ is also invariant under the geodesic flow if k≥3. In addition, other properties of Jacobi operators related to the Ledger conditions are obtained, and they are used to give applications to Iwasawa type spaces. In the class of D’Atri spaces of Iwasawa type, we show two different characterizations of the symmetric spaces of noncompact type: they are exactly the $\frak{C}$ -spaces, and on the other hand they are k -D’Atri spaces for some k≥3. In the last case, they are k-D’Atri for all k=1,…,n?1 as well. In particular, Damek–Ricci spaces that are k -D’Atri for some k≥3 are symmetric. Finally, we characterize k-D’Atri spaces for all k=1,…,n?1 as the $\frak{SC}$ -spaces (geodesic symmetries preserve the principal curvatures of small geodesic spheres). Moreover, applying this result in the case of 4 -dimensional homogeneous spaces, we prove that the properties of being a D’Atri (1-D’Atri) space, or a 3-D’Atri space, are equivalent to the property of being a k-D’Atri space for all k=1,2,3.     

Embedding height balanced trees and Fibonacci trees in hypercubes

A height balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the difference b _T (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree T _h of height h is a subtree of the hypercube Q _h+1 of dimension h+1, if T _h contains a path P from its root to a leaf such that $\mathbf{b}_{T_{h}}(v)=1$ , for every non-leaf vertex v in P. A Fibonacci tree $\mathbb{F}_{h}$ is a height balanced tree T _h of height h in which $\mathbf{b}_{\mathbb{F}_{h}}(v)=1$ , for every non-leaf vertex. $\mathbb{F}_{h}$ has f(h+2)?1 vertices where f(h+2) denotes the (h+2)th Fibonacci number. Since f(h)～2^0.694h , it follows that if $\mathbb{F}_{h}$ is a subtree of Q _n , then n is at least 0.694(h+2). We prove that $\mathbb{F}_{h}$ is a subtree of the hypercube of dimension approximately 0.75h.     

Presentations of the amalgamated free product of two infinite cycles

LetH=〈a,b;a ^k =b ^l 〉, wherek,l≧2 andk+l>4. McCool and Pietrowski have proved that any pair of generators forH is Nielsen equivalent to a pairx=a ^r andy=b ^s where $$(a){\text{ }}gcd(r, s) = gcd(r, k) = gcd(s, l) = 1,$$ $$(b){\text{ }}0< 2r \leqq ks{\text{ }}and{\text{ }}0< 2s \leqq lr.$$ In terms ofx andy,H can be presented as $$G = \left\langle {x,{\text{ }}y;{\text{ }}x^{ks} = y^{lr} ,\left[ {x,{\text{ }}y^l } \right] = \left[ {x^k ,{\text{ }}y} \right] = 1} \right\rangle$$ and Zieschang has shown that ifr=1 ors=1, thenH can be defined by a single relation inx andy. We establish the exact converse of Zieschang's result, namely thatH is not defined by a single relation inx andy unlessr=1 ors=1. The proof is based on an observation of Magnus which associates polynomials with relators and some elementary facts about cyclotomic polynomials.