Topological classification of holomorphic, semi-hyperbolic germs, in ``Quasi-Absence' of resonances

We give the classification, under topological conjugacy, of invertible holomorphic germs f:, with λ₁, . . . ,λ_n eigenvalues of d f₀, and |λ_i|≠1 for i=2, . . . ,n while λ₁ is a root of the unity, in the suitable hypothesis of ``quasi-absence' of resonances (i.e., assuming that for r_i≥0 and i=2, . . . ,n, with ).     

Bipartite Subgraphs and Quasi-Randomness

We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in G_n is at most (1+o(1))p^e(H)n^v(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs K_a,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003     

Prediction for discrete time series

Let {X_n} be a stationary and ergodic time series taking values from a finite or countably infinite set Assume that the distribution of the process is otherwise unknown. We propose a sequence of stopping times _n along which we will be able to estimate the conditional probability P(=x|X₀,...,) from data segment (X₀,...,) in a pointwise consistent way for a restricted class of stationary and ergodic finite or countably infinite alphabet time series which includes among others all stationary and ergodic finitarily Markovian processes. If the stationary and ergodic process turns out to be finitarily Markovian (among others, all stationary and ergodic Markov chains are included in this class) then almost surely. If the stationary and ergodic process turns out to possess finite entropy rate then _n is upperbounded by a polynomial, eventually almost surely.Mathematics Subject Classification (2000): 62G05, 60G25, 60G10     

The volumetric barrier for convex quadratic constraints

Let where and _i is an n×n positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for are and self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining , and our earlier results on the volumetric barrier for SDP. The self-concordance results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of .Mathematics Subject Classification (1991):90C25, 90C30     

Orthogonal Double Covers of Complete Graphs by Caterpillars of Diameter 5

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection = {G_i|i = 1,2, . . . ,n} of spanning subgraphs of K_n, all isomorphic to G, with the property that every edge of K_n belongs to exactly two members of and any two distinct members of share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K_n.     

The Rees algebra of a positive normal affine semigroup ring

Let R be a positive normal affine semigroup ring of dimension d and let be the maximal homogeneous ideal of R. We show that the integral closure of is equal to for all n ∈ℕ with n ≥ d − 2. From this we derive that the Rees algebra R[t] is normal in case that d ≤ 3. If emb dim(R) = d + 1, we can give a necessary and sufficient condition for R[t] to be normal.     

An exact algorithm for scheduling identical coupled tasks

The coupled task problem is to schedule n jobs on one machine where each job consists of two subtasks with required delay time between them. The objective is to minimize the makespan. This problem was analyzed in depth by Orman and Potts [3]. They investigated the complexity of different cases depending on the lengths a_i and b_i of the two subtasks and the delay time L_i. -hardness proofs or polynomial algorithms were given for all cases except for the one where a_i=a, b_i=b and L_i=L. In this paper we present an exact algorithm for this problem with time complexity O(nr^2L) where holds. Therefore the algorithm is linear in the number of jobs for fixed L.Acknowledgements. The authors are grateful to Hans Kellerer who called their attention to this problem.Research was supported by DAAD exchange program 324 PPP-Ungarn.     

Associated primes and cofiniteness of local cohomology modules

Let be an ideal of Noetherian ring R and let s be a non-negative integer. Let M be an R-module such that is finite R-module. If s is the first integer such that the local cohomology module is non -cofinite, then we show that is finite. In particular, the set of associated primes of is finite. Let be a local Noetherian ring and let M be a finite R-module. We study the last integer n such that the local cohomology module is not -cofinite and show that n just depends on the support of M.The research of the first author was supported in part by a grant from IPM (No. 83130114).The second author was supported by a grant from University of Tehran (No. 6103023/1/01).     

Estimates for stable hypersurfaces of prescribed F-mean curvature

We consider immersed hypersurfaces :Mⁿ→ℝⁿ⁺¹ with prescribed anisotropic mean curvature . Such hypersurfaces can be characterized as critical points of parametric functionals of the type with an elliptic Lagrangian F depending on normal directions and a smooth vectorfield Q satisfying . We establish curvature estimates for stable hypersurfaces of dimension n≤5, provided F is C³-close to the area integrand.     

Conjugacy classes of affine automorphisms of and linear automorphisms of ℙ n in the Cremona groups

We describe the conjugacy classes of affine automorphisms in the group Aut(n,) (respectively Bir()) of automorphisms (respectively of birational maps) of . From this we deduce also the classification of conjugacy classes of automorphisms of ℙⁿ in the Cremona group Bir().     

Hölder and Young Inequalities for the Trace of Operators

If A₁, . . . , A_m are positive semidefinite n × n matrices, and if p₁, . . . , p_m are positive real numbers such that then where |X| denotes and tr(X) denotes the trace of X. Moreover, equality holds in either of these inequalities if and only if . This result will be shown to hold as well in unital C*-algebras that have a faithful tracial state.     

The Maximum Size of 3-Wise Intersecting and 3-Wise Union Families

Let be an n-uniform hypergraph on 2n vertices. Suppose that and holds for all F₁,F₂,F₃ ∈ . We prove that the size of is at most . The second author was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027     

2-universal -lattices over real quadratic fields

Let be a real quadratic field with m a square-free positive rational integer, and be the ring of integers in F. An -lattice L on a totally positive definite quadratic space V over F is called r-universal if L represents all totally positive definite -lattices l with rank r over . We prove that there exists no 2-universal -lattice over F with rank less than 6, and there exists a 2-universal -lattice over F with rank 6 if and only if m=2, 5. Moreover there exists only one 2-universal -lattice with rank 6, up to isometry, over .     

Constructions of Quad-Rooted Double Covers

A collection of spanning subgraphs of K_n is called an orthogonal double cover if (i) every edge of K_n belongs to exactly two of the G_is and (ii) any two distinct G_is intersect in exactly one edge. Chung and West [3] conjectured that there exists an orthogonal double cover of K_n for all n, in which each G_i has maximum degree 2, and proved this result for n in six of the residue classes modulo 12. In [6], Gronau, Mullin and Schellenberg solved the conjecture. In addition to solving the conjecture, they went on to consider a problem for n 5 mod 6 such that each spanning subgraph G_i consists of the vertex-disjoint union of an isolated vertex, a quadrilateral, and triangles. They proved that for any n 2 mod 3 and n {8, 11, 38, 41, 44, 47, 50, 53, 59, 62, 71, 83, 86, 89, 95, 101, 107, 113, 122, 131, 143, 146, 149, 158, 164, 167, 173, 176, 179, 218, 242, 248, 287}, there exists a quad-rooted double cover of order n. In this note, we improve their result by showing that such designs exist for any n 2 mod 3 and n {8, 11, 38, 41, 44, 50, 53, 62, 71}.     

On the Rellich inequality with magnetic potentials

In lectures given in 1953 at New York University, Franz Rellich proved that for all f∈C₀^∞(Rⁿ \{0}) and n≠2where the constant C(n):=n²(n−4)²/16 is sharp. For n=2 extra conditions were required for f, and for n=4, C(4)=0, producing a trivial inequality. Influenced by recent work of Laptev-Weidl on Hardy-type inequalities in R², the authors show that for n≥2, the inclusion of a magnetic field B=curl(A) of Aharonov-Bohm type yields non-trivial Rellich-type inequalities of the formwhere Δ_A=(∇−iA)² is the magnetic Laplacian. As in the Laptev-Weidl inequality, the constant C(n,α) depends upon the distance of the magnetic flux to the integers Z. When the flux is an integer and α=0, the inequalities reduce to Rellich’s inequality.The first author gratefully acknowledges the hospitality and support of the Mathematics Department at UAB where much of this work was done.     

Topologically transitive extensions of bounded operators

Let X be any Banach space and T a bounded operator on X. An extension of the pair (X,T) consists of a Banach space in which X embeds isometrically through an isometry i and a bounded operator on such that When X is separable, it is additionally required that be separable. We say that is a topologically transitive extension of (X, T) when is topologically transitive on , i.e. for every pair of non-empty open subsets of there exists an integer n such that is non-empty. We show that any such pair (X,T) admits a topologically transitive extension , and that when H is a Hilbert space, (H,T) admits a topologically transitive extension where is also a Hilbert space. We show that these extensions are indeed chaotic.Mathematics Subject Classification (2000): 47 A 16     

Asymptotic laws for regenerative compositions: gamma subordinators and the like

For a random closed set obtained by exponential transformation of the closed range of a subordinator, a regenerative composition of generic positive integer n is defined by recording the sizes of clusters of n uniform random points as they are separated by the points of . We focus on the number of parts K_n of the composition when is derived from a gamma subordinator. We prove logarithmic asymptotics of the moments and central limit theorems for K_n and other functionals of the composition such as the number of singletons, doubletons, etc. This study complements our previous work on asymptotics of these functionals when the tail of the Lévy measure is regularly varying at 0+. Research supported in part by N.S.F. Grant DMS-0071448     

On topological Kadec norms

We present a topological analogue of the classic Kadec Renorming Theorem, as follows. Let be two separable metric topologies on the same set X. We prove that every point in X has an -neighbourhood basis consisting of sets that are -closed if and only if there exists a function φ: X→ℝ that is -lower semi-continuous and such that is the weakest topology on X that contains and that makes φ continuous. An immediate corollary is that the class of almost n-dimensional spaces consists precisely of the graphs of lower semi-continuous functions with at most n-dimensional domains.     

Orthonormal rational function vectors

Summary In this paper, we develop a matrix framework to solve the problem of finding orthonormal rational function vectors with prescribed poles with respect to a certain discrete inner product that is defined by a set of data points and corresponding weight vectors w_i,j. Our algorithm for solving the problem is recursive, and it is of complexity If all data points are real or lie on the unit circle, then the complexity is reduced by an order of magnitude.     

On the gap between the quadratic integer programming problem and its semidefinite relaxation

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap We establish the uniqueness of the SDR solution and prove that if and only if γ_r:=n⁻¹max{x^TVV^Tx:x ∈ {-1, 1}ⁿ}=1 where V is an orthogonal matrix whose columns span the (r–dimensional) null space of D−Q and where D is the unique SDR solution. We also give a test for establishing whether that involves 2^r−1 function evaluations. In the case that γ_r<1 we derive an upper bound on γ which is tighter than Thus we show that `breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D−Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.