More on an Erdős–Szekeres-Type Problem for Interior Points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k≥1, let g(k) be the smallest integer such that every planar point set in general position with at least g(k) interior points has a convex subset of points with exactly k interior points of P. In this article, we prove that g(3)=9.     

Up-Embeddability of a Graph by Order and Girth

Let G be a connected graph of order n and girth g. If d_G(u) + d_G(v) ≥ n − 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3. Partially supported by the Postdoctoral Seience Foundation of Central South University and NNSFC under Grant No. 10751013.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Approximation Algorithms for Steiner and Directed Multicuts

In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log³(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log² k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Limiting process for integral functionals of a wiener process on a cylinder

We prove that integral functionals, whose integrands are bounded functions of a Wiener process on a cylinder, weakly converge to the processw ₁(τ(t)), τ(t) = β₁ t + (β₂ − β₁)mes {s:w ₂(s)≥0,s<t}, wherew ₁(t andw ₂(t) are independent one-dimensional Wiener processes, β₁ and β₂ are nonrandom values, and β₂≥β₁≥0. Kiev University, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 6, pp. 765–768, June, 1994.     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

An optimal bound on the tail distribution of the number of recurrences of an event in product spaces

 Let X ₁ ,X ₂ ,... be independent random variables and a a positive real number. For the sake of illustration, suppose A is the event that |X _i+1 +...+X _j |≥a for some integers 0≤i<j<∞. For each k≥2 we upper-bound the probability that A occurs k or more times, i.e. that A occurs on k or more disjoint intervals, in terms of P(A), the probability that A occurs at least once. More generally, let X=(X ₁ ,X ₂ ,...)Ω=Π _{j ≥1}Ω _j be a random element in a product probability space (Ω,ℬ,P=⊗ _{j ≥1} P _j ). We are interested in events AB that are (at most contable) unions of finite-dimensional cylinders. We term such sets sequentially searchable. Let L(A) denote the (random) number of disjoint intervals (i,j] such that the value of X _(i,j] =(X _i+1 ,...,X _j ) ensures that XA. By definition, for sequentially searchable A, P(A)≡P(L(A)≥1)=P(𝒩_{−ln (P(Ac))} ≥1), where 𝒩_γ denotes a Poisson random variable with some parameter γ>0. Without further assumptions we prove that, if 0<P(A)<1, then P(L(A)≥k)<P(𝒩_{−ln (P(Ac))} ≥k) for all integers k≥2. An application to sums of independent Banach space random elements in l ^∞ is given showing how to extend our theorem to situations having dependent components. Received: 8 June 2001 / Revised version: 30 October 2002 Published online: 15 April 2003 RID="*" ID="*" Supported by NSF Grant DMS-99-72417. RID="†" ID="†" Supported by the Swedish Research Council. Mathematics Subject Classification (2000): Primary 60E15, 60G50 Key words or phrases: Tail probability inequalities – Hoffmann-Jo rgensen inequality – Poisson bounds – Number of event recurrences – Number of entrance times – Product spaces     

Hypergraphs with independent neighborhoods

For each k ≥ 2, let ρ _k ∈ (0, 1) be the largest number such that there exist k-uniform hypergraphs on n vertices with independent neighborhoods and (ρ _k + o(1))( _k ⁿ ) edges as n → ∞. We prove that ρ _k = 1 − 2logk/k + Θ(log log k/k) as k → ∞. This disproves a conjecture of Füredi and the last two authors.     

The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

On partitioning the edges of graphs into connected subgraphs

For any positive integer s, an s-partition of a graph G = (V, E) is a partition of E into E₁ ∪ E₂ ∪…? ∪ E_k, where ∣E_i∣ = s for 1 ≤ i ≤ k ? 1 and 1 ≤ ∣E_k∣ ≤ s and each E_i induces a connected subgraph of G. We prove

• (i) If G is connected, then there exists a 2-partition, but not necessarily a 3-partition;
• (ii) If G is 2-edge connected, then there exists a 3-partition, but not necessarily a 4-partition;
• (iii) If G is 3-edge connected, then there exists a 4-partition;
• (iv) If G is 4-edge connected, then there exists an s-partition for all s.

     

Non-<Emphasis Type="Italic">φ</Emphasis>-admissible normal subgroups of free burnside groups

In the present paper for arbitrary automorphism φ of the free Bunside group B(m, n) and for any odd number n ≥ 1003 a sufficient condition for existence of non-φ-admissible normal subgroup of B(m, n) was found. In particular, if automorphism φ is normal, then for any basis {a ₁, a ₂, …, a _m } of the group B(m, n) there is an integer k such that for each i the elements a _i and φ(a i) ^k are conjugates.     

Approximation Properties of Julia Polynomials

Let G be a finite simply connected domain in the complex plane C, bounded by a rectifiable Jordan curve L, and let w = φ0 （z） be the Riemann conformal mapping of G onto D （0, r0） ：= {E-mail： ： ｜｜ 〈 r0}, normalized by the conditions φ0 （z0） = 0, φ＇0 （z0） = 1. In this work, the rate of approximation of φ0 by the polynomials, defined with the help of the solutions of some extremal problem, in a closed domain G is studied. This rate depends on the geometric properties of the boundary L.     

Spanning k-Trees of n-Connected Graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg _G (u) + deg _G (v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.     

Asymptotic results on infinite tandem queueing networks

We consider an infinite tandem queueing network consisting of ·/GI/1/∞ stations with i.i.d. service times. We investigate the asymptotic behavior of t(n, k), the inter-arrival times between customers n and n + 1 at station k, and that of w(n, k), the waiting time of customer n at station k. We establish a duality property by which w(n, k) and the “idle times”y(n, k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k∈ℕ} and {t(n, 0), n∈ℕ}, are given. In the half-plane version, the sequence {t(n, 0), n∈ℕ} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n, k), n∈ℕ} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that 1/n∑ _k=1 ⁿ w(0, k) converges almost surely and in L ₁ to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n∈ℤ} converges weakly with k to an invariant limiting distribution. Received: 23 March 1999 / Revised version: 5 January 2000 / Published online: 12 October 2000     

Punishing Factors for Finitely Connected Domains

Let Ω and Π be two finitely connected hyperbolic domains in the complex plane \Bbb C{\Bbb C} and let R(z, Ω) denote the hyperbolic radius of Ω at z and R(w, Π) the hyperbolic radius of Π at w. We consider functions f that are analytic in Ω and such that all values f(z) lie in the domain Π. This set of analytic functions is denoted by A(Ω, Π). We prove among other things that the quantities C_n(W,P) := sup_{f ? A(W,P)}sup_{z ? W}\frac|f⁽ⁿ⁾(z)| R(f(z),P)n! (R(z,W))ⁿC_n(\Omega,\Pi)\,:=\,\sup_{f\in A(\Omega,\Pi)}\sup_{z\in \Omega}\frac{\vert f^{(n)}(z)\vert\,R(f(z),\Pi)}{n!\,(R(z,\Omega))^n} are finite for all n ? \Bbb N{n \in {\Bbb N}} if and only if ∂Ω and ∂Π do not contain isolated points.     

Upper bound theorems for homology manifolds

In this paper we prove the Upper Bound Conjecture (UBC) for some classes of (simplicial) homology manifolds: we show that the UBC holds for all odd-dimensional homology manifolds and for all 2k-dimensional homology manifolds Δ such that β _k (Δ)⩽Σ{β _i (Δ):i ≠k-2,k,k+2 and 1 ⩽i⩽2k-1}, where β _i (Δ) are reduced Betti numbers of Δ. (This condition is satisfied by 2k-dimensional homology manifolds with Euler characteristic χ≤2 whenk is even or χ≥2 whenk is odd, and for those having vanishing middle homology.) We prove an analog of the UBC for all other even-dimensional homology manifolds. Kuhnel conjectured that for every 2k-dimensional combinatorial manifold withn vertices, . We prove this conjecture for all 2k-dimensional homology manifolds withn vertices, wheren≥4k+3 orn≤3k+3. We also obtain upper bounds on the (weighted) sum of the Betti numbers of odd-dimensional homology manifolds.     

Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ⁻¹-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ⁻¹-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2⁻¹-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2⁻¹-isomorphic and 3⁻¹-isomorphic pairs of STS(15)s.     

A characteristic property of spheres

Summary We prove: Let S be a closed n-dimensional surface in an(n+1)-space of constant curvature (n ≥ 2); k₁ ≥ ... ≥ k_n denote its principle curvatures. Let φ(ξ₁, ..., ξ_n) be such that . Then if φ(k₁, ..., k_n)=const on S and S is subject to some additional general conditions (those(II ₀) or(II) n^o 1), S is a sphere. To Enrico Bompiani on his scientific Jubilee     

Trigonometric Approximation of SO(N) Loops

This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a Hölder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order $\mathcal{O}(n^{-\alpha+\epsilon})This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a H?lder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order O(n^-a+e)\mathcal{O}(n^{-\alpha+\epsilon}) for n≥k, where k=k(Q) is determined by topological properties of the loop and ε>0 is arbitrarily small. The convergence rate is therefore ε-close to the optimal achievable rate of approximation. The construction of polynomial loops involves higher-order splitting methods for the matrix exponential. A novelty in this work is the factorization technique for SO(N) loops which incorporates the loops’ topological aspects.