Der Satz von Tits für PGL2(R), R ein kommutativer Ring vom stabilen Rang 2

Certain permutation groups on sets with distance relation are characterized as groups of projectivities PGL₂(R) on the projective line over a commutative ring R of stable rank 2, thus generalizing a classical result of Tits where R is a field.

     

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.     

On the number of vertices and edges of the Buneman graph

In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splitsS, the vertices of the Buneman graph correspond precisely to the subsetsS′ ofS such that the splits inS′ are pairwise incompatible and the edges correspond to pairs (S′, S) withS′ as above andS∈S′. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits inS are compatible.     

Projective representations i. projective lines over rings

We discuss representations of the projective line over a ringR with 1 in a projective space over some (not necessarily commutative) fieldK. Such a representation is based upon a (K, R)-bimoduleU. The points of the projective line overR are represented by certain subspaces of the projective space ℙ(K, U ×U) that are isomorphic to one of their complements. In particular, distant points go over to complementary subspaces, but in certain cases, also non-distant points may have complementary images.     

Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

Incidence and Combinatorial Properties of Linear Complexes

In this paper a generalisation of the notion of polarity is exhibited which allows to completely describe, in an incidence-geometric way, the linear complexes of h-subspaces. A generalised polarity is defined to be a partial map which maps (h−1)-subspaces to hyperplanes, satisfying suitable linearity and reciprocity properties. Generalised polarities with the null property give rise to linear complexes and vice versa. Given that there exists for h > 1 a linear complex of h-subspaces which contains no star – this seems to be an open problem over an arbitrary ground field – the combinatorial structure of a partition of the line set of the projective space into non-geometric spreads of its hyperplanes can be obtained. This line partition has an additional linearity property which turns out to be characteristic. Received: December 3, 2007. Revised: December 13, 2007.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Symmetric designs with bruck subdesigns

IfP is a finite projective plane of ordern with a proper subplaneQ of orderm which is not a Baer subplane, then a theorem of Bruck [Trans. AMS 78(1955), 464–481] asserts thatn≧m ²+m. If the equalityn=m ²+m were to occur thenP would be of composite order andQ should be called a Bruck subplane. It can be shown that if a projective planeP contains a Bruck subplaneQ, then in factP contains a designQ′ which has the parameters of the lines in a three dimensional projective geometry of orderm. A well known scheme of Bruck suggests using such aQ′ to constructP. Bruck’s theorem readily extends to symmetric designs [Kantor, Trans. AMS 146 (1969), 1–28], hence the concept of a Bruck subdesign. This paper develops the analoque ofQ′ and shows (by example) that the analogous construction scheme can be used to find symmetric designs.     

Intersection theorems with geometric consequences

In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ₀, μ₁, ..., μ_s are distinct residues modp (p is a prime) such thatk ≡ μ₀ (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μ_i (modp) for somei, 1 ≦i≦s, then |ℱ|≦( _s ⁿ ). As a consequence we show that ifR ⁿ is covered bym sets withm<(1+o(1)) (1.2) ⁿ then there is one set within which all the distances are realised. It is left open whether the same conclusion holds for compositep.     

How many s-subspaces must miss a point set in PG(d, q)

The following result is well-known for finite projective spaces. The smallest cardinality of a set of points of PG(n, q) with the property that every s-subspace has a point in the set is (q ^n+1-s - 1)/(q - 1). We solve in finite projective spaces PG(n, q) the following problem. Given integers s and b with 0 ≤ s ≤ n - 1 and 1 ≤ b ≤ (q ^n+1-s - 1)/(q - 1), what is the smallest number of s-subspaces that must miss a set of b points. If d is the smallest integer such that b ≤ (q ^d+1 - 1)/(q - 1), then we shall see that the smallest number is obtained only when the b points generate a subspace of dimension d. We then also determine the smallest number of s-subspaces that must miss a set of b points of PG(n, q) which do not lie together in a subspace of dimension d. The results are obtained by geometrical and combinatorial arguments that rely on a strong algebraic result for projective planes by T. Szőnyi and Z. Weiner.     

Polynomial-time computation of the degree of a dominant morphism in zero characteristic. II

Consider a projective algebraic variety W which is an irreducible component of the set of all common zeros of a family of homogeneous polynomials of degrees less than d in n + 1 variables over a field of zero characteristic. Consider a dominant rational morphism from W to W′ given by homogeneous polynomials of degree d′. We suggest algorithms for constructing objects in general position related to this morphism. They generalize some algorithms from the first part of the paper to the case dim W > dim W′. These algorithms are deterministic and polynomial in (dd′)n and the size of the input. Bibliography: 12 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 325, 2005, pp. 181–224.     

Harmonic Functions on Homogeneous Spaces

 Given a locally compact group G acting on a locally compact space X and a probability measure σ on G, a real Borel function f on X is called σ-harmonic if it satisfies the convolution equation . We give conditions for the absence of nonconstant bounded harmonic functions. We show that, if G is a union of σ-admissible neighbourhoods of the identity, relative to X, then every bounded σ-harmonic function on X is constant. Consequently, for spread out σ, the bounded σ-harmonic functions are constant on each connected component of a [SIN]-group and, if G acts strictly transitively on a splittable metric space X, then the bounded σ-harmonic functions on X are constant which extends Furstenberg’s result for connected semisimple Lie groups. (Received 13 June 1998; in revised form 31 March 1999)     

Realisierungen des idealen Randes einer Riemannschen Fläche unter konformen Abschließungen

Let a noncompact Riemann surface R of positive finite genus g be given. If f : R → R′ is a conformal mapping of R into a compact Riemann surface R′ of genus g, we have a realization of the ideal boundary of R on the surface R′. We consider (for the fixed R) all the possible R′ and the associated conformal mappings, and study how large the realized boundary can be. To this aim we pass to the (common) universal space ℂ ^g of the Jacobi variety of any R′ and show that the image sets of the ideal boundary of R in ℂ ^g are uniformly bounded.

     

Polynomial-Time Computation of the Degree of a Dominant Morphism in Characteristic Zero. I

Consider a projective algebraic variety W that is an irreducible component of the set of all common zeros of a family of homogeneous polynomials of degrees less than d in n + 1 variables over the field of characteristic zero. We show how to compute the degree of a dominant rational morphism from W to W′. The morphism is given by homogeneous polynomials of degree d′.This algorithms is deterministic and polynomial in (dd′)ⁿ and the size of the input. Bibliography: 11 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 307, 2003, pp. 189–235.     

Faulkner geometry

Axioms are presented for a Barbilian geometry of dimension n2 over a ring for which ab=1 implies ba=1. It is shown that any Faulkner geometry of dimension n3 is coordinatized by a unique associative two-sided units ring R and that the group generated by all transvections is a group of Steinberg type over R.     

On smallest covers of finite projective spaces

A t-cover of a finite projective space ℙ is a set of t-dimensional subspaces covering all points of ℙ. Beutelspacher [1] constructed examples of t-covers and proved that his examples are of minimal cardinality. We shall show that all examples of minimal cardinality “look like” the examples of Beutelspacher.     

Variétés Galois-maximales et éclatements

 Let X and X^′ be irreducible projective nonsingular algebraic varieties over R. We suppose that X is obtained from X^′ by a finite sequence of blow-ups and blow-downs along nonsingular centers and that all these centers are GM-varieties. Then we show that X is a GM-variety if and only if X^′ is a GM-variety. Receivded: 3 June 2002 / Revised version: 4 November 2002 Published online: 3 March 2003     

On the lattice property of the plane and some problems of Dirac,Motzkin and Erdős in combinatorial geometry

LetS be a set ofn non-collinear points in the Euclidean plane. It will be shown here that for some point ofS the number ofconnecting lines through it exceedsc · n. This gives a partial solution to an old problem of Dirac and Motzkin. We also prove the following conjecture of Erdős: If any straight line contains at mostn−x points ofS, then the number of connecting lines determined byS is greater thanc · x · n. Dedicated to Paul Erdős on his seventieth birthday     

Roth’s estimate of the discrepancy of integer sequences is nearly sharp

Letg be a coloring of the set {1, ...,N} = [1,N] in red and blue. For each arithmetic progressionA in [1,N], consider the absolute value of the difference of the numbers of red and of blue members ofA. LetR(g) be the maximum of this number over all arithmetic progression (thediscrepancy ofg). Set over all two-coloringsg. A remarkable result of K. F. Roth gives*R(N)≫N ^1/4. On the other hand, Roth observed thatR(N)≪N ^1/3+ɛ and suggested that this bound was nearly sharp. A. Sárk?zy disproved this by provingR(N)≪N ^1/3+ɛ. We prove thatR(N)=N ^1/4+o(1) thus showing that Roth’s original lower bound was essentially best possible. Our result is more general. We introduce the notion ofdiscrepancy of hypergraphs and derive an upper bound from which the above result follows.     

Gorenstein projective dimensions of complexes

We show that over a right coherent left perfect ring R, a complex C of left R-modules is Gorenstein projective if and only if C ^m is Gorenstein projective in R-Mod for all m ∈ ℤ. Basing on this we show that if R is a right coherent left perfect ring then Gpd(C) = sup{Gpd(C ^m )|m ∈ ℤ} where Gpd(−) denotes Gorenstein projective dimension.