Eigenvalue distributions of random unitary matrices

 Let U be an n × n random matrix chosen from Haar measure on the unitary group. For a fixed arc of the unit circle, let X be the number of eigenvalues of M which lie in the specified arc. We study this random variable as the dimension n grows, using the connection between Toeplitz matrices and random unitary matrices, and show that (X -E [X])/(\Var (X))^1/2 is asymptotically normally distributed. In addition, we show that for several fixed arcs I ₁ , ..., I _m , the corresponding random variables are jointly normal in the large n limit. Received: 15 November 2000 / Revised version: 27 September 2001 / Published online: 17 May 2002     

Packing graphs with odd and even trees

The Gyárfás-Lehel tree-packing conjecture asserts that any sequence T₁, T₂, …, T_n^?1 of trees with 1, 2, …, n - 1 edges packs into the complete graph K_n on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás-Lehel conjecture: 1. For n even, any T₁, T₃, …, T_n^?1 pack into the half-complete graph Hn on n vertices.2. For n odd, any T₂, T₄, …, T_n^?1 pack into the half-complete graph Hn on n vertices. The H_n are uniquely defined by their degree sequences: H_n and H_n+1 are complements in K_n+1. It is shown that H_n and T_n+1 pack into H_n+2 if T_n+1 is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás-Lehel conjecture holds for n ≤ 9.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

A multipartite Ramsey number for odd cycles

In this article we study multipartite Ramsey numbers for odd cycles. Our main result is the proof that a conjecture of Gyárfás et al. (J Graph Theory 61 (2009), 12–21), holds for graphs with a large enough number of vertices. Precisely, there exists n₀ such that if n?n₀ is a positive odd integer then any two‐coloring of the edges of the complete five‐partite graph K_{(n ? 1)/2, (n ? 1)/2, (n ? 1)/2, (n ? 1)/2, 1} contains a monochromatic cycle of length n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Tur��n Numbers for Disjoint Copies of Graphs

The Turán number ex(n,H){ex(n,\mathcal H)} of H{\mathcal H} is the maximum number of edges of an n-vertex simple graph having no member of H{\mathcal H} as a subgraph. We show lower and upper bounds for Turán numbers for disjoint copies of graphs.     

Zero Distribution of Bergman Orthogonal Polynomials for Certain Planar Domains

   Abstract. Let G be a simply connected domain in the complex plane bounded by a closed Jordan curve L and let P _n , n≥ 0 , be polynomials of respective degrees n=0,1,··· that are orthonormal in G with respect to the area measure (the so-called Bergman polynomials). Let ϕ be a conformal map of G onto the unit disk. We characterize, in terms of the asymptotic behavior of the zeros of P _n 's, the case when ϕ has a singularity on L . To investigate the opposite case we consider a special class of lens-shaped domains G that are bounded by two orthogonal circular arcs. Utilizing the theory of logarithmic potentials with external fields, we show that the limiting distribution of the zeros of the P _n 's for such lens domains is supported on a Jordan arc joining the two vertices of G . We determine this arc along with the distribution function.     

A Universality Property of Gaussian Analytic Functions

We consider random analytic functions defined on the unit disk of the complex plane f(z) = ?_n=0^￥ a_n X_n zⁿf(z) = \sum_{n=0}^{\infty} a_{n} X_{n} z^{n}, where the X _n ’s are i.i.d., complex-valued random variables with mean zero and unit variance. The coefficients a _n are chosen so that f(z) is defined on a domain of ℂ carrying a planar or hyperbolic geometry, and Ef(z)[`(f(w))]\mathbf{E}f(z)\overline{f(w)} is covariant with respect to the isometry group. The corresponding Gaussian analytic functions have been much studied, and their zero sets have been considered in detail in a monograph by Hough, Krishnapur, Peres, and Virág. We show that for non-Gaussian coefficients, the zero set converges in distribution to that of the Gaussian analytic functions as one transports isometrically to the boundary of the domain. The proof is elementary and general.     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense. Supported by OTKA grants 043520 and 049301, and by the EU Marie Curie grants Discconvgeo, Budalggeo and PHD. Authors’ addresses: Károly J. B?r?czky, Alfréd Rényi Institute of Mathematics, P.O. Box 127, Budapest H–1364, Hungary, and Department of Geometry, Roland E?tv?s University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary; Salvador S. Gomis, Department of Mathematical Analysis, University of Alicante, 03080 Alicante, Spain; Péter Tick, Gyűrű utca 24, Budapest H–1039, Hungary     

On the values of the divisor function

For a positive integer n we let τ(n) denote the number of its positive divisors. In this paper, we obtain lower and upper bounds for the average value of the ratio τ(n + 1)/τ(n) as n ranges through positive integers in the interval [1,x]. We also study the cardinality of the sets {τ(p − 1) : p ≤ x prime} and {τ(2ⁿ − 1) : n ≤ x}. Authors’ addresses: Florian Luca, Instituto de Matemáticas, Universidad Nacional Autónoma'de'México, C.P. 58089, Morelia, Michoacán, México; Igor E. Shparlinski, Department of Computing, Macquarie University, Sydney, NSW 2109, Australia     

On q-Parametric Szász-Mirakjan Operators

In the present paper, we introduce q-parametric Szász-Mirakjan operators. We study convergence properties of these operators S _n,q (f). We obtain inequalities for the weighted approximation error of q-Szász-Mirakjan operators. Such inequalities are valid for functions of polynomial growth and are expressed in terms of weighted moduli of continuity. We also discuss Voronovskaja-type formula for q-Szász-Mirakjan operators.     

Real hypersurfaces of a complex space form

In this paper, we show that an n-dimensional connected non-compact Ricci soliton isometrically immersed in the flat complex space form ){(C^{\frac{n+1}{2}},J,\left\langle ,\right\rangle )}, with potential vector field of the Ricci soliton is the characteristic vector field of the real hypersurface is an Einstein manifold. We classify connected Hopf hypersurfaces in the flat complex space form (C ^{á ñ\fracn+12},J, á , ñ ){(C^{\frac{n+1}{2}},J,\left\langle ,\right\rangle )} and also obtain a characterization for the Hopf hypersurfaces in (C^\fracn+12,J, á , ñ ) {(C^{\frac{n+1}{2}},J,\left\langle ,\right\rangle ) }.     

Extremal graphs with bounded densities of small subgraphs

Let Ex(n, k, μ) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most μ edges. Here we summarize some known results of the problem of determining Ex(n, k, μ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new results, one of our main aims is to show how the classical Turáan theory can be applied to such problems. The case μ = is the famous result of Turáan. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 185–207, 1998     

Boxes for curves of constant length

We prove that every arc of lengthL inE ⁿ lies in some hypercube of diagonalL and that every closed curve of lengthL lies in some hypercube of diagonalL/2. In the casen=2, we find the smallest rectangle that can accommodate every arc of lengthL and the smallest rectangle that can accommodate every closed curve of lengthL.     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.     

Unit and Proper Tube Orders

In 2005, we defined the n-tube orders, which are the n-dimensional analogue of interval orders in 1 dimension, and trapezoid orders in 2 dimensions. In this paper we consider two variations of n-tube orders: unit n-tube orders and proper n-tube orders. It has been proven that the classes of unit and proper interval orders are equal, and the classes of unit and proper trapezoid orders are not. We prove that the classes of unit and proper n-tube orders are not equal for all n ≥ 3, so the general case follows the situation in 2 dimensions.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

On Polynomial Approximation of Square Integrable Functions on a Subarc of the Unit Circle

Let E be an arc on the unit circle and let L²(E) be the space of all square integrable functions on E. Using the Banach–Steinhaus Theorem and the weak* compactness of the unit ball in the Hardy space, we study the L² approximation of functions in L²(E) by polynomials. In particular, we will investigate the size of the L² norms of the approximating polynomials in the complementary arc E of E. The key theme of this work is to highlight the fact that the benefit of achieving good approximation for a function over the arc E by polynomials is more than offset by the large norms of such approximating polynomials on the complementary arc E.