代数图论（影印版）
点击看大图基本信息
- 原书名：Algebraic Graph Theory
- 原出版社： Springer-Verlag
- 作者： Chris Godsil,Gordon Royle
- 丛书名： Graduate Texts in Mathematics
- 出版社：世界图书出版公司
- ISBN：7506266180
- 上架时间：2004-9-30
- 出版日期：2004 年4月
- 开本：24开
- 页码：439
- 版次：1-1
- 所属分类：
数学 > 代数，数论及组合理论 > 模糊数学
教材 > 研究生/本科/专科教材 > 理学 > 数学
内容简介回到顶部↑
Many authors begin their preface by confidently describing how their book arose. We started this project so long ago, and our memories are so weak, that we could not do this truthfully. Others begin by stating why they decided to write. Thanks to Freud, we know that unconscious reasons can be as important as conscious ones, and so this seems impossible, too. Moreover, the real question that should be addressed is why the reader should struggle with this text.
目录回到顶部↑
preface
1 graphs
1.1 graphs
1.2 subgraphs
1.3 automorphisms
1.4 homomorphisms
1.5 circulant graphs
1.6 johnson graphs
1.7 line graphs
1.8 planar graphs
exercises
notes
references
2 groups
2.1 permutation groups
2.2 counting
2.3 asymmetric graphs
2.4 orbits on pairs
2.5 primitivity
2.6 primitivity and connectivity
1 graphs
1.1 graphs
1.2 subgraphs
1.3 automorphisms
1.4 homomorphisms
1.5 circulant graphs
1.6 johnson graphs
1.7 line graphs
1.8 planar graphs
exercises
notes
references
2 groups
2.1 permutation groups
2.2 counting
2.3 asymmetric graphs
2.4 orbits on pairs
2.5 primitivity
2.6 primitivity and connectivity
前言回到顶部↑
Many authors begin their preface by confidently describing how their book arose. We started this project so long ago, and our memories are so weak, that we could not do this truthfully. Others begin by stating why they decided to write. Thanks to Freud, we know that unconscious reasons can be as important as conscious ones, and so this seems impossible, too. Moreover, the real question that should be addressed is why the reader should struggle with this text.
Even that question we cannot fully answer, so instead we offer an explanation for our own fascination with this subject. It offers the pleasure of seeing many unexpected and useful connections between two beautiful, and apparently unrelated, parts of mathematics: algebra and graph theory. At its lowest level, this is just the feeling of getting something for nothing. After devoting much thought to a graph-theoretical problem, one suddenly realizes that the question is already answered by some lonely algebraic fact. The canonical example is the use of eigenvalue techniques to prove that certain extremal graphs cannot exist, and to constrain the parameters of those that do. Equally unexpected, and equally welcome, is the realization that some complicated algebraic task reduces to a question in graph theory, for example, the classification of groups with BN pairs becomes the study of generalized polygons.
Although the subject goes back much further, Tutte's work was fundamental. His famous characterization of graphs with no perfect matchings was proved using Pfaffians; eventually, proofs were found that avoided any reference to algebra, but nonetheless, his original approach has proved fruitful in modern work developing parallelizable algorithms for determining the maximum size of a matching in a graph. He showed that the order of the vertex stabilizer of an arc-transitive cubic graph was at most 48. This is still the most surprising result on the autmomorphism groups of graphs, and it has stimulated a vast amount of work by group theorists interested in deriving analogous bounds for arc-transitive graphs with valency greater than three. Tutte took the chromatic polynomial and gave us back the Tutte polynomial, an important generalization that we now find is related to the surprising developments in knot theory connected to the Jones polynomial.
But Tutte's work is not the only significant source. Hoffman and Singleton's study of the maximal graphs with given valency and diameter led them to what they called Moore graphs. Although they were disappointed in that, despite the name, Moore graphs turned out to be very rare, this was nonetheless the occasion for introducing eigenvalue techniques into the study of graph theory.
Moore graphs and generalized polygons led to the theory of distanceregular graphs, first thoroughly explored by Biggs and his collaborators. Generalized polygons were introduced by Tits in the course of his fundamental work on finite simple groups. The parameters of finite generalized polygons were determined in a famous paper by Feit and Higman; this can still be viewed as one of the key results in algebraic graph theory. Seidel also played a major role. The details of this story are surprising: His work was actually motivated by the study of geometric problems in general metric spaces. This led him to the study of equidistant sets of points in projective space or, equivalently, the subject of equiangular lines. Extremal sets of equiangular lines led in turn to regular two-graphs and strongly regular graphs. Interest in strongly regular graphs was further stimulated when group theorists used them to construct new finite simple groups.
We make some explanation of the philosophy that has governed our choice of material. Our main aim has been to present and illustrate the main tools and ideas of algebraic graph theory, with an emphasis on current rather than classical topics. We place a strong emphasis on concrete examples, agreeing entirely with H. Luneburg's admonition that "...the goal of theory is the mastering of examples." We have made a considerable effort to keep our treatment self-contained.
Our view of algebraic graph theory is inclusive; perhaps some readers will be surprised by the range of topics we have treated--fractional chromatic number, Voronoi polyhedra, a reasonably complete introduction to matroids, graph drawing--to mention the most unlikely. We also find occasion to discuss a large fraction of the topics discussed in standard graph theory texts (vertex and edge connectivity, Hamilton cycles, matchings, and colouring problems, to mention some examples).
We turn to the more concrete task of discussing the contents of this book. To begin, a brief summary: automorphisms and homomorphisms, the adjacency and Laplacian matrix, and the rank polynomial.
In the first part of the book we study the automorphisms and homomorphisms of graphs, particularly vertex-transitive graphs. We introduce the necessary results on graphs and permutation groups, and take care to describe a number of interesting classes of graphs; it seems silly, for example, to take the trouble to prove that a vertex-transitive graph with valency k has vertex connectivity at least 2(k + 1)/3 if the reader is not already in position to write down some classes of vertex-transitive graphs. In addition to results on the connectivity of vertex-transitive graphs, we also present material on matchings and Hamilton cycles.
There are a number of well-known graphs with comparatively large automorphism groups that arise in a wide range of different settings--in particular, the Petersen graph, the Coxeter graph, Tutte's 8-cage, and the Hoffman-Singleton graph. We treat these famous graphs in some detail. We also study graphs arising from projective planes and symplectic forms over 4-dimensional vector spaces. These are examples of generalized polygons, which can be characterized as bipartite graphs with diameter d and girth 2d. Moore graphs can be defined to be graphs with diameter d and girth 2d + 1. It is natural to consider these two classes in the same place, and we do so.
We complete the first part of the book with a treatment of graph homomorphisms. We discuss Hedetniemi's conjecture in some detail, and provide an extensive treatment of cores (graphs whose endomorphisms are all automorphisms). We prove that the complement of a perfect graph is perfect, offering a short algebraic argument due to Gasparian. We pay particular attention to the Kneser graphs, which enables us to treat fractional chromatic number and the ErdSs-Ko-Rado theorem. We determine the chromatic number of the Kneser graphs (using Borsuk's theorem).
The second part of our book is concerned with matrix theory. Chapter 8 provides a course in linear algebra for graph theorists. This includes an extensive, and perhaps nonstandard, treatment of the rank of a matrix. Following this we give a thorough treatment of interlacing, which provides one of the most powerful ways of using eigenvalues to obtain graph-theoretic information. We derive the standard bounds on the size of independent sets, but also give bounds on the maximum number of vertices in a bipartite induced subgraph. We apply interlacing to establish that certain carbon molecules, known as fullerenes, satisfy a stability criterion. We treat strongly regular graphs and two-graphs. The main novelty here is a careful discussion of the relation between the eigenvalues of the subconstituents of a strongly regular graph and those of the graph itself. We use this to study the strongly regular graphs arising as the point graphs of generalized quadrangles, and characterize the generalized quadra, ngles with lines of size three.
The least eigenvalue of the adjacency matrix of a line graph is at least -2. We present the beautiful work of Cameron, Goethals, Shult, and Seidel, characterizing the graphs with least eigenvalue at least -2. We follow the original proof, which reduces the problem to determining the generalized quadrangles with lines of size three and also reveals a surprising and close connection with the theory of root systems.
Finally we study the Laplacian matrix of a graph. We consider the relation between the second-largest eigenvalue of the Laplacian and various interesting graph parameters, such as edge-connectivity. We offer several viewpoints on the relation between the eigenvectors of a graph and various natural graph embeddings. We give a reasonably complete treatment of the cut and flow spaces of a graph, using chip-firing games to provide a novel approach to some aspects of this subject.
The last three chapters are devoted to the connection between graph theory and knot theory. The most startling aspect of this is the connection between the rank polynomial and the Jones polynomial.
For a graph theorist, the Jones polynomial is a specialization of a straightforward generalization of the rank polynomial of a graph. The rank polynomial is best understood in the context of matroid theory, and consequently our treatment of it covers a significant part of matroid theory. We make a determined attempt to establish the importance of this polynomial, offering a fairly complete list of its remarkable applications in graph theory (and coding theory). We present a version of Tutte's theory of rotors, which allows us to construct nonisomorphic 3-connected graphs with the same rank polynomial.
After this work on the rank polynomial, it is not difficult to derive the Jones polynomial and show that it is a useful knot invariant. In the last chapter we treat more of the graph theory related to knot diagrams. We characterize Gauss codes and show that certain knot theory operations are just topological manifestations of standard results from graph theory, in particular, the theory of circle graphs.
As already noted, our treatment is generally self-contained. We assume familiarity with permutations, subgroups, and homomorphisms of groups. We use the basics of the theory of symmetric matrices, but in this case we do offer a concise treatment of the machinery. We feel that much of the text is accessible to strong undergraduates. Our own experience is that we can cover about three pages of material per lecture. Thus there is enough here for a number of courses, and we feel this book could even be used for a first course in graph theory.
The exercises range widely in difficulty. Occasionally, the notes to a chapter provide a reference to a paper for a solution to an exercise; it is then usually fair to assume that the exercise is at the difficult end of the spectrum. The references at the end of each chapter are intended to provide contact with the relevant literature, but they are not intended to be complete.
It is more than likely that any readers familiar with algebraic graph theory will find their favourite topics slighted; our consolation is the hope that no two such readers will be able to agree on where we have sinned the most.
Even that question we cannot fully answer, so instead we offer an explanation for our own fascination with this subject. It offers the pleasure of seeing many unexpected and useful connections between two beautiful, and apparently unrelated, parts of mathematics: algebra and graph theory. At its lowest level, this is just the feeling of getting something for nothing. After devoting much thought to a graph-theoretical problem, one suddenly realizes that the question is already answered by some lonely algebraic fact. The canonical example is the use of eigenvalue techniques to prove that certain extremal graphs cannot exist, and to constrain the parameters of those that do. Equally unexpected, and equally welcome, is the realization that some complicated algebraic task reduces to a question in graph theory, for example, the classification of groups with BN pairs becomes the study of generalized polygons.
Although the subject goes back much further, Tutte's work was fundamental. His famous characterization of graphs with no perfect matchings was proved using Pfaffians; eventually, proofs were found that avoided any reference to algebra, but nonetheless, his original approach has proved fruitful in modern work developing parallelizable algorithms for determining the maximum size of a matching in a graph. He showed that the order of the vertex stabilizer of an arc-transitive cubic graph was at most 48. This is still the most surprising result on the autmomorphism groups of graphs, and it has stimulated a vast amount of work by group theorists interested in deriving analogous bounds for arc-transitive graphs with valency greater than three. Tutte took the chromatic polynomial and gave us back the Tutte polynomial, an important generalization that we now find is related to the surprising developments in knot theory connected to the Jones polynomial.
But Tutte's work is not the only significant source. Hoffman and Singleton's study of the maximal graphs with given valency and diameter led them to what they called Moore graphs. Although they were disappointed in that, despite the name, Moore graphs turned out to be very rare, this was nonetheless the occasion for introducing eigenvalue techniques into the study of graph theory.
Moore graphs and generalized polygons led to the theory of distanceregular graphs, first thoroughly explored by Biggs and his collaborators. Generalized polygons were introduced by Tits in the course of his fundamental work on finite simple groups. The parameters of finite generalized polygons were determined in a famous paper by Feit and Higman; this can still be viewed as one of the key results in algebraic graph theory. Seidel also played a major role. The details of this story are surprising: His work was actually motivated by the study of geometric problems in general metric spaces. This led him to the study of equidistant sets of points in projective space or, equivalently, the subject of equiangular lines. Extremal sets of equiangular lines led in turn to regular two-graphs and strongly regular graphs. Interest in strongly regular graphs was further stimulated when group theorists used them to construct new finite simple groups.
We make some explanation of the philosophy that has governed our choice of material. Our main aim has been to present and illustrate the main tools and ideas of algebraic graph theory, with an emphasis on current rather than classical topics. We place a strong emphasis on concrete examples, agreeing entirely with H. Luneburg's admonition that "...the goal of theory is the mastering of examples." We have made a considerable effort to keep our treatment self-contained.
Our view of algebraic graph theory is inclusive; perhaps some readers will be surprised by the range of topics we have treated--fractional chromatic number, Voronoi polyhedra, a reasonably complete introduction to matroids, graph drawing--to mention the most unlikely. We also find occasion to discuss a large fraction of the topics discussed in standard graph theory texts (vertex and edge connectivity, Hamilton cycles, matchings, and colouring problems, to mention some examples).
We turn to the more concrete task of discussing the contents of this book. To begin, a brief summary: automorphisms and homomorphisms, the adjacency and Laplacian matrix, and the rank polynomial.
In the first part of the book we study the automorphisms and homomorphisms of graphs, particularly vertex-transitive graphs. We introduce the necessary results on graphs and permutation groups, and take care to describe a number of interesting classes of graphs; it seems silly, for example, to take the trouble to prove that a vertex-transitive graph with valency k has vertex connectivity at least 2(k + 1)/3 if the reader is not already in position to write down some classes of vertex-transitive graphs. In addition to results on the connectivity of vertex-transitive graphs, we also present material on matchings and Hamilton cycles.
There are a number of well-known graphs with comparatively large automorphism groups that arise in a wide range of different settings--in particular, the Petersen graph, the Coxeter graph, Tutte's 8-cage, and the Hoffman-Singleton graph. We treat these famous graphs in some detail. We also study graphs arising from projective planes and symplectic forms over 4-dimensional vector spaces. These are examples of generalized polygons, which can be characterized as bipartite graphs with diameter d and girth 2d. Moore graphs can be defined to be graphs with diameter d and girth 2d + 1. It is natural to consider these two classes in the same place, and we do so.
We complete the first part of the book with a treatment of graph homomorphisms. We discuss Hedetniemi's conjecture in some detail, and provide an extensive treatment of cores (graphs whose endomorphisms are all automorphisms). We prove that the complement of a perfect graph is perfect, offering a short algebraic argument due to Gasparian. We pay particular attention to the Kneser graphs, which enables us to treat fractional chromatic number and the ErdSs-Ko-Rado theorem. We determine the chromatic number of the Kneser graphs (using Borsuk's theorem).
The second part of our book is concerned with matrix theory. Chapter 8 provides a course in linear algebra for graph theorists. This includes an extensive, and perhaps nonstandard, treatment of the rank of a matrix. Following this we give a thorough treatment of interlacing, which provides one of the most powerful ways of using eigenvalues to obtain graph-theoretic information. We derive the standard bounds on the size of independent sets, but also give bounds on the maximum number of vertices in a bipartite induced subgraph. We apply interlacing to establish that certain carbon molecules, known as fullerenes, satisfy a stability criterion. We treat strongly regular graphs and two-graphs. The main novelty here is a careful discussion of the relation between the eigenvalues of the subconstituents of a strongly regular graph and those of the graph itself. We use this to study the strongly regular graphs arising as the point graphs of generalized quadrangles, and characterize the generalized quadra, ngles with lines of size three.
The least eigenvalue of the adjacency matrix of a line graph is at least -2. We present the beautiful work of Cameron, Goethals, Shult, and Seidel, characterizing the graphs with least eigenvalue at least -2. We follow the original proof, which reduces the problem to determining the generalized quadrangles with lines of size three and also reveals a surprising and close connection with the theory of root systems.
Finally we study the Laplacian matrix of a graph. We consider the relation between the second-largest eigenvalue of the Laplacian and various interesting graph parameters, such as edge-connectivity. We offer several viewpoints on the relation between the eigenvectors of a graph and various natural graph embeddings. We give a reasonably complete treatment of the cut and flow spaces of a graph, using chip-firing games to provide a novel approach to some aspects of this subject.
The last three chapters are devoted to the connection between graph theory and knot theory. The most startling aspect of this is the connection between the rank polynomial and the Jones polynomial.
For a graph theorist, the Jones polynomial is a specialization of a straightforward generalization of the rank polynomial of a graph. The rank polynomial is best understood in the context of matroid theory, and consequently our treatment of it covers a significant part of matroid theory. We make a determined attempt to establish the importance of this polynomial, offering a fairly complete list of its remarkable applications in graph theory (and coding theory). We present a version of Tutte's theory of rotors, which allows us to construct nonisomorphic 3-connected graphs with the same rank polynomial.
After this work on the rank polynomial, it is not difficult to derive the Jones polynomial and show that it is a useful knot invariant. In the last chapter we treat more of the graph theory related to knot diagrams. We characterize Gauss codes and show that certain knot theory operations are just topological manifestations of standard results from graph theory, in particular, the theory of circle graphs.
As already noted, our treatment is generally self-contained. We assume familiarity with permutations, subgroups, and homomorphisms of groups. We use the basics of the theory of symmetric matrices, but in this case we do offer a concise treatment of the machinery. We feel that much of the text is accessible to strong undergraduates. Our own experience is that we can cover about three pages of material per lecture. Thus there is enough here for a number of courses, and we feel this book could even be used for a first course in graph theory.
The exercises range widely in difficulty. Occasionally, the notes to a chapter provide a reference to a paper for a solution to an exercise; it is then usually fair to assume that the exercise is at the difficult end of the spectrum. The references at the end of each chapter are intended to provide contact with the relevant literature, but they are not intended to be complete.
It is more than likely that any readers familiar with algebraic graph theory will find their favourite topics slighted; our consolation is the hope that no two such readers will be able to agree on where we have sinned the most.
)
加载中...
