Research Reports on
Transfinite and Nonstandard Graphs and Networks
These
reports are archived as CEAS Technical Reports in the Science and Engineering
Library of the State University of New York at Stony Brook. Copies of them can be obtained by sending a request
to the email address: zeman@ee.sunysb.edu.
Report
785: Nonstandard Transfinite Graphs and
Random Walks on Them. (October 2000,
revised January 2002) Abstract.
Report 788: Hyperreal Transients in Transfinite RLC
Networks. (January 2001) Abstract.
Report
789: Walk-Based Transfinite Graphs and Networks.
(August 2001) Abstract.
Report
795: Nonstandard Transfinite Electrical
Networks. (January 2002) Abstract.
Report 796: Ordinal Distances in Transfinite Graphs:
II. (March 2001,
revised and extended January 2002)
Abstract.
Report 799: Hyperreal Transients on Transfinite Distributed Transmission Lines and Cables. (February 2002) Abstract.
Report 802: Nonstandard Graphs Based on Tips as the Individual Elements. (June 2002) Abstract
Report 803: Nonstandard Graphs. (June 2002) Abstract
Report 807: A Shorter Proof for the Transitivity of Transfinite Connectedness (December 2002) Abstract
Report 811: Hyperreal Waves on Transfinite, Terminated, Distortionless and Lossless, Transmission Lines (June 2004) Abstract
Report 812: Nonstandard Graphs and Networks of Higher Ranks (June 2004) Abstract
Report 813: The Galaxies of Nonstandard Enlargements of Infinite and Transfinite Graphs (September 2004) Abstract
Report 814: The Galaxies of Nonstandard
Enlargements of Transfinite Graphs of Higher Ranks (September 2004) Abstract
Report 819: The Galaxies of Nonstandard Enlargements of
Infinite and Transfinite Graphs: II (April 2005) Abstract
Report 820: The Galaxies of Nonstandard Enlargements of
Transfinite Graphs of Higher Ranks: II (April 2005) Abstract
Report 821: A Circuit-Theoretic Anomaly Resolved by
Nonstandard Analysis (August 2005) Abstract
Abstract for CEAS Technical Report 785, University at Stony Brook,
October 2000, revised January 2002:
NONSTANDARD TRANSFINITE GRAPHS AND
RANDOM WALKS ON THEM
It is shown that transfinite graphs can be generated
through two simple operations, called ``appending a branch’’ and ``inserting a
branch,’’ applied to finite graphs infinitely many times. In this way, transfinite graphs are natural
extensions of conventional graphs.
Certain pathological graphs cannot be so obtained. For those transfinite graphs that can, a
specific procedure for obtaining them from an expanding sequence of finite
subgraphs is established. That sequence
of finite sub graphs determines a ``nonstandard graph,’’ the sequence being a
representative of an equivalence class of sequences of finite graphs modulo a
chosen nonprincipal ultrafilter. This
mimics a definition of the hyper real numbers as equivalence classes of real
numbers. With such nonstandard
transfinite graph in hand, random walks on it can be obtained by considering
random walks on a representative sequence of sub graphs. This allows us to lift many standard results
into a nonstandard setting, but now probabilities will be hyperreals. A typical result is that we can now quantify
and compare infinitesimal escape probabilities from different nodes, thereby
comparing probabilities of recurrence.
All the many restrictions needed to establish random walks on standard
transfinite graphs are no longer needed.
Abstract for CEAS Technical Report 788, University
at Stony Brook, January 2001.
HYPERREAL TRANSIENTS IN
TRANSFINITE RLC NETWORKS
Up to the present time, there have been no transient
analyses of RLC transfinite networks. Standard analyses of transfinite networks have
been restricted to purely resistive ones.
In this paper, it is shown how nonstandard analysis can be used to
examine the transient behavior of transfinite networks having lumped resistors,
inductors, and capacitors. To do so, the
time line is expanded into the hyperreal time line, and the transients obtained
take on hyperreal values. It is also
shown how the diffusion of signals on artificial RC cables and the propagation
of waves on artificial RLC transmission lines can ``pass through infinity’’ and
penetrate transfinite extensions of those cables and lines. Less precisely but more suggestively, we can
say that diffusions and waves can reach---with appreciable values---nodes that
are transfinitely far away from their starting points, but that it will take
infinitely long times in order to do so in order to get there.
Abstract
for CEAS Technical Report 789, University at Stony Brook, August 2001.
WALK-BASED TRANSFINITE GRAPHS AND
NETWORKS
The theory of transfinite graphs developed so far has been
based on the ideas that connectedness is accomplished through paths and that
the infinite extremities of
the graph are specified through one-way infinite paths. As a result, a variety of difficulties arise
in that theory, leading to the need to restrict such path-based transfinite
graphs in various ways in order to obtain certain results. In this work, we present a more general
theory of transfinite graphs wherein connectedness and the designation of extremities
are accomplished through walks rather than paths. This leads to a simpler and
yet more general theory wherein new kinds of transfinite extremities are also
encompassed. For instance, an
ordinal-valued distance function can now be defined on all pairs of
walk-connected nodes, in contrast to the path-based theory wherein no distance
function is definable for those pairs of nodes that are not path-connected even
though they are walk---connected. Some
results concerning eccentricities, radii, and diameters are presented in this
more general walk-based transfinite graph theory. Another new result herein is the development
of an electrical network theory for networks whose graphs are walk-based. A unique voltage-current regime is
established under certain conditions.
The current regime is built up from current flows in closed transfinite
walks---in contrast to a prior theory based upon flows in transfinite
loops. A notable advantage of the
present approach is that node voltages with respect to a given ground node are always
unique whenever they exist. Moreover,
the present approach is more general in that it provides nontrivial
voltage-current regimes for certain networks for which the prior approach would
only provide trivial solutions having only zero currents and voltages
everywhere.
Abstract for CEAS Technical Report 793, University
at Stony Brook, January 2002.
NONSTANDARD TRANSFINITE GRAPHS
For any given sequence of transfinite graphs all of the
same rank, a nonstandard transfinite graph of that same rank is
constructed. The procedure is similar to
an ultrapower construction of an internal set from a sequence of subsets of the
real line, but now the primitive standard entities are the nodes of various
ranks instead of real
numbers.
Abstract for CEAS Technical Report 795, University
at Stony Brook, January 2002.
NONSTANDARD TRANSFINITE ELECTRICAL
NETWORKS
Transfinite resistive electrical networks may (or may not)
have operating points, and, even when voltages and currents do exist within
them, Kirchhoff’s laws may not be satisfied everywhere. Moreover, rather severe restrictions have to
be placed on such networks in order to obtain such results because of the inability of
standard calculus to encompass certain interchanges of limiting processes. However, the comparatively recent theory of
nonstandard analysis has this ability.
The idea of a nonstandard electrical network, introduced in a prior
work, is expanded herein to cover all transfinite networks that are
``restorable’’ in the sense that the network is taken to be the end result of
an expanding sequence
of finite networks. Kirchhoff’s laws
will always be satisfied in restorable transfinite networks. Several transfinite networks are then
examined under nonstandard analysis, and explicit hyperreal currents and
voltages are established for them
Abstract for CEAS Technical Report 796, University
at Stony Brook, January 2002.
ORDINAL DISTANCES IN TRANSFINITE
GRAPHS: II
An ordinal-valued metric, taking its values in the set of
all countable ordinals, can be assigned to a metrizable set M of nodes in any
transfinite graph. M contains all the
nonsingleton nodes, as well as certain singleton nodes. Moreover, this yields a graphical realization
of Cantor’s countable ordinals, as well as the Aristotelian ideas of ``potential’’ and
``actual’’ infinities, the former being represented by the arrow ranks and the
latter by the ordinal ranks of transfiniteness.
This construct also extends transfinitely the ideas of nodal
eccentricities, radii, diameters, centers, peripheries, and blocks for graphs,
and the following generalizations are established. With n denoting the rank of an n-graph G, the
n-nodes of G
comprise the center of a larger n-graph.
Also, when there are only finitely many n-nodes and when those n-nodes
are ``pristine’’ in the sense that they do not embrace nodes of lower ranks,
the infinitely many nodes of all ranks have eccentricities of the form w^{n}p,
where w is the first transfinite ordinal and p lies in a finite set of natural
numbers. Furthermore, the center is
contained in a single block of highest rank. Also, when each loop of the n-graph is
confined within an (n-1)-section, the center either is a single node of highest
rank, or is the set of internal nodes of an (n-1)-section, or is the union of
the latter two kinds of centers.
Abstract for CEAS Technical Report 797, University
at Stony Brook, January 2002.
GENERATING TRANSFINITE AND NONSTANDARD
GRAPHS BY APPENDING AND INSERTING BRANCHES
Transfinite graphs can be obtained by ``appending’’ and ``inserting’’ branches infinitely many times into finite graphs. This is alternative way of generating transfinite graphs, which then appear as natural extensions of conventional graphs. This leads to the idea of nonstandard transfiniteness for graphs, electrical networks, and random walks, in which voltages, currents, and probabilities are hyperreal numbers and do not require the many restrictions imposed under standard analysis to ensure their existence.
Abstract for CEAS Technical Report 799, University at Stony Brook, February 2002.
HYPERREAL TRANSIENTS ON TRANSFINITE DISTRIBUTED
TRANSMISSION LINES AND CABLES
A prior work showed how nonstandard analysis could be used to derive
hyperreal transients in transfinite electrical networks containing lumped
inductors, capacitors, resistors, and sources. In this work hyperreal
transients are derived for transfinite electrical networks whose parameters
are distributed. In particular, explicit expressions are derived for
hyperreal transients on uniform transmission lines and cables that ``extend
beyond infinity'' transfinitely. This requires a substantially altered
technique as compared to the prior work. The present one uses a different
kind of truncation procedure and then expands the latter in steps to ``fill
out'' the transfinite line or cable.
Abstract for CEAS Technical Report 802. University at Stony Brook, June 2002.
NONSTANDARD GRAPHS BASED ON TIPS AS THE INDIVIDUAL ELEMENTS
From any given sequence of finite or infinite graphs, a nonstandard graph is constructed. The procedure is similar to an ultrapower construction of an internal set from a sequence of subsets of the real line, but now the individual entities are the tips of the branches instead of real numbers.
_________________________________________________________________________________________________
Abstract for CEAS Technical Report 803, University at Stony Brook, June 2002.
NONSTANDARD GRAPHS
From any given sequence of finite or infinite graphs, a nonstandard graph is constructed. The procedure is similar to an ultrapower construction of an internal set from a sequence of subsets of the real line, but now the individual elements are the vertices of the graphs instead of real numbers. The transfer principle is then invoked to extend several graph-theoretic results to the nonstandard case. After incidences and adjacencies between nonstandard vertices and edges are defined, several formulas regarding numbers of vertices and edges , and nonstandard versions of Eulerian graphs, Hamiltonian graphs, and a coloring theorem are established for these nonstandard graphs.
___________________________________________________________________
Abstract for CEAS Technical Report 807, University at Stony Brook, Dec. 2002.
A SHORTER PROOF OF THE TRANSITIVITY OF TRANSFINITE CONNECTEDNESS
A criterion is established for the transitivity of connectedness in a transfinite graph. Its proof is much shorter than a prior argument published previously for that criterion.
___________________________________________________________________
Abstract for CEAS Technical Report 811,University at Stony Brook, June 2004
HYPERREAL WAVES ON TRANSFINITE, TERMINATED, DISTORTIONLESS AND LOSSLESS, TRANSMISSION LINES
A prior work examined the propagation of an electromagnetic wave on a transfinite transmission line---transfinite in the sense that infinitely many one-way infinite transmission lines are connected in cascade. (See the book by A.H. Zemanian, "Graphs and Networks: Transfinite and Nonstandard," published by Birkhauser-Boston, Cambridge, Mass. 2004, Chapter 7.) That there are infinitely many such lines results in the wave propagating without ever reflecting at some discontinuity. This work examines the case where the cascade is terminated after finitely many one-way infinite transmission lines with the result that reflected waves are now produced at both the far end as well as at the initial end of the transmission line. The questions of whether the reflected waves are infinitesimal or appreciable and whether they sum to an infinitesimal or appreciable amount are resolved for both distortionless and lossless lines. Finally, the generalization to higher ranks of transfiniteness is briefly summarized.
____________________________________________________________________
Abstract for CEAS Technical Report 812, University at Stony Brook, June 2004
NONSTANDARD GRAPHS AND NETWORKS OF HIGHER RANKS
In Chapter 8 of the book, ``Graphs and Networks: Transfinite and Nonstandard,'' (published by Birkhauser-Boston in 2004), nonstandard version of transfinite graphs and of electrical networks having such graphs were defined and examined but only for the first two ranks, 0 and 1, of transfiniteness. In the present work, these results are extended to higher ranks of transfiniteness. Such is done in detail for the natural-number ranks and also for the first transfinite ordinal rank. Results for still higher ranks of transfiniteness can be established in much the same way. Once the transfinite graphs of higher ranks are established, theorems concerning the existence of hyperreal operating points and the satisfaction of Kirchhoff's laws in nonstandard networks of higher ranks can be proven just as they are for nonstandard networks of the first rank.
___________________________________________________________________
Abstract for CEAS Technical Report 813, University at Stony Brook, Sept., 2004
THE GALAXIES OF NONSTANDARD ENLARGEMENTS OF INFINITE AND TRANSFINITE GRAPHS
The galaxies of the nonstandard enlargements of conventionally infinite graphs as well as of transfinite graphs are defined, analyzed, and illustrated by some examples. It is shown that any such enlargement either has exactly one galaxy, its principle one, or it has infinitely many such galaxies. In the latter case, the galaxies are partially ordered by their "closeness'' to the principal galaxy. Certain sets of galaxies that are totally ordered by that "closeness'' are identified.
____________________________________________________________________________________
Abstract for CEAS Technical Report 814, University at Stony Brook, Sept. 2004
THE GALAXIES OF NONSTANDARD ENLARGEMENTS OF TRANSFINITE GRAPHS OF HIGHER RANKS
In a prior work the galaxies of the nonstandard enlargements of conventionally infinite graphs and also of transfinite graphs of the first rank of transfiniteness were defined, examined, and illustrated by some examples. In this work it is shown how the results of the prior work extend to transfinite graphs of higher ranks. Among those results are following principal ones. Any such enlargement either has exactly one galaxy, it principal one, or it has infinitely many such galaxies. In the latter case, the galaxies are partially ordered by their "closeness'' to the principal galaxy. Also, certain sets of galaxies that are totally ordered by that "closeness" criterion are identified.
___________________________________________________________________________________
Abstract for CEAS
Technical Report 818, University at Stony Brook, February 2005
BOUNDS
ON THE NODAL STATUSES OF SOME TRANSFINITE GRAPHS
The
bounds on the statuses of the nodes in a finite graph established by Entringer,
Jackson, and Snyder are extended herein so that they apply to the statuses of
the nodes in transfinite graphs of a certain kind.
Abstract for CEAS
Technical Report 819, University at Stony Brook, April 2005
The
Galaxies of Nonstandard Enlargements of Infinite and Transfinite Graphs: II
This
report is an improvement of a prior report (Report 813). It sharpens the principal theorems (Theorems
4.2 and 11.2 of Report 813) while simplifying their proofs. There are also several minor changes
involving clarifications and corrections of misprints. Otherwise, the abstract is the same as
before.
Abstract for CEAS Technical Report 820,
University at Stony Brook, April 2005
The
Galaxies of Nonstandard Enlargements of Transfinite Graphs of Higher Ranks: II
This report is an improvement of a prior
report (Report 814). It sharpens the
principal Theorem (Theorem 5.1 of Report 814) and also simplifies its
proof. Theire are also several minor
changes involving clarifications and corrections of misprints. Otherwise, the
abstract is the same as before.
_______________________________________________________________________________________________
Abstract
for CEAS Technical Report 821, University at Stony Brook, August 2005
A
Circuit-Theoretic Anomaly Resolved by Nonstandard Analysis
An anomaly in circuit theory is the
disappearance of some of the stored energy when two capacitors, one charged and
the other uncharged, are connected together through resistanceless wires. Nonstandard analysis shows that, when the
wires are taken to have infinitesimally small but nonzero resistance, the
energy dissipated in the wires equals the substantial amount of energy that had
disappeared, and that all but an infinitesimal amount of this dissipation
occurs during an infinitesimal initial time period. This provides still another but quite simple
model of what is in fact a multifaceted physical phenomenon. It also exemplifies the efficacy of at least
one application of nonstandard analysis to circuit theory.