Random maximal independent sets and the unfriendly theater seating arrangement problem (Q1044988)

A problem of randomly seating people in an rectangular theater consisting of \(m\times n\) seats such that each occupied seat has all 4 directly neighboring seats empty is treated. The interesting value is the expected number of occupied seats divided by seats present \((m.n)\). The special case \((m=1)\) was solved in the year 1962, the expected value is asympotically \((n\to\text{infinity})\) \(1/2- 1/(2e^2)\) (=roughly \(0.43\)). Two main results are shown, one is the solution of the special case \((m=2)\), where the expected value tends asympotically to \(1/2- 1/(4e)\) (=roughly \(0.41\)); the other is the existence of an asymptotic limit for \(m> 2\). The simulation results for \(m\) between 3 and 15 show that the limits are decreasing with \(n\) and for \(n=15\) a value of roughly 0.37 is reached -- this ``decreasing'' is stated as a conjecture, but not proven. The solution method for the case \(m=2\) consists of solving simultanous recursions and I assume this method is not suitable for larger values of \(m\)! Nevertheless further results in this problem area are expected in the near future.