کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654357 | 1632821 | 2009 | 4 صفحه PDF | دانلود رایگان |
For integers m>0,n>0m>0,n>0, and R={(x,y):0≤x≤m and 0≤y≤n}, a set HH of closed rectangles that are all subsets of RR and the vertices of which have integer coordinates is called a system of rectangular islands if for every pair of rectangles in HH one of them contains the other or they do not overlap at all. Let IRIR denote the ordered set of systems of rectangular islands on RR, and let max(IR)max(IR) denote the maximal elements of IRIR. For f(m,n)=max{|H|:H∈max(IR)}f(m,n)=max{|H|:H∈max(IR)}, G. Czédli [G. Czédli, The number of rectangular islands by means of distributive lattices, European Journal of Combinatorics, in press (doi:10.1016/j.ejc.2008.02.005)] proved f(m,n)=⌊(mn+m+n−1)/2⌋f(m,n)=⌊(mn+m+n−1)/2⌋. For g(m,n)=min{|H|:H∈max(IR)}g(m,n)=min{|H|:H∈max(IR)} in [Z. Lengvárszky, The minimum cardinality of maximal systems of rectangular islands, European Journal of Combinatorics 30 (1) 216–219], we proved g(m,n)=m+n−1g(m,n)=m+n−1. Systems of square islands are systems of rectangular islands with RR and all members of HH being squares. The functions f(n)f(n) and g(n)g(n) are defined analogously to f(m,n)f(m,n) and g(m,n)g(m,n), and we show f(n)≤n(n+2)/3f(n)≤n(n+2)/3 (best polynomial bound), and g(n)=ng(n)=n.
Journal: European Journal of Combinatorics - Volume 30, Issue 4, May 2009, Pages 889–892