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.