PROJECT DESCRIPTIONS1. Random Walks on Fractals:One of the classical problems in statistical physics has been to consider a specificprobability model (trees, random walks, self-avoiding walks, etc) with certainquantities QNon some space and to prove, either rigorously or by simulation,power laws for the expectation of QN, i.e. < QN>∼ Ns. The parameter sdepends on the dimension of the space. For example, for random walks defined ona d-dimensional lattice, if QNis the distance traveled by the random walker afterN steps, then it is known that the root mean square displacement follows thepower law < Q2N>1/2∼√N in all dimensions. Several studies [1,2,3] extendedthis 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 definedon Z2is < Q2N>1/2∼ Ns, where s =ln2ln5. Because of the difference in values forthe parameter s, random walks on Zdand random walks on the Sierpinski gasketdefined on Z2are said to belong to different universal classes. In this regard, hereare two projects students can work on1.1. Critical Behavior of Long-Ranged Random Walks on Zd: Define aprobability distribution P (X = x) =cα|x|αwhere |x| is the Euclidean norm of x inZdand cαis a normalizing constant. Consider a “long range” random walk thatvisits sites according to the above probability distribution for the increment ofeach step. We will first determine the universal classes of such long range randomwalks. Then we will also consider the universality of the associated self-avoidingrandom 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 onthe Sierpinski Gasket: Define a probability distribution P (X = x) =cαeα(|x|−1)where |x| is the number of steps x from the origin and cαis a normalizingconstant. Note that if α = ∞ one gets the the widely studied nearest neighbor selfvoiding random walk on the Sierpinski gasket. Students will investigate if longrange self avoiding walks and the nearest neighbor self avoiding walk belong tothe same universal class. More precisely, using numerical methods, studentsinvestigate the existence and magnitude of a critical αcsuch that for α > αcthelong range self-avoiding walk has the same universality as the nearest-neighborself-avoiding walk, and for α < αcthe two processes belong to different universalclasses. It will also be interesting to formulate similar results for random walksdefined on other fractal structures (the two sided Sierpinski gasket, the Sierpinskicarpet, etc).12 PROJECT DESCRIPTIONSReferences(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 ofStatistical 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.htm2. Combinatorial Identities:The focus will be in formulating and proving combinatorial identities that arisefrom enumeration problems [3]. Students will conjecture and formulate formulasfor summation expressions and will get working experience in a variety of prooftechniques (algebraic methods, combinatorial (counting) methods andcomputerized proof techniques, such as Gosper’s and Zeilberger’s algorithms, andthe Wilf-Zeilberger Method). They will also learn how to apply various computersummation algorithms for discovering and proving combinatorial-identities. Thefollowing is a project for this group.2.1. Exploring Binomial Sums: Sums involving binomial sums arise frommany enumeration problems in combinatorics. In this regard consider the sumS(k, m, n ) =k−1Xi=0µk −1i¶µm − (k − 1)k − i¶nk−i−1, 1 ≤ k ≤ m.Using combinatorial arguments and computerized proof techniques one can showthat S(k, m, 1) =¡mk¢and S(k, m, 2) =k−1Xi=0µk − 1i¶µn − i)k¶. It will beinteresting to find similar results for n ≥ 3.References(1) W. Koepf, Hypergeometric Summation: An Algorithmic Approach toSummation 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, CambridgeUniversity Press, 1997.(4) K. Wegschaider, Computer Generated Proofs of Binomial Multi-SumIdentities, Diploma Thesis (1997), RISC, J. Kepler University, Linz.3. Mathematical Games:Students will study mathematical games on graphs. In particular, they willinvestigate the “Cops and Robbers” game. (This game will be immediatelyPROJECT DESCRIPTIONS 3familiar to those who have played the game Scotland Yard by RavensburgerGames.) Consider a connected simple graph G having n vertices. Suppose thereare k “cops” and one “robber”. At the beginning of the game, each cop is assignedto a vertex. After this choice is made, the robber is assigned to a vertex. The copsand robbers alternately take turns moving to an adjacent vertex. The game ends ifthe 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 allconnected simple graphs with n vertices. This is a quantity of obviousmathematical interest. Meyniel conjectures that c(n) is O(√n) [3]. Planar graphshave a copper number of less than four [1]. Recently, Bollobas, Kun, and Leaderhave shown that a sparse random graph on n vertices has a copper number whichis 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 novelresearch question. For instance, what is the copper number if the robber isallowed to “burn bridges”, meaning that an edge may be deleted once the robberhas 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 saythat 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