Maximal 2-dimensional binary words of bounded degree

2025/05/19 by Massé, Alexandre Blondin, Goupil, Alain, L'Heureux, Ralphael +1
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2505.13640

Abstract

Let d be an integer between 0 and 4, and W be a 2-dimensional word of dimensions h x w on the binary alphabet 0, 1, where h, w in Z > 0. Assume that each occurrence of the letter 1 in W is adjacent to at most d letters 1. We provide an exact formula for the maximum number of letters 1 that can occur in W for fixed (h, w). As a byproduct, we deduce an upper bound on the length of maximum snake polyominoes contained in a h x w rectangle.

Citations

• Nivat's conjecture holds for sums of two periodic configurations
• Nonexpansive Z² subdynamics and Nivat's conjecture

Related

• Words with Repeated Letters in a Grid
• Improved bounds on maximum sets of letters in sequences with forbidden alternations
• Palindromic Subsequences in Finite Words
• A proof that a word of length n has less than 1.5n distinct squares
• On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words