Sam Northshield's 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.
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.
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.
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.
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.
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 [American Mathematical Monthly, 109, Mar.
2002, pp. 246-257] Winner
of Lester R. Ford award, 2003
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.
Quasi-regular graphs, cogrowth, and amenability [in Dynamical Systems and Differential Equations (W. Feng et al., eds.), AIMS, 2003]
We extend Grigorchuk's cogrowth criterion for amenability of groups to the case of non-regular graphs for which a certain regularity condition is satisfied. The proof involves generalized Laplacians which are inverses of growth series and whose determinants are closely related to zeta functions on graphs.
Cogrowth of Arbitrary Graphs [in Geometry and Random Walks
(Vadim Kaimanovich, ed.) , de Gruyter, 2004]
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.
On integral Apollonian circle packings [J. Number Theory, 119 #2 (2006) 171-193]
The curvatures of four mutually tangent circles with disjoint interiors form what is called a Descartes quadruple. The four least curvatures in an Apollonian circle packing form what is called a root Descartes quadruple and, if the curvatures are relatively prime, we say that it is a primitive root quadruple. We prove a conjecture of Mallows by giving a closed formula for the number of primitive root quadruples with minimum curvature -n. An Apollonian circle packing is called strongly integral if every circle has curvature times center a Gaussian integer. The set of all such circle packings for which the curvature plus curvature times center is congruent to 1 modulo 2 is called the "standard super-gasket". Those centers in the unit square are in one-to-one correspondence with the primitive root quadruples and exhibit certain symmetries first conjectured by Mallows. We prove these symmetries; in particular, the centers are symmetric around y=x if n is odd, around x=1/2 if n is an odd multiple of 2, and around y=1/2 if n is a multiple of 4.
Not mixing is just as cool [Mathematics Magazine, 80 #4 (2007) pp. 294-298]
Newton's law of cooling, a staple of the Calculus curriculum, is an empirical law not meant for mathematical proof. However, we show it is mathematically equivalent to the intuitively appealing principle that the average temperature of two cooling objects is equal to the temperature of a single object with initial temperature the average of the other two.
Sums across Pascal's triangle modulo 2 [to appear, Proceedings of the Twelfth International Conference on Fibonacci Numbers and their Applications]
We consider sums of the binomial coefficients C(i+j,i) modulo 2 over lines ai+bj=n. Many interesting sequences (old and new) arise this way.
On two types of exotic addition [to appear, Aequationes Mathematicae]
We classify, under reasonable assumptions, all continuous functions f for which the 'secant method' [xf(y)-yf(x)]/[f(y)-f(x)] is associative. Further, we classify all differentiable functions for which the similar type of addition [xf(y)+yf(x)] is associative. We show several connections between the theories of differential equations, matrices, and functional equations.
On Stern’s Diatomic
Sequence 0,1,1,2,1,3,2,3,1,4,…[submitted]
We investigate several of the many interesting properties of the title sequence. In particular, we focus on the combinatorics of the sequence (e.g., what the numbers count), some parallels with the Fibonacci sequence, some connections with Minkowski’s question-mark function, and some geometric aspects.
A note on the
color-transitivity of graphs, [submitted]
A graph is ‘n-color transitive’ if it has a proper vertex n-coloring and once can change any such n-coloring to any other by a sequence of changes of colors of single vertices such that any coloring along the way is proper. We show that every 3-color transitive graph is 2-colorable but not every 4-color transitive graph is 3-colorable.
Integrating across
Pascal’s triangle
Sums across the rows of Pascal’s triangle yield powers of 2 while certain diagonal sums yield the Fibonacci numbers which are asymptotic to powers of the golden ratio. Sums across other diagonals yield quantities asymptotic to powers of c where c depends on the direction of the diagonals. We generalize this to the continuous case. Using the gamma function, we generalize the binomial coefficients to real variables and thus form a generalization of Pascal’s triangle. Integration of these generalized binomial coefficients over various families of lines and curves yield quantities asymptotic to powers of some c where c can be determined explicitly. Finally, we revisit the discrete case.
Other Items
Square Roots of 2x2 Matrices [a paper in eternal progress]
This paper is designed to pique the interest of undergraduate students who are familiar
with the concepts of linear algebra. We investigate five methods of computing
square roots of two-by-two matrices. Each method gives rise to
applications and examples. Topics touched upon include solutions to Abel's
functional equation, Fibonacci numbers, Mobius transformations, systems of
differential equations, Newton's method applied to matrices (including surprising
pictures and open questions), continued fraction representations of matrices, quadratic
number fields, and quadratic forms.
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 Jan. 17, 2008. We welcome your comments, questions, and
suggestions about this site.