The Ramsey property for collections of sequences not containing all arithmetic progressions

A family of sequences has the Ramsey property if for every positive integerk, there exists a least positive integerf (k) such that for every 2-coloring of {1,2, ...,f (k)} there is a monochromatick-term member of . For fixed integersm > 1 and 0 q < m, let _q(m) be the collection of those increasing sequences of positive integers {x ₁,..., x_k} such thatx _i+1 – x_i q(modm) for 1 i k – 1. Fort a fixed positive integer, denote byA _t the collection of those arithmetic progressions having constant differencet. Landman and Long showed that for allm 2 and 1 q < m, _q(m) does not have the Ramsey property, while _q(m) A _m does. We extend these results to various finite unions of _q(m) 's andA _t 's. We show that for allm 2, _q=1 ^m–1 _q(m) does not have the Ramsey property. We give necessary and sufficient conditions for collections of the form _q(m) ( _{t T} A _t) to have the Ramsey property. We determine when collections of the form _a(m₁) _b(m₂) have the Ramsey property. We extend this to the study of arbitrary finite unions of _q(m)'s. In all cases considered for which has the Ramsey property, upper bounds are given forf .     

Maximal Classes of Topological Spaces and Domains Determined by Function Spaces

In this paper the question of what classes A of T ₀-spaces should be paired with classes of domains in order that all function spaces [AB] for AA and B are -compact domains is considered. It is shown that core compact spaces are paired with bounded complete domains and a class of topological spaces called RW-spaces (with finitely many components) is paired with the class of -compact pointed L-domains (L-domains).     

A Lévy Type Martingale Convergence Theorem for Random Sets with Unbounded Values

Given a nondecreasing sequence ( _n ) of sub--fields and a real or vector valued random variable f, the Lévy Martingale convergence Theorem (LMCT) asserts that E(f/ _n ) converges to E(f/) almost surely and in L ¹, where stands for the -field generated by the _n . In the present paper, we study the validity of the multivalued analog this theorem for a random set F whose values are members of (X), the space of nonempty closed sets of a Banach space X, when (X) is endowed either with the Painlevé–Kuratowski convergence or its infinite dimensional extensions. We deduce epi-convergence results for integrands via the epigraphical multifunctions. As it is known, these results are useful for approximating optimization problems. The method relies on countability supportness hypotheses which are shown to hold when the values of the random set E(F/ _n ) do not contain any line. On the other hand, since the values of F are not assumed to be bounded, conditions involving barrier and asymptotic cones are shown to be necessary. Moreover, we discuss the relations with other multivalued martingale convergence theorems and provide examples showing the role of the hypotheses. Even in the finite dimensional setting, our results are new or subsume already existing ones.     

Target-Oriented Branch and Bound Method for Global Optimization

We introduce a very simple but efficient idea for branch and bound (&) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new & approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used & techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical & techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method.     

Self-Converse Directed BIBDs with Block Size Four

A directed balanced incomplete block design (or D B(k,;v)) (X,) is called self-converse if there is an isomorphic mapping f from (X,) to (X,^–1), where ^–1={B ^–1:B} and B ^–1=(x _k ,x _{k –1},,x ₂,x ₁) for B=(x ₁,x ₂,,x _{k –1},x _k ). In this paper, we give the existence spectrum for self-converse D B(4,1;v). AMS Classification:05BResearch supported in part by NSFC Grant 10071002 and SRFDP under No. 20010004001     

Semimodular lattices with isomorphic graphs

Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik.     

On the asymptotic and invariantσ-algebras of random walks on locally compact groups

Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , ^a ,Q) andL (G , ⁱ ,Q) where ^a and ⁱ stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , ^a ,Q) L (G , ⁱ ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers ⁿ.     

Almost Covers Of 2-Arc Transitive Graphs

Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case K _v+1 is covered by results of Gardiner and Praeger. We consider here the general case where K _v+1, and prove that, for some even integer n 4, is a near n-gonal graph with respect to a certain G-orbit on n-cycles of . Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .)     

On semiregular conditional distributions

Let (,A,P) denote some probability space and some sub--algebra ofA. It is shown that there exists a semiregular versionQ (A),A, , of the conditional distributionP(A|), AA, i.e., Q (A), (AA fixed) is andAQ (A),AA ( fixed), is a probability charge satisfyingQ (N)=0, , for allP-zero setsN, if and only ifL ₁(,P|) has a lifting, which exists for any sub--algebra ofA ifL ₁(,A P) is separable. Separability ofL ₁(,A,P) implies also the existence of a strongly semiregular versionQ (A),A, , ofP(A|), A , i.e., Q (A), (AA fixed), is -measurable andAQ (A),A ( fixed), is a probability charge. Furthermore,P can be written as P ₁+(1–)P ₂, 01, whereP ₁ are probability measures onA such thatP ₁(A|),AA, has a semiregular version vanishing for anyP-zero setN andP ₂ is singular with respect to any probability measure onA of the type ofP ₁. In the case 0<<1 the probability measuresP _j ,j=1, 2, are uniquely determined. The decomposition can be carried over to the case, where the additional condition thatQ (N)=0 for all and anyP-zero setN is valid, is omitted respectively semiregularity is replaced by (i) strong semiregularity, or (ii) classical regularity. In the last mentioned case (ii) the decomposition is multiplicative.     

Bijectivity of -endomorphisms of ℬ(H) and the unilateral shift

LetH be a separable infinite-dimensional complex Hilbert space. We prove that if : (H)(H) is a^*-preserving ring homomorphism whose range contains a rank-one operator and an operator with dense range, then is an isometric linear or conjugate-linear algebra automorphism of (H). In particular, if the unilateral shift is contained in the range of a^*-endomorphism of (H), then is bijective.Research partially supported by the Hungarian National Research Science Foundation, Operating Grant Number OTKA 1652 and K&H Bank Ltd., Universitas Foundation.     

Extremal Properties of Bases for Representations of Semisimple Lie Algebras

Let be a complex semisimple Lie algebra with specified Chevalley generators. Let V be a finite dimensional representation of with weight basis . The supporting graph P of is defined to be the directed graph whose vertices are the elements of and whose colored edges describe the supports of the actions of the Chevalley generators on V. Four properties of weight bases are introduced in this setting, and several families of representations are shown to have weight bases which have or are conjectured to have each of the four properties. The basis can be determined to be edge-minimizing (respectively, edge-minimal) by comparing P to the supporting graphs of other weight bases of V. The basis is solitary if it is the only basis (up to scalar changes) which has P as its supporting graph. The basis is a modular lattice basis if P is the Hasse diagram of a modular lattice. The Gelfand-Tsetlin bases for the irreducible representations of sl(n, ) serve as the prototypes for the weight bases sought in this paper. These bases, as well as weight bases for the fundamental representations of sp(2n, ) and the irreducible one-dimensional weight space representations of any semisimple Lie algebra, are shown to be solitary and edge-minimal and to have modular lattice supports. Tools developed here are used to construct uniformly the irreducible one-dimensional weight space representations. Similar results for certain irreducible representations of the odd orthogonal Lie algebra o(2n + 1, ), the exceptional Lie algebra G ₂, and for the adjoint and short adjoint representations of the simple Lie algebras are announced.     

Nuclei of point sets of sizeq+1 contained in the union of two lines inPG(2,q)

We give a complete classification for pairs ( (),) where () is the set of all nuclei of a set ofq+1 not collinear points contained in the union of two lines in a desarguesian planePG(2,q) of orderq. We also obtain some new results concerning blocking sets of Rédei type and certain point-sets of type [0,1,m,n] inPG(2, q).     

When Is a Subspace of B(H) Ideal?

Let be a real or complex Hilbert space and let () denote the algebra of all bounded linear operators on . We show that if N is a subspace of (H) and for positive operators P₁, P₂ and every A N, P₁P₂A^* + AP₁P₂ N then N is an ideal. Furthermore if is an infinite dimensional real space then N = (H).AMS Subject Classification (1991): Primary 47B47, 47D25     

Homotopy Classification of Categorical Torsors

The long-known results of Schreier on group extensions are here raised to a categorical level by giving a factor set theory for torsors under a categorical group (G,) over a small category . We show a natural bijection between the set of equivalence classes of such torsors and [B({}),B(G,)], the set of homotopy classes of continuous maps between the corresponding classifying spaces. These results are applied to algebraically interpret the set of homotopy classes of maps from a CW-complex X to a path-connected CW-complex Y with _i (Y)=0 for all i1,2.     

On the K0 groups of nest algebras

In this paper we compute the K ₀ group of any nest subalgebra of ().     

Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

Fenchel-type duality for matroid valuations

The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroidsM _i = (V, _i , _i ) (i = 1,2) defined on a common ground setV, find a common baseB _{1 2} that maximizes ₁ (B) + ₂ (B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Part of this paper has been presented at fifth SIAM Conference on Optimization, Victoria, May 1996.This work was done while the author was at Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 1994–1995.     

Explicit matchings in the middle levels of the Boolean lattice

New classes of explicit matchings for the bipartite graph (k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that (k) is Hamiltonian.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8041281.     

2-designs overGF(2 m )

At – (n, k, ; q) design is a collection ofk-dimensional subspaces of ann-dimensional vector space overGF(q) with the property that anyt-dimensional subspace is contained in exactly members of . It is also called a design over a finite field or aq-analoguet-design. The first nontrivial example fort 2 was given by S. Thomas. Namely, he constructed a series of 2 – (n, 3, 7; 2) design for alln 7 satisfying (n, 6) = 1. Under the same restriction onn, we show that the base field of Thomas' design is extensible toGF(2 ^m ), i.e., we construct a 2 – (n, 3, 2^2m + 2 ^m + 1; 2 ^m ) design for allm 1.Dedicated to Professor Tuyosi Oyama on his 60th Birthday     

Finite uniform generators for ergodic,finite entropy,free actions of amenable groups

Summary Let (X) be a Lebesgue space. We prove in the first part of this paper that any ergodic ²-action on (X) with finite entropy hLogk has generating partition P that is uniform and has k atoms. In the second part, we prove a similar result for any ergodic, free G-action with finite entropy hLog(k-2), for any discrete amenable group G.