Size direction games over the real line. II

Variants of two basic infinite games of perfect information are studied. A notion of continuous strategy for the playerS (Size) is shown to be related to a notion of convergence norm for sequences of reals. With each such norm, a variant of each of the basic games is associated in which the size player has to see that each play obeys the norm. Restriction to choose only rational numbers is also imposed onS. Some games are completely solved, and in this caseS has a winning strategy iff his set includes a perfect subset, andD has a winning strategy iffS's set is at most denumerable. Some other games, in whichS has to choose only rationals and obey a norm, induce a hierarchy structure on the class of nowhere dense perfect sets, that is embedded cofinally in the lattice of infinite sequences of integers modulo finite differences.     

Whaley's Theorem for Finite Lattices

Whaley's Theorem on the existence of large proper sublattices of infinite lattices is extended to ordered sets and finite lattices. As a corollary it is shown that every finite lattice L with |L|≥3 contains a proper sublattice S with |S|≥|L|^1/3. It is also shown that that every finite modular lattice L with |L|≥3 contains a proper sublattice S with |S|≥|L|^1/2, and every finite distributive lattice L with |L|≥4 contains a proper sublattice S with |S|≥3/4|L|. This revised version was published online in June 2006 with corrections to the Cover Date.     

The lattice of embedded subsets

In cooperative game theory, games in partition function form are real-valued function on the set of the so-called embedded coalitions, that is, pairs (S,π) where S is a subset (coalition) of the set N of players, and π is a partition of N containing S. Despite the fact that many studies have been devoted to such games, surprisingly nobody clearly defined a structure (i.e., an order) on embedded coalitions, resulting in scattered and divergent works, lacking unification and proper analysis. The aim of the paper is to fill this gap, thus to study the structure of embedded coalitions (called here embedded subsets), and the properties of games in partition function form.     

GEODETIC GAMES FOR GRAPHS

ABSTRACT

Let S be a subset of the vertex set V(G) of a nontrivial connected graph G. The geodetic closure (S) of S is the set of all vertices on geodesics between two vertices in S. The first player A chooses a vertex v₁ of G. The second player B then picks v₂ ≠ v₁ and forms the geodetic closure (S₂) = ({v₁, v₂}). Now A selects v₃ ε V—S₂ and forms (S₃) = ({v₁, v₂, v₃}), etc. The player who first selects a vertex v_n such that (S_n) = V wins the achievement game, but loses the avoidance game. These geodetic achievement and avoidance games are solved for several families of graphs by determining which player is the winner.     

Galois connections among fuzzy groups, similarities, distances

Given a set S, we define Galois connections between the lattices of the fuzzy subgroups of transformations in S, the lattice of the similarities in S and the lattice of the distances in S.     

Routing sets in the integer lattice

A set of vertices S in a graph G is a routing set if it ensures some kind of connectivity between all pairs of vertices outside of S. Additional constraints may apply; a connected dominating set, for instance, is a special case of a routing set. We determine the size of a minimum routing set in subgraphs of the integer lattice, as well as (asymptotically) for the lattice itself.     

Adelic version of Margulis arithmeticity theorem

We generalize Margulis's S-arithmeticity theorem to the case when S can be taken as an infinite set of primes. Let R be the set of all primes including infinite one and set . Let S be any subset of R. For each , let be a connected semisimple adjoint -group and be a compact open subgroup for each finite prime . Let denote the restricted topological product of 's, with respect to 's. Note that if S is finite, . We show that if , any irreducible lattice in is a rational lattice. We also present a criterion on the collections and for to admit an irreducible lattice. In addition, we describe discrete subgroups of generated by lattices in a pair of opposite horospherical subgroups. Received: 30 November 2000 / Revised version: 2 April 2001 / Published online: 24 September 2001     

On the Connection Between the Projection and the Extension of a Parallelotope

This paper presents a result concerning the connection between the parallel projection P _v,H of a parallelotope P along the direction v (into a transversal hyperplane H) and the extension P + S(v), meaning the Minkowski sum of P and the segment S(v) = {λv | −1 ≤ λ ≤ 1}. A sublattice L _v of the lattice of translations of P associated to the direction v is defined. It is proved that the extension P + S(v) is a parallelotope if and only if the parallel projection P _v,H is a parallelotope with respect to the lattice of translations L _v,H , which is the projection of the lattice L _v along the direction v into the hyperplane H.     

Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001     

Apery Sets of Numerical Semigroups #

Let S be a numerical semigroup. We examine a particular subset of the Apery set of S and establish a correspondence between this subset and the holes of S . This correspondence allows us to establish conditions for S to be almost symmetric.     

A Notion of Rank for Right Congruences on Semigroups

ABSTRACT

We introduce a new notion of rank for a semigroup S. The rank is associated with pairs (I,ρ), where ρ is a right congruence and I is a ρ-saturated right ideal. We allow I to be the empty set; in this case the rank of (?, ρ) is the Cantor-Bendixson rank of ρ in the lattice of right congruences of S, with respect to a topology we title the finite type topology. If all pairs have rank, then we say that S is ranked. Our notion of rank is intimately connected with chain conditions: every right Noetherian semigroup is ranked, and every ranked inverse semigroup is weakly right Noetherian.

Our interest in ranked semigroups stems from the study of the class ± b? _S of existentially closed S-sets over a right coherent monoid S. It is known that for such S the set of sentences in the language of S-sets that are true in every existentially closed S-set, that is, the theory T _S of ± b? _S , has the model theoretic property of being stable. Moreover, T _S is superstable if and only if S is weakly right Noetherian. In the present article, we show that T _S satisfies the stronger property of being totally transcendental if and only if S is ranked and weakly right Noetherian.     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

Compatible extensions of nearrings

If R is a zero-symmetric nearring with 1 and G is a faithful R-module, a compatible extension of R is a subnearring S of M ₀(G) containing R such that G is a compatible S-module and the R-ideals and S-ideals of G coincide. The set of these compatible extensions forms a complete lattice and we shall study this lattice. We also will obtain results involving the least element of this lattice related to centralizers and the largest element of this lattice related to uniqueness of minimal factors with an application to 1-affine completeness of the R-module G.     

Compatible extensions of nearrings

If R is a zero-symmetric nearring with 1 and G is a faithful R-module, a compatible extension of R is a subnearring S of M ₀(G) containing R such that G is a compatible S-module and the R-ideals and S-ideals of G coincide. The set of these compatible extensions forms a complete lattice and we shall study this lattice. We also will obtain results involving the least element of this lattice related to centralizers and the largest element of this lattice related to uniqueness of minimal factors with an application to 1-affine completeness of the R-module G.     

Congruences via abelian groups

Given a group G acting on a set S, Möbius inversion over the lattice of subgroups can be used to obtain congruences relating the number of elements of S stabilized by each subgroup. By taking S to be a set of subsets, partitions, or permutations congruences for binomial and multinomial coefficients, Stirling numbers of both kinds, and various other combinatorial sequences are derived. Congruences for different moduli are obtained by varying the order of G.     

Embeddings into Orthomodular Lattices with Given Centers,State Spaces and Automorphism Groups

We prove that, given a nontrivial Boolean algebra B, a compact convex set S and a group G, there is an orthomodular lattice L with the center isomorphic to B, the automorphism group isomorphic to G, and the state space affinely homeomorphic to S. Moreover, given an orthomodular lattice J admitting at least one state, L can be chosen such that J is its subalgebra.     

The Structure of the Reduced Product of Preinjective Modules Over a Hereditary Right Pure Semisimple Ring

Abstract

For a monoid S , a (left) S -act is a nonempty set B together with a mapping S ×B→B sending (s, b) to sb such that S (tb)?=?lpar;st)b and 1b ?=?b for all S , t?∈?S and B ?∈?B. Right S -acts A can also be defined, and a tensor product A ??? _s B (a set)can be defined that has the customary universal property with respect to balanced maps from A?×?B into arbitrary sets. Over the past three decades, an extensive theory of flatness properties has been developed (involving free and projective acts, and flat acts of various sorts, defined in terms of when the tensor product functor has certain preservation properties). A recent and complete discussion of this area is contained in the monograph Monoids, Acts and Categories by M. Kilp et al. (New York: Walter de Gruyter, 2000). To date, there have been only a few attempts to generalize this material to ordered monoids acting on partially ordered sets ( S -posets). The present paper is devoted to such a generalization. A unique decomposition theorem for S -posets is given, based on strongly convex, indecomposable S -subposets, and a structure theorem for projective S -posets is given. A criterion for when two elements of the tensor product of S -posets given, which is then applied to investigate several flatness properties.     

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

Root Sublattices and Torus-Restriction of Prehomogeneous Vector Spaces Associated with Dynkin Quivers

For a Dynkin quiver Γ with r vertices, a subset S of the vertices of Γ, and an r-tuple d = (d⁽¹⁾, d⁽²⁾,…, d^(r)) of positive integers, we define a “torus-restricted” representation (G_S, R _d (Γ)) in natural way. Here we put G_S = G₁ × G₂ × … ×G_r, where each G_i is either SL(d⁽ⁱ⁾) or GL(d⁽ⁱ⁾) according to S containing i or not. In this paper, for a prescribed torus-restriction S, we give a necessary and sufficient condition on d that R _d (Γ) has only finitely many G_S-orbits. This can be paraphrased as a condition whether or not d is contained in a certain lattice spanned by positive roots of Γ. We also discuss the prehomogeneity of (G_S, R _d (Γ)).     

MAXIMUM INDEPENDENT,MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS

Abstract

We introduce a new type of graph-theoretic parameter, namely, “single set, prioritized multi-property” parameters. The example described here uses independence as the priority property and redundance as the secondary property, and we consider the problem of minimizing (total) redundance for a maximum independent set S. We show that we have an Np-hard problem but that there exists a linear time algorithm to find such a set S in a series-parallel graph.