New results for the Mondrian art problem
MetadataShow full item record
The Mondrian problem consists of dissecting a square of side length n ∈ N into non-congruent rectangles with natural length sides such that the difference d(n) between the largest and the smallest areas of the rectangles partitioning the square is minimum. In this paper, we compute some bounds on d(n) in terms of the number of rectangles of the square partition. These bounds provide us optimal partitions for some values of n ∈ N. We provide a sequence of square partitions such that d(n)/n2 tends to zero for n large enough. For the case of 'perfect' partitions, that is, with d(n) = 0, we show that, for any fixed powers s1, . . . , sm, a square with side length n = p s1 1 · · · p smm , can have a perfect Mondrian partition only if p1 satisfies a given lower bound. Moreover, if n(x) is the number of side lengths x (with n ≤ x) of squares not having a perfect partition, we prove that its 'density' n(x) x is asymptotic to (log(log(x))2 2 log x , which improves previous results.
Is part ofDiscrete Applied Mathematics, 2021, vol. 293, p. 64-73
European research projects
The following license files are associated with this item:
Showing items related by title, author, creator and subject.
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Elsevier, 2017)A mixed graph can be seen as a type of digraph containing some edges (or two opposite arcs). Here we introduce the concept of sequence mixed graphs, which is a generalization of both sequence graphs and iterated line ...
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Wiley, 2018-04-04)Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this arti- cle, we consider the case where such graphs are bipartite. As main results, we show that in this ...
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Elsevier B.V., 2018)A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a ...