November 2012 - mathfun@mailman.xmission.com

[math-fun] Domino problem, sketch of solution(?) & history
by Warren Smith 30 Nov '12

30 Nov '12

>The following is Strogatz' presentation from Joy of x. I'm wondering if a 2D version of this has been solved. Imagine there's a very popular new movie showing at the local theater. It's a romantic comedy, and hundreds of couples (many more than the theater can accommodate) are lined up at the box office, desperate to get in. Once a lucky couple get their tickets, they scramble inside and choose two seats right next to each other. To keep things simple, let's suppose they choose these seats at random, wherever there's room. In other words, they don't care whether they sit close to the screen or far away, on the aisle or in the middle of a row. As long as they're together, side by side, they're happy. Also, let's assume no couple will ever slide over to make room for another. Once a couple sits down, that's it. No courtesy whatsoever. Knowing this, the box office stops selling tickets as soon as there are only single seats left. Otherwise brawls would ensue. At first, when the theater is pretty empty, there's no problem. Every couple can find two adjacent seats. But after a while, the only seats left are singles -- solitary, uninhabitable dead spaces that a couple can't use. In real life, people often create these buffers deliberately, either for their coats or to avoid sharing an armrest with a repulsive stranger. In this model, however, these dead spaces just happen by chance. The question is: When there's no room left for any more couples, what fraction of the theater's seats are unoccupied? -------------------------------------------------------------------------------------------------------- Well, this was kind of annoying because it took many posts for me even to figure out what the problem was. And even now, I'm rather revolted by the description. So anyhow, let me rephrase it again. First of all, all those romantic couples can go bleep themselves, they are much better viewed as "dominos." NON-REVOLTING 1-PARAGRAPH PROBLEM STATEMENT: Start with the d-dimensional grid graph (the integer lattice with nearest neighbors joined by edges -- an "edge" is a "pair of adjacent vertices" as usual in graph theory). Single edges of this graph are colored red, chosen uniformly at random from among edges neither of whose endpoints are yet colored. The process continues until it can no longer. At that point: what fraction of the vertices are colored? Ok? Now this problem is not new. It has arisen before in statistical physics under names such as the "dimer problem" and "monomer-dimer problem." My initial though was: I did not think it was correct to claim the problem is solved in one dimension and unsolved in two. I instead thought it was long ago (in the 1960s or earlier) solved in two dimensions. Indeed, the more general problem of finding the "partition function" was long ago solved in the plane. The essential trick is to realize that problems of counting such dimer configurations, aka "matchings" to non-physicists, is soluble in a PLANAR graph by use of "pfaffians," a special kind of determinant, to write an exact formula for the configuration-count. Indeed, you can even get a formula for the "weighted" config-count where each edge has a positive real pre-assigned weight, and weight of a matching is the product of the weights of its used-edges. The pfaffian in turn can be evaluated in the limit for large grid by noting eigenvectors of the matrix are fourier modes. In general nonplanar graphs, however, the counting problem requires "permanents" which are much nastier to deal with, cannot express in terms of eigenvalues, hence you cannot expect to go beyond 2 dimensions. Now the "partition function" involves a further parameter X -- we are not interested merely in counting matchings on the grid graph, we want to count matchings that involve X dominos, for each possible value of X. Then it will turn out that some particular X (as a fraction of the vertex count) maximizes this count, and that yields the solution to the problem posed. One can express things in terms of some other parameter ("temperature" where each domino has a fixed "energy" for existing) which is equivalent. Thus it is clear that finding the partition function is a far more general thing than the here-posed problem, which is a very special case of it. Thus if my vague recollection that this more general problem was long-ago solved, is correct, then game over. But... examining some of the literature below, it looks like (1) one can do higher dimensions than 2 in the sense that efficient+rigorous randomized permanent-approximation algorithms are available (2) I am not seeing a full closed form solution for the partition function even in 2D, in the papers I saw in this quick scan. If one could count incomplete (aka non-perfect) matchings, aka dimer partial-coverings, then one could count monomer-dimer solutions with arbitrary weights for the dimers, by some simple planarity-preserving graph-surgery. The stumbling block appears to be that the pfaffian techniques only (?) work for counting PERFECT, i.e. complete, matchings, i.e. full coverings with no monomers. If that limitation is correct then the problem does not have an easy solve using known pfaffian-based techniques as outlined above, but it nevertheless should have a solution using permanents and the approx-algorithms in (1), see Kenyon-Randall-Sinclair cite. [Here by "easy" I exaggerate. It actually is very beautiful and amazing, I'm just saying this ground has been explored before.] ---------------large set of references:------------------------- Robin Thomas: A survey of pfaffian orientations of graphs, 2006 ICM lecture http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_47.pdf FY Wu: Pfaffian solution of a dimer-monomer problem: Single monomer on the boundary Phys. Rev. E 74,2 (2006) 020104(R) [4 pages] Kenyon, Claire; Randall, Dana; Sinclair, Alistair: Approximating the number of monomer-dimer coverings of a lattice, Journal of Statistical Physics 83, 3-4 (1996) 637-659 Dana Randall: PhD Thesis, Berkeley 1994. Claude Berge: graphs & Hypergraphs, book, discusses this problem. Cohn H., Kenyon R., Propp J: A variational principle for domino tilings, J. Amer. Math. Soc., 14, 2 (2001) 297-346. P.Kasteleyn: Graph theory and crystal physics, Graph Theory and Theoretical Physics, pp. 43-110 Academic Press, London 1967. Kasteleyn, P. W. : The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice". Physica 27,12 (1961) 1209-1225. James Propp: Lambda-determinants and domino-tilings http://arxiv.org/pdf/math/0406301v1.pdf Richard Kenyon and Andrei Okounkov: What is... a dimer? http://www.ams.org/notices/200503/what-is.pdf Richard Kenyon: Dimer Problems, http://www.math.brown.edu/~rkenyon/papers/de2.pdf Henryk Minc: An asymptotic solution of the multidimensional dimer problem, Linear and Multilinear Algebra 8,3 (1980) 235-239 Elliott H Lieb: Solution of the Dimer Problem by the Transfer Matrix Method J. Math'l. Phys. 8,12 (1967) 2339-2341 Fa Wang and F. Y. Wu: Exact solution of close-packed dimers on the kagome lattice, Phys. Rev. E 75,4 (2007) 040105(R) [4 pages] J. Propp, A reciprocity theorem for domino tilings, The Electronic Journal of Combinatorics 8 (2001), R18. H.N.V. Temperley and M.E. Fisher, Dimer problem in statistical mechanics - An exact result, Philosophical Magazine 6 (1961) 1061-1063. O.J. Heilmann, E.H. Lieb: Theory of monomer-dimer systems, Commun. Math'l. Physics, 25 (1972) 190-232. P.W. Kasteleyn: The statistics of dimers on a lattice, Physica 27 (1961), 1209-1225. PW Kastelyn: Dimer statistics and phase transitions, J Mathl Phys 4 (1963) 287-293. --end.

2 1

[math-fun] checkerboard version of an e-related dating problem
by Gary Antonick 29 Nov '12

29 Nov '12

Cornell mathematician Steven Strogatz thinks this is an unsolved problem but am wondering if there's something being overlooked. Here's the basic -- and solved -- problem. There's a long line of people standing near each other. They're told to hold hands with someone - either the person to their right or to their left, if available, but not both. The ratio of the resulting singles to all the people in line approaches 1/e^2 as the line increases. Now the unsolved version: what if the people are instead in a grid and have up to four people to choose from (but can hold hands with at most 1)?

4 10

[math-fun] Algorithm for computing linear representation of a Coxeter group?
by Mike Stay 29 Nov '12

29 Nov '12

Given a presentation of a Coxeter group with n generators, what's the most straightforward algorithm for producing a set of n matrices that satisfy the same relations? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

5 7

[math-fun] No three in line
by Warren Smith 27 Nov '12

27 Nov '12

Given an NxN grid, your mission is to select the maximum number of gridpoints such that no three are collinear. Obviously, it is impossible to select more than 2N points, because then at least 3 would lie on a horizontal gridline. So if you can find 2N, your solution automatically is optimal. For each N=2,3,4,5,..., 46, solutions with 2N points have been found. ** ** and **. *.* .** and *.*. ..** **.. .*.* are sample solutions for N=2, 3 and 4 respectively. However, it is unknown whether a 2N-point solution exists with N=47. More importantly, what happens when N-->infinity? It is known that a solution on an NxN grid with at least (1.5-epsilon)*N points always exists where epsilon-->0 for N large. Can the lower-bound constant 1.5 be increased? Can the upper-bound constant 2 be decreased? Are there an infinite set of 2N-point solutions? Problem originally posed by Dudeney 1917.

1 0

[math-fun] Glider gun on a Penrose tiling
by Adam P. Goucher 27 Nov '12

27 Nov '12

A couple of people from Kyoto University have discovered a glider in a 3-state cellular automaton on a Penrose tiling together with a glider gun in a related automaton: http://cp4space.wordpress.com/2012/11/26/miscellany/ Sincerely, Adam P. Goucher

5 4

[math-fun] Cycloids and other "roulettes"
by Henry Baker 27 Nov '12

27 Nov '12

A cycloid is one example of a "roulette": one curve (circle) which rolls upon another (line). I came across a 99-page 1890 monogram "Notes on Roulettes and Glissettes" by W.H. Besant. math-fun doesn't allow attachments, so email me directly if you'd like a pdf.

1 0

[math-fun] Fifth cipher challenge
by Adam P. Goucher 27 Nov '12

27 Nov '12

Hello, mathematicians! The fifth cipher challenge has just been released, if you're interested: http://cp4space.wordpress.com/2012/11/27/cipher-5-99-problems-or-23 When deciphered, the text contains a password enabling one to visit a secret discussion board and introduce yourself. Sincerely, Adam P. Goucher

1 0

[math-fun] Inverse cycloid problem ?
by Henry Baker 26 Nov '12

26 Nov '12

A cycloid is produced by a point on a circle as the circle rotates without slipping on a surface. What if we turn the problem around ? What curves can be produced by another curve rotating without slipping on a surface ? E.g., a semicircle is produced by a line segment "rotating without slipping" on a surface.

3 2

Re: [math-fun] Inverse cycloid problem ?
by Henry Baker 26 Nov '12

26 Nov '12

The term I was seeking was a "roulette" curve. http://en.wikipedia.org/wiki/Roulette_%28curve%29 E.g., the focus of a rolling parabola is a catenary. But the main question is: what is the class of curves that can be roulettes on a horizontal line? I.e., What is the class {K | there exists a convex curve C s.t. C rolling (rouletting?) on a line generates K}. At 10:05 AM 11/26/2012, Fred lunnon wrote: >On 11/26/12, Henry Baker <hbaker1(a)pipeline.com> wrote: >> A cycloid is produced by a point on a circle as the circle rotates without >> slipping on a surface. > >I think this may have been intended to read something like: > >"A cycloid is the curve described by a point on a circle as the circle moves >rigidly in the plane, while maintaining contact with a fixed line >without slipping." > >> What if we turn the problem around ? >> >> What curves can be produced by another curve rotating without slipping on a >> surface ? >> >> E.g., a semicircle is produced by a line segment "rotating without slipping" >> on a surface. > >But I'm afraid I still can't decipher this description ... WFL

1 0

[math-fun] cycloidal clock, pendulum sci=fi, other nuttery
by Bill Gosper 26 Nov '12

26 Nov '12

Warren S> Somebody in England actually did build what he claimed was the world's most accurate pendulum clock, using pendulum swinging low-amplitude in vacuum, photosensor "escapement" with electromagnet kicker, old-invar rod. Whole thing built inside a special hut with heavy concrete foundation, and active temperature regulation using "box inside a box" 2-level temperature control. Pointless exercise, really, but he enjoyed it and offered evidence from comparison with atomic clocks he'd indeed achieved greater accuracy than any previous pendulum clock, and also he was able using it to detect the motion of the moon, which might make a good sci-fi story -- you know, the alien race trapped on planet shrouded in perpetual fog, nevertheless detects the existence of moon via pendulum clocks. [...] ------- Without an atomic clock monitoring the pendulum clock? At any rate, I visited a lab in the 1960s testing a gyro on a concrete/steel pillar extending down to bedrock. It clearly recorded the tides. --rwg

1 0