Papers (with abstracts)
Geodesics and Bounded Harmonic Functions on Infinite Graphs
[Proc.
Amer. Math. Soc. 113 (1) (1991) 229-233]
It is shown here that an infinite connected planar graph with a uniform
upper bound on vertex degree and rapidly decreasing Green's function (relative
to the simple random walk) has infinitely many pairwise finitely intersecting
geodesic rays starting at each vertex. We then demonstrate the existence
of nonconstant bounded harmonic functions on the graph.
Gauge and conditional gauge on negatively curved graphs [Stoch.
Anal. Appl. 9 (4) 461-482(1991)]
In this paper, we study certain edge-weighted random walks on infinite
graphs with bounded vertex degree for which the second smallest eigenvalue
of the Laplacian is negative. We find analogues of the Feynman-Kac
functional and give several conditions equivalent to the boundedness of
the corresponding gauge function. From this result we derive a new
formula for the second smallest eigenvalue of the Laplacian and we apply
this formula to the theory of graph coverings. An analogue of the
conditional gauge theorem is shown to hold for certain Schrodinger operators.
Potential theory of a Schrodinger equation on negatively
curved graphs [in Proceedings of the Conference on
Probability Models in Mathematical Physics, World Scientific Publishing
Co., 1991]
We prove analogues of several theorems about diffusions on Euclidean
domains in the setting of random walks on negatively curved
graphs.
Cogrowth of Regular Graphs [Proc. Amer. Math. Soc.
116 #1 (1992) 203-205]
Let $G$ be a $d$-regular graph and $T$ the covering tree of $G$.
We define a cogrowth constant of $G$ in $T$ and express it in terms of
the first eigenvalue of the Laplacian on $G$. As a corollary, we
show that the cogrowth constant is as large as possible if and only if
the first eigenvalue of the Laplacian on $G$ is zero. Grigorchuk's
criterion for amenability of finitely generated groups follows.
Amenability and superharmonic functions [Proc. Amer.
Math. Soc. 119 #2 (1993) 561-566]
Let $G$ be a countable group and $\mu$ a symmetric and aperiodic probability
measure on $G$. We show that $G$ is amenable if and only if
every positive superharmonic function is nearly constant on certain arbitrarily
large subsets of $G$. We use this to show that if $G$ is amenable,
then the Martin boundary of $G$ contains a fixed point. More generally,
we show that $G$ is amenable if and only if each member of a certain family
of $G$-spaces contains a fixed point.
Circle Boundaries of Planar Graphs [Potential Analysis
#2 (1993) 299-314]
Let $G$ be an infinite, connected, planar graph with bounded vertex degree,
which obeys a strong isoperimetric inequality and which can be embedded
in the plane so that each cycle surrounds only finitely many vertices.
We investigate a certain class of compactifications of $G$; one of
which has boundary homeomorphic to a circle. We shall show that if
$G$ is a tree. or, more generally, if $G$ is hyperbolic, then this circle
boundary supports an integral representation of any given bounded harmonic
function. We further show that in the specific case of a triangulation
of the plane, the graph is hyperbolic and therefore the Martin boundary
is a circle.
On The Rational Recursive Sequence $x_{n+1}=(\beta x_n^2)/(1+x^2_{n-1})$
[Computers
and Mathmatics with Applications 28 #1-3 (1994) 37-43; with E. Camouzis,
G. Ladas, and I.W. Rodrigues]
We investigate the behavior of solutions of the equation in the title under
the hypotheses that $\beta$ is a positive constant and the initial conditions
$x_{-1}$ and $x_0$ are arbitrary positive numbers.
On the spectrum and Martin boundary of homogeneous spaces [Statistics
and Probability Letters, 22 (1995) 275-279]
Given a conservative, spatially homogeneous Markov process $X$ on a homogeneous
space $\Chi$, we show that if the bottom of the spectrum of the generator
of $X$ is zero then the Martin boundary of $\Chi$ contains a unique point
fixed by the isometry gorup of $\Chi$.
On the Commute Time of Random Walks on Graphs [REBRAPE,
2 (1995) 169-175; with J.L. Palacios]
Given a simple random walk on an undirected connected graph, the commute
time of the vertices $x$ and $y$ is defined as $C(x,y)=E_xxT_y+E_yT_x$.
We give a new proof, based on the optional sampling theorem for martingales,
of the formula $C(x,y)=\frac{1}{\pi(y)e(y,x)}$ in terms of the escape probability
$e(y,x) (the probability that once the random walk leaves $x$, it hits
$y$ before it returns to $x$) and the stationary distribution $\pi(\cdot)$.
We use this formula for $C(x,y) to show that the maximum commute time among
all barbell-type graphs in $N$ vertices is attained for the lollipop graph
and its value is $O(\frac{4N^3}{27})$.
A note on recurrence, amenability, and the universal cover of graphs [in
Random Discrete Structures (Aldous and Pemantle, eds.), IMA
Vol. 76, Springer, New York, 1996]
Given a regular graph $G$, and its universal covering tree $T$, we give
conditions which relate recurrence and amenability of $G$ to the size of
a certain subset $R$ of the Martin boundary of $T$. In particular,
$G$ is recurrent if and only if $R$ has full harmonic measure; $G$
is amenable if and only if $R$ has full Hausdorff dimension.
Random Products in Rings [in Interaction between
functional analysis, harmonic analysis, and probability (Kalton et al.,
eds.) Lecture Notes in Pure and Applied Mathematics #175, Dekker,
New York, 1996]
Given a ring, what is the probability distribution of a product of several
random elements? Although the distribution may be written in terms
of asymptotic densities (actual computation of which may be difficult)
we may also express it in terms of i.i.d. random variables taking values
in a Bohr compactification of the ring. This method allows us to
find explicit formulas for the distribution.
Flows and harmonic functions on graphs [in Harmonic
Functions on Trees and Buildings, Contemp. Math. #206, 1997,
pp. 153-155]
If F is a positive edge function on a tree T, we
say that F is subcritical if $\sum F^n<\infty$, critical if $\sum F^n=\infty$
but $\sum c^nF^n<\infty$ for all c<1, and supercritical otherwise.
We show that if F is supercritical, then there are no positive F-invariant
functions on T; if F is critical, then the space of such functions is one
dimensional. If F is subcritical, then we may define a bijection
from the F-invariant functions on T to the set of flows on T which is positive
(i.e. the space of positive flows (corresponding to positive measures on
the boundary of T) and the space of positive F-invariant functions on T
are in one-to-one correspondence. This is equivalent to the Martin
representation theorem.
Positive Solutions of Schrodinger's equation on trees
[J.
Difference Equations and Applications, 1998 Vol. 4, pp. 59-66]
For $x$ and $y$ vertices of a tree $T$, suppose $F(x,y)$ is positive
or zero according to whether $x$ and $y$ are adjacent or not. Then
$F$ (as a matrix) defines a linear operator on the space of real functions
on $T$. Let $H^+$ denote the set of positive solutions of $Ff=f$.
We show that $H^+$ is empty, isomorphic to the space of "positive flows"
on $T$, or one-dimensional according to whether $\sum c^nF^n$ diverges
(for some $c<1$), $\sum F^n$ converges, or neither respectively.
As a consequence, if $\sum F^n$ converges, then the Martin boundary of
$T$ with respect to $F$ is isomorphic to the geometric boundary of the
tree.
A note on the complexity of Graphs [J.
Comb. Theory, Ser. B 74 (1998) 408-410]
The number of spanning trees in a finite graph is first expressed as
the derivative (at 1) of a determinant and then in terms of a zeta function.
This generalizes a result of Hashimoto to non-regular graphs
Two proofs of Ihara's theorem [in Emerging Applications
of Number Theory, IMA Volume 109, Springer, NY, 1999]
We give two proofs that, for a finite regular graph, the reciprocal of
Ihara's zeta function can be expressed as a simple polynomial times a determinant
involving the adjacency matrix of the graph. The first proof is based
on representing radial symmetric eigenfunctions on regular
treees in terms of certain polynomials. The second proof
is a consequence of the fact that the resolvent of the adjacency operator
on regular trees is exponential. The number of spanning trees
in a finite graph is first expressed as the derivative (at 1) of a determinant
and then in terms of a zeta function. This generalizes a result of
Hashimoto to non-regular graphs.
On Iterates of Moebius transformations on fields [Math.
Comp., 70, no. 235 (2001) 1305-1310]
Let $p$ be a quadratic polynomial over a splitting field $K$ and $S$ be
the set of zeros of $p$. We define an associative and commutative
binary relation on $G\equiv K\cup\{\infty\}-S$ so that every M\"obius transformation
with fixed point set $S$ is of the form $x$ plus $c$ for some $c$.
This permits an easy proof of a generalization of Aitken acceleration as
well as generalizations of known results concerning Newton's method, the
secant method, Halley's method, and higher order methods. If $K$
is equipped with a valuation, then we give necessary and sufficient conditions
for the iterates of a M\"obius transformation $m$ to converge (necessarily
to one of its fixed points) in the valuation topology. Finally, we
show that if the fixed points of $m$ are distinct and the iterates of $m$
converge, then Newton's method converges with order 2, and higher order
generalizations converge accordingly.
Associativity of the Secant Method [to appear,
American Mathematical Monthly]
Iterating a function like 1+1/x gives a sequence
which converges to the Golden Mean but does so at a much slower rate than
those sequences derived from Newton's method or the secant method.
There is, however, a surprising relation between all these sequences.
This relation, easily explained by the use of good notation, is generalized
by means of Pascal's "Mysterium Hexagrammicum". Throughout, we make
contact with many areas of mathematics and physics including abstract groups,
calculus, continued fractions, differential equations, elliptic curves,
Fibonacci numbers, functional equations, fundamental groups, Lie groups,
matrices, Moebius transformations, pi, polynomial approximation, relativity,
and resistors.
Cogrowth of Arbitrary Graphs [preprint]
We extend Grigorchuk's criterion for amenability
of finitely generated groups to non-necessarily regular graphs. In
particular, we show that a graph with bounded vertex degree is amenable
if and only if a certain cogrowth constant, expressed in terms of
harmonic measure on the covering tree's boundary, is one. For graphs
which cover a finite graph, we show further that amenability is equivalent
to the equality of the growth of the covering tree and the growth of a
point's preimage in the covering tree.
Tech reports, etc.
Several proofs of Ihara's theorem [IMA Preprint Series
#1459, 1997]
We give three proofs that the reciprocal of Ihara's zeta function can be
expressed as a simple polynomial times a determinant involving the adjacency
matrix of the graph. The first proof
for regular graphs, is based on representing radial symmetric eigenfunctions
on regular treees in terms of certain polynomials. The second
proof, also for regular graphs, is a consequence of the fact that
the resolvent of the adjacency operator on regular trees is exponential.
A third proof, in many ways simpler than the rest, works for irregular
graphs as well.
Embedded Graphs and the Smoothness of Planar Domains [Tech.
Summary Report #94-1, CMS, U. Wisconsin, 7/93]
We consider the relations between boundary smoothness of simply connected
planar domains and properties of certain graphs contained in these domains.
We define a domain $D$ to be "smooth" if certain Riemannian metrics make
$D$ into a negatively curved manifold. We show that $C^2$ domains
and certain H\"older domains are smooth. We consider the graphs dual
to certain polygonizations of $D$. we show that all such graphs arising
from smooth domains are hyperbolic in the sense of Gromov. This shows,
for example, that the Martin boundary and Euclidean boundary coincide for
smooth domains.
Other Items
Schrodinger Operators on Infinite Graphs [Ph.D. Dissertation,
University of Rochester, 1989]
Problem #1412 [Mathematics
Magazine, 65 #5, Dec. 1992]
Problem #10397 (w/ J.L. Palacios) [Amer.
Math. Monthly, 101 #7, 1994]
Problem (Symmetry of a doubly-indexed
sequence) [Math. Mag., Apr. 1997]
Solution, Problem #10440 [Amer.
Math. Monthly, Apr. 1999]
Cellular Automata and Applications
(w/ M. Daven, A. Kheyfits, and M. Zeleke) [Teaching
Module for DIMACS Reconnect-2000 Conference, 2000]
This page last modified on August
30, 2001. We welcome your comments, questions,
and suggestions about this site.