The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.     

Homogeneous Vector Bundles and Koszul Algebras

Let G be a reductive algebraic group defined over an algebraically closed field of characteristic zero and let P be a parabolic subgroup of G. We consider the category of homogeneous vector bundles over the flag variety G/P. This category is equivalent to a category of representations of a certain infinite quiver with relations by a generalisation of a result in [BK]. We prove that both categories are Koszul precisely when the unipotent radical P_u of P is abelian.     

Sylow products and the solvable radical

We study products of Sylow subgroups of a finite group G. First we prove that G is solvable if and only if G = P₁ ... P_m for any choice of Sylow p_i-subgroups P_i , where p₁,..., p_m are all of the distinct prime divisors of |G|, and for any ordering of the p_i . Then, for a general finite group G, we show that the intersection of all Sylow products as above is a subgroup of G which is closely related to the solvable radical of G. Received: 18 November 2004     

Hyperbolic elements in negatively curved groups

We show that in a negatively curved groupG the conjugacy class of any infinite cyclic subgroup contains a straight element, an elementg with |g ⁿ |=n|g|, and thus the translation number of an element in a negatively curved group is rational with uniformly bounded denominator. We also find an upper bound on the cardinality of a finite normal subgroup.     

On tree‐decompositions of one‐ended graphs

A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays.     

On generating countable sets of endomorphisms

Sierpiski proved that every countable set of mappings on an infinite set X is contained in a 2-generated subsemigroup of the semigroup of all mappings on X. In this paper we prove that every countable set of endomorphisms of an algebra which has an infinite basis (independent generating set) is contained in a 2-generated subsemigroup of the semigroup of all endomorphisms of .     

Classification of disordered tilings

A tilingT is a disordered realization of a periodic tilingP with symmetry group Γ if we can map the complement of a compact set ofT onto the quotientP/Γ in such a way that this map respects the features of the tilingT andP. We show that the global type of a 2-dimensional tilingT is determined by the periodic tilingP it is a disordered realization of, a conjugacy class of Γ which can be associated toT and a winding number. In some cases, we need in addition some kind of orientation. For higher-dimensional tilings of spaces which are simply connected at infinity, e.g. ℝ ⁿ withn≥3, the associated periodic tiling alone is sufficient.     

On the modality of parabolic subgroups of linear algebraic groups

For a linear algebraic group G over an algebraically closed field k and a parabolic subgroup P of G the modality of P is defined to be the maximal number of parameters upon which a family of G-orbits on Lie P _u depends and it is denoted by mod P, where P _u is the unipotent radical of P. The principal aim of this note is a generalization of two basic “monotonicity” results from [19] to positive characteristic: (1) If Θ is a semisimple automorphism of G and P is Θ-stable, then mod P ^\Θ≤ mod P. (2) If G is reductive, char k is a good prime for G, and H is a closed reductive subgroup of G normalized by a maximal torus T⊂P of G, then mod (P∩H)≤ mod P. Received: 22 April 1998 / Revised version: 3 July 1998     

Global solution of semi-infinite programs

Optimization problems involving a finite number of decision variables and an infinite number of constraints are referred to as semi-infinite programs (SIPs). Existing numerical methods for solving nonlinear SIPs make strong assumptions on the properties of the feasible set, e.g., convexity and/or regularity, or solve a discretized approximation which only guarantees a lower bound to the true solution value of the SIP. Here, a general, deterministic algorithm for solving semi-infinite programs to guaranteed global optimality is presented. A branch-and-bound (B&B) framework is used to generate convergent sequences of upper and lower bounds on the SIP solution value. The upper-bounding problem is generated by replacing the infinite number of real-valued constraints with a finite number of constrained inclusion bounds; the lower-bounding problem is formulated as a convex relaxation of a discretized approximation to the SIP. The SIP B&B algorithm is shown to converge finitely to –optimality when the subdivision and discretization procedures used to formulate the node subproblems are known to retain certain convergence characteristics. Other than the properties assumed by globally-convergent B&B methods (for finitely-constrained NLPs), this SIP algorithm makes only one additional assumption: For every minimizer x* of the SIP there exists a sequence of Slater points x_n for which (cf. Section 5.4). Numerical results for test problems in the SIP literature are presented. The exclusion test and a modified upper-bounding problem are also investigated as heuristic approaches for alleviating the computational cost of solving a nonlinear SIP to guaranteed global optimality.     

Blocks of minimal dimension

Any block with defect group P of a finite group G with Sylow-p-subgroup S has dimension at least |S|²/|P|; we show that a block which attains this bound is nilpotent, answering a question of G. R. Robinson. Received: 20 November 2006     

On Subspaces and Quotients of Banach Spaces C(K, X)

 We study the relation of to the subspaces and quotients of Banach spaces of continuous vector-valued functions , where K is an arbitrary dispersed compact set. More precisely, we prove that every infinite dimensional closed subspace of totally incomparable to X contains a copy of complemented in . This is a natural continuation of results of Cembranos-Freniche and Lotz-Peck-Porta. We also improve our result when K is homeomorphic to an interval of ordinals. Next we show that complemented subspaces (resp., quotients) of which contain no copy of are isomorphic to complemented subspaces (resp., quotients) of some finite sum of X. As a consequence, we prove that every infinite dimensional quotient of which is quotient incomparable to X, contains a complemented copy of . Finally we present some more geometric properties of spaces. Received 8 November 2000; in revised form 7 December 2001     

Groupes Moyennables, Dimension Topologique Moyenne et sous-décalages

Let G be an infinite countable residually finite amenable group. In this paper we construct a continuous action of G on a compact metrisable space X such that the dynamical system (X, G) cannot be embedded in the G-shift on [0,1] ^G . This result generalizes a construction due to E. Lindenstrauss and B. Weiss (Mean topological dimension, Israel J. Math. 115 (2000), 1–24) for .     

A case of the 3-dimensional problem of Apollonius

Summary Inn-dimensions the problem of Apollonius is to determine the (n–1)-spheres tangent ton+1 given (n–1)-spheres. In case no two of the given (n–1)-spheres intersect and no three have the property that one separates the other two, the expected number of solutions is 2 ⁿ⁺¹. Whenn=2 this special problem does indeed always have 8 solutions, but for higher dimensions it turns out that the number of solutions becomes dependent on the relative size and location of the given (n–1)-spheres. We describe in detail the dependence of the number of solutions in the case of the 3-dimensional problem of Apollonius on the 6 inversively invariant parameters that describe configurations of 4 given spheres. We find that the number of solutions, if finite, can be any integer from 0 to 16 and, if infinite, can be a one-, two- or three-fold infinity where the stated multiplicity refers to the number of one-parameter families of solutions that are present.     

Maximal Parabolic Subgroups in Classical Groups are of Modality Zero

The principal aim of this paper is to show that every maximal parabolic subgroup P of a classical reductive algebraic group G operates with a finite number of orbits on its unipotent radical. This is a consequence of the fact that each parabolic subgroup of a group of type A _n whose unipotent radical is of nilpotent class at most two has this finiteness property.     

Mutation of Auslander Generators for Selfinjective Algebras

Let Λ be an artin algebra with representation dimension equal to three and M an Auslander generator of Λ. We show how, under certain assumptions, we can mutate M to get a new Auslander generator whose endomorphism ring is derived equivalent to the endomorphism ring of M. We apply our results to selfinjective algebras with radical cube zero of infinite representation type, where we construct an infinite set of Auslander generators.     

THE NUMBER AND SIZE OF ORBITS OF SOME PERMUTATION GROUPS

Abstract

It is shown that Aut ?, the group of homeomorphisms of the rational numbers with the usual topology, has 2 ^N_o orbits on the power set P(?). We call S ? ? a moiety if S and its complement in ? are infinite. It is shown that the orbit of any moiety S under Aut ? has cardinality 2^N_o while the orbit of S under Aut(?, ≤), the group of order preserving automorphisms of ?, has cardinality N_o if and only if S is a finite union of disjoint rational intervals with rational endpoints.     

Coût des relations d’équivalence et des groupes

We study a new dynamical invariant for dicrete groups: the cost. It is a real number in {1−1/n}∪[1,∞], bounded by the number of generators of the group, and it is well behaved with respect to finite index subgroups. Namely, the quantities 1 minus the cost are related by multiplying by the index. The cost of every infinite amenable group equals 1. We compute it in some other situations, including free products, free products with amalgamation and HNN-extensions over amenable groups and for direct product situations. For instance, the cost of the free group on n generators equals n. We prove that each possible finite value of the cost is achieved by a finitely generated group. It is dynamical because it relies on measure preserving free actions on probability Borel spaces. In most cases, groups have fixed price, which implies that two freely acting groups which define the same orbit partition must have the same cost. It enables us to distinguish the orbit partitions of probability-preserving free actions of free groups of different ranks. At the end of the paper, we give a mercuriale, i.e. a list of costs of different groups. The cost is in fact an invariant of ergodic measure-preserving equivalence relations and is defined using graphings. A treeing is a measurable way to provide every equivalence class (=orbit) with the structure of a simplicial tree, this an example of graphing. Not every relation admits a treeing: we prove that every free action of a cost 1 non-amenable group is not treeable, but we prove that subrelations of treeable relations are treeable. We give examples of relations which cannot be produced by an action of any finitely generated group. The cost of a relation which can be decomposed as a direct product is shown to be 1. We define the notion for a relation to be a free product or an HNN-extension and compute the cost for the resulting relation from the costs of the building blocks. The cost is also an invariant of the pairs von Neumann algebra/Cartan subalgebra. Oblatum 27-I-1999 & 4-IV-1999 / Published online: 22 September 1999     

On the Boolean dimension of spherical orders

It is well known that if a planar order P is bounded, i.e. has only one minimum and one maximum, then the dimension of P (LD(P)) is at most 2, and if we remove the restriction that P has only one maximum then LD(P)3. However, the dimension of a bounded order drawn on the sphere can be arbitrarily large.The Boolean dimension BD(P) of a poset P is the minimum number of linear orders such that the order relation of P can be written as some Boolean combination of the linear orders. We show that the Boolean dimension of bounded spherical orders is never greater than 4, and is not greater than 5 in the case the poset has more than one maximal element, but only one minimum. These results are obtained by a characterization of spherical orders in terms of containment between circular arcs.Part of this work was carried out while both authors were visiting the Department of Applied Mathematics (KAM) of Charles University, Prague. The authors acknowledge support from the EU HCM project DONET.     

The <Emphasis Type="Italic">K</Emphasis>(π,1)-conjecture for the affine braid groups

The complement of the hyperplane arrangement associated to the (complexified) action of a finite, real reflection group on ⁿ is known to be a K(,1) space for the corresponding Artin group $\Cal A$. A long-standing conjecture states that an analogous statement should hold for infinite reflection groups. In this paper we consider the case of a Euclidean reflection group of type à _n and its associated Artin group, the affine braid group $\tilde{\Cal A}$. Using the fact that $\tilde{\Cal A}$ can be embedded as a subgroup of a finite type Artin group, we prove a number of conjectures about this group. In particular, we construct a finite, $n$-dimensional K(,1)-space for $\tilde{\Cal A}$, and use it to prove the K(,1) conjecture for the associated hyperlane complement. In addition, we show that the affine braid groups are biautomatic and give an explicit biautomatic structure.