covering a square with unit squares - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T10:15:21Z http://mathoverflow.net/feeds/question/29528 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29528/covering-a-square-with-unit-squares covering a square with unit squares Martin Erickson 2010-06-25T16:37:32Z 2010-06-26T11:54:28Z <p>Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)</p> http://mathoverflow.net/questions/29528/covering-a-square-with-unit-squares/29530#29530 Answer by Ben Green for covering a square with unit squares Ben Green 2010-06-25T16:44:55Z 2010-06-25T16:51:25Z <p>This reference is certainly pertinent, being the second Google hit for "covering a square with squares" (after your question). Just reading it now...</p> <p><a href="http://www.uccs.edu/~faculty/asoifer/docs/untitled.pdf" rel="nofollow">http://www.uccs.edu/~faculty/asoifer/docs/untitled.pdf</a></p> <p>UPDATE: so far as I can tell from looking at this article, the author regards your question as an unsolved problem. There is a further article by him and Karabash, apparently in (his) journal Geombinatorics, vol. 18, which I cannot access online and which has not been reviewed on MathSciNet.</p> http://mathoverflow.net/questions/29528/covering-a-square-with-unit-squares/29531#29531 Answer by Joseph O'Rourke for covering a square with unit squares Joseph O'Rourke 2010-06-25T17:03:51Z 2010-06-25T19:12:46Z <p>To supplement Ben Green's key reference (to "Covering a square of side n + ε with unit squares") , there is some follow-on work: Karabash &amp; Soifer, "A sharp upper bound for cover-up squares," <em>Geombinatorics</em>, v16, 219-226, 2006; "Note on covering square with equal squares," <em>Geombinatorics</em>, v18, 13-17, 2008; Chung &amp; Graham, "<a href="http://portal.acm.org/citation.cfm?id=1540668.1541153" rel="nofollow">Note: Packing equal squares into a large square</a>," <em>Journal of Combinatorial Theory Series A</em>, Volume 116, Issue 6 (August 2009), 1167-1175. </p> <p><b>Addendum</b> in response to Ben Green's remark: I do have the 2008 <em>Geombinatorics</em> paper (but not the 2006 one). They define $\Pi(n)$ as the number of unit squares that can cover a square of side length $n+\epsilon$. It appears that the status as of this 2008 paper was that $\Pi(n)=n^2+O(n^{2/3})$ has been established, and they conjecture that $\Pi(n)=n^2+ \Omega(n^{1/2})$.</p>