You are here

enumeration of lattice paths and walks

Download pdf | Full Screen View

Date Issued:
2011
Summary:
A well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger, Mireille Bousquet-Mlou, Thomas Prellberg, Neal Madras, Gordon Slade, Agnes Dit- tel, E.J. Janse van Rensburg, Harry Kesten, Stuart G. Whittington, Lincoln Chayes, Iwan Jensen, Arthur T. Benjamin, and many others. More than three hundred papers and a few volumes of books were published in this area. A SAW is interesting for simulations because its properties cannot be calculated analytically. Calculating the number of self-avoiding walks is a common computational problem. A recently proposed model called prudent self-avoiding walks (PSAW) was first introduced to the mathematics community in an unpublished manuscript of Pra, who called them exterior walks. A prudent walk is a connected path on square lattice such that, at each step, the extension of that step along its current trajectory will never intersect any previously occupied vertex. A lattice path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. We will discuss some enumerative problems in self-avoiding walks, lattice paths and walks with several step vectors. Many open problems are posted.
Title: The enumeration of lattice paths and walks.
246 views
67 downloads
Name(s): Gao, Shanzhen.
Charles E. Schmidt College of Science
Department of Mathematical Sciences
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Date Issued: 2011
Publisher: Florida Atlantic University
Physical Form: electronic
Extent: vii, 101 p. : ill.
Language(s): English
Summary: A well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger, Mireille Bousquet-Mlou, Thomas Prellberg, Neal Madras, Gordon Slade, Agnes Dit- tel, E.J. Janse van Rensburg, Harry Kesten, Stuart G. Whittington, Lincoln Chayes, Iwan Jensen, Arthur T. Benjamin, and many others. More than three hundred papers and a few volumes of books were published in this area. A SAW is interesting for simulations because its properties cannot be calculated analytically. Calculating the number of self-avoiding walks is a common computational problem. A recently proposed model called prudent self-avoiding walks (PSAW) was first introduced to the mathematics community in an unpublished manuscript of Pra, who called them exterior walks. A prudent walk is a connected path on square lattice such that, at each step, the extension of that step along its current trajectory will never intersect any previously occupied vertex. A lattice path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. We will discuss some enumerative problems in self-avoiding walks, lattice paths and walks with several step vectors. Many open problems are posted.
Identifier: 751980598 (oclc), 3183129 (digitool), FADT3183129 (IID), fau:3709 (fedora)
Note(s): by Shanzhen Gao.
Thesis (Ph.D.)--Florida Atlantic University, 2011.
Includes bibliography.
Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.
Subject(s): Combinatorial analysis
Approximation theory
Mathematical statistics
Limit theorems (Probabilty theory)
Persistent Link to This Record: http://purl.flvc.org/FAU/3183129
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU