Browsing Mathematics Faculty Work by Publication date
Now showing items 120 of 20

Geodesics and Bounded Harmonic Functions on Infinite GraphsIt is shown there 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 finitelyintersecting geodesic rays starting at each vertex. We then demonstrate the existence of nonconstant bounded harmonic functions on the graph.

Cogrowth of Regular GraphsLet G be a dregular 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 functionsLet G be a countable group and u 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 Gspaces contains a fixed point.

On the Commute Time of Random Walks on GraphsGiven a simple random walk on an undirected connected graph, the commute time of the vertices x and y is defined as C(x,y) = ExTy+EyTx. We give a new proof, based on the optional sampling theorem for martingales, of the formula C(x,y) = 1/(Π(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 Π(·). We use this formula for C(x,y) to show that the maximum commute time among all barbelltype graphs in N vertices is attained for the lollipop graph and its value is O[(4N3)/27]

On the spectrum and Martin boundary of homogeneous spacesGiven a conservative, spatially homogeneous Markov process X on an homogeneous spaces χ, we show that if the bottom of the spectrum of the generator of X is zero then the Martin boundary of contains a unique point fixed by the isometry group of χ.

On Iterates of Moebius transformations on fieldsLet 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 ≡ K ∪ {∞ } S so that every Moebius transformation with fixed point set S is of the form x plus" c for some c. This permits an easy proof 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 norm, then we give necessary and sufficient conditions for the iterates of a Moebius transformation m to converge (necessarily to one of its fixed points) in the norm 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.

A note on the Zeta Function of a GraphThe number of splanning 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 nonregular graphs.

Associativity of the Secant MethodIterating 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.

On integral Apollonian circle packingsThe curvatures of four mutually tangent circles with disjoint interior form what is called a Descartes quadruple. The four smallest curvatures of circles 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 center of the largest circle is in the unit square and for which curvature plus curvature times center is congruent to 1 modulo 2 is called the standard supergasket. These centers are in onetoone 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 coolNewton'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.

On two types of exotic additionWe classify, under reasonable assumptions, all differentiable functions f for which the 'secant method' [xf(y) yf(x)]/[f(y) f(x)] is continuous and associative. Further, we classify all differentiable functions for which the similar type of addition xf(y) + yf(x) is associative.

Sums across Pascal's triangle modulo 2We 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 Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,...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 questionmark function, and some geometric aspects.

Square Roots of 2x2 MatricesThis 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 twobytwo 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.

A short proof and generalization of Lagrange's theorem on continued fractionsWe present a short new proof that the continued fraction of a quadratic irrational eventually repeats. The proof easily generalizes; we construct a large class of functions which, when iterated, must eventually repeat when starting with a quadratic irrational.

Integrating across Pascal's triangleSums 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.

A Lyness equation for graphsThe Lyness equation, x(n+1)=(x(n)+k)/x(n1), can be though of as an equation defined on the 2regular tree T2: we can think of every vertex of T2 as a variable so that if x and z are the vertices adjacent to y, then x,y,z satisfy xz=y+k. This makes sense for any 2regular graph. We generalize this to 3regular graphs by considering xyz=w+k and xy+xz+yz=w+k where x,y,z are the three neighbors of w. In the special case where an auxiliary condition x+y+z=f(w) also hold, a solutions is determined by (any) two values and, in some cases, an invariant can be found.

A rootfinding algorithm for cubicsNewton's method applied to a quadratic polynomial converges rapidly to a root for almost all starting points and almost all coefficients. This can be understood in terms of an associative binary operation arising from 2 x 2 matrices. Here we develop an analogous theory based on 3 x 3 matrices which yields a twovariable generally convergent algorithm for cubics.

Complex Descartes Circle TheoremWe present a short proof of Descartes Circle Theorem on the curvaturecenters of four mutually tangent circles. Key to the proof is associating an octahedral configuration of spheres to four mutually tangent circles. We also prove an analogue for spheres.

A New Parameterization of Ford CirclesLester Ford introduced Ford Circles in 1938 in order to geometrically understand the approximation of an irrational number by rational numbers. We shall construct Ford circles by a recursive geometric procedure and by a (wellknown) parameterization by rational numbers. We introduce a new parameterization in terms of relatively prime integer solutions of (a + b + c)² = a² + b² + c².