Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$15,000.00

Enumeration and classification of lattice paths models

EF 2010-11

Résumé
A self-avoiding walk is a path from one point to another which never intersects itself. It is generally modelled in a lattice, starting at the origin, with a finite number of discrete steps (the length). It is a very simple, and instructive model in physics; it is fundamental in polymer and percolation studies. However, despite its apparent simplicity, physicists and mathematicians alike have been unable to determine explicit enumerative formulae for the number of walks of a given length in a square lattice. Even explicit asymptotic formulae have been out of reach, despite rigourous approximations. We can, however, approach variant sub-problems. Lattice paths also figure prominently as models in queuing theory. For example, a walk restricted to the quarter plane with steps in the directions {W, S, NE} models the problem of processing a line-up using two servers. Many techniques for lattice path enumeration transcend the context. In particular, our primary tool is the generating function, a formal power series that keeps track of the enumerative data. It is closely related to the probability generating function which one uses to analyze the stationary distribution. Properties about these functions (like the kinds of equations they satisfy) reflects structure in the objects they model. We can now summarize major motivations for this project: 1. Development of tools and methods for exact lattice path enumeration; 2. Combinatorial characterization of generating function types; 3. Develop a dialogue connecting the physical and probabilistic applications and tools of lattice paths.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
312582-2010
Name nom
Mishna, Marni
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2010
Award amount
15000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
1
Application title
Enumeration and classification of lattice paths models
Keyword
NSERC
Application summary
A self-avoiding walk is a path from one point to another which never intersects itself. It is generally modelled in a lattice, starting at the origin, with a finite number of discrete steps (the length). It is a very simple, and instructive model in physics; it is fundamental in polymer and percolation studies. However, despite its apparent simplicity, physicists and mathematicians alike have been unable to determine explicit enumerative formulae for the number of walks of a given length in a square lattice. Even explicit asymptotic formulae have been out of reach, despite rigourous approximations. We can, however, approach variant sub-problems. Lattice paths also figure prominently as models in queuing theory. For example, a walk restricted to the quarter plane with steps in the directions {W, S, NE} models the problem of processing a line-up using two servers. Many techniques for lattice path enumeration transcend the context. In particular, our primary tool is the generating function, a formal power series that keeps track of the enumerative data. It is closely related to the probability generating function which one uses to analyze the stationary distribution. Properties about these functions (like the kinds of equations they satisfy) reflects structure in the objects they model. We can now summarize major motivations for this project: 1. Development of tools and methods for exact lattice path enumeration; 2. Combinatorial characterization of generating function types; 3. Develop a dialogue connecting the physical and probabilistic applications and tools of lattice paths.