The size of maximal systems of brick islands

zbMATH Open1289.05002arXiv1010.4578MaRDI QIDQ5395558

Publication date: 17 February 2014

Abstract: For integers

m_{1}, . . ., m_{d} > 0

and a cuboid

M = [0, m_{1}] i m e s . . . i m e s [0, m_{d}] s u b s e t m a t h b b R^{d}

, a brick of

M

is a closed cuboid whose vertices have integer coordinates. A set

H

of bricks in

M

is a system of brick islands if for each pair of bricks in

H

one contains the other or they are disjoint. Such a system is maximal if it cannot be extended to a larger system of brick islands. Extending the work of Lengv'{a}rszky, we show that the minimum size of a maximal system of brick islands in

M

is

s u m_{i = 1}^{d} m_{i} - (d - 1)

. Also, in a cube

C = [0, m]^{d}

we define the corresponding notion of a system of cubic islands, and prove bounds on the sizes of maximal systems of cubic islands.

Full work available at URL: https://arxiv.org/abs/1010.4578

zbMATH Keywords

rectangular grid cubic grid brick islands

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal combinatorics (05D99)