Ancestor tree for arbitrary multi-terminal cut functions

In many applications, a function is defined on the cuts of a network. In the max-flow min-cut theorem, the function on a cut is simply the sum of all capacities of edges across the cut, and we want the minimum value of a cut separating a given pair of nodes. To find the minimum cuts separating pairs of nodes, we only needn – 1 computations to construct the cut-tree. In general, we can define arbitrary values associated with all cuts in a network, and assume that there is a routine which gives the minimum cut separating a pair of nodes. To find the minimum cuts separating pairs of nodes, we also only needn – 1 routine calls to construct a binary tree which gives all minimum partitions. The binary tree is analogous to the cut-tree of Gomory and Hu.     

Riesz Idempotent and Weyl’s Theorem for w-hyponormal Operators

Let T be a w-hyponormal operator on a Hilbert space H, its Aluthge transform, λ an isolated point of the spectrum of T, and E_λ and the Riesz idempotents, with respect to λ, of T and respectively. It is shown that Consequently, E_λ is self-adjoint, and if λ ≠ 0. Moreover, it is shown that Weyl’s theorem holds for f(T), where f ∈ H(σ (T)).     

Spectra of Composition Operators on BMOA

It is shown that if ϕ is a univalent self-map on the unit disk is not an automorphism and has a fixed point in and if the essential spectral radius of the composition operator C_ϕ on H² is different from zero, then the spectrum of C_ϕ on BMOA coincides with This answers in the affirmative a conjecture by MacCluer and Saxe.     

On Linear Codes over $${\mathbb{Z}}_{2^{s}}$$

In an earlier paper the authors studied simplex codes of type α and β over and obtained some known binary linear and nonlinear codes as Gray images of these codes. In this correspondence, we study weight distributions of simplex codes of type α and β over The generalized Gray map is then used to construct binary codes. The linear codes meet the Griesmer bound and a few non-linear codes are obtained that meet the Plotkin/Johnson bound. We also give the weight hierarchies of the first order Reed-Muller codes over The above codes are also shown to satisfy the chain condition.A part of this paper is contained in his Ph.D. Thesis from IIT Kanpur, India     

Dynamics of the Mapping Class Group on the Moduli of a Punctured Sphere with Rational Holonomy

Let M be a four-holed sphere and Γ the mapping class group of M fixing the boundary ∂M. The group Γ acts on which is the space of completely reducible SL (2, -gauge equivalence classes of flat SL -connections on M with fixed holonomy on ∂M. Let and be the compact component of the real points of . These points correspond to SU(2)-representations or SL(2, -representations. The Γ-action preserves and we study the topological dynamics of the Γ-action on and show that for a dense set of holonomy , the Γ-orbits are dense in . We also produce a class of representations such that the Γ-orbit of [ρ] is finite in the compact component of , but is dense in SL(2, .Mathematics Subject Classiffications (2000). 57M05, 54H20, 11D99     

Schiffer’s Problem and an Isoperimetric Inequality for the First Buckling Eigenvalue of Domains on $$\mathbb{S}^{2}$$

We consider the overdetermined eigenvalue problem on a sufficiently regular connected open domain Ω on the 2-sphere :

On Some Sets with Even Valued Partition Function

Let IN be the set of positive integers, = {b₁ < ⋅s < b_h}⊂IN, N∊IN and N≥ b_h. = ₀( ,N) is the set (introduced by J.-L. Nicolas, I.Z. Ruzsa and A. Sárközy) such that {1,..., N} = and p( ,n)≡ 0 (mod 2) for n∊IN and n > N, where p( ,n) denotes the number of partitions of n with parts in . Let us denote by σ ( ,n) the sum of the divisors of n belonging to . In a paper jointly written with J.-L. Nicolas, we have recently proved that, for all k≥ 0, the sequence (σ( ,2^k n))_{n≥ 1}mod 2^k+1 is periodic with an odd period q_k. In this paper, we will characterize for any fixed odd positive integer q, the sets and the integers N such that q₀ = q, and those for which q_k = q for all k≥ 0. Moreover, a set = ₀( ,N) is constructed with the property that its period, i.e. the period of (σ( ,n))_{n≥ 1}mod 2, is 217, and for which the counting function is asymptotically equal to that of ₀({1,2,3,4,5},5) which is a set of period 31.Dedicated to Professor J.-L. Nicolas on the occasion of his 60th birthday2000 Mathematics Subject Classification: Primary—11P81, 11P83Research supported by MIRA 2002 program n^o 0203012701, Number Theory, Lyon-Monastir.     

Group Pairs with Property (T), from Arithmetic Lattices

Let Γ be an arithmetic lattice in an absolutely simple Lie group G with trivial centre. We prove that there exists an integer N ≥ 2, a subgroup Λ of finite index in Γ, and an action of Λ on such that the pair ( ) has property (T). If G has property (T), then so does . If G is the adjoint group of Sp(n, 1), then is a property (T) group satisfying the Baum–Connes conjecture. If Γ is an arithmetic lattice in SO(n, 1), then the associated von Neumann algebra is a II₁-factor in Popa’s class . Elaborating on this result of Popa, we construct a countable family of pairwise nonstably isomorphic group II₁-factors in the class , all with trivial fundamental groups and with all L²-Betti numbers being zero.Mathematics Subject Classiffications (2000). 22E40, 22E47, 46L80, 37A20     

Surfaces with many solitary points

It is classically known that a real cubic surface in cannot have more than one solitary point (or -singularity, locally given by x ² + y ² + z ² = 0) whereas it can have up to four nodes (or -singularity, locally given by x ² + y ² − z ² = 0). We show that on any surface of degree d ≥ 3 in the maximum possible number of solitary points is strictly smaller than the maximum possible number of nodes. Conversely, we adapt a construction of Chmutov to obtain surfaces with many solitary points by using a refined version of Brusotti’s Theorem. Combining lower and upper bounds, we deduce: , where denotes the maximum possible number of solitary points on a real surface of degree d in . Finally, we adapt this construction to get real algebraic surfaces in with many singular points of type for all k ≥ 1.      

Modified Alternating $$\vec{k}$$–generators

This paper deals with a class of pseudorandom bit generators – modified alternating –generators. This class is constructed similarly to the class of alternating step generators. Three subclasses of are distinguished, namely linear, mixed and nonlinear generators. The main attention is devoted to the subclass of linear and mixed generators generating periodic sequences with maximal period lengths. A necessary and sufficient condition for all sequences generated by the linear generators of to be with maximal period lengths is formulated. Such sequences have good statistical properties, such as distribution of zeroes and ones, and large linear complexity. Two methods of cryptanalysis of the proposed generators are given. Finally, three new classes of modified alternating –generators, designed especially to be more secure, are presented.     

Metric Geometry in Homogeneous Spaces of the Unitary Group of a C*-Algebra. Part II. Geodesics Joining Fixed Endpoints

This article focuses on the study of the metric geometry of homogeneous spaces (the unitary group of a C*-algebra modulo the unitary group of a C*-subalgebra ) where the invariant Finsler metric in is induced by the quotient norm of Under the assumption that is of compact type, i.e. when the unitary group is relatively compact in the strong operator topology, this work presents local and global versions of Hopf-Rinow-like theorems: given points there exists a minimal uniparametric group curve joining ρ₀ and ρ₁.     

Solution of the Truncated Hyperbolic Moment Problem

Let Q(x, y) = 0 be an hyperbola in the plane. Given real numbers β ≡ β ⁽²ⁿ⁾={ β _ij } _{i,j ≥ 0,i+j ≤ 2n} , with β₀₀ > 0, the truncated Q-hyperbolic moment problem for β entails finding necessary and sufficient conditions for the existence of a positive Borel measure μ, supported in Q(x, y) = 0, such that We prove that β admits a Q-representing measure μ (as above) if and only if the associated moment matrix is positive semidefinite, recursively generated, has a column relation Q(X,Y) = 0, and the algebraic variety associated to β satisfies card In this case, if then β admits a rank -atomic (minimal) Q-representing measure; if then β admits a Q-representing measure μ satisfying      

Local Schur’s Lemma and Commutative Semifields

A set of linear maps , V a finite vector space over a field K, is regular if to each there corresponds a unique element such that R(x)=y. In this context, Schur’s lemma implies that is a field if (and only if) it consists of pairwise commuting elements. We consider when is locally commutative: at some μ ∈V*, AB(μ)=BA(μ) for all , and has been normalized to contain the identity. We show that such locally commutative are equivalent to commutative semifields, generalizing a result of Ganley, and hence characterizing commutative semifield spreads within the class of translation planes. This enables the determination of the orders |V| for which all locally commutative on V are (globally) commutative. Similarly, we determine a sharp upperbound for the maximum size of the Schur kernel associated with strictly locally commutative . We apply our main result to demonstrate the existence of a partial spread of degree 5, with nominated shears axis, that cannot be extend to a commutative semifield spread. Finally, we note that although local commutativity for a regular linear set implies that the set of Lie products consists entirely of singular maps, the converse is false.     

The Quasiapproximate $(\mathcal{U} + \mathcal{K})$ –Invariants of Essentially Normal Operators

For a class of essentially normal operators, we characterize their norm closures of –orbits. Moreover, we introduce a notion of the quasiapproximate – equivalence of essentially normal operators and determine completely the quasiapproximate –invariants. Finally, we give the canonical forms of essentially normal operators under this quasiapproximate –equivalence.     

The Cosserat eigenfunctions for the elliptic exterior problem with applications to thermoelasticity and Stokes flow

The Cosserat eigenvalue problem for the elliptic exterior is considered. It is shown that the only Cosserat eigenvalue different from the infinite multiple eigenvalues and is which also has an infinite multiplicity. The orthogonal basis of the eigenspace corresponding to is constructed. Application to thermoelasticity and Stokes flow – extensional and shear – past a rigid elliptical cylinder are presented and agreement is obtained with classical solutions for a circle. The fact that the solutions consist of only two eigenfunctions reveals the efficiency of the method.Received: February 27, 2003     

A Szemerédi-type regularity lemma in abelian groups, with applications

Szemerédi’s regularity lemma is an important tool in graph theory which has applications throughout combinatorics. In this paper we prove an analogue of Szemerédi’s regularity lemma in the context of abelian groups and use it to derive some results in additive number theory. One is a structure theorem for sets which are almost sum-free. If has δ N² triples (a₁, a₂, a₃) for which a₁ + a₂ = a₃ then A = B ∪ C, where B is sum-free and |C| = δ′N, and as Another answers a question of Bergelson, Host and Kra. If 0,$$" align="middle" border="0"> if \,N_{0}(\alpha, \epsilon)$$" align="middle" border="0"> and if has size α N, then there is some d ≠ 0 such that A contains at least three-term arithmetic progressions with common difference d.Received: November 2003 Revision: October 2004 Accepted: December 2004     

Infinite independent sets in distributive lattices

We show that a poset P contains a subset isomorphic to if and only if the poset J(P) consisting of ideals of P contains a subset isomorphic to the power set of κ. If P is a join-semilattice this amounts to the fact that P contains an independent set of size κ. We show that if κ := ω and P is a distributive lattice, then this amounts to the fact that P contains either or as sublattices, where Γ and Δ are two special meet-semilattices already considered by J. D. Lawson, M. Mislove and H. A. Priestley.Dedicated to the memory of Ivan RivalReceived April 22, 2003; accepted in final form July 11, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Navigating in the Cayley Graphs of {\rm SL}_{N}(\mathbb{Z}) and {\rm SL}_{N}(\mathbb{F}_{p})

We give a nondeterministic algorithm that expresses elements of , for N ≥ 3, as words in a finite set of generators, with the length of these words at most a constant times the word metric. We show that the nondeterministic time-complexity of the subtractive version of Euclid’s algorithm for finding the greatest common divisor of N ≥ 3 integers a₁, ..., a_N is at most a constant times . This leads to an elementary proof that for N ≥ 3 the word metric in is biLipschitz equivalent to the logarithm of the matrix norm – an instance of a theorem of Mozes, Lubotzky and Raghunathan. And we show constructively that there exists K>0 such that for all N ≥ 3 and primes p, the diameter of the Cayley graph of with respect to the generating set is at most .Mathematics Subject Classification: 20F05     

Minimum-Volume Enclosing Ellipsoids and Core Sets

We study the problem of computing a (1+ε)-approximation to the minimum-volume enclosing ellipsoid of a given point set . Based on a simple, initial volume approximation method, we propose a modification of the Khachiyan first-order algorithm. Our analysis leads to a slightly improved complexity bound of operations for . As a byproduct, our algorithm returns a core set with the property that the minimum-volume enclosing ellipsoid of provides a good approximation to that of . Furthermore, the size of depends on only the dimension d and ε, but not on the number of points n. In particular, our results imply that for .We thank the Associate Editor and an anonymous referee for handling our paper efficiently and for helpful comments and suggestions.This author was supported in part by NSF through Grant CCR-0098172.This author was supported in part by NSF through CAREER Grant DMI-0237415.     

Approximation of Continuous Functions by de La Vallee-Poussin Operators

We study the asymptotic (as σ → ∞) behavior of upper bounds of the deviations of functions belonging to the classes and from the so-called de la Vallee-Poussin operators. We obtain asymptotic equalities that, in some important cases, give a solution of the Kolmogorov-Nikol’skii problem for the de la Vallee-Poussin operators on the classes and .__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 2, pp. 230–238, February, 2005.