Graphs and Cubes

verfasst von: Sergei Ovchinnikov

Verlag: Springer New York

Buchreihe : Universitext

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This introductory text in graph theory focuses on partial cubes, which are graphs that are isometrically embeddable into hypercubes of an arbitrary dimension, as well as bipartite graphs, and cubical graphs. This branch of graph theory has developed rapidly during the past three decades, producing exciting results and establishing links to other branches of mathematics.

Currently, Graphs and Cubes is the only book available on the market that presents a comprehensive coverage of cubical graph and partial cube theories. Many exercises, along with historical notes, are included at the end of every chapter, and readers are encouraged to explore the exercises fully, and use them as a basis for research projects.

The prerequisites for this text include familiarity with basic mathematical concepts and methods on the level of undergraduate courses in discrete mathematics, linear algebra, group theory, and topology of Euclidean spaces. While the book is intended for lower-division graduate students in mathematics, it will be of interest to a much wider audience; because of their rich structural properties, partial cubes appear in theoretical computer science, coding theory, genetics, and even the political and social sciences.

Inhaltsverzeichnis

Frontmatter

1. Graphs

Abstract

The main goal of this chapter is to introduce some very basic concepts and constructions of graph theory. We consciously made this chapter short and proved only a few simple facts. Combined with exercises at the end of the chapter this material can be used as a concise introduction to graph theory.

Sergei Ovchinnikov

2. Bipartite Graphs

Abstract

In this book, we deal mostly with bipartite graphs. The main thrust of this chapter is to characterize bipartite graphs using geometric and algebraic structures defined by the graph distance function. Fundamental sets and the two theta relations introduced in Section 2.3 play a crucial role in our studies of partial cubes in Chapter 5.

Sergei Ovchinnikov

3. Cubes

Abstract

In the first four sections of this chapter we introduce objects that are commonly known as “cubes” in geometry, algebra, and graph theory. A definition of a cube as a graph is given in Section 3.5. We continue by discussing properties of infinite Cartesian products, metric geometry of cubes, and their automorphisms. Finite cubes are characterized in the last section.

Sergei Ovchinnikov

4. Cubical Graphs

Abstract

Cubical graphs are subgraphs of cubes. We use c-valuations on graphs to characterize cubical graphs and investigate their properties.

Sergei Ovchinnikov

5. Partial Cubes

Abstract

This is the central chapter of the book. Unlike general cubical graphs, isometric subgraphs of cube—partial cubes—can be effectively characterized in many different ways and possess much finer structural properties. In this chapter, we present what can be called a “micro” theory of partial cubes.

Sergei Ovchinnikov

6. Lattice Embeddings

Abstract

Any partial cube is isomorphic to an isometric subgraph of an integer lattice (Theorem 6.4). The dimension of this lattice may be much lower than the isometric dimension of the partial cube making lattice representations a valuable tool in visualizing large and infinite partial cubes.

Sergei Ovchinnikov

7. Hyperplane Arrangements

Abstract

In this chapter, we study region graphs of hyperplane arrangements in Euclidean spaces. These graphs are highly symmetrical partial cubes and the theory has a distinctive geometric flavor. Two nongeometric applications are presented in Sections 7.5 and 7.7.

Sergei Ovchinnikov

8. Token Systems

Abstract

The chapter deals with algebraic and stochastic structures of token systems. Cubical token systems and media are defined as systems satisfying two sets of axioms, and elements of formal theories of these systems are introduced. Cubical systems and media serve as algebraic components of random walk models introduced in the last section of the chapter.

Sergei Ovchinnikov

Backmatter

Titel: Graphs and Cubes
verfasst von: Sergei Ovchinnikov
Verlag: Springer New York
Electronic ISBN: 978-1-4614-0797-3
Print ISBN: 978-1-4614-0796-6
DOI: https://doi.org/10.1007/978-1-4614-0797-3