Graeffe's method for eigenvalues

Let an entire functionF(z) of finite genus have infinitely many zeros which are all positive, and take real values for realz. Then it is shown how to give two-sided bounds for all the zeros ofF in terms of the coefficients of the power series ofF, in fact in terms of the coefficients obtained byGraeffe's algorithm applied toF. A simple numerical illustration is given for a Bessel function.     

Properties of Algebraic Equations on the Set of E-Functions over the Field of Rational Functions

The paper presents several theorems on the linear and algebraic independence of the values at algebraic points of the set of E-functions related by algebraic equations over the field of rational functions, as well as some estimates of the absolute values of polynomials with integer coefficients in the values of such functions. The results are obtained by using the properties of ideals in the ring of polynomials of several variables formed by equations relating the above functions over the field of rational functions.     

Über das Stekloffsche Eigenwertproblem: Isoperimetrische Ungleichungen für symmetrische Gebiete

Summary Isoperimetric inequalities ofPólya [6] for symmetric membranes are extended to the Stekloff problem. The given symmetric domainG _z is mapped conformally onto a circle; some (harmonic) eigenfunctions of the circle are transplanted ontoG _z ; application of Rayleigh's and Poincaré's principles to the transplanted functions gives upper bounds for a number of eigenvalues ofG _z which depends on the order of symmetry of the domain.     

The connectivity and minimum degree of circuit graphs of matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.     

Lower bound for a linear form

By using Padé approximations of the first kind, we obtain a lower bound for the absolute value of a linear form with integer coefficients from the values of polylogarithmic functions at rational points. This estimate takes into account the growth of all coefficients of the linear form. Translated fromMatematicheskie Zametki, Vol. 66, No. 4, pp. 617–623, October, 1999.     

Algebraic independence of the values ofE-functions at singular points and Siegel’s conjecture

We prove a generalization of Shidlovskii’s theorem on the algebraic independence of the values ofE-functions satisfying a system of linear differential equations that is well known in the theory of transcendental numbers. We consider the case in which the values ofE-functions are taken at singular points of these systems. Using the obtained results, we prove Siegel’s conjecture that, for the case of first-order differential equations, anyE-function satisfying a linear differential equation is representable as a polynomial in hypergeometricE-functions. Translated fromMatematicheskie Zametki, Vol. 67, No. 2, pp. 174–190, February, 2000.     

An Asymptotic Expansion of the Double Gamma Function

The Barnes double gamma function G(z) is considered for large argument z. A new integral representation is obtained for log G(z). An asymptotic expansion in decreasing powers of z and uniformly valid for |Arg z|<π is derived from this integral. The expansion is accompanied by an error bound at any order of the approximation. Numerical experiments show that this bound is very accurate for real z. The accuracy of the error bound decreases for increasing Arg z.     

Equivariant frame fields on spheres with complementary equivariant complex structures

LetG be a finite group and letM be a unitary representation space ofG. We consider the existence problem of equivariant frame fields on the unit sphereS(M) whose orthogonal complements in the tangent bundleT(S(M)) admitG-equivariant complex structures. Under mild fixed point conditions we give a complete solution for this problem whenG is either ℤ/2ℤ or a finite group of odd order. This article was processed by the author using theLaT_EX style filecljourl from Springer-Verlag.     

There exist graphs with super‐exponential Ramsey multiplicity constant

The Ramsey multiplicity M(G;n) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph K_n. For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C(G) to be , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of K_n. In 1980, Burr and Rosta showed that 0 ≥ C(G) ≤ 2^1?E for all graphs G, and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2^E?1C(G) arbitrarily small. We prove that for each positive integer E, there is a graph G with E edges and C(G) ≤ E^{?E/2 + o(E)}. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008     

On the 3-Connected Matroids That are Minimal Having a Fixed Restriction

 Let N be a restriction of a 3-connected matroid M and let M ^′ be a 3-connected minor of M that is minimal having N as a restriction. This paper gives a best-possible upper bound on |E(M ^′)−E(N)|. Received: July 17, 1998 Revised: March 15, 1999     

The connectivities of line and total graphs

Sharp lower bounds for the point connectivity and line connectivity of the line graph L(G) and the total graph T(G) of a graph G are determined. The lower bounds are expressed in terms of the point connectivity k, line connectivity λ, and minimum degree δ of G. It is also shown that 2λ is an upper bound for k(T(G)) and that λ(T(G))= 2δ = δ(T(G)). In each case the realizable values beyond the lower bound are determined.     

Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds

Let k ≥ 2, be an integer and M be a closed two-manifold with Euler characteristic χ(M) ≤ 0. We prove that each polyhedral map G onM , which has at least (8 k² + 6 k − 6)|χ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4 k + 4. Moreover, we show that the bound 4k + 4 is best possible. Fabrici and Jendrol’ proved that for the sphere this bound is 10 ifk = 2 and 4 k + 3 if k ≥ 3. We also show that the same holds for the projective plane.     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Largest Non-Unique Subgraphs

The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail. Supported by a grant from the Danish Natural Science Research Council.     

Vizing's coloring algorithm and the fan number

Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P ≠ NP . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010     

Exponential sums and singular hypersurfaces

We give upper bounds for the absolute value of exponential sums in several variables attached to certain polynomials with coefficients in a finite field. This bounds are given in terms of invariants of the singularities of the projective hypersurface defined by its highest degree form. For exponential sums attached to the reduction modulo a power of a large prime of a polynomial f with integer coefficients and veryfying a certain condition on the singularities of its highest degree form, we give a bound in terms of the dimension of the Jacobian quotient . Received: 3 November 1997     

Weinberg bounds over nonspherical graphs

Let Aut(G) and E(G) denote the automorphism group and the edge set of a graph G, respectively. Weinberg's Theorem states that 4 is a constant sharp upper bound on the ratio |Aut(G)|/|E(G)| over planar (or spherical) 3‐connected graphs G. We have obtained various analogues of this theorem for nonspherical graphs, introducing two Weinberg‐type bounds for an arbitrary closed surface Σ, namely: where supremum is taken over the polyhedral graphs G with respect to Σ for W_P(Σ) and over the graphs G triangulating Σ for W_T(Σ). We have proved that Weinberg bounds are finite for any surface; in particular: W_P = W_T = 48 for the projective plane, and W_T = 240 for the torus. We have also proved that the original Weinberg bound of 4 holds over the graphs G triangulating the projective plane with at least 8 vertices and, in general, for the graphs of sufficiently large order triangulating a fixed closed surface Σ. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 220–236, 2000     

Remarks on linear independence of certain <Emphasis Type="Italic">q</Emphasis>-series

We obtain lower bounds for linear forms in values of certain q-series with integer coefficients.     

Estimation of the parameters for unstable AR models

ＥＳＴＩＭＡＴＩＯＮＯＦＴＨＥＰＡＲＡＭＥＴＥＲＳＦＯＲＵＮＳＴＡＢＬＥＡＲＭＯＤＥＬＳＡＮＨｏＮＧＺＨＩ（安鸿志）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ,ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ,Ｂｅｉｊｉｎｇ１０...     

On the codimensions of the verbally prime P.I. algebras

Razmyslov’s theory of trace identities for the prime P.I. algebrasM _{k, l} is applied to give bounds for the cocharacters and the codimensions of these algebrasM _{k, l}, as well as for the matrix algebrasM _k(E) over the Grassmann algebraE. These bounds are easier to obtain and are better (tighter) than earlier obtained bounds. Work supported by NSF grant DMS 9100258. Work supported by NSF grant DMS 9101488.