Empty convex polygons in almost convex sets

A finite set of points, in general position in the plane, is almost convex if every triple determines a triangle with at most one point in its interior. For every ℓ ≥ 3, we determine the maximum size of an almost convex set that does not contain the vertex set of an empty convex ℓ-gon. Partially supported by grants T043631 and NK67867 of the Hungarian NFSR (OTKA).     

There Exist Highly Critically Connected Graphs of Diameter Three

Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ. Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding 2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3.     

Group Representations with Empty Residual Spectrum

Let X be a Banach space on which a discrete group Γ acts by isometries. For certain natural choices of X, every element of the group algebra, when regarded as an operator on X, has empty residual spectrum. We show, for instance, that this occurs if X is ℓ ²(Γ) or the group von Neumann algebra VN(Γ). In our approach, we introduce the notion of a surjunctive pair, and develop some of the basic properties of this construction. The cases X = ℓ ^p (Γ) for 1 ≤ p < 2 or 2 < p < ∞ are more difficult. If Γ is amenable we can obtain partial results, using a majorization result of Herz; an example of Willis shows that some condition on Γ is necessary.     

The Number of Generalized Balanced Lines

Let S be a set of r red points and b=r+2δ blue points in general position in the plane, with δ≥0. A line ℓ determined by them is balanced if in each open half-plane bounded by ℓ the difference between the number of blue points and red points is δ. We show that every set S as above has at least r balanced lines. The proof is a refinement of the ideas and techniques of Pach and Pinchasi (Discrete Comput. Geom. 25:611–628, 2001), where the result for δ=0 was proven, and introduces a new technique: sliding rotations.     

Denting and strongly extreme points in the unit ball of spaces of operators

For 1 ≤p ≤ ∞ we show that there are no denting points in the unit ball of ℓ(l^p). This extends a result recently proved by Grząślewicz and Scherwentke whenp = 2 [GS1]. We also show that for any Banach spaceX and for any measure space (Ω, A, μ), the unit ball of ℓ(L ¹ (μ), X) has denting points iffL ¹(μ) is finite dimensional and the unit ball ofX has a denting point. We also exhibit other classes of Banach spacesX andY for which the unit ball of ℓ(X, Y) has no denting points. When X* has the extreme point intersection property, we show that all ‘nice’ operators in the unit ball of ℓ(X, Y) are strongly extreme points.     

Large almost monochromatic subsets in hypergraphs

We show that for all ℓ and ε > 0 there is a constant c = c(ℓ, ε) > 0 such that every ℓ-coloring of the triples of an N-element set contains a subset S of size $ c\sqrt {\log N} $ c\sqrt {\log N} such that at least 1 − ε fraction of the triples of S have the same color. This result is tight up to the constant c and answers an open question of Erdős and Hajnal from 1989 on discrepancy in hypergraphs. For ℓ ≥ 4 colors, it is known that there is an ℓ-coloring of the triples of an N-element set whose largest monochromatic subset has cardinality only Θ(log log N). Thus, our result demonstrates that the maximum almost monochromatic subset that an ℓ-coloring of the triples must contain is much larger than the corresponding monochromatic subset. This is in striking contrast with graphs, where these two quantities have the same order of magnitude. To prove our result, we obtain a new upper bound on the ℓ-color Ramsey numbers of complete multipartite 3-uniform hypergraphs, which answers another open question of Erdős and Hajnal.     

Isomorphic embeddings and harmonic behaviour of smooth operators

LetY be a Banach space, 1<p<∞. We give a simple criterion for embedding ℓ _p ⊂Y, namely it suffices that the positive cone ℓ _p ⁺ ⊂Y. This result is applied to the study of highly smooth operators from ℓ _p intoY (p is not an even integer). The main result is that every such operator has a harmonic behaviour unless ℓ _p/K ⊂Y for someK ∈ ℕ. Supported by grants GAUK 277/2001, GAČR 201-01-1198, A1019205.     

A new proof of Fréchet differentiability of Lipschitz functions

We give a relatively simple (self-contained) proof that every real-valued Lipschitz function on ℓ₂ (or more generally on an Asplund space) has points of Fréchet differentiability. Somewhat more generally, we show that a real-valued Lipschitz function on a separable Banach space has points of Fréchet differentiability provided that the w ^* closure of the set of its points of Gateaux differentiability is norm separable. Received May 31, 1999 / final version received February 16, 2000?Published online April 19, 2000     

Central units in salternative loop rings

Let L be an RA loop, that is, a loop whose loop ring in any characteristic is an alternative, but not associative, ring. We show that every central unit in the integral loop ring ZL is the product ℓμ₀ of an element ℓ ∈ L and a loop ring element μ₀ whose support is in the torsion subloop of L and use this result to determine when all central units of ZL are trivial. Received: 8 October 2004     

Lines Pinning Lines

A line ℓ is a transversal to a family F of convex polytopes in ℝ³ if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ³ such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.     

Classification of gradient space of dimension 8 by a reducible <Emphasis Type="Italic">s</Emphasis>ℓ(2, C) action

This paper deals with a reducible sℓ(2,C) action on the formal power series ring. The purpose of this paper is to confirm a special case of the Yau conjecture: Suppose that sℓ(2,C) acts on the formal power series ring via (1.1). Then I(f) = (ℓ _i1) ⊕ (ℓ _i2) ⊕... ⊕ (ℓ _is ) modulo some one dimensional sℓ(2,C) representations where (ℓ _i ) is an irreducible sℓ(2,C) representation of ℓ _i dimension and {ℓ _i1 ℓ _i2,...,ℓ _is } ⊆ {ℓ ₁ , ℓ ₂...,ℓ _r }. Unlike classical invariant theory which deals only with irreducible action and 1-dimensional representations, we treat the reducible action and higher dimensional representations successively.     

Noise sensitivity of Boolean functions and applications to percolation

It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on ann+1 byn grid. A configuration is a function that assigns to every edge the value 0 or 1. Let ω be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges ℓ with ω(ℓ)=1. By duality, the probability for having a crossing is 1/2. Fix an ɛ ∈ (0, 1). For each edge ℓ, let ω′(ℓ)=ω(ℓ) with probability 1 − ɛ, and ω′(ℓ)=1 − ω(ℓ) with probability ɛ, independently of the other edges. Letp(τ) be the probability for having a crossing in ω, conditioned on ω′ = τ. Then for alln sufficiently large,P{τ : |p(τ) − 1/2| > ɛ}<ɛ.     

Deductive systems of a cone algebra — II: Isomorphism theorem

We prove that there is an isomorphism φ of the lattice of deductive systems of a cone algebra onto the lattice of convex ℓ-subgroups of a lattice ordered group (determined by the cone algebra) such that for any deductive system A of the cone algebra, A is respectively a prime, normal or polar if and only if φ(A) is a prime convex ℓ-subgroup, ℓ-ideal or polar subgroup of the ℓ-group, thus generalizing and extending the result of Rachůnek that the lattice of ideals of a pseudo MV-algebra is isomorphic to the lattice of convex ℓ-subgroups of a unital lattice ordered group.      

Perfect residuated lattice ordered monoids

Bounded Rℓ-monoids form a large subclass of the class of residuated lattices which contains certain of algebras of fuzzy and intuitionistic logics, such as GMV-algebras (= pseudo-MV-algebras), pseudo-BL-algebras and Heyting algebras. Moreover, GMV-algebras and pseudo-BL-algebras can be recognized as special kinds of pseudo-MV-effect algebras and pseudo-weak MV-effect algebras, i.e., as algebras of some quantum logics. In the paper, bipartite, local and perfect Rℓ-monoids are investigated and it is shown that every good perfect Rℓ-monoid has a state (= an analogue of probability measure).     

Vive la différence III

We show that, consistently, there is an ultrafilter on ω such that if N _n^ℓ = (P _n^ℓ ∪ Q _n^ℓ, P _n^ℓ, Q _n^ℓ, R _n^ℓ) (for ℓ = 1, 2, n < ω), P _n^ℓ ∪ Q _n^ℓ ⊆ ω, and are models of the canonical theory t ^ind of the strong independence property, then every isomorphism from onto is a product isomorphism. The first version of this work done in 93; First typed: May 1993. This research was partially supported by the United States-Israel Binational Science Foundation. Publication 509     

Weak* Hypercyclicity and Supercyclicity of Shifts on ℓ∞

We study hypercyclicity and supercyclicity of weighted shifts on ℓ^∞, with respect to the weak * topology. We show that there exist bilateral shifts that are weak * hypercyclic but fail to be weak * sequentially hypercyclic. In the unilateral case, a shift T is weak * hypercyclic if and only if it is weak * sequentially hypercyclic, and this is equivalent to T being either norm, weak, or weak-sequentially hypercyclic on c₀ or ℓ^p (1 ≤ p < ∞). We also show that the set of weak * hypercyclic vectors of any unilateral or bilateral shift on ℓ^∞ is norm nowhere dense. Finally, we show that ℓ^∞ supports an isometry that is weak * sequentially supercyclic.     

The inclusion of the Schur algebra in B(?2) is not inverse-closed

The Schur algebra is the algebra of operators which are bounded on ℓ ¹ and on ℓ ^∞. In this note, we exhibit an element of the group algebra of the free group with two generators, which, as a convolution operator, is invertible in ℓ ², and whose inverse is not bounded on ℓ ¹ nor on ℓ ^∞. In particular, this shows that the Schur algebra is not inverse-closed.     

The configuration polytope of ℓ-line configurations in Steiner triple systems

It has been shown that the number of occurrences of any ℓ-line configuration in a Steiner triple system can be written as a linear combination of the numbers of full m-line configurations for 1 ≤ m ≤ ℓ; full means that every point has degree at least two. More precisely, the coefficients of the linear combination are ratios of polynomials in v, the order of the Steiner triple system. Moreover, the counts of full configurations, together with v, form a linear basis for all of the configuration counts when ℓ ≤ 7. By relaxing the linear integer equalities to fractional inequalities, a configuration polytope is defined that captures all feasible assignments of counts to the full configurations. An effective procedure for determining this polytope is developed and applied when ℓ = 6. Using this, minimum and maximum counts of each configuration are examined, and consequences for the simultaneous avoidance of sets of configurations explored. To Alex Rosa on the Occasion of his Seventieth Birthday     

Low dimensional sections versus projections of convex bodies

The structure of low dimensional sections and projections of symmetric convex bodies is studied. For a symmetric convex bodyB ⊂ ℝ ⁿ , inequalities between the smallest diameter of rank ℓ projections ofB and the largest in-radius ofm-dimensional sections ofB are established, for a wide range of sub-proportional dimensions. As an application it is shown that every bodyB in (isomorphic) ℓ-position admits a well-bounded (√n, 1)-mixing operator. Research of this author was partially supported by KBN Grant no. 1 P03A 015 27. This author holds the Canada Research Chair in Geometric Analysis.     

A homological characterization of hyperbolic groups

A finitely presented group G is hyperbolic iff H ⁽¹⁾ ₁(G,ℝ)=0=⁽¹⁾ ₂(G, ℝ), where H ⁽¹⁾ _* (resp. ⁽¹⁾ _*) denotes the ℓ₁-homology (resp. reduced ℓ₁-homology). If Γ is a graph, then every ℓ₁ 1-cycle in Γ with real coefficients can be approximated by 1-cycles of compact support. A 1-relator group G is hyperbolic iff H ⁽¹⁾ ₁(G,ℝ)=0. Oblatum: 30-IV-1997 & 14-V-1998 / Published online: 14 January 1999