Adrian Dumitrescu

T. Rado conjectured in 1928 that if F is a finite set of axis-parallel squares in the plane, then there exists an independent subset I of pairwise disjoint squares, such that I covers at least 1/4 of the area covered by F. This conjecture was disproved in 1973 by Ajtai. The construction we illustrate here (2008, by Bereg, Dumitrescu and Jiang) is a refinement of Ajtai's construction and yields the current record upper bound, 1/4 - 1/384. What you see is a composite tile made of larger squares of size10, smaller ones of sizes 1 and 2, and holes (the coloured parts). By replicating this composite tile one gets a plane tiling where every independent set covers a fraction of at most 1/4 - 1/384 of the total union area.