0 0 11 views

**Unformatted text preview:**

PROJECT DESCRIPTIONS 1 Random Walks on Fractals One of the classical problems in statistical physics has been to consider a specific probability model trees random walks self avoiding walks etc with certain quantities QN on some space and to prove either rigorously or by simulation power laws for the expectation of QN i e QN N s The parameter s depends on the dimension of the space For example for random walks defined on a d dimensional lattice if QN is the distance traveled by the random walker after N steps then it is known that the root mean square displacement follows the power law Q2N 1 2 N in all dimensions Several studies 1 2 3 extended this approach to graphs such as fractals One such fractal is the Sierpinski gasket The root mean square distance for a random walk on the Sierpinski gasket defined on Z2 is Q2N 1 2 N s where s ln2 Because of the difference in values for ln5 the parameter s random walks on Zd and random walks on the Sierpinski gasket defined on Z2 are said to belong to different universal classes In this regard here are two projects students can work on 1 1 Critical Behavior of Long Ranged Random Walks on Zd Define a c probability distribution P X x x where x is the Euclidean norm of x in d Z and c is a normalizing constant Consider a long range random walk that visits sites according to the above probability distribution for the increment of each step We will first determine the universal classes of such long range random walks Then we will also consider the universality of the associated self avoiding random walks The universality should depend on the dimension d the parameter and the self avoiding or non self avoiding nature of the random walk 1 2 Critical Behavior of Long Ranged Self Avoiding Random Walks on c the Sierpinski Gasket Define a probability distribution P X x e x 1 where x is the number of steps x from the origin and c is a normalizing constant Note that if one gets the the widely studied nearest neighbor self voiding random walk on the Sierpinski gasket Students will investigate if long range self avoiding walks and the nearest neighbor self avoiding walk belong to the same universal class More precisely using numerical methods students investigate the existence and magnitude of a critical c such that for c the long range self avoiding walk has the same universality as the nearest neighbor self avoiding walk and for c the two processes belong to different universal classes It will also be interesting to formulate similar results for random walks defined on other fractal structures the two sided Sierpinski gasket the Sierpinski carpet etc 1 2 PROJECT DESCRIPTIONS References 1 H Isliker and Vlahos L Random Walk through Fractal Environments Physical Review E vol 67 Issue 2 2003 2 Rammal R Random Walk Statistics on Fractal Structures Journal of Statistical Physics Vol 36 Numbers 5 6 1984 3 The Power Law for a Random Walker on the Sierpinski Gasket 1989 Available at http polymer bu edu ogaf html chp82 htm 2 Combinatorial Identities The focus will be in formulating and proving combinatorial identities that arise from enumeration problems 3 Students will conjecture and formulate formulas for summation expressions and will get working experience in a variety of proof techniques algebraic methods combinatorial counting methods and computerized proof techniques such as Gosper s and Zeilberger s algorithms and the Wilf Zeilberger Method They will also learn how to apply various computer summation algorithms for discovering and proving combinatorial identities The following is a project for this group 2 1 Exploring Binomial Sums Sums involving binomial sums arise from many enumeration problems in combinatorics In this regard consider the sum k 1 X k 1 m k 1 S k m n nk i 1 1 k m i k i i 0 Using combinatorial arguments and computerized proof techniques one can show k 1 X k 1 n i m that S k m 1 k and S k m 2 It will be i k i 0 interesting to find similar results for n 3 References 1 W Koepf Hypergeometric Summation An Algorithmic Approach to Summation and Special Function Identities AMS 1998 2 M Petkovsek H S Wilf and D Zeilberger A B A K Peters Wellesley Massachusetts 1996 3 R P Stanley Enumerative Combinatorics Volume I Cambridge University Press 1997 4 K Wegschaider Computer Generated Proofs of Binomial Multi Sum Identities Diploma Thesis 1997 RISC J Kepler University Linz 3 Mathematical Games Students will study mathematical games on graphs In particular they will investigate the Cops and Robbers game This game will be immediately PROJECT DESCRIPTIONS 3 familiar to those who have played the game Scotland Yard by Ravensburger Games Consider a connected simple graph G having n vertices Suppose there are k cops and one robber At the beginning of the game each cop is assigned to a vertex After this choice is made the robber is assigned to a vertex The cops and robbers alternately take turns moving to an adjacent vertex The game ends if the cop captures the robber by virtue of being at the same vertex as the robber If there is a winning strategy with k cops then we say the copper number of G denoted c G is less than or equal to k We define c G to be the minimal such k Given a positive integer n let c n be the maximum value of c G among all connected simple graphs with n vertices This is a quantity of obvious mathematical interest Meyniel conjectures that c n is O n 3 Planar graphs have a copper number of less than four 1 Recently Bollobas Kun and Leader have shown that a sparse random graph on n vertices has a copper number which is bounded by a term on the order of n 5 O 1 2 The students will modify the statement of the problem and embark on a novel research question For instance what is the copper number if the robber is allowed to burn bridges meaning that an edge may be deleted once the robber has traversed an edge What is the effect on subdivision on copper number What is the copper number of the 1 skeleton of semi or quasi regular polytope If k cops move randomly and catch the robber with probability p can you say that implies that c G is greater than k References 1 Aigner and Fromme A Game of Cops and Robbers Discrete Appl Math 8 1984 1 12 2 Bollobas Kun and Leader Cops and Robbers in a Random Graph arXiv 0805 2709v1 math CO 18 May 2008 3 Maamoun and Meyniel On a Game of Policemen and Robber Discrete Appl Math 17 1987 307 309