Search Results

This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.

This chapter considers the order homomorphisms induce on the set of all cores; this order is rich enough to represent all countable partial orders. Antichains in the homomorphism order are discussed, which are collections of incomparable graphs (graphs without homomorphisms between any two of them). Of particular interest are finite maximal antichains, and their structure turns out to be surprisingly revealing. Graphs only have trivial finite maximal antichains, while digraphs have many such antichains of all possible sizes, arising from duality relationships. This chapter also contains the (probabilistic) proof of the Sparse Incomparability Lemma, of the fact that asymptotically almost all graphs on $n$ vertices are cores, and of the fact that the number of incomparable graphs on $n$ vertices differs little (asymptotically) from the total number of non-isomorphic graphs on $n$ vertices. The density of the homomorphism order is related to duality, revealing an unexpected connection between these two seemingly unrelated concepts. Finally, it is shown that one can gain interesting insights into many traditional graph topics, such as Hadwiger’s conjecture, when interpreting them as statements about the homomorphism order.

This chapter focuses on the structure, as opposed to just the existence, of the family of homomorphisms among a set of graphs. The difference is noticeable with even just one graph. For instance, a graph having only the identity homomorphisms to itself is called rigid; rigid graphs are the building blocks of many constructions. Many useful constructions of rigid graphs are provided, and it is shown that asymptotically almost all graphs are rigid; infinite rigid graphs with arbitrary cardinality are also constructed. The homomorphisms among a set of graphs impose the algebraic structure of a category, and every finite category is represented by a set of graphs. This is the generalization of the theorem of Frucht from Chapter 1. Also, as in the case studied by Frucht, it is shown that the representing graphs can be required to have any of a number of graph theoretic properties. However, these properties cannot include having bounded degrees — somewhat surprisingly, since Frucht proved that cubic graphs represent all finite groups.

This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.

This chapter studies operator algebras ‘up to isomorphism’ or ‘up to complete isomorphism’. Topics covered include homomorphisms of operator algebras, completely bounded characterizations, examples of operator algebra structures, Q-algebras, and applications to isomorphic theory. Notes and historical remarks are presented at the end of the chapter.

This chapter brings together the basic properties of fibre bundles, fibrations, and vector bundles required in surgery theory. The tangent and normal bundles of a manifold are introduced. The bundle-theoretic interpretation of the Hopf invariant and J-homomorphism in homotopy theory is also discussed.

This chapter provides an introduction to the basic definitions and properties of Mumford-Tate groups in both the case of Hodge structures and of mixed Hodge structures. Hodge structures of weight n are sometimes called pure Hodge structures, and the term “Hodge structure” then refers to a direct sum of pure Hodge structures. The chapter presents three definitions of a Hodge structure of weight n, given in historical order. In the first definition, a Hodge structure of weight n is given by a Hodge decomposition; in the second, it is given by a Hodge filtration; in the third, it is given by a homomorphism of ℝ-algebraic groups. In the first two definitions, n is assumed to be positive and the p,q's in the definitions are non-negative. In the third definition, n and p,q are arbitrary. For the third definition, the Deligne torus integers are used.

This chapter begins with a brief introduction to the numerical measurement theory upon which the ‘measurement-theoretic’ account of the attitudes will be modeled. Topics covered include the historical development of measurement theory, homomorphisms and other structural relations; representation, abstraction, idealization, and representational artifacts; a second-order intensional version of measurement theory; and measure predicates. It is argued that the significance of measurement theory lies primarily in the justification and explanation it provides for established measurement practices, thereby providing an understanding of the empirical content of our measurement claims.

This chapter presents a novel semantic analysis of the English resultative construction that crucially models telicity (aspectual boundedness) in terms of the event-argument homomorphism model (Krifka 1998) rather than the commonly assumed result state model (Dowty 1979). This assumption, together with recent insights on the semantics of scalar adjectives (Hay et al. 1999; Kennedy 1999; Kennedy and McNally 1999), leads us to an explanation for a myriad of facts. Corpus data from Boas (2000) strongly support our conclusions. The central idea of this analysis is that resultatives involve an abstract ‘path’ argument corresponding to degrees along the scale denoted by the resultative predicate.

This chapter deals with Dehn twists, the simplest infinite-order elements of Mod(S). It first defines Dehn twists and proves that they are nontrivial elements of the mapping class group. In particular, it considers the action of Dehn twists on simple closed curves. As one application of this study, the chapter proves that if two simple closed curves in Sɡ have geometric intersection number greater than 1, then the associated Dehn twists generate a free group of rank 2 in Mod(S). It also proves some fundamental facts about Dehn twists and describes the center of the mapping class group, along with algebraic relations that can occur between two Dehn twists. Finally, it explores three geometric operations on a surface that each induces an algebraic operation on the corresponding mapping class group: the inclusion homomorphism, the capping homomorphism, and the cutting homomorphism.

Aspectual properties of dynamic predicates such as telicity and durativity are often assumed to be partly determined by the expression of some privileged argument of the predicate called an ‘incremental theme’ where the progress of the event described by the predicate is measured by parts of the incremental theme. The chapter provides evidence that many if not all dynamic predicates actually have at least two incremental themes, namely some theme that undergoes the change described by the predicate and some scale that measures the change the theme undergoes, which stand in a mutually constraining relationship to the event. This chapter proposes a ternary Figure/Path Relation by which events are measured by the progress of subparts of the theme changing along subparts of the scale sharing a common goal. This analysis makes a number of key, novel predictions about the aspectual properties of dynamic predicates, and more accurately captures their truth-conditional content.

This chapter discusses the basic properties of the group of symplectomorphisms of a compact connected symplectic manifold and its subgroup of Hamiltonian symplectomorphisms. It begins by showing that the group of symplectomorphisms is locally path-connected and then moves on to the flux homomorphism. The main result here is a theorem of Banyaga that characterizes the Hamiltonian symplectomorphisms in terms of the flux homomorphism. In the noncompact case there is another interesting homomorphism, called the Calabi homomorphism, that takes values in the reals and may be defined on the universal cover of the group of Hamiltonian symplectomorphisms. The chapter ends with a brief comparison of the topological properties of the group of symplectomorphisms with those of the group of diffeomorphisms.

This chapter assesses the general properties of equivariant cohomology. Both the homotopy quotient and equivariant cohomology are functorial constructions. Equivariant cohomology is particularly simple when the action is free. Throughout the chapter, by a G-space, it means a left G-space. Let G be a topological group and consider the category of G-spaces and G-maps. A morphism of left G-spaces is a G-equivariant map (or G-map). Such a morphism induces a map of homotopy quotients. The map in turn induces a ring homomorphism in cohomology. The chapter then looks at the coefficient ring of equivariant cohomology, as well as the equivariant cohomology of a disjoint union.

This chapter studies representation theory. In order to state the equivariant localization formula of Atiyah–Bott and Berline–Vergne, one will need to know some representation theory. Representation theory “represents” the elements of a group by matrices in such a way that group multiplication becomes matrix multiplication. It is a way of simplifying group theory. The chapter provides the minimal representation theory needed for equivariant cohomology. A real representation of a group G is a group homomorphism. Every representation has at least two invariant subspaces, 0 and V. These are called the trivial invariant subspaces. A representation is said to be irreducible if it has no invariant subspaces other than 0 and V; otherwise, it is reducible.

This chapter examines vector bundles. It begins with a standard definition of vector bundles, and this is followed by some first examples of vector bundles. It then discusses the tangent bundle with corresponding examples; and the cotangent bundle; bundle homomorphisms. Finally it looks at sections of vector bundles.

Any linear operation that can be performed to generate a new vector space from a given set of initial vector spaces can be done fibre-wise with an analogous set of vector bundles to generate a new vector bundle. This chapter describes the most important examples. The discussions cover subbundles; quotient bundles; the dual bundle; bundles of homomorphisms; tensor product bundles; the direct sum; and tensor powers.

In chapter 8, the author brings causal, teleosemantic and resemblance theories of content together by extending CT (as presented in chapter 7) to explain how homomorphism (more specifically, analog relations, or second-order similarity relations) can play a content-constitutive role. While the idea that some systems have the function to model the world might explain why a natural representational system counts as a representational system, it is neutral between iconic mental representation and a more language-like version of Mentalese. The author then addresses traditional objections to resemblance theories of content, to show how they can now be met. She argues that sensory-perceptual systems can have functions to produce inner state changes that are caused by and the analogs of their contents, and that this casts light on the intuitive appeal of resemblance theories of mental representation, and that it permits some sensory-perceptual simples to represent novel and non-existent contents. Chapter 8 also addresses the fourth and fifth content-determinacy challenges: why does R have the content there’s C and not there’s Q, when (iv) C is a determinate of Q, or (v) C is a determinable for Q? In the last few sections, Berkeley’s problem of abstraction and two contemporary strategies for its solution are discussed, insofar as it concerns the representation of perceptible properties (e.g., shape and color).

This chapter considers the notion of a group in mathematics. It begins with a discussion of the problem of determining the symmetry of an object such as a planar shape, a higher-dimensional solid, a group, or an electric field. It then describes every group as a group of symmetries of some object and shows what it means for a group to be a group of symmetries of an object. These ideas are at the very heart of geometric group theory, the study of groups, spaces, and the interactions between them. The chapter also examines infinite groups, homomorphisms and normal subgroups, and group presentations. A number of exercises are included.

This chapter considers some preliminary notions, starting with standard pseudo-reductive groups, Levi subgroups, and root systems. It reviews the “standard construction” of pseudo-reductive k-groups and shows that any connected reductive group equipped with a chosen split maximal torus is generated by that maximal torus and its root groups for the simple positive and negative roots relative to a choice of positive system of roots in the root system. It also discusses the basic exotic construction, noting that the only nontrivial multiplicities that occur for the edges of Dynkin diagrams of reduced irreducible root systems are 2 and 3. Finally, it explains the minimal type pseudo-reductive k-group G, along with quotient homomorphism between pseudo-reductive groups.

This chapter develops the weighted feature-matching account of similarity. Most accounts of the model–world relation draw on logical properties such as isomorphism and homomorphism. In contrast, accounts offered by Nancy Cartwright and Ronald Giere emphasize that the model–world relation is one of similarity in certain respects and degrees, but they provide little further analysis. Weighted feature-matching, which is derived from Amos Tversky’s contrast account of similarity, is a way of formalizing the notion of similarity in respects and degrees. Roughly, it says that a model is similar to its target when they share many, and do not fail to share too many, features that are thought to be salient by the scientific community.