|
TRANSFINITENESS FOR GRAPHS, ELECTRICAL NETWORKS,
AND RANDOM WALKS |
| PREFACE ``What good is a newborn baby?'' Michael Faraday's reputed response when asked, ``What good is magnetic induction?'' But, it must be admitted that a newborn baby may die in infancy. What about this one --- the idea of transfiniteness for graphs, electrical networks, and random walks? At least its bloodline is robust. Those subjects, along with Cantor's transfinite numbers, comprise its ancestry. There seems to be general agreement that the theory of graphs was born when Leonhard Euler published his solution to the ``Konigsberg bridge problem'' in 1736. Similarly, the year of birth for electrical network theory might well be taken to be 1847, when Gustav Kirchhoff published his voltage and current laws. Ever since those dates until just a few years ago, all infinite undirected graphs and networks had an inviolate property: Two branches either were connected through a finite path or were not connected at all. The idea of two branches being connected only through transfinite paths, that is, only through paths having infinitely many branches was never invoked, or so it appears from a perusal of various surveys of infinite graphs. Our objective herein is to explore this idea and some of its ramifications. It should be noted however that directed graphs having transfinite paths have appeared in set theory, but, by virtue of that directedness and the sets the graphs represent, the question of connections at infinite extremities of graphs is either avoided or trivially resolved. This question is however a substantial issue in our theory of undirected arbitrary transfinite graphs and is resolved by the invention of a new kind of node. Research on graphs, electrical networks, and random walks continues to thrive, and new ideas for them are proliferating. It therefore is incumbent upon us to argue why still another may be of interest. One reason is offered in Section 1.4, where it is shown that a transfinite network is the natural outcome of an effort to close a heretofore unaddressed lacuna in the theory of infinite electrical ladders. A more compelling consideration is that transfiniteness introduces radically new constructs and expands the three aforementioned topics far beyond their conventional boundaries. For instance, a transfinite graph is not a graph in any prior sense but is instead an extension roughly analogous to Cantor's extension of the natural numbers to the transfinite ordinals. It is undoubtedly way too much to expect that the introduction of transfinite graphs will eventually be as important as Cantor's invention of the transfinite numbers. However, even a small fraction of that success would be ample justification for our endeavor. Transfiniteness for undirected graphs and electrical networks was first introduced through some embryonic ideas and then in all its generality This book expands upon those prior works with a variety of new results. It is in fact a sequel to the book, ``Infinite Electrical Networks'' but can be read independently; there is no need to read that book before embarking on this one. All definitions and results within the mainstream of this present book are thoroughly developed herein. Some peripheral ideas that broaden our discussions but are not critical to them are borrowed from several sources, including ``Infinite Electrical Networks.'' Moreover, most of that book was restricted to conventional infinite networks, and the lesser part of it on transfinite networks focussed upon the first rank of transfiniteness, that is, upon ``1-networks.'' Now, however, we exclusively examine transfinite graphs and networks with due attention to higher ranks of transfiniteness. Moreover, we expand our theory considerably with the introduction of several new topics related to connectedness problems, discrete potential theory, uncountable networks, and random walks. A critical issue in the development of transfinite graphs and networks was the choice of appropriate definitions. Much effort was expended in pursuing likely possibilities, many of which failed because of inherent contradictions or unmanageable entanglements. An example of the latter is described in Section 1.2. The definitions we have chosen appear to be free of those obstacles and yet sufficiently general for our purposes. To be sure, we could simplify a few definitions by weakening them, but this again leads to complications because of the variety of situations that then arise. We believe that we have arrived at a satisfactory compromise between the complexity of definitions and the complexity of subsequent discussions. On the other hand, we introduce many new concepts. This is due to the unavoidable circumstance that transfinite undirected graphs are multifaceted structures and entirely novel. We cannot borrow from established theories but instead must construct everything we need. This is exacerbated by the many ranks of transfiniteness, one for each countable ordinal. Were we to restrict ourselves to the first rank, that is, to ``1-graphs,'' the number of definitions would be comparable to that for conventional graphs. But the extensions to higher ranks through recursion expand that number severalfold, especially since some of the definitions needed for a limit-ordinal rank are significantly different from those for a successor-ordinal rank. Almost all the ideas about transfinite graphs introduced in ``Infinite Electrical Networks'' are employed herein without alteration, but there are a few differences. One of them concerns the specification of a path, which previously involved some ambiguity---with the result that a path could be represented in different ways. The tighter definition we now use prevents this. A related matter is that we now make a distinction between a path ``reaching'' a node and ``meeting'' a node, the former concept being weaker than the latter. Still another alteration is that we abandon the idea of a ``reduced graph'' and use instead a ``subgraph.'' A reduced graph is obtained from a given transfinite graph by choosing just some of the branches and interconnecting them in accordance with the given graph. It is so defined that a reduced graph is a transfinite graph too, but this requires the introduction of other nodes. A subgraph uses the same interconnections of the chosen branches but does not proliferate nodes; however, it is in general something other than a transfinite graph. This replacement of reduced graphs by subgraphs simplifies our theory. Our book is arranged as follows. Chapter 1 is introductory. After explicating notations and terminology in Section 1.1, we argue why transfinite graphs and networks should be of interest and how they are needed to close a gap in the theory of conventional infinite networks. We also indicate why we adopt an unusual approach to conventional graphs in order to enable a simpler transfinite generalization. Transfinite graphs are treated in Chapters 2 through 4, electrical networks in Chapters 5 and 6, and random walks in Chapter 7. Chapter 2 is devoted almost entirely to the many definitions needed for the transfiniteness of graphs. Here---and indeed throughout this book---we illustrate new concepts with many examples. Connectedness problems are taken up in Chapter 3. We show that transfinite connectedness need not be transitive as a binary relation between branches. Conditions under which transitivity does hold are then obtained. Chapter 3 closes with a discussion of the cardinality of the branch set of a transfinite graph. In Chapter 4 we develop the idea of ``finite structuring'' for transfinite graphs, which mimics local-finiteness for conventional infinite graphs. This will be needed when we discuss discrete potential theory and random walks. Here we also present a transfinite generalization of Konig's classical lemma on the existence of one-way infinite paths. Chapter 5 presents some fundamental theorems asserting the existence and uniqueness of voltage-current regimes in transfinite electrical networks under very broad conditions. No restrictions on the transfinite graph of the network are imposed. These theorems are based on a generalization of Tellegen's equation, since Kirchhoff's laws are no longer inviolate principles in the transfinite case. Furthermore, node voltages need not be unique nor even exist. The chapter ends by establishing additional conditions under which node voltages are uniquely existent. Maximum principles for node voltages and branch currents are established in Chapter 6. This last result makes full use of the finite structuring developed in Chapter 4 and therefore holds for a class of transfinite networks that is smaller than that for the fundamental theorems. Finally, a theory for random walks on a finitely structured transfinite network is established in Chapter 7. The theory extends nearest-neighbor random walks by allowing them to pass through transfinite nodes. This is accomplished by exploiting the relationship between electrical network theory and random-walk phenomena. The appendices present brief surveys of three topics of importance to our theory, namely ordinal and cardinal numbers, summable series, and irreducible and reversible Markov chains. With this information our book should be accessible to anyone familiar with the basic ideas about graphs, Hilbert spaces, and resistive electrical networks. A.H. Zemanian Stony Brook, New York |
