Lipschitz functions, proper colorings and cutsets in high ...

Lipschitz functions, proper colorings and cutsets in high ...

Lipschitz functions, proper colorings and cutsets in high dimensions 2.6.2011 BIRS Ron Peled (Tel Aviv University) Portions joint with Ohad N. Feldheim (Tel Aviv University) Random surfaces d Surface:f : R or f : Z. a box in Z . Hamiltonian: H(f) V f(x) f(y) for a potential V : R R. x~y DGFF : V(x) x 2 . Hwith (f) Random surface: sampled probability e (density) proportional to with 0 parameter representing inverse

temperature. Boundary conditions: zero on boundary, zero at one point, sloped boundary conditions, etc. Properties of random surfaces Properties predicted to be universal. Independent of potential V under minor assumptions. When is a box of side length n, have: n fluctuations in 1 dimensions. log n fluctuations in 2 dimensions. Bounded fluctuations in 3 dimensions. When V is strictly convex, many universal properties established by a long list of authors. Some recent progress also for continuous, non-convex potentials (Adams, Biskup, Cotar, Deuschel, Koteck, Mller, Spohn). Integer-valued random surfaces f : Z, When the surface takes integer values a new transition is expected: a twodimensional roughening transition. Transition from previous logarithmic

fluctuations to bounded fluctuations as the temperature decreases. Established only in 2 models! The integer2 V(x) x valued DGFF: and the Solid-On-Solid model: V(x)x (Frhlich and Spencer 81) Random Lipschitz functions A random Lipschitz function is the case 0 1 x 1 V(x) otherwise The so-called hammock potential. Here, the parameter is irrelevant and the function is a just a uniformly sampled Lipschitz function on . Natural also from an analytic point of view. Analysis of this case is wide open for all d2! A uniform Lipschitz function in 2 and 3 dimensions

Integer-valued Lipschitz functions A random M-Lipschitz function is an potential f : Z sampled with the 0 M x M is an integer V(x) otherwise Almost no analysis available for these functions. A random (graph) homomorphism function is the case 0 x { 1, 1} V(x) otherwise Investigated on general graphs as a generalization of SRW. 2

In Z , it is the height function for the square ice model. Benjamini,Yadin, Yehudayoff 07:lower bound (logn)1/d on maximum. 0,1 d d On hypercube Galvin, Kahn 03-04: , takes 5 values with high probability as . A 2-dimensional homomorphism Level sets of 2D homomorphism Outermost 01 level sets of homomorphism functions Trivial level sets (having exactly 4 edges) not drawn 2 and 3-dimensional homomorphism functions Rigidity of 3-dimensional homomorphism function Equals 0 (Green in the picture) on nearly all of the even sub-lattice (when the boundary values are 0 on even boundary vertices). Obtain 2 values for 1-Lipschitz

functions (M=1 case). d Proper colorings of Z Z, duniformly sample a proper q-coloring of Given a box . Howdoes this coloring look? Does it have long-range order? Are there multiple Gibbs measures as ? Zd Predicted interplay between d and q as follows: No structure when q is large compared to d a unique Gibbs measure. Proven when q11d/3 (Vigoda 00). Rigidity when d is large compared to q most colorings use only about half of the colors on the even sub-lattice and about half of the colors on the odd sub-lattice. Little is proven about this regime. Proper q-colorings are the same as the anti-ferromagnetic qstate Potts model at zero temperature. Transition from above behavior to unique Gibbs measure as temperature increases. Homomorphisms 3-colorings

Normalized homomorphism height functions: f : Z d Z, f(u) - f(v) 1 for u ~ v and f(0) 0 are in bijection with proper 3-colorings taking the color zero at the origin. The bijection is given simply by f f mod 3. Works also for f : Z when is a box in Z d. Does not work when Zdn is a torus due to existence of non-trivial cycles (there exist 3colorings on Zdn which are not modulo 3 of homomorphisms). Main results (I) fluctuations d Theorem(P.): such that if d dand f is a 0 0 uniformly sampled homomorphism function on then P f(x) t exp( c d t d ) for all x, Z dn max x f(x) Cd log(n)1/d with high probability as n . The boundary values for the above theoremdare fixing f to be 0 on an arbitrary subset of Z. n

Matching lower bound on maximum follows from results of BYY in the case of a one-point boundary condition. The results extend to 1-Lipschitz functions via a bijection of Yadin. Main results (II) level sets A level set of f is a (minimal) set of edges separating the boundary set from a point and having 0s on one side and 1s on the other. d 0 d Main Theorem(P., d d 0 , x Z nP. & Feldheim): such d Zn that if and f is a uniformly P(level set of length L aroundfunction x) exp(-c sampled homomorphism ond L) then 0 1 0 -1 0 1 c d c/dlog 4 d. -1 0 1 0 1 0 We prove

0 1 2 1 2 1 1 2 3 2 1 0 0 1 2 1

0 -1 -1 0 1 0 1 0 Structure of homomorphism functions and proper 3-colorings It follows that if f is sampled with zeros on the even boundary of a large box, then it will be zero on nearly all even vertices inside the box, with the largest breakup of the pattern having logarithmic boundary length. By taking modulo 3, we obtain the same rigidity also for proper 3-colorings. This establishes for the first time the

existence of a phase transition in the 3-state anti-ferromagnetic Potts model. Roughening transition The results do not apply to the homomorphism model in 2 dimensions (the square ice model). However, they may be applied to tori with non-equal side lengths: n.1Need n 2 n d d is large and that the torus is nononly that d1 linear: 1 nd exp ni 3 d log (d ) i 1

Thus the model on the n x n x 2 x 2 x x 2 torus (with a fixed number of 2s) has bounded fluctuations. I.e., the roughening transition occurs when adding a critical number of such 2s! We prove the full roughening transition occurs between the model on an n x log(n) torus and the model on an n x log(n) x 2 x x 2 torus. Refutes a conjecture of Benjamini, Yadin, Yehudayoff and answers a question of Benjamini, Hggstrm and Mossel. Limits of homomorphism functions (joint with Feldheim) d Z Infinite volume limit: We prove that as with zero boundary conditions, the model converges to a limiting Gibbs measure gives a meaning to a uniformly sampled homomorphism or 1-Lipschitz d Z function on the whole . For 3-colorings prove existence of 6 different Gibbs measures (in each, one of the 3 colors is dominant on one of the two sub-lattices). d

0,1 Scaling limit: Embedding in and taking finer and finer mesh, we find that the scaling limit of the model is white noise. Integrals over disjoint regions converge to independent Gaussian limits. Proof ideas for level set theorem d Z Work on n . Place zeros on the even boundary and uniformly sample a homomorphism function. Fix a point x and consider outermost level set around x. Denote it by LS(f). We want to show thatP LS(f) L exp( c L). d 0 1

0 -1 0 1 -1 0 1 0 1 0 0 1 2 1 2 1 1

2 3 2 1 0 0 1 2 1 0 -1 -1 0 1 0 1

0 Shift transformation I 0 1 0 -1 0 1 -1 0 1 0 1 0 0 1 2

1 2 1 1 2 3 2 1 0 1 2 1 -1 0 1 0

0 1 0 -1 0 1 -1 0 -1 0 -1 0 0 1 0 1

0 -1 0 1 2 1 0 -1 0 0 -1 0 1 0 -1 0 -1

1 0 -1 0 -1 0 1 0 Shift Transformation The value at each vertex inside the level set is replaced by the value to its right minus 1. Remain with a homomorphism height function! Shift transformation II 0 1 0 -1

0 1 -1 0 1 0 1 0 0 1 2 1 2 1 1 2

3 2 1 0 1 2 1 -1 0 1 0 0 1 0 -1 0

1 -1 0 -1 0 -1 0 0 1 0 1 0 -1 0 1 2

1 0 -1 0 0 -1 0 1 0 -1 0 -1 1 0 -1 0 -1

0 1 0 Shift Transformation Vertices with level set on right are surrounded by zeros after the shift! Can change their values arbitrarily to 1. There are exactly |LS(f)|/2d such vertices. Transformation still invertible given the level set. Estimate for given contour Thus, given a contour, or cutset, , we ||/ 2 d 2 associate to each f with LS(f) = a set of other homomorphisms in an invertible ||/2d way. P LS(f) 2 . It follows that || / 2 d Can we conclude by2a union bound (Peierls || / 2 d ||/ 2 d 2

argument), by2enumerating all possible contours? ||/ 2 d The union bound fails!!! There 2 are too many LS(f)= possible contours. Coarse graining Instead of using a union bound, we use a coarse graining technique, grouping the cutsets into sets according to common features and bounding the probability of each set. We note that our cutsets have a distinguishing feature they are odd cutsets. Cutsets whose interior boundary is on the odd sub-lattice. Denote by OCut Lthe set of all odd cutsets with exactly L edges. L / 2d OCut 2 L

It turns out that while , there are much fewer global shapes for cutsets and most cutsets are minor perturbations of some shape. Interior approximation I Interior approximation I Interior approximation II d A Z Say that n is an interior approximation to OCut L if in exposed( ) A interior( ) where exposed() is the set of vertices (2d d adjacent to many edges of edges). Interior approximation III Theorem: For any L, there exists a set containing an OCut

interior approximation to every cutset in withL Clog 2 d exp L . 3/2 d Much smaller if d is large than . L/2d OCut L 2 Thus, to conclude the proof it is sufficient to give a good bound on the probability that LS(f) is any of the cutsets with a given interior approximation. This is what we end up doing, but our bound is sufficiently good only for cutsets having a certain regularity. That they do not have almost all their edges on exposed vertices. Counting irregular cutsets We conclude by proving that there are relatively few irregular cutsets. Fewer than exp(L/100d) of them inOCut L . Thus, we may separately apply a union bound using our previous estimate P LS(f) 2 ||/2d

to show that none of these cutsets occur as a level set of f. Open questions 1. 2. 3. 4. Analyze other Lipschitz function models. Is the behavior similar? As mentioned, analysis of the 1-Lipschitz model follows from our results by a bijection of Yadin. Analyze sloped boundary values. Analyze proper q-colorings for q>3. Show rigidity of a typical coloring when d is sufficiently high. There does not seem to be a similar connection to height functions any more. Analyze regular (non odd) cutsets and prove similar structure theorems. Can be useful in many models (Ising, percolation, colorings, etc.) as the cutsets form the phase boundary between two pure phases. Improve structure theorems for odd cutsets will reduce the minimal dimension for our theorems and will help in analyzing other models. With W. Samotij we use these theorems to improve the bounds on the phase transition point in the hard-core model.

Recently Viewed Presentations



    MEDI-CAL OVERVIEW (CONT.). Medi-Cal is California's Medicaid program. This is a public health insurance program which provides needed health care services for low-income individuals including families with children, seniors, persons with disabilities, foster care, pregnant women, and low income people...
  • ONR 6.2 Project Annual Review Presentation

    ONR 6.2 Project Annual Review Presentation

    Scoring: a team point awarded for every five seconds location remains controlled ... Each bot is assigned a single domination location that it attempts to capture and hold during the whole game. GreedyBot. Attempts to recapture any location that is...
  • "Fit for Duty"

    "Fit for Duty"

    "FIT for Duty" American Disabilities Act . Family Medical Leave . Workers Compensations. American Disability Act of 1990. If a driver and attendant has a mental and/or physical disability prior hiring and the district is fully aware of the disability...
  • Ethnic Differences in Educational Achievement

    Ethnic Differences in Educational Achievement

    "The ultra tough ghetto superstar, an image constantly reinforced through rap lyrics and MTV videos". (Arnot, 2004) Many black boys are therefore subject to powerful anti-school peer group pressure. This forms a strong barrier to educational achievement.
  • All about the SSRMC

    All about the SSRMC

    Work through "90-minute Stata" Moodle course and worksheets for FIAS. Take . Introduction to Stata. module. If you're entering at BQA, DMA or FTMA and have not used Stata: Foundations in Applied Statistics. Basic Quantitative Methods. Doing Multivariate Analysis. Further...
  • SharePoint 2010 & PowerShell: Tips, Tricks, and Random Goodness

    SharePoint 2010 & PowerShell: Tips, Tricks, and Random Goodness

    SharePoint 2010 & PowerShell:Tips, Tricks, and Random Goodness. Gary Lapointe. Director, Aptillon, Inc. SharePoint MVP
  • Attachment Issues: How the Developmental Process Is Affected ...

    Attachment Issues: How the Developmental Process Is Affected ...

    Early Attachment - what the infant brings Inborn social prediliction Innate releasers (Bowlby) Root/suck/cling/cry Visual regard + Physical dependency + Cute + own temperament Biologically predisposed for social vs nonsocial human voice empathic distress interactional synchrony Social Predisposition and Sensory...
  • interview Definition  a series of questions and answers

    interview Definition a series of questions and answers

    Synonyms - news, facts Antonyms - fairy tale drawing conclusions Definition - taking bits of information and coming up with something else Synonyms - figure out, reason Antonyms - guess problem and solution Definition - author describes a problem and...