Generalized hexagons and Singer geometries

In this paper, we consider a set of lines of with the properties that (1) every plane contains 0, 1 or q + 1 elements of , (2) every solid contains no more than q ² + q + 1 and no less than q + 1 elements of , and (3) every point of is on q + 1 members of , and we show that, whenever (4) q ≠ 2 (respectively, q = 2) and the lines of through some point are contained in a solid (respectively, a plane), then is necessarily the set of lines of a regularly embedded split Cayley generalized hexagon in , with q even. We present examples of such sets not satisfying (4) based on a Singer cycle in , for all q.      

A {\mathsf{D}}-induced duality and its applications

This paper attempts to extend the notion of duality for convex cones, by basing it on a prescribed conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the nonnegativity of the inner-product is replaced by a pre-specified conic ordering, defined by a convex cone , and the inner-product itself is replaced by a general multi-dimensional bilinear mapping. This new type of duality is termed the -induced duality in the paper. We further introduce the notion of -induced polar sets within the same framework, which can be viewed as a generalization of the -induced dual cones and is convenient to use for some practical applications. Properties of the extended duality, including the extended bi-polar theorem, are proven. Furthermore, attention is paid to the computation and approximation of the -induced dual objects. We discuss, as examples, applications of the newly introduced -induced duality concepts in robust conic optimization and the duality theory for multi-objective conic optimization. Research supported in part by the Foundation ‘Vereniging Trustfonds Erasmus Universiteit Rotterdam’ in The Netherlands, and in part by Hong Kong RGC Earmarked Grants CUHK4174/03E and CUHK418406.     

Well-posedness of constrained minimization problems via saddle-points

In this paper, it is proved a very general well-posedness result for a class of constrained minimization problems of which the following is a particular case: Let X be a Hausdorff topological space and let be two non-constant functions such that, for each , the function has sequentially compact sub-level sets and admits a unique global minimum in X. Then, for each , the restriction of J to has a unique global minimum, say , toward which every minimizing sequence converges. Moreover, the functions and are continuous in .     

Degrees of difficulty of generalized r.e. separating classes

Important examples of classes of functions are the classes of sets (elements of ^ω 2) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions f ∈ ^ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let denote the Medvedev degrees of those such that no m + 1 sets among A ₀,...,A _k-1 have a nonempty intersection. It is shown that each is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions is the greatest element of . If 2 ≤ l < k, then 0 _M is the only degree in which is below a member of . Each is densely ordered and has the splitting property and the same holds for the lattice it generates. The elements of are exactly the joins of elements of for . Supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

A complete classification of the computational complexity of the fixed-point existence problem for Boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes and graph classes , an ()-system is a Boolean dynamical system such that all local transition functions lie in and the underlying graph lies in . Let be a class of Boolean functions which is closed under composition and let be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If contains the self-dual functions and contains the planar graphs, then the fixed-point existence problem for ()-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If contains the self-dual functions and contains the graphs having vertex covers of size one, then the fixed-point existence problem for ()-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.      

A rank six geometry related to the McLaughlin sporadic simple group

In the literature, there are but a few incidence geometries on which the McLaughlin sporadic group acts as a flag-transitive automorphism group. Their highest rank is four. In the present paper, we construct a geometry of rank six on which acts flag-transitively and which has the following diagram.      

The intersection map of subgroups and certain classes of finite groups

The goals of this paper are twofold. One is to look at the behavior of the collections of permutable subgroups and S-permutable subgroups under the intersection map into a fixed subgroup of a group. The other is to locally analyze the intersection map in connection with -, -, and -groups. In particular, we generalize Theorem 1 of Bauman [Arch. Math. (Basel) 25:337–340, 1974] to - and -groups.      

On the spectrum of lamplighter groups and percolation clusters

Let be a finitely generated group and X its Cayley graph with respect to a finite, symmetric generating set S. Furthermore, let be a finite group and the lamplighter group (wreath product) over with group of “lamps” . We show that the spectral measure (Plancherel measure) of any symmetric “switch–walk–switch” random walk on coincides with the expected spectral measure (integrated density of states) of the random walk with absorbing boundary on the cluster of the group identity for Bernoulli site percolation on X with parameter . The return probabilities of the lamplighter random walk coincide with the expected (annealed) return probabilities on the percolation cluster. In particular, if the clusters of percolation with parameter are almost surely finite then the spectrum of the lamplighter group is pure point. This generalizes results of Grigorchuk and Żuk, resp. Dicks and Schick regarding the case when is infinite cyclic. Analogous results relate bond percolation with another lamplighter random walk. In general, the integrated density of states of site (or bond) percolation with arbitrary parameter is always related with the Plancherel measure of a convolution operator by a signed measure on , where or another suitable group. M. Neuhauser’s research supported by the Marie-Curie Excellence Grant MEXT-CT-2004-517154. The research of W. Woess was partially supported by Austrian Science Fund (FWF) P18703-N18.