A Markov-Nikolskii type inequality for absolutely monotone polynomials of order <Emphasis Type="Italic">K</Emphasis>

A function Q is called absolutely monotone of order k on an interval I if Q(x) ≥ 0, Q′(x) ≥ 0, …, Q(k)(x) ≥ 0, for all x ε I. An essentially sharp (up to a multiplicative absolute constant) Markov inequality for absolutely monotone polynomials of order k in L _p [−1, 1], p > 0, is established. One may guess that the right Markov factor is cn ²/k, and this indeed turns out to be the case. Similarly sharp results hold in the case of higher derivatives and Markov-Nikolskii type inequalities. There is also a remarkable connection between the right Markov inequality for absolutely monotone polynomials of order k in the supremum norm and essentially sharp bounds for the largest and smallest zeros of Jacobi polynomials. This is discussed in the last section of the paper.     

Binding Numbers and Connected Factors

In this paper, we obtain some sufficient conditions based on binding number for a graph to have a connected factor with degree restrictions. Let α and k be positive integers with α + k ≥ 4. Let G be a connected graph with a spanning subgraph F, each component of which has order at least α. We show that if the binding number of G is greater than (α k − α)/(α k − α −1) (k ≥ 2) and α/(α −2) (k = 1) then G has a connected subgraph which has F and in which every vertex v has degree at most deg _F (v) + k. From the result, we derive various sufficient conditions for a graph to have a connected [a, b]-factor.     

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.     

On local Torelli for a class of extremal varieties

We study the local behaviour of the period map for smooth non-degenerate extremal varieties sitting inside scrolls. We conclude with the following theorem:the period map for smooth non-degenerate extremal varieties of dimension k ≠ 2,3in n-projective space with n≥2k+4is generically locally injective for sufficiently high degree d. In particular, the following two conditions on d suffice: (1)d≥3.k.(n−k)+3; (2)d≥(n − k)²+1.     

Error estimates for the numerical approximation of a quaslinear Neumann problem under minimal regularity of the data

The finite element based approximation of a quasilinear elliptic equation of non monotone type with Neumann boundary conditions is studied. Minimal regularity assumptions on the data are imposed. The consideration is restricted to polygonal domains of dimension two and polyhedral domains of dimension three. Finite elements of degree k ≥ 1 are used to approximate the equation. Error estimates are established in the L ²(Ω) and H ¹(Ω) norms for convex and non-convex domains. The issue of uniqueness of a solution to the approximate discrete equation is also addressed.     

<Emphasis Type="Italic">k</Emphasis>–Pyramidal One–Factorizations

We consider one–factorizations of complete graphs which possess an automorphism group fixing k ≥ 0 vertices and acting regularly (i.e., sharply transitively) on the others. Since the cases k = 0 and k = 1 are well known in literature, we study the case k≥ 2 in some detail. We prove that both k and the order of the group are even and the group necessarily contains k − 1 involutions. Constructions for some classes of groups are given. In particular we extend the result of [7]: let G be an abelian group of even order and with k − 1 involutions, a one–factorization of a complete graph admitting G as an automorphism group fixing k vertices and acting regularly on the others can be constructed.     

Separation of the Monotone NC Hierarchy

, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-≠ monotone-. 3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const). Only a separation of monotone- from monotone- was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1.  For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2.  For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known. Received: December 19, 1997     

On the k-normality of projected algebraic varieties

We give a necessary and sufficient condition for the isomorphic projection of a k-normal variety to remain k-normal, k ≥ 2; the condition is based on a scheme ℤ_k naturally associated to degree k forms vanishing on the variety. We furnish many applications and examples especially in the case of varieties defined by quadratic equations. A non-vanishing theorem for the Koszul cohomology of projected varieties allows us to construct interesting examples in the last sections. All the results are effective and also interesting from the computational point of view. Received: 21 January 2002     

On eigenvalue pinching in positive Ricci curvature

We shall show that for manifolds with Ric≥n−1 the radius is close to π iff the (n+1)st eigenvalue is close to n. This extends results of Cheng and Croke which show that the diameter is close to π iff the first eigenvalue is close to n. We shall also give a new proof of an important theorem of Colding to the effect that if the radius is close to π, then the volume is close to that of the sphere and the manifold is Gromov-Hausdorff close to the sphere. From work of Cheeger and Colding these conditions imply that the manifold is diffeomorphic to a sphere. Oblatum 29-V-1998 & 4-II-1999 / Published online: 21 May 1999     

A k-Tree Containing Specified Vertices

A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that 1 ￡ t ￡ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem.     

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace δ − 1 by δ, respectively.     

Selberg＇s Normal Density Theorem for Automorphic L-Functions for GLm

Let π be an irreducible unitary cuspidal representation of GLm（AQ） with m ≥ 2, and L（s, Tr） the L-function attached to π. Under the Generalized Riemann Hypothesis for L（s,π）, we estimate the normal density of primes in short intervals for the automorphic L-function L（s, π）. Our result generalizes the corresponding theorem of Selberg for the Riemann zeta-function.     

On the diophantine equation x 2 + p 2k = y n

Let 2 ≤ p < 100 be a rational prime and consider equation (3) in the title in integer unknowns x, y, n, k with x > 0, y > 1, n ≥ 3 prime, k ≥ 0 and gcd(x, y) = 1. Under the above conditions we give all solutions of the title equation (see the Theorem). We note that if in (3) gcd(x, y) = 1, our Theorem is an extension of several earlier results [15], [27], [2], [3], [5], [23]. Received: 25 April 2008     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

On the quantitative steinitz theorem in the plane

We prove that for anyk ≥ 4, any setX of points in the plane, and any pointP ε interior conv(X), there is a subsetY (X of at mostk points such that if conv(X) contains a disk with radiusr aroundP, then conv(Y) contains a disk with radius [cos(2/(k + 1))π]/[cos(1/(k + 1))π]r aroundP. This generalizes the quantitative Steinitz theorem in the plane and proves a conjecture of Bárány and Heppes. Dedicated to Professor Dr. Jürgen Flachsmeyer on the occasion of his sixtieth birthday     

The existence of even regular factors of regular graphs on the number of cut edges

For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs.     

Potentially <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> — <Emphasis Type="Italic">G</Emphasis>-graphical sequences: A survey

The set of all non-increasing nonnegative integer sequences π = (d(v ₁), d(v ₂), …, d(v _n )) is denoted by NS _n . A sequence π ∈ NS _n is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of π. The set of all graphic sequences in NS _n is denoted by GS _n . A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph, while π is forcibly H-graphical if every realization of π contains H as a subgraph. Let K _k denote a complete graph on k vertices. Let K _m −H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K _m ). This paper summarizes briefly some recent results on potentially K _m −G-graphic sequences and give a useful classification for determining σ (H, n).     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.