Elementary proof techniques for the maximum number of islands

DOI10.1016/J.EJC.2010.10.001zbMATH Open1227.05006arXiv0910.4647OpenAlexW1965042402MaRDI QIDQ616385FDOQ616385

Authors: János Barát, Péter Hajnal, Eszter K. Horváth 

Publication date: 7 January 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Islands are combinatorial objects that can be intuitively defined on a board consisting of a finite number of cells. Based on the neighbor relation of the cells, it is a fundamental property that two islands are either containing or disjoint. Recently, numerous extremal questions have been answered using different methods. We show elementary techniques unifying these approaches. Our building parts are based on rooted binary trees and discrete geometry. Among other things, we show the maximum cardinality of islands on a toroidal board and in a hypercube. We also strengthen a previous result by rarefying the neighborhood relation.

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

Recommendations

• A general framework for island systems
• Islands: from coding theory to enumerative combinatorics and to lattice theory -- overview and open problems
• The number of square islands on a rectangular sea
• The number of brick islands by means of distributive lattices
• The size of maximal systems of square islands

zbMATH Keywords

rectangular islandstriangular islands

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Graph theory
• The number of triangular islands on a triangular grid
• Weakly independent subsets in lattices
• The number of rectangular islands by means of distributive lattices
• The number of brick islands by means of distributive lattices
• The minimum cardinality of maximal systems of rectangular islands
• On instantaneous codes

Cited In (9)

• CD-independent subsets in meet-distributive lattices.
• Cut approach to islands in rectangular fuzzy relations
• The number of triangular islands on a triangular grid
• Counting Islands in Nurikabe
• The number of brick islands by means of distributive lattices
• The number of square islands on a rectangular sea
• Cardinality of height function's range in case of maximally many rectangular islands -- computed by cuts
• Systems of islands with continuous height functions
• A general framework for island systems

This page was built for publication: Elementary proof techniques for the maximum number of islands

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616385)